PRETTY GOOD PRIVACY (PGP)
Pretty Good Privacy (PGP, весьма хорошая секретность) - это свободно распространяемая программа безопасной электронной почты, разработанная Филипом Циммерманном (Philip Zimmermann) [1652]. Для шифрования данных она использует IDEA, для управления ключами и цифровой подписи - RSA (длина ключа до 2047 битов), а для однонаправленного хэширования - MD5.
Для получения случайных открытых ключей PGP использует вероятностную проверку чисел на простоту, используя для получения стартовых последовательностей интервалы между нажатиями пользователем клавиш на клавиатуре. PGP генерирует случайные ключи IDEA с помощью метода, в ANSI X9.17, Appendix C (см. раздел 8.1) [55], используя вместо DES в качестве симметричного алгоритма IDEA. PGP также шифрует закрытый ключ пользователя с помощью хэшированной парольной фразы, а не пароля непосредственно.
Сообщения, зашифрованные PGP, имеют несколько уровней безопасности. Единственная вещь, известная криптоаналитику о зашифрованном сообщении, - это получатель сообщения при условии, что криптоаналитику известен ID ключа получателя. Только расшифровав сообщение, получатель узнает, кем оно подписано, если оно подписано. Это резко отличается от сообщения PEM, в заголовке которого немало информации об отправителе, получателе и самом сообщении хранится в незашифрованном виде.
Стандарт генерации ключей X9.17
Стандарт ANSI X9.17 определяет способ Генерации ключей (см. Рис. -1) [55]. Он не создает легко запоминающиеся ключи, и больше подходит для генерации сеансовых ключей или псевдослучайных чисел в системе. Для генерации ключей используется криптографический алгоритм DES, но он может быть легко заменен любым другим алгоритмом.
Рис. -1. Генерация ключей ANSI X9.17
Пусть EK(X) - это X, зашифрованный DES ключом K, специальным ключом, предусмотренным для генерации секретных ключей. V0 - это секретная 64-битовая стартовая последовательность. T - это метка времени. Для генерации случайного ключа Ri вычислим:
Ri= EK(EK(Ti) Å Vi)
Для генерации Vi+1, вычислим:
Vi+1= EK(EK(Ti) Å Ri)
Для превращения Ri в ключ DES, просто удалите каждый восьмой бит. Если вам нужен 64-битовый ключ, используйте ключ без изменения. Если вам нужен 128-битовый ключ, создайте пару ключей и объедините их.
Описание IDEA
Схема IDEA представлена на Рис. 13-9. 64-битовый блок данных делится на четыре 16-битовых подблока: X1, X2, X3 и X4. Эти четыре подблока становятся входными данными для первого этапа алгоритма. Всего в алгоритме восемь этапов. На каждом этапе четыре подблока подвергаются операциям XOR, сложениям и умножениям друг с другом и с шестью 16-битовыми подключами. Между этапами обмениваются местами второй и третий подблоки. Наконец четыре подблока объединяются с четырьмя подключами в окончательном преобразовании. На каждом этапе события происходят в следующей последовательности:
(1) Перемножаются X1 и первый подключ.
(2) Складываются X2 и второй подключ.
(3) Складываются X3 и третий подключ.
(4) Перемножаются X4 и четвертый подключ.
(5) Выполняется XOR над результатами этапов (1) и (3).
(6) Выполняется XOR над результатами этапов (2) и (4).
(7) Перемножаются результаты этапа (5) и пятый подключ.
(8) Складываются результаты этапов (6) и (7).
(9) Перемножаются результаты этапа (8) и шестой подключ.
(10) Складываются результаты этапов (7) и (9).
(11) Выполняется XOR над результатами этапов (1) и (9).
(12) Выполняется XOR над результатами этапов (3) и (9).
(13) Выполняется XOR над результатами этапов (1) и (10).
(14) Выполняется XOR над результатами этапов (4) и (10).
Рис. 13-9. IDEA.
Выходом этапа являются четыре подблока - результаты действий (11), (12), (13) и (14). Поменяйте местами два внутренних подблока (но не в последнем этапе), и вы получите исходные данные для следующего этапа.
После восьмого этапа выполняется заключительное преобразование:
(1) Перемножаются Xl и первый подключ.
(2) Складываются X2 и второй подключ.
(3) Складываются X3 и третий подключ.
(4) Перемножаются X4 и четвертый подключ.
Наконец четыре подблока снова соединяются, образуя шифротекст.
Также несложно создавать подключи. Алгоритм использует 52 из них (шесть для каждого из восьми этапов и еще четыре для заключительного преобразования). Сначала 128-битовый ключ делится на восемь 16-битовых подключей. Это первые восемь подключей алгоритма (шесть для первого этапа и два - для второго). Затем ключ циклически сдвигается налево на 25 битов и снова делится на восемь подключей. Первые четыре используются на этапе 2, а оставшиеся четыре - на этапе 3. Ключ циклически сдвигается налево на 25 битов для получения следующих восьми подключей, и так до конца алгоритма.
Дешифрирование выполняется точно также за исключением того, что подключи инвертируются и слегка изменяются. Подключи при дешифрировании представляют собой обратные значения ключей шифрования по отношению к операциям либо сложения, либо умножения. (Для IDEA подблоки, состоящие из одних нулей, считаются равными 216 = -1 для умножения по модулю 216 + 1, следовательно, обратным значением 0 относительно умножения является 0.) Эти вычисления могут занять некоторое время, но их нужно выполнить один раз для каждого ключа дешифрирования. В Табл. 13-4 представлены подключи шифрования и соответствующие подключи дешифрирования.
Табл. 13-4.
Подключи шифрования и дешифрирования IDEA
| Этап | Подключи шифрования | Подключи дешифрирования | ||||||||||||||
| Z1(1) | Z2(1) | Z3(1) | Z4(1) | Z5(1) | Z6(1) | Z1(9)-1 | -Z2(9) | -Z3(9) | Z4(9)-1 | Z5(8) | Z6(8) | |||||
| Z1(2) | Z2(2) | Z3(2) | Z4(2) | Z5(2) | Z6(2) | Z1(8)-1 | -Z2(8) | -Z3(8) | Z4(8)-1 | Z5(7) | Z6(7) | |||||
| Z1(3) | Z2(3) | Z3(3) | Z4(3) | Z5(3) | Z6(3) | Z1(7)-1 | -Z2(7) | -Z3(7) | Z4(7)-1 | Z5(6) | Z6(6) | |||||
| Z1(4) | Z2(4) | Z3(4) | Z4(4) | Z5(4) | Z6(4) | Z1(6)-1 | -Z2(6) | -Z3(6) | Z4(6)-1 | Z5(5) | Z6(5) | |||||
| Z1(5) | Z2(5) | Z3(5) | Z4(5) | Z5(5) | Z6(5) | Z1(5)-1 | -Z2(5) | -Z3(5) | Z4(5)-1 | Z5(4) | Z6(4) | |||||
| Z1(6) | Z2(6) | Z3(6) | Z4(6) | Z5(6) | Z6(6) | Z1(4)-1 | -Z2(4) | -Z3(4) | Z4(4)-1 | Z5(3) | Z6(3) | |||||
| Z1(7) | Z2(7) | Z3(7) | Z4(7) | Z5(7) | Z6(7) | Z1(3)-1 | -Z2(3) | -Z3(3) | Z4(3)-1 | Z5(2) | Z6(2) | |||||
| Z1(8) | Z2(8) | Z3(8) | Z4(8) | Z5(8) | Z6(8) | Z1(2)-1 | -Z2(2) | -Z3(2) | Z4(2)-1 | Z5(1) | Z6(1) | |||||
| заключительное преобразование | Z1(9) | Z2(9) | Z3(9) | Z4(9) | Z1(1)-1 | -Z2(1) | -Z3(1) | Z4(1)-1 | ||||||||
Скорость IDEA
Современные программные реализации IDEA примерно в два раза быстрее, чем DES. На компьютере с i386/33 МГц IDEA шифрует данные со скоростью 880 Кбит/с, а на компьютере с i486/33 МГц - со скоростью 2400 Кбит/с. Вы могли подумать, что IDEA должен был быть побыстрее, но умножения - недешевое удовольствие. Умножение двух 32-битовых чисел на процессоре i486 занимает 40 тактов (10 на процессоре Pentium).
Реализация PES на базе СБИС шифрует данные со скоростью 55 Мбит/с при тактовой частоте 25 МГц [208,398]. Другая СБИС, разработанная ETH Zurich и состоящая из of 251000 транзисторов на кристалле площадью 107.8 мм2, шифрует данные с помощью алгоритма IDEA со скоростью 177 Мбит/с при тактовой частоте 25 МГц [926, 207, 397].
Криптоанализ IDEA
Длина ключа IDEA равна 128 битам - более чем в два раза длиннее ключа DES. При условии, что наиболее эффективным является вскрытие грубой силой, для вскрытия ключа потребуется 2128 (1038) шифрований. Создайте микросхему, которая может проверять миллиард ключей в секунду, объедините миллиард таких микросхем, и вам потребуется 1013 лет для решения проблемы - это больше, чем возраст вселенной. 1024 таких микросхем могут найти ключ за день, но во вселенной не найдется столько атомов кремния, чтобы построить такую машину. Наконец мы чего-то достигли, хотя в некоторых темных вопросах я лучше останусь сторонним наблюдателем.
Может быть вскрытие грубой силой - не лучший способ вскрытия IDEA. Алгоритм все еще слишком нов, чтобы можно было говорить о каких-то конкретных криптографических результатах. Разработчики сделали все возможное, чтобы сделать алгоритм устойчивым к дифференциальному криптоанализу. Они определили понятие марковского шифра и продемонстрировали, что устойчивость к дифференциальному криптоанализу может быть промоделирована и оценена количественно [931, 925]. (Для сравнения с алгоритмом IDEA, устойчивость которого к дифференциальному криптоанализу была усилена, и который показан на Рис. 13-9, на Рис. 13-10 приведен первоначальный алгоритм PES. Удивительно, как такие незначительные изменения могут привести к столь большим различиям.) В [925] Лай (Lai) утверждал (он привел подтверждение, но не доказательство), что IDEA устойчив к дифференциальному криптоанализ уже после 4 из 8 этапов. Согласно Бихаму, его попытка вскрыть IDEA с помощью криптоанализа со связанными ключами также не увенчалась успехом [160].
CAST
CAST был разработан в Канаде Карлайслом Адамсом (Carlisle Adams) и Стаффордом Таваресом (Stafford Tavares) [10, 7]. Они утверждают, что название обусловлено ходом разработки и должно напоминать о вероятностном характере процесса, а не об инициалах авторов. Описываемый алгоритм CAST использует 64-битовый блок и 64-битовый ключ.
CAST имеет знакомую структуру. Алгоритм использует шесть S-блоков с 8-битовым входом и 32-битовым выходом. Работа этих S-блоков сложна и зависит от реализации, подробности можно найти в литературе.
Для шифрования сначала блок открытого текста разбивается на левую и правую половины. Алгоритм состоит из 8 этапов. На каждом этапе правая половина объединяется с частью ключа с помощью функции f, а затем XOR результата и левой половины выполняется для получения новой правой половины. Первоначальная (до этапа) правая половина становится новой левой половиной. После 8 этапов (не переставьте левую и правую половины после восьмого этапа) две половины объединяются, образуя шифротекст. Функция f проста:
(1) Разбейте 32-битовый вход на четыре 8-битовых части: a, b, c, d.
(2) Разбейте 16-битовый подключ на две 8-битовых половины: e, f.
(3) Подайте a на вход S-блока 1, b - на вход S-блока 2, c - на вход S-блока 3, d - на вход S-блока 4, e - на вход S-блока 5 и f - на вход S-блока 6.
(4) Выполните XOR шести выходов S-блоков, получая 32-битовый результат.
Иначе, 32-битовый вход может быть объединен с помощью XOR с 32 битами ключа, разбит на четыре 8-битовых части, которые обрабатываются S-блоками и затем объединяются с помощью XOR [7]. Безопасность N этапов, организованных таким образом, по видимому, соответствует N + 2 этапам другого варианта.
16-битовые подключи этапов легко получаются из 64-битового ключа. Если k 1, k 2,... k 8 - это 8 байтов ключа, то на этапах алгоритма используются следующие подключи:
Этап 1: k 1, k 2
Этап 2: k 3, k 4
Этап 3: k 5, k 6
Этап 4: k 7, k 8
Этап 5: k 4, k 3
Этап 6: k 2, k 1
Этап 7: k 8, k 7
Этап 8: k 6, k 5
Сила этого алгоритма заключена в его S-блоках. У CAST нет фиксированных S-блоков, для каждого приложения они конструируются заново. Критерии проектирования описаны в [10], изогнутыми функциями являются столбцы S-блоков, обеспечивающие необходимые свойства S-блоков (см. раздел 14.10). Созданный для данной реализации CAST S‑блоков уже больше никогда не меняется. S-блоки зависят от реализации, а не от ключа.
В [10] было показано, что CAST устойчив к дифференциальному криптоанализу, а в [728] - что CAST устойчив и к линейному криптоанализу. Неизвестно иного, чем грубая сила, способа вскрыть CAST.
Northern Telecom использует CAST в своем пакете программ Entrust для компьютеров Macintosh, PC и рабочих станций UNIX. Выбранные ими S-блоки не опубликованы. Канадское правительство считает CAST новым стандартом шифрования. Патентная заявка на CAST находится в процессе рассмотрения.
Краткое введении в AES (Advanced Encryption Standard).
Является симметричным блочным алгоритмом шифрования. Оперирует блоком в 128 бит, ключом размера 128/192/256 бит.
Собрались с мыслями, переходим к определениям, которые нам нужны:
· State (форма)– матрица (двумерный массив) байтов, расположенных следующем образом:
· Round (раунд) – итерация цикла преобразования над State (формой). Количество итераций зависит от длины ключа, чем больше длина ключа, тем больше итераций.
· Round key (раундовый ключ) ― уникальный ключ, который применяется в каждом отдельном в раунде.
· S-Box (таблица подстановок) –таблица, которая задает отображение одного байта в другой (биективное отображение):
· Обратная таблица подстановок ― аналогично S-Box, задает обратное отображение:
Как происходит шифрование.
1. ExpandKey — Функция для вычисления всех раундовых ключей;
2. SubBytes — Функция для подстановки байтов, использующая таблицу подстановок;
3. ShiftRows — Функция, обеспечивающая циклический сдвиг в форме на различные величины;
4. MixColumns — Функция, которая смешивает данные внутри каждого столбца формы;
5. AddRoundKey — Сложение ключа раунда с формой.
В виде блок-схемы
Где Nr – количество раундов.