47587 (566458), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Таблица 10. Размер сдвига строк в операции ShiftRow

Lb	cLb,1	cLb,2	cLb,3
4	1	2	3
6	1	2	3
8	1	3	4

При обратном преобразовании позиция с номером j в строках i = 1,2,3 сдвигается на позицию с номером j + c_{Lb, i} mod L_b.

2.4 ПРЕОБРАЗОВАНИЕ MixColumn

После того как выполнена последняя построчная перестановка, на следующем шаге каждый столбец (b_i,j) блока текста, где i = 0,...,3, j = 0,...,L_b, представляется в виде полинома над полем F₂8 и умножается на фиксированный полином a (x) = а₃x³ + а₂x² + а₁x + a₀ с коэффициентами a₀ (x) =x, a₁ (x) = 1, a₂ (x) = 1, a₃ (x) = х + 1. Затем вычисляется остаток от деления полученного произведения на модуль М (х) = х⁴ + 1. Таким образом, каждый байт столбца взаимодействует со всеми остальными байтами столбца. При построковом преобразовании ShiftRow на каждом раунде байты взаимодействуют друг с другом в других комбинациях. То есть эти две операции дают сильное перемешивание.

Этот шаг можно свести к умножению на матрицу:

Умножение на '02' (соответственно на х) мы уже реализовали в виде функции xtime (см. таблицу 3). Умножение на '03' (соответственно на х + 1) тоже сделано по аналогии.

Для обращения преобразования MixColumn умножаем каждый столбец (b_i,j) блока текста на полином г (х) = r₃х³ + r₂х² + r₁х + r₀ с коэффициентами r₀ (х) =х³ + х² + х, r₁ (х) = х³ + 1, r₂ (х) = х³ + х² + 1, r₃ (х) = х³ + х + 1 и приводим результат по модулю М (х) = х⁴ + 1. Соответствующая матрица имеет вид:

2.5 СЛОЖЕНИЕ С КЛЮЧОМ РАУНДА

На последнем шаге цикла раундовый ключ складывается по модулю 2 с блоком текста:

2.6 ПОЛНАЯ ПРОЦЕДУРА ЗАШИФРОВАНИЯ БЛОКА

Зашифрование по алгоритму Rijndael реализуется в виде следующего псевдокода. Аргументы обрабатываются как указатели на поля байтов или четырехбайтовых слов. Интерпретация полей, переменных и функций дана в таблицах 11-13.

Таблица 11

Интерпретация переменных

Переменные	Интерпретация
Nk	Длина Lk секретного ключа пользователя в четырехбайтовых словах
Nb	Длина Lb блока в четырехбайтовых словах
Nr	Число раундов Lr в соответствии с таблицами выше

Таблица 12

Интерпретация полей

Переменные	Размер в байтах	Интерпретация
CipherKey	4*Nk	Секретный ключ пользователя
ExpandedKey	4*Nb* (Nr+1)	Поле четырехбайтовых слов под развертку ключа
Rcon	4*Nb* (Nr+1) /Nk	Поле четырехбайтовых слов под константы c (j) = (rc (j), 0, 0, 0)
State	4*Nb	Поле ввода открытого текста и вывода зашифрованного текста
RoundKey	4*Nb	Раундовый ключ, фрагмент ExpandedKey

Таблица 13

Интерпретация функций

Функция	Интерпретация
KeyExpansion	Генерация раундового ключа
RotByte	Сдвиг четырехбайтового слова влево на 1 байт: (abcd) (bcda)
ByteSub	Подстановка в S-блоке всех байтов поля
Round	Обычный раунд
FinalRound	Последний раунд без преобразования MixColumn
ShiftRow	Преобразование ShiftRow
MixColumn	Преобразование MixColumn
AddRoundKey	Сложение с ключом раунда

Генерация ключа при L_k < 8:

KeyExpansion (byte CipherKey, word ExpandedKey)

{

for (i = 0; i < Nk; i++)

ExpandedKey [i] = (CipherKey [4*i], CipherKey [4*i + 1], CipherKey [4*i + 2], CipherKey [4*i + 3]);

for (i = Nk; i

{

temp = ExpandedKey [i - 1] ; if (i% Nk == 0)

temp = ByteSub (RotByte (temp)) ^Rcon [i/Nk] ; ExpandedKeyp] = ExpandedKey [i - Nk] ^temp;

}

}

Генерация ключа при L_k = 8:

KeyExpansion (byte CipherKey, word ExpandedKey)

{

for (i = 0; i < Nk; i++)

ExpandedKey [i] = (CipherKey [4*i], CipherKey [4*i + 1], CipherKey [4*i + 2], CipherKey [4*i + 3]);

for (i = Nk; i < Nb * (Nr + 1); i++)

{

temp = ExpandedKey [i - 1] ; if (i% Nk == 0)

temp = ByteSub (RotByte (temp)) ^Rcon [i/Nk] ; else if (i% Nk == 4)

temp = ByteSub (temp); ExpandedKey [i] = ExpandedKey [i - Nk] ^temp;

}

}

Раундовые функции:

Round (word State, word RoundKey)

{

ByteSub (State);

ShiftRow (State); MixColumn (State); AddRoundKey (State, RoundKey)

FinalRound (word State, word RoundKey) {

ByteSub (State);

ShiftRow (State);

AddRoundKey (State, RoundKey)

}

Полная процедура зашифрования блока текста:

Rijndael (byte State, byte CipherKey)

{

KeyExpansion (CipherKey, ExpandedKey);

AddRoundKey (State, ExpandedKey);

for (i = 1; i < Nr; i++)

Round (State, ExpandedKey + Nb*i);

FinalRound (State, ExpandedKey + Nb*Nr);

}

Раундовый ключ можно заготовить и вне функции Rijndael, a вместо ключа пользователя CipherKey использовать развертку ключей ExpandedKey. Преимущества такого варианта очевидны, когда для зашифрования текста длиной более одного блока нужно несколько раз вызывать функцию Rijndael с одним и тем же ключом пользователя.

Rijndael (byte State, byte ExpandedKey)

{

AddRoundKey (State, ExpandedKey);

for (i = 1; i < Nr; i++) Round (State, ExpandedKey + Nb*i);

FinalRound (State, ExpandedKey + Nb*Nr);

}

Для 32-разрядных процессоров раундовое преобразование лучше вычислять заранее и хранить результаты в виде таблиц. Заменяя операции перестановки и умножения на матрицу обращением к таблице, мы значительно сокращаем время работы как при зашифровании, так и (как будет видно позже) при расшифровании. С помощью таблиц вида

каждая из которых содержит по 256 четырехбайтовых слов (здесь w = 0,...,255; S (w) - S-блок подстановки), преобразование блока j = 0,..., L_b - 1, можно быстро выполнить как

,

где (см. ShiftRow) и - j-й столбец раундового ключа.

На последнем раунде преобразование MixColumn не выполняется, поэтому результат получается как

Конечно, можно воспользоваться таблицей из 256 четырехбайтовых слов, тогда

где r (a,b,c,d) = (d,a,b, с) - циклический сдвиг вправо на один байт.д.ля приложений с ограниченной памятью этот вариант чрезвычайно удобен, немного увеличится лишь время вычислений, необходимое для выполнения трех сдвигов.

2.7 РАСШИФРОВАНИЕ

При расшифровании алгоритмом Rijndael процесс зашифрования выполняется в обратном порядке с обратными преобразованиями. Вот эти обратные функции:

InvFinalRound (word State, word RoundKey)

{

AddRoundKey (State, RoundKey);

InvShiftRow (State);

InvByteSub (State);

}

InvRound (word State, word RoundKey)

{

AddRoundKey (State, RoundKey);

InvMixColumn (State);

InvShiftRow (State);

InvByteSub (State);

}

Полная процедура расшифрования выглядит следующим образом:

InvRijndael (byte State, byte CipherKey)

{

KeyExpansion (CipherKey, ExpandedKey);

InvFinalRound (State, ExpandedKey + Nb*Nr);

for (i = Nr - 1; i > 0; i--)

InvRound (State, ExpandedKey + Nb*i);

AddRoundKey (State, ExpandedKey);

}

Алгебраическая структура алгоритма Rijndael позволяет упорядочить преобразования зашифрования так, что и для них можно будет использовать таблицы. Заметим, что подстановка S и преобразование ShiftRow коммутируют, поэтому внутри одного раунда их можно поменять местами. Благодаря свойству гомоморфизма линейных преобразований, операции InvMixColumn и сложение с раундовым ключом можно тоже поменять местами. В пределах одного раунда это выглядит так:

InvFinalRound (word State, word RoundKey)

{

AddRoundKey (State, RoundKey);

InvByteSub (State);

InvShiftRow (State);

}

InvRound (word State, word RoundKey)

{

InvMixColumn (State);

AddRoundKey (State, InvMixColumn (RoundKey));

InvByteSub (State);

InvShiftRow (State);

}

Если порядок функций не менять, то их можно переопределить:

AddRoundKey (State, RoundKey);

InvRound (word State, word RoundKey)

{

InvByteSub (State);

InvShiftRow (State);

InvMixColumn (State);

AddRoundKey (State, InvMixColumn (RoundKey));

}

InvFinalRound (word State, word RoundKey)

{

InvByteSub (State);

InvShiftRow (State);

AddRoundKey (State, RoundKey);

}

Отсюда получаем структуру, аналогичную зашифрованию. Из соображений эффективности в процедуре lnvRound () отложим применение функции InvMixColumn к раундовому ключу до вычисления развертки, в которой первый и последний раундовые ключи из InvMixColumn оставим без изменений. "Обратные" раундовые ключи генерируются процедурой

InvKeyExpansion (byte CipherKey, word InvEpandedKey)

{

KeyExpansion (CipherKey, InvExpandedKey);

for (i = 1; i < Nr; i++)

InvMixColumn (InvExpandedKey + Nb*i);

}

Теперь полная процедура расшифрования выглядит так:

InvRijndael (byte State, byte CipherKey)

{

InvKeyExpansion (CipherKey, InvExpandedKey);

AddRoundKey (State, InvExpandedKey + Nb*Nr);

for (i = Nr-1; i>0; i--)

InvRound (State, InvExpandedKey + Nb*i);

InvFinalRound (State, InvExpandedKey);

}

По аналогии с зашифрованием можно и для расшифрования составить таблицы предвычислений. С помощью следующих преобразований:

(где w = 0,...,255; S^-1 (w) - обратный S-блок подстановки) получаем результат обратного раундового преобразования блока j = 0,..., L_b - 1:

,

где и - j-й столбец "обратного" раундового ключа.

Здесь на последнем раунде тоже не выполняется преобразование MixColumn, и результатом последнего раунда будет

,

где j = 0,…,L_b -1.

Для экономии памяти для расшифрования также можно составить таблицу всего из 256 четырехбайтовых слов, в которой

,

где r (а,b,c,d) = (d,a,b, с) - циклический сдвиг вправо на один байт.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. М. Вельшенбах. Криптография на Си и С++ в действии. М.: ТРИУМФ, 2004.

2. М. Яхтсмен. Теория и практика информационной безопасности. Под редакцией Зегжды П.Д. 1996.

3. Методы и средства защиты компьютерной информации. Методические указания к лабораторным работам для студентов специальности 220100 - Вычислительные машины, комплексы, системы и сети и направления 552800 - Информатика и вычислительная техника Сост.С. С. Соколов.

4. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2005.33 с.

РАБОТА 4. КРИПТОСИСТЕМА PGP

Задание: провести шифрование и расшифрование текстов с помощью криптосистемы PGP.

1. ХАРАКТЕРИСТИКА PGP

PGP (Pretty Good Privacy) - это криптографическая (шифровальная) программа с высокой степенью надежности, которая позволяет пользователям обмениваться информацией в электронном виде в режиме полной конфиденциальности.

Главное преимущество этой программы состоит в том, что для обмена зашифрованными сообщениями пользователям нет необходимости передавать друг другу тайные ключи, т.к эта программа построена на новом принципе работы - публичной криптографии или обмене открытыми (публичными) ключами, где пользователи могут открыто посылать друг другу свои публичные ключи с помощью сети "Интернет" и при этом не беспокоиться о возможности несанкционированного доступа каких-либо третьих лиц к их конфиденциальным сообщениям.

В PGP применяется принцип использования двух взаимосвязанных ключей: открытого и закрытого. К закрытому ключу имеете доступ только вы, а свой открытый ключ вы распространяете среди своих корреспондентов.

Характеристики

Список файлов лабораторной работы