Однонаправленные хэш-функции

Глава 18

Однонаправленные хэш-функции

Однонаправленная функция ЩМ) применяется к сообщению произвольной длины М и возвращает значение фиксированной длины h. h = ЩМ), где h имеет длину т Многие функции позволяют вычислять значение фиксированной длины по входным данным произвольной длины, но у…

Длины однонаправленных хэш-функций

документа с одинаковыми хэш-значениями, для вскрытия методом дня рождения придется хэшировать 2м слу­чайных документов, что, впрочем, недостаточно,… Для удлинения хэн-значений, выдаваемых конкретной хэш-функцией, был предложен… (1) Для сообщения с помощью одной из упомянутых в этой книге однонаправленных хэш-функций генерир у-ется…

Обзор однонаправленных хэш-функций

hi =/(M„ Л.-.О Это хэш-значение вместе со следующим блоком сообщения становится следующим… M i J---------------------------------

Рис. 18-1. Однонаправленная функция

Хэшируемый вход должен каким-то способом содержать бинарное представление длины всего сообщения . Таким образом преодолевается потенциальная проблема, вызванная тем, что сообщения различной длины могут давать одно и то же хэш-значение [1069, 414]. Иногда такой метод называется MD-усилением[930].

Различные исследователи выдвигали предположения, что если функция сжатия безопасна, то этот метод х э-ширования исходных данных произвольной длины также безопасен - но ничего не было доказано [1138, 1070, 414].

На тему проектирования однонаправленных хэш-функций написано много. Более подробную математиче­скую информацию можно найти [1028, 793, 791, 1138, 1069, 414, 91, 858, 1264]. Возможно самым толковой интерпретацией однонаправленных хэш-функций являются тезисы Барта Пренела (Bart Preneel) [1262].

18.2 Snefru

Snefru - это однонаправленная хэш-функция, разработанная Ральфом Мерклом [1070]. (Snefru, также как Khufu и Khafre, был египетским фараоном.) Snefru хэширует сообщения произвольной длины, превращая их в 128-битовые 256-битовые значения.

Сначала собщение разбивается на кусочки длиной по 512-от. (Переменная т является длитной хэш-значения.) Если выход - это 128-битовое значение, то длина кусочков равна 384 битам, а если выход -128-битовое значение, то длина кусочков - 256 битов.

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

Функция Н основывается на Е, обратимой функции блочного шифрования, работающей с 512 битовыми

блоками. Н - это последние т битов выхода Е, объединенные посредством XOR с первыми т битами входа Е.

Безопасность Snefru опирается на функцию Е, которая рандомизирует данные за несколько проходов . Каж­дый проход состоит из 64 рандомизирующих этапов. В каждом этапе в качестве входа S-блока используется другой байт данных. Выходное слово подвергается операции XOR с двумя соседними словами сообщения. По­строение S-блоков аналогично построению S-блоков в Khafre (см. раздел 13.7). Кроме того, выполняется ряд циклических сдвигов. Оригинальный Snefru состоял из двух проходов.

Криптоанализ Snefru

Для 128-битового Snefru их вскрытия работают лучше, чем вскрытие грубой силой для четырех и менее пр о-ходов. Вскрытие Snefru методом дня рождения… Хотя Бихам и Шамир не анализировали 256-битовые хэш-значения, они провели… В настоящее время Меркл рекомендует использовать Snefru по крайней мере с восемью проходами [1073]. Однако с таким…

М-хэш

N-хэш - это алгоритм, придуманный в 1990 году исследователями Nippon Telephone and Telegraph, теми же людьми, которые изобрели FEAL [1105, 1106]. Л^-хэш использует 128-битовые блоки сообщения, сложную ран-домизирующую функцию, похожую на FEAL, и выдает 128-битовое хэш-значение.

Хэш-значение каждого 128-битового блока является функцией блока и хэш-значения предыдущего блока .

Я₀ = /, где / - случайное начальное значение

Hi = g(M„ Я,_ч) © Mi © Я,_ч

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

Функция g достаточно сложна. Схема алгоритма приведена на 16-й. Сначала переставляются левая и правая 64-битовые половины 128-битового хэш-значения предыдущего блока Я„_ь а затем выполняется XOR с повто­ряющимся шаблоном (128-битовым) и XOR с текущим блоком сообщения М„ Далее это значение каскадно пре­образуется в N (на рисунках N= 8) стадий обработки. Другим входом стадии обработки является предыдущее хэш-значение, подвергнутое XOR с одной из восьми двоичных констант.

PS

PS

EXG: перестановка левой и правой частей v. 1010 ... 1010 (двоичное, 128 битов) PS: стадия обработки (processing stage) Ц-=б||А_у1 6ЦД-2 б||Д₃ б||Д₄ ||: конкатенация б: 000 ... 0 (двоичное, 24 бит) д._Л=4*(/-1)+/с(/с=1,2,3,4, А]_к - 8 битов в длину) Hi = g(Mi, H_iи)® Mi® H_iи

Лм

128 битов

Mi 128 битов

i— Я

v

EXG

PS

Уг

PS

PS

4 4 4 4

Ve

Ф

-*• hi

128 битов

 

•0-

v₈

PS

PS

PS

Рис. 18-2. Схема iV-хэш.

Одна стадия обработки показана на 15-й. Блок сообщения разбивается на четыре 32-битовых значения . Пре­дыдущее хэш-значение также разбивается на четыре 32-битовых значения . Функция f представлена на 14th. Функции S₀ и Si те же самые, что и в FEAL.

S₀(a,b) = циклический сдвиг влево на два бита ((а + Ъ) mod 256)

S_x{a,b) = циклический сдвиг влево на два бита((а + Ъ + 1) mod 256)

32 бита

32 бита

X X₂

У Уг

Вход:Х=Х₁||Х₂||Хз||Х4 P= Р1ЦР2ЦР3ЦР4

Выход: У=У

У2||Уз||У4 y=PS(X,P) X3 X4 Уз У4 Рис. 18-3. Одна стадия обработки iV-хэш. Выход одной стадии обработки становится входом следующей стадии обработки . После последней стадии обработки выполняется XOR выхода с М, и Я„ь а затем к хэшированию готов следующий блок. X ,-, 32 бита ^ Р ----------- ►© 8 битов 8 битов 32 бита 8 битов 8 битов Ю О* St So So И St   ▼____ £ |32 бита f{x,P) y=So(X1,X2)=Rot2((X1+X2) mod 256) y=S1(X1,X2)=Rot2((X1+X2+1) mod 256) У: выходные 8 битов, ХЬХ2 (8 битов): входы Rot2(V): циклический сдвиг влево на 2 бита 8-битовых данных У Рис. 18-4. Функция/. Криптоанализ N-хэш Берт ден Боер (Bert den Boer) открыл способ создавать столкновения в функции этапа N-хэш [1262]. Бихам и Шамир применили дифференциальный криптоанализ для вскрытия 6-этапной N-хэш [169, 172]. Конкретное выполненное ими вскрытие (конечно же, могли быть и другие) работает для любого N, делящегося на 3, и эф­фективнее вскрытия методом дня рождения для любого N, меньшего 15. То же самое вскрытие может обнаруживать пары сообщений с одинаковым хэш-значением для 12-этапной N-хэш за 256 операций (для вскрытия грубой силой нужно 2м операций). Л^-хэш с 15 этапами безопасна по от­ношению к дифференциальному криптоанализу: для вскрытия потребуется 272 операций. Разработчики алгоритма рекомендуют использовать N-хэш не меньше, чем с 8 этапами [1106]. С учетом до­казанной небезопасности N-хэш и FEAL (и ее скорости при 8 этапах) я рекомендую полностью отказаться от этого алгоритма. 18.4 MD4 MD4 - это однонаправленная хэш-функция, изобретенная Роном Ривестом [1318, 1319, 1321]. MD обознача­ет Message Digest (краткое изложение сообщения), алгоритм для входного сообщения выдает 128-битовое хэш-значение, или краткое изложение сообщения. В [1319] Ривест описал цели, преследуемые им при разработке алгоритма : Безопасность. Вычислительно невозможно найти два сообщения с одинаковым хэш-значением . Вскрытие грубой силой является самым эффективным. Прямая безопасность. Безопасность MD4 не основывается на каких-либо допущениях, например, предпо­ложении о трудности разложения на множители. Скорость. MD4 подходит для высокоскоростных программных реализаций . Она основана на простом набо­ре битовых манипуляций с 32-битовыми операндами. Простота и компактность. MD4 проста, насколько это возможна, и не содержит больших структур данных или сложных программных модулей. Удачна архитектура. MD4 оптимизирована для микропроцессорной архитектуры (особенно для микропро­цессоров Intel), для более крупных и быстрых компьютеров можно выполнить любые необходимые изменения . После первого появления алгоритма Берт ден Боер и Антон Босселаерс (Antoon Bosselaers) достигли успеха при криптоанализе последних двух из трех этапов алгоритма [202]. Ральфу Мерклу совершенно независимо удалось вскрыть первые два этапа [202]. Эли Бихам рассмотрел использование дифференциального криптоан а-лиза против первых двух этапов MD4 [159]. Хотя все эти вскрытия не были распространены на полный алго­ритм, Ривест усилил свою разработку. В результате появилась MD5. 18.5 MD5 MD5 - это улучшенная версия MD4 [1386, 1322]. Хотя она сложнее MD4, их схемы похожи, и результатом MD5 также является 128-битовое хэш-значение.

Описание MD5

Во первых, сообщение дополняется так, чтобы его длина была на 64 бита короче числа, кратного 512. Этим дополнением является 1, за которой вплоть до… А = 0x01234567 В = 0x89abcdef

Безопасность MD5

1. Добавился четвертый этап. 2. Теперь в каждом действии используется уникальная прибавляемая константа… 3. Функция G на этапе 2 с ((XaY)v(XaZ)v(YaZ)) была изменена на (XaZ)v(Ya(­Z)), чтобы сделать G менее симметричной. …

Описание SHA

Инициализируются пять 32-битовых переменных (в MD5 используется четыре переменных, но рассматри­ваемый алгоритм должен выдавать 160-битовое… А = 0x67452301 В = 0xefcdab89

W-, Kt

Рис. 18-7. Одна операция SHA.

После всего этого а, Ь, с, d и е добавляются к А, В, С D и Е, соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение A, B, C DhE.

Безопасность SHA

1. "Добавился четвертый этап." В SHA тоже. Однако в SHA на четвертом этапе используется та же функция f, что и на втором этапе. 2. "Теперь в каждом действии используется уникальная прибавляемая… 3. "Функция G на этапе 2 с ((XaY)v(XaZ)v(YaZ)) была изменена на (XaZ)v(Ya(­Z)), чтобы сделать G менее…

Схемы, в которых длина хэш-значения равна длине блока

Н0 = 1„, , где 1„ - случайное начальное значение Щ = ЕА(В) © С где А, В и С могут быть либо М„ Я,.ь (М,- © Я,ч), либо константы (возможно равные 0). Я0 - это некоторое случайное…

Рис. 18-8. Обобщенная хэш-функция, у которой длина хэш-значения равна длине блока

Табл. 18-1. Безопасные хэш-функции, у которых

Длина хэш-значения равна длине блока

Hi=EHi(Mi)⊕Hi-l⊕Mi Hi=EHi(Mi⊕Hi-l)⊕Mi Д. =£м_ (#,.-,)⊕#,-,

Рис. 18-9. Четыре безопасных хэш-функции, у которых длина хэш-значения равна длине блока

Первая схема была описана в [1028]. Третья схема была описана в [1555, 1105, 1106] и предлагалась в каче­стве стандарта ISO [766]. Пятая схема была предложена Карлом Майером (Carl Meyer), но в литературе обычно называется Davies-Meyer [1606, 1607, 434, 1028]. Десятая схема была предложена в качестве режима хэш-функции для LOKI [273].

Скорость хэширования первой, второй, третьей, четвертой, пятой и одиннадцатой схем равна 1 - длина кл то­ча равна длине блока. Скорость хэширования других схем составляет kin, где к -длина ключа. Это означает, что если длина ключа короче длины блока, то блок сообщения должен быть по длине равен ключу . Не рекомендует­ся, чтобы блок сообщения был длиннее ключа, даже если длина ключа алгоритма шифрования больше, чем длина блока.

Если блочный алгоритм подобно DES обладает свойством комплиментарности и слабыми ключами, для всех 12 схем существует возможность дополнительного вскрытия. Оно не слишком опасно и в действительности не стоит об это м беспокоиться. Однако вы можете обезопасить себя от такого вскрытия, зафиксировав значение второго и третьего битов ключа, равное "01" или "10" [1081,1107]. Конечно же это уменьшит длину А: с 56 битов до 54 битов (для DES) и уменьшит скорость хэширования.

Было показано, что следующие схемы, описанные в литературе, небезопасны .

Эта схема [1282] была взломана в [369]:

Н,=Е_К(Н_-)

Дэвис (Davies) и Прайс (Price) предложили вариант, в котором все сообщение циклически обрабатывается алгоритмом дважды [432, 433]. Вскрытие Копперсмита взламывает такую схему даже при небольшой вычисл и-тельной мощности [369]. В [1606] была показана небезопасность еще одной схемы [432, 458]:

H i =E M,⊕tf,-₁№-l)

В [1028] была показана небезопасность следующей схемы (с - константа):

H_i=E_c(M_i⊕H_i-l)⊕M_i⊕H_i-l

Модификация схемы Davies-Meyer

Я0 = 1Н, , где 1„ - случайное начальное значение Д= E H,-uM,(H i-l) Эта функция хэширует сообщение 64-битовыми блоками и выдает 64-битовое значение (см. 8-й). Более простое вскрытие этой…

Mi

Hi_И

I Ключ! Шифрование

+ H_i

Рис. 18-10. Модификация схемы Davies-Meyer.

Preneel-Bosselaers-Govaerts-Vandewalle

При 64-битовом блочном алгоритме схема выдает два 64-битовых хэш-значения , G, и Я„ объединение кото­рых и дает 128-битовое хэш-значение. У… Go = IG, где IG - случайное начальное значение Н0 = /я, , где 1Н - другое случайное начальное значение

Quisquater-Girault

G0 = IG, где IG - случайное начальное значение Но = /я, , где /я - другое случайное начальное значение Hf=£A(G-⊕^)⊕^⊕ff-

Параллельная схема Davies-Meyer

Это еще одна попытка создать алгоритм со скоростью хэширования 1, который выдает хэш-значение, в два раза большее длины блока. [736].

Go = I_G, где I_G - случайное начальное значение

Н₀ = 1_Н, , где 1„ - другое случайное начальное значение

К сожалению эта схема тоже небезопасна [928, 861]. Оказывается, что хэш-функция удвоенной длины со скоростью хэширования, равной 1, не может быть безопаснее, чем Davies-Meyer [861].

Тандемная (Tandem) и одновременная (Abreast) схемы Davies-Meyer

НИ Шифрование Ключ

Рис. 18-11. Тандемная (Tandem) схема Davies-Meyer.

Впервой схеме две модифицированные функции Davies-Meyer работают тандемом, конвейерно (см. 7-й).

Go = I_G, где I_G - случайное начальное значение

Н₀ = /_я, , где /_я - другое случайное начальное значение

Щ = Е

(Д-i)

G,. = £,.-,©£„ Л£,.-,)

н = щ® я

В следующей схеме используются две модифицированные функции, работающие одновременно (см. 6-й).

Go = I_G, где I_G - случайное начальное значение

Я₀ = /_я, , где /_я - другое случайное начальное значение

Gi = Gi-_l®E„„(­Gi-_l)

Н=Н^Е^ЛН-)

Н_и ■

Шифрование

Ключ

-+©

H_i

M_i

G_M ■

I Ключ! Шифрование

-+Ф

G,

Рис. 18-12. Одновременная (Abreast) схема Davies-Meyer.

Вобеих схемах два 64-битовых значения, Gi и H_i„ объединяются, образуя единое 128-битовое хэш-значение .

Насколько известно, безопасность 128-битовой хэш-функции этих алгоритмов идеальна : для обнаружения сообщения с заданным хэш-значением требуется 2 ¹²⁸ попыток, а для нахождения двух случайных сообщений с одинаковым хэш-значением - 2^м попыток, при условии, что лучшим способом вскрытия является применение грубой силы.

MDC-2 u MDC-4

Скорость хэширования MDC-2 равна V2, длина хэш-значения этой функции в два раза больше размера блока.Ее схема показана на 5-й. MDC-4 также выдает…   Gh -------------- I     …        

Рис. 18-13. MDC-2.

G_M

I Ключ! Шифрование

I Ключ! Шифрование

Gi

Mi

* Н

Н_и

Шифрование I Ключ!

Рис. 18-14. MDC-4.

Эти схемы были проанализированы в [925, 1262]. Они безопасны с учетом сегодняшних возможностей вы­числительной техники, но их надежность не так велика, как хотелось разработчикам . Их устойчивость к диффе­ренциальному криптоанализу при DES в качестве блочного алгоритма была рассмотрена в [1262].

MDC-2 и MDC-4 запатентованы [223].

Хэш-функция AR

Hi = EgUMi © Я,ч © Я„2 © с) © Mi Функция выглядит привлекательной, но не является безопасной . После некоторой…

Хэш-функция ГОСТ

Функция сжатия, Я, = f(M„HlA) (оба операнда - 256-битовые величины) определяется следующим образом: (1) При помощи линейного смешивания М„ Я,ч и некоторых констант генерируется… (2) Каждый ключ используется для шифрования отличных 64 битов Я,ч в режиме ЕСВ. Полученные 256 би­тов сохраняются во…

СВС-МАС

Потенциальная проблема, связанная с безопасностью этого метода, состоит в том, что получатель должен знать ключ, и этот ключ позволяет ему…

Алгоритм проверки подлинности сообщения (Message Authenticator Algorithm, MAA)

v = v <« 1 e =v®w х = ((((е + у) mod 232) v А а С) * (х © М,)) mod 232-l

Двунаправленный MAC

Этот MAC выдает хэш-значение, которое в два раза длиннее блока алгоритма [978). Сначала для сообщения вычисляется СВС-МАС. Затем вычисляется СВС-МАС сообщения с обратным порядком блоков. Двунаправ­ленный MAC просто является объединением этих двух значений. К сожалению эта схема небезопасна [1097].

Методы Джунемана

Н0 = /я, , где 1Н - секретный ключ Я, = (#„! + М,)2 mod p, где/; - простое число, меньшее 2m-l, a + обозначает… Джунеман (Jueneman) предлагает п = 16 ир = 231-1. В [792] он также предлагает, чтобы Щ использовался в качестве…

RIPE-MAC

Алгоритм состоит из трех частей. Во первых, сообщение увеличивается так, чтобы его длина была кратна 64 битам. Затем, увеличенное сообщение…

IBC-хэш

hi = ((М, mod/0 + v) mod 2" Секретный ключ представляет собой пару р и v, где р - и-битовое простое число,…

Однонаправленная хэш-функция MAC

сделать. Со методами MD-усиления этот способ работает, но есть серьезные проблемы.… Безопасными кажутся следующие конструкции:

Рис. 18-15. MAC с использованием потокового шифра

Глава 19 Алгоритмы с открытыми ключами 19.1 Основы

Концепция криптографии с открытыми ключами была выдвинута Уитфилдом Диффи ( Whitfield Diffie) и Мартином Хеллманом (Martin Hellman), и независимо Ральфом Мерклом (Ralph Merkle). Их вкладом в крипто­графию было убеждение, что ключи можно использовать парами - ключ шифрования и ключ дешифрирования -и что может быть невозможно получить один ключ из другого (см. Раздел 2.5). Диффи и Хеллман впервые представили эту идею на Национальной компьютерной конференции (National Computer Conference) 1976 года [495], через несколько месяцев была опубликована их основополагающая работа "New Directions in Cryptogra­phy" ("Новые направления в криптографии") [496]. (Из-за бесстрастного процесса публикации первый вклад Меркла в эту область вышел появился только в 1978 году [1064].)

С 1976 года было предложено множество криптографических алгоритмов с открытыми ключами . Многие из них небезопасны. Из тех, которые являются безопасными, многие непригодны для практической реализации . Либо они используют слишком большой ключ, либо размер полученного шифротекста намного превышает ра з-мер открытого текста.

Немногие алгоритмы являются и безопасными, и практичными . Обычно эти алгоритмы основаны на одной из трудных проблем, рассмотренных в разделе 11.2. Некоторые из этих безопасных и практичных алгоритмов подходят только для распределения ключей. Другие подходят для шифрования (и для распределения ключей). Третьи полезны только для цифровых подписей. Только три алгоритма хорошо работают как при шифровании, так и для цифровой подписи: RSA, EIGamal и Rabin. Все эти алгоритмы медленны. Они шифруют и дешифри­руют данные намного медленнее, чем симметричные алгоритмы. Обычно их скорость недостаточна для шифр о-вания больших объемов данных.

Гибридные криптосистемы (см. раздел 2.5) позволяют ускорить события: для шифрования сообщения ис­пользуется симметричный алгоритм со случайным ключом, а алгоритм с открытым ключом применяется для шифрования случайного сеансового ключа.

Безопасность алгоритмов с открытыми ключами

Это особенно важно, если алгоритм с открытым ключом используется для шифрования сеансового ключа . Ева может создать базу данных всех возможных… Алгоритмы с открытыми ключами спроектированы так, чтобы противостоять… В системах, в которых операция, обратная шифрованию, используется для цифровой подписи, это вскрытие невозможно…

Открытый текст 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0

Рюкзак 1 5 611 14 20 1 5 611 14 20 1 5 611 14 20 1 5 611 14 20

Шифротекст1+5+6+20=32 5+11+14=30 0=0 5+6=11

Рис. 19-1. Шифрование с рюкзаками

Фокус в том, что на самом деле существуют две различные проблемы рюкзака , одна решается за линейное время, а другая, как считается, - нет. Легкую проблему можно превратить в трудную. Открытый ключ представ­ляет собой трудную проблему, которую легко использовать для шифрования, но невозможно для дешифриров а-ния сообщений. Закрытый ключ является легкой проблемой, давая простой способ дешифрировать сообщения . Тому, кто не знает закрытый ключ, придется попытаться решить трудную проблему рюкзака .

Сверхвозрастающие рюкзаки

Что такое легкая проблема рюкзака? Если перечень масс представляет собой сверхвозрастающую последо­вательность,то полученную проблему рюкзака легко решить. Сверхвозрастающая последовательность - это последовательность, в которой каждой член больше суммы всех предыдущих членов . Например, последова­тельность {1,3,6,13,27,52} является сверхвозрастающей, а {1,3,4,9, 15,25} -нет.

Решение сверхвозрастающего рюкзаканайти легко. Возьмите полный вес и сравните его с самым боль­шим числом последовательности. Если полный вес меньше, чем это число, то его не кладут в рюкзак . Если пол­ный вес больше или равен этому числу, то оно кладется в рюкзак . Уменьшим массу рюкзака на это значение и перейдем к следующему по величине числу последовательности . Будем повторять, пока процесс не закончится. Если полный вес уменьшится до нуля, то решение найдено. В противном случае , there isn't.

Например, пусть полный вес рюкзака - 70, а последовательность весов {2,3,6, 13,27,52}. Самый большой вес, 52, меньше 70, поэтому кладем 52 в рюкзак. Вычитая 52 из 70, получаем 18. Следующий вес, 27, больше 18, поэтому 27 в рюкзак не кладется. вес, 13,меныпе 18, поэтому кладем 13 в рюкзак. Вычитая 13 из 18, полу­чаем 5. Следующий вес, 6, больше 5, поэтому 6 не кладется в рюкзак. Продолжение этого процесса покажет, что и 2, и 3 кладутся в рюкзак, и полный вес уменьшается до 0, что сообщает о найденном решении. Если бы это был блок шифрования методом рюкзака Меркла-Хеллмана, открытый текст, полученный из значения шифро­текста 70, был бы равен 110101.

Не сверхвозрастающие, или нормальные, рюкзаки представляют собой трудную проблему - быстрого алг о-ритма для них не найдено. Единственным известным способом определить, какие предметы кладутся в рюкзак, является методическая проверка возможных решений, пока вы не наткнетесь на правильное . Самый быстрый алгоритм, принимая во внимание различную эвритсику, имеет экспоненциальную зависимость от числа воз­можных предметов. Добавьте к последовательности весов еще один член, и найти решение станет вдвое труднее. Это намного труднее сверхвозрастающего рюкзака, где, если вы добавите один предмет к последов а-тельности, поиск решения увеличится на одну операцию .

Алгоритм Меркла-Хеллмана основан на этом свойстве . Закрытый ключ является последовательностью весов проблемы сверхвозрастающего рюкзака. Открытый ключ - это последовательность весов проблемы нормально­го рюкзака с тем же решением. Меркл и Хеллман, используя модульную арифметику, разработали способ пр е-образования проблемы сверхвозрастающего рюкзака в проблему нормального рюкзака.

Создание открытого ключа из закрытого

2*31 mod 105 = 62 3*31 mod 105 = 93 6*31 mod 105 = 81

Шифрование

Например, если сообщение в бинарном виде выглядит как 011000110101101110, шифрование, использую­щее предыдущую последовательность рюкзака, будет… сообщение = 011000 110101 101110 011000 соответствует 93 + 81 = 174

Дешифрирование

В нашем примере сверхвозрастающая последовательность - {2,3,6,13,27,52), от равно 105, а и - 31. Шифро­текстом служит 174,280,333. В этом случае п1… 174*61 mod 105 = 9 = 3 + 6, что соответствует 011000 280*61 mod 105 = 70 = 2 + 3 + 13 + 52, что соответствует 110101

Практические реализации

Вскрывать подобные рюкзаки при помощи грубой силы бесполезно . Если компьютер может проверять мил­лион вариантов в секунду, проверка всех возможных… лион машин, работающих параллельно, не успеет решить эту задачу до превращения…

ДУ-

Безопасность метода рюкзака

Варианты рюкзака

После вскрытия оригинальной схемы Меркла-Хеллмана было предложено множество других систем на принципе рюкзака: несколько последовательных рюкзаков, рюкзаки Грэм-Шамира (Graham-Shamir), и другие. Все они были проанализированы и взломаны, как правило, с использованием одних и тех же криптографиче­ских методов, и их обломки были сметены со скоростного шоссе криптографии [260, 253, 269, 921, 15, 919, 920, 922, 366, 254, 263, 255]. Хороший обзор этих систем и их криптоанализ можно найти в [267, 479, 257, 268].

Были предложены и другие алгоритмы, использующие похожие идеи, но все они тоже были взломаны . Криптосистема Lu-Lee [990, 13] была взломана в [20, 614, 873], ее модификация [507] также оказалась небезо­пасной [1620]. Вскрытия криптосистемы Goodman-McAuley приведены в [646, 647, 267, 268]. Криптосистема Pieprzyk [1246] была взломана аналогичным образом. Криптосистема Niemi [1169], основанная на модульных рюкзаках, взломана в [345, 788]. Новый, многостадийный рюкзак [747] пока еще не был взломан, но я не опти­мистичен. Другим вариантом является [294].

Хотя вариант алгоритма рюкзака в настоящее время безопасен - алгоритм рюкзака Char-Rivest [356], не­смотря на "специализированное вскрытие" [743] - количество необходимых вычислений делает его намного менее полезным, чем другие рассмотренные здесь алгоритмы. Вариант, названный Powerline System (система электропитания) небезопасен [958]. Более того, учитывая легкость с которой пали все остальные варианты, д о-верять устоявшим пока вариантом, по видимому, неосторожно .

Патенты

Оригинальный алгоритм Меркла-Хеллмана запатентован в Соединенных Штатах [720] и в остальном мире (см. 18th). Public Key Partners (PKP) получила лицензию на патент вместе с другими патентами криптографии с открытыми ключами (см. раздел 25.5). Время действия патента США истечет 19 августа 1997 года.

Табл. 19-1. Иностранные патенты на алгоритм рюкзака Меркла-Хеллмана

 

Страна	Номер	Дата получения
Бельгия		5 апреля 1979 года
Нидерланды		10 апреля 1979 года
Великобритания		2 мая 1979 года
Германия		10 мая 1979 года
Швеция		14 мая 1979 года
Франция		8 июня 1979 года
Германия		3 января 1982 года
Германия		15 июля 1982 года
Канада		20 июля 1982 года
Великобритания	2.006580	18 августа 1982 года
Швейцария		14 января 1983 года
Италия		28 сентября 1985 года

19.3 RSA

Вскоре после алгоритма рюкзака Меркла появился первый полноценный алгоритм с открытым ключом , ко­торый можно использовать для шифрования и цифровых подписей : RSA [1328, 1329]. Из всех предложенных за эти годы алгоритмов с открытыми ключами RSA проще всего понять и реализовать. (Мартин Гарднер (Martin Gardner) опубликовал раннее описание алгоритма в своей колонке "Математические игры" в Scientific American [599].) Он также является самым популярным. Названный в честь трех изобретателей - Рона Ривеста (Ron Rivest), Ади Шамира (Adi Shamir) и Леонарда Эдлмана (Leonard Adleman) - этот алгоритм многие годы проти­востоит интенсивному криптоанализу. Хотя криптоанализ ни доказал, ни опроверг безопасность RSA, он, по сути, обосновывает уровень доверия к алгоритму.

Безопасность RSA основана на трудности разложения на множители больших чисел . Открытый и закрытый ключи являются функциями двух больших (100 - 200 разрядов или даже больше) простых чисел. Предполагает­ся, что восстановление открытого текста по шифротексту и открытому ключу эквивалентно разложению на множители двух больших чисел.

Для генерации двух ключей используются два больших случайных простых числа , р и q. Для максимальной безопасности выбирайте р и q равной длины. Рассчитывается произведение:

п —р q

Затем случайным образом выбирается ключ шифрования е, такой что е и (p-l)(q-l) являются взаимно про­стыми числами. Наконец расширенный алгоритм Эвклида используется для вычисления ключа дешифриров а-ния d, такого что

efi?=l(mod (p-l)for-l))

Другими словами

rf= e-¹ mod((p-l)(_?-l))

Заметим, что d и п также взаимно простые числа. Числа е и п - это открытый ключ, а число d - закрытый. Два простых числам и q больше не нужны. Они должны быть отброшены, но не должны быть раскрыты .

Для шифрования сообщения от оно сначала разбивается на цифровые блоки, меньшие п (для двоичных дан­ных выбирается самая большая степень числа 2, меньшая и). То есть, если/; и q - 100-разрядные простые числа, то п будет содержать около 200 разрядов, и каждый блок сообщения от, должен быть около 200 разрядов в длину. (Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями ел е-ва, чтобы гарантировать, что блоки всегда будут меньше п. Зашифрованное сообщение с будет состоять из бло­ков с, той же самой длины. Формула шифрования выглядит так

с, = от,^е mod n

Для расшифровки сообщения возьмите каждый зашифрованный блок с, и вычислите

от,■ = с? mod n

Так как

с? = (от,У = m?d = OT,^-1)^fe-1)+1 = от,от,*^№1) = от,*1 = от,; все (mod n)

формула восстанавливает сообщение. Это сведено в 17-й.

Табл. 19-2. Шифрование RSA

Открытый ключ:

п произведение двух простых чисел puq (puq должны храниться в секрете) е число, взаимно простое с (р-1)(д-1)

Закрытый ключ:

d e^lmo&{(p-){q-))

Шифрование:

c = m^e mod n

Дешифрирование:

m = c^dmod n

Точно также сообщение может быть зашифровано с помощью d, а зашифровано с помощью е, возможен любой выбор. Я уберегу вас от теории чисел, доказывающей, почему этот алгоритм работает. В большинстве

книг по криптографии этот вопрос подробно рассмотрен .

Короткий пример возможно поможет пояснить работу алгоритма . Если/; = 47 и q = 71, то

и = pq = 3337

Ключ е не должен иметь общих множителей

(р-1)(д-1)= 46*70 =3220

Выберем (случайно) еравным 79. В этом случае rf = 79"¹ mod 3220 = 1019

При вычислении этого числа использован расширенный алгоритм Эвклида (см. раздел 11.3). Опубликуем е и п, сохранив в секрете d. Отбросим/; и q. Для шифрования сообщения

т= 6882326879666683

сначала разделим его на маленькие блоки. Для нашего случая подойдут трехбуквенные блоки. Сообщение разбивается на шесть блоков от,:

От! = 688

от₂ = 232

от₃ = 687

от₄ = 966

от₅ = 668

от₆ = 003

Первый блок шифруется как 688⁷⁹ mod 3337 = 1570 = с,

Выполняя те же операции для последующих блоков, создает шифротекст сообщения :

с = 1570 2756 2091 2276 2423 158

Для дешифрирование нужно выполнить такое же возведение в степень, используя ключ дешифрирования 1019:

1570¹⁰¹⁹ mod 3337 = 688 = от:

Аналогично восстанавливается оставшаяся часть сообщения .

Аппаратные реализации RSA

Существует много публикаций, затрагивающих тему аппаратных реализаций RSA [1314, 1474, 1456, 1316, 1485, 874, 1222, 87, 1410, 1409, 1343, 998, 367, 1429, 523, 772]. Хорошими обзорными статьями служат [258, 872]. Шифрование RSA выполняется многими микросхемами [1310, 252, 1101, 1317, 874, 69, 737, 594, 1275, 1563, 509, 1223]. Частичный список доступных в настоящее время микросхем RSA, взятый из [150, 258], приве­ден в 16th. He все из них доступны в свободной продаже.

Табл. 19-3. Существующие микросхемы RSA

 

Компания	Тактовая частота	Скорость	Тактовые циклы	Технология	Битов на	Количество
		передачи в Бодах	для шифрования		микросхему	транзисторов
		на 512 бит	512 бит
Alpha Techn.	25 МГц	13К	0.98 М	2 микрона
AT&T	15 МГц	19К	0.4 М	1.5 микрона
British Telecom	10 МГц	5.IK	1 М	2.5 микрона		-------------
Business Sim. Ltd.	5 МГц	3.8К	0.67 М	Вентильная матрица		-------------
CalmosSyst-Inc.	20 МГц	2.8К	0.36 М	2 микрона
CNET	25 МГц	5.3К	2.3 М	1 микрон
Cryptech	14 МГц	17К	0.4 М	Вентильная матрица
Cylink	30 МГц	6.8К	1.2 М	1.5 микрона
GEC Marconi	25 МГц	10.2К	0.67 М	1.4 микрона
Pijnenburg	25 МГц	50К	0.256 М	1 микрон
Sandia	8 МГц	ЮК	0.4 М	2 микрона
Siemens	5 МГц	8.5К	0.03 М	1 микрон

Скорость RSA

ют 1024-битовое шифрование RSA. В настоящее время разрабатываются микросхемы, которые, используя 512-битовый модуль, приблизятся к рубежу 1 Мбит/с.… Программно DES примерно в 100 раз быстрее RSA. Эти числа могут незначительно… Табл. 19-4. Скорости RSA для различных длин модулей при 8-битовом от­крытом ключе (на SPARC II)

Вскрытие с выбранным шифротекстом против RSA

Сценарий 1: Еве, подслушавшей линии связи Алисы, удалось перехватить сообщение с, шифрованное с по­мощью RSA открытым ключом Алисы. Ева хочет… Для раскрытия от она сначала выбирает первое случайное число г, меньшее я. Она… х = re mod я

Вскрытие общего модуля RSA

что если одно и то же сообщение когда-нибудь шифровалось разными показателями степени (с одним и тем же модулем), и эти два показателя - взаимно… Пусть т - открытый текст сообщения. Два ключа шифрования - ег и е2. Общий… Cj = m"1 mod и

Вскрытие малого показателя шифрования RSA

Это также гарантирует, что т mod п Ф те. Так делается в большинстве практических реализаций RSA, на­пример, в РЕМ и PGP (см. разделы 24.10 и… Мораль: Дополняйте сообщения перед шифрованием случайными значениями,…

Вскрытие малого показателя дешифрирования RSA

Другим вскрытием, предложенным Майкл Винер (Michael Wiener), раскрывает d, где d не превышает чет­верти размера п, а е меньше п [1596]. При случайном выборе е и d это встречается редко, и никогда не произой­дет, если значение е мало.

Мораль: Выбирайте большое значение d.

Полученные уроки

— Знание одной пары показателей шифрования/дешифрирования для данного модуля позволяет взломщику разложить модуль на множители. — Знание одной пары показателей шифрования/дешифрирования для данного модуля… — В протоколах сетей связи, применяющих RSA, не должен использоваться общий модуль. (Это является быть очевидным…

Вскрытие шифрования и подписи с использованием RSA

Алиса хочет послать сообщение Бобу. Сначала она шифрует его открытым ключом Боба, а затем подписы­вает своим закрытым ключом. Ее зашифрованное и… те" то&пвУА то&пА Вот как Боб может доказать, что Алиса послала ему т', а не т. Так как Бобу известно разложение на множи­тели ид (это…

Стандарты

Патенты

19.4 Pohlig-Hellman Схема шифрования Pohlig-Hellman [1253] похожа на RSA. Это не симметричный… C = Pe mod«

Патенты

19.5 Rabin Безопасность схемы Рабина (Rabin) [1283, 1601] опирается на сложность поиска… Сначала выбираются два простых числа р и q, конгруэнтных 3 mod 4. Эти простые числа являются закры­тым ключом, а их…

Табл. 19-5. Подписи EIGamal

Открытый ключ:

р простое число (может быть общим для группы пользователей)

g <p (может быть общим для группы пользователей)

у =g^x mod p

Закрытый ключ:
х <р

Подпись:
к выбирается случайным образом, взаимно простое с р-1

а (подпись) =/ mod/;

Ъ (подпись), такое что М= (ха + kb) mod (p - 1)

Проверка: Подпись считается правильной, если у^аа^ъ mod/; = g^M mod p

Например, выберем/; = 11 и g = 2, а закрытый ключ х = 8. Вычислим

у = g^x mod/; = 2⁸ mod 11 = 3

Открытым ключом являются j = 3, g = 2H/>=ll. Чтобы подписать М = 5, сначала выберем случайное число к=9. Убеждаемся, что gcd(9, 10)= 1. Вычисляем

a = /mod/; = 2⁹ modll= 6

и с помощью расширенного алгоритма Эвклида находим Ъ:

М= (xa + kb) mod (р - 1)

5 = (8*6 + 9*ft) modl0

Решение: Ъ = 3, а подпись представляет собой пару: а = 6 и й = 3.

Для проверки подписи убедимся, что

j/Vmod/^mod/;

3⁶6³ modll= 2⁵ modll

Вариант EIGamal, используемый для подписей, описан в [1377]. Томас Бет (Thomas Beth) изобрел вариант схемы EIGamal, подходящий для доказательства идентичности [146]. Существуют варианты для проверки под­линности пароля [312] и для обмена ключами [773]. И еще тысячи и тысячи других (см. раздел 20.4).

Шифрование EIGamal

a = gk mo&p b = укМ mod p Пара (а,Ь) является шифротекстом. Обратите внимание, что шифротекст в два раза длиннее открытого те к-ста. Для…

Табл. 19-6. Шифрование EIGamal

Открытый ключ:

р простое число (может быть общим для группы пользователей)

g <p (может быть общим для группы пользователей)

у =g^x mod p

Закрытый ключ:
х <р

Шифрование:
к выбирается случайным образом, взаимно простое с р-1

а (шифротекст) =g* mod/;

b (шифротекст^/M mod/;

Дешифрирование: М (открытый текст) = Ъ1с? mod/;

Скорость

Некоторые примеры скорости работы программных реализаций EIGamal приведены в 12-й [918].

Табл. 19-7.

Скорости EIGamal для различных длин модулей при 160-битовом пока­
зателе степени (на SPARC II)

512 битов 768 битов 1024 битов

Шифрование 0.33 с 0.80 с 1.09 с

Дешифрирование 0.24 с 0.58 с 0.77 с

Подпись 0.25 с 0.47 с 0.63 с

Проверка 1.37 с 5.12 с 9.30 с

Патенты

19.7 МсЕМесе В 1978 году Роберт МакЭлис (Robert McEliece) разработал криптосистему с… Пусть ddx,y) обозначает расстояние Хэмминга между хну. Числа п, ки t служат параметрами системы.

Другие алгоритмы, основанные на линейных кодах, исправляющих ошибки

Другой алгоритм, используемый для идентификации и цифровых подписей, основан на декодировании синдрома [1501], пояснения см. в [306]. Алгоритм [1621], использующий коды,… 19.8 Криптосистемы с эллиптическими кривыми

Глава 20

Алгоритмы цифровой подписи с открытым ключом

Алгоритм цифровой подписи (DIGITAL SIGNATURE ALGORITHM, DSA)

Предлагается Федеральный стандарт обработки информации (Federal Information Processing Standard, FIPS) для Стандарта цифровой подписи (Digital… В этом стандарте принимается схема подписи с открытым ключом, использующая… И:

Ускоряющие предварительные вычисления

В 18-й приведены примеры скорости работы программных реализаций DSA [918].

Табл. 20-2.

Скорость DSA для различных длин модулей с

Битовым показателем степени (на SPARC II)

Подпись 0.20 с 0.43 с 0.57 с Проверка 0.35 с 0.80 с 1.27 с Практические реализации DSA часто можно ускорить с помощью предварительных вычислений. Обратите внимание, что значение…

Табл. 20-3. Сравнение времени вычислений RSA и DSA

 

	DSA	RSA	DSA с общими/;, д, g
Глобальные вычисления	Off-card (P)	N/A	Off-card (P)
Генерация ключа	14 с	Off-card (S)	4с
Предварительные вычисления	14 с	N/A	4с
Подпись	0.03 с	15 с	0.03 с
Проверка	16 с	1.5 с	Юс
	1-5 с off-card (P)	1-3 с off-card (P)

Вычисления вне карточки (off-card) выполнялись на персональном компьютере i80386/33 МГц. (Р) указыва­ет открытые параметры off-card, a (S) - на закрытые параметры off-card. В обоих алгоритмах используется 512-битовый модуль.

Генерация простых чисел DSA

В [1154] NIST рекомендовал конкретный метод генерации двух простых чисел ,р и д, где д является делите­лем р-1. Длина простого числа/; - между 512 и… (1) Выберем произвольную последовательность, по крайней мере, 160 битов и… (2) Вычислим U = SHA(S) © SHA((S + 1) mod 2g), где SHA описан в разделе 18.7.

Шифрование RSA с DSA

Шифрование RSA еще проще. Используя модуль п, сообщение т и открытый ключ е, вызовем

DSAsign(n,n,m,e,0,0,r,s)

Возвращенное значение г и есть шифротекст. Дешифрирование RSA является точно таким же. Если d - за­крытый ключ, то

DSAsign(n,n,m,d,0,0,r,s)

возвращает открытый текст как значение г.

Безопасность DSA

Что касается предполагаемой лазейки в DSS. Мы считаем, что термин "лазейка" вводит в заблуждение, так он предпол а-гает, что через лазейку… DSS не шифрует никаких данных. По сути вопросом является, не может ли кто-то… Более того, предположение о чувствительности к лазейке справедливо для любой системы проверки подлинности с от­крытыми…

Вскрытия к

Опасности общего модуля

Подсознательный канал в DSA Гус Симмонс (Gus Simmons) открыл в DSA подсознательный канал [1468, 1469] (см.… Патенты

Табл. 20-4.

Возможные перестановки», бис

(r'= r modq)

± r' ± s от

± r' m ± s 1

+ г' от + ms 1

± m r' ± r' s 1

± ms ± r' s 1

В 15th перечислены возможные варианты подписи и проверки, полученные только из первой строки воз­можных значений а, Ъ и с без учета эффектов ±.

Табл. 20-5.

Схемы цифровой подписи с использованием

Дискретных логарифмов

(1) r'k=s+mx mod q (2) r'k=m+sx mod q (3) sk= r'+mx mod q

ONG-SCHNORR-SHAMIR

h = -к'2 mod n = -(kAf mod n Открытым ключом служат h и и; а закрытым - к. Чтобы подписать сообщение М, сначала генерируется случайное число г, взаимно простое с п. Затем вычис­ляется:

ESIGN

ESICN -это схема цифровой подписи, разработанная NTT Japan [1205, 583]. Утверждалось, что она не менее безопасна, чем RSA или DSA, и намного быстрее при тех же размерах ключа и подписи. Закрытым ключом служит пара больших простых чисел ряд. Открытым ключом является п, для которого

п = p²*q

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

(1) Алиса выбирает случайное число х, меньшее pq.

(2) Алиса вычисляет:

w, наименьшее целое, которое больше или равно

(Щт) -х^к mod n)lpq

s = x + ((wlkx^k-¹ mod p) pq

(3) Алиса посылает s Бобу.

(4) Для проверки подписи Боб вычисляет s mod п. Кроме этого, он вычисляет а, наименьшее целое, которое больше или равно удвоенному числу битов п, деленному на 3. Если Щт) меньше или равна / mod n, и ес­ли / mod n меньше Щт)+2^а, то подпись считается правильной.

Выполнив ряд предварительных вычислений, этот алгоритм можно ускорить . Эти вычисления могут быть выполнены в произвольный момент времени и никак не связаны с подписываемым сообщением . Выбрав х, Алиса может разбить этап (2) на два подэтапа. Сначала.

(2а) Алиса вычисляет:

u = x^k mod n

v-l/ikx^mod p

(2b) Алиса вычисляет:

w= наименьшее целое, которое больше или равно

(Щт) - u)lpq

s = x + ((wv mod p) pq

Для обычно используемых размеров чисел предварительные вычисления ускоряют процесс подписи на п о-рядок. Почти вся трудная работа выполняется именно на стадии предварительных вычислений . Обсуждение действий модульной арифметики, выполняемых при ускорении ESIGN, можно найти в [1625, 1624]. Этот алго-

ритм можно расширить для работы с эллиптическими кривыми [1206].

Безопасность ESIGN

В настоящее время авторы рекомендуют использовать следующие значения к: 8, 16, 32, 64, 128, 256, 512 и 1024. Они также рекомендуют, чтобы р и q были…

Патенты

20.7 Клеточные автоматы Совершенно новая идея, изученная Папуа Гуамом (Papua Guam) [665], состоит в… 20.8 Другие алгоритмы с открытым ключом