Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
q = простое число - множитель p-1, длиной от 254 до 256 битов. a = любое число, меньшее p-1, для которого a q mod p = 1. x = число, меньшее q. y = a x mod p. Этот алгоритм также использует однонаправленную хэш-функцию : H(x). Стандарт определяет использова- ние хэш-функции ГОСТ Р 34.1 1-94 (см. раздел 18.1 1), основанной на симметричном алгоритме ГОСТ (см. раздел 14.1) [657]. Первые три параметра, p, q и a, открыты и могут использоваться совместно пользователями сети . Закрытым ключом служит x, а открытым - y. Чтобы подписать сообщение m (1) Алиса генерирует случайное число k, меньшее q (2) Алиса генерирует I = (a* mod p) mod q s = (ct + k(H(m))) mod q r = (a k mod p) mod q s = (xr + k(H(m))) mod q Если H(m) mod q =0, то значение хэш-функции устанавливается равным 1. Если r =0, то выберите другое значение k и начните снова. Подписью служат два числа: r mod 2 256 и s mod 2 256 , Алиса посылает их Бобу. (3) Боб проверяет подпись, вычисляя v = H(m) q-2 mod q z 1 = (sv) mod q z 2 = ((q-r)*v) mod q u = (( a y z z 1 2 * ) mod p) mod q Если u = r, то подпись правильна. Различие между этой схемой и DSA в том, что в DSA s = (k -1 (H(m) + xr)) mod q, что дает другое уравне- ние проверки. Любопытно, однако, что длина q равна 256 битам. Большинству западных криптографов кажется достаточным q примерно 160 битов длиной. Может быть это просто следствие русской привычки играть в сверхбезопасность. Стандарт используется с начала 1995 года и не закрыт грифом "Для служебного пользования", что бы это не значило. 20.4 Схемы цифровой подписи с использованием дискретных логарифмов Схемы подписи ElGamal, Schnorr (см. раздел 21.3) и DSA очень похожи. По сути, все они являются тремя примерами общей схемы цифровой подписи, использующей проблему дискретных логарифмов . Вместе с тыся- чами других схем подписей они являются частью одного и того же семейства [740, 741, 699, 1184]. Выберем p, большое простое число, и q, равное либо p-1, либо большому простому множителю p-1. Затем выберем g, число между 1 и p, для которого g q ? 1 (mod p). Все эти числа открыты, и могут быть совместно ис- пользованы группой пользователей. Закрытым ключом является x, меньшее q. Открытым ключом служит y =g x mod q. Чтобы подписать сообщение m, сначала выберем случайное значение k, меньшее q и взаимно простое с ним. Если q тоже простое число, то будет работать любое k, меньшее q. Сначала вычислим r = g k mod p Обобщенное уравнение подписи примет вид ak = b + cx mod q Коэффициенты a, b и c могут принимать различные значения. Каждая строка 16th предоставляет шесть воз- можностей. Проверяя подпись, получатель должен убедиться, что r a = g b y c mod p Это уравнение называется уравнением проверки. Табл. 20-4. Возможные перестановки a, b и c (r'= r mod q) ± r ± s m ± r m ± s 1 ± r m ± ms 1 ± m r ± r s 1 ± ms ± r s 1 В 15th перечислены возможные варианты подписи и проверки, полученные только из первой строки воз- можных значений a, b и c без учета эффектов ±. Табл. 20-5. Схемы цифровой подписи с использованием дискретных логарифмов Уравнение подписи Уравнение проверки (1) r'k=s+mx mod q r r' =g s y m mod p (2) r'k=m+sx mod q r r' =g m y s mod p (3) sk= r'+mx mod q r s =g r' y m mod p (4) sk= m+ r'x mod q r s =g m y r' mod p (5) mk= s+ r'x mod q r m =g s y r' mod p (6) mk= r'+sx mod q r m =g r' y s mod p Это шесть различных схем цифровых подписей . Добавление минуса увеличивает их количество до 24. При использовании всех возможных значения a, b и c число схем доходит 120. EIGamal [518, 519] и DSA [1154] по существу основаны на уравнении (4). Другие схемы - на уравнении (2) [24, 1629]. Schnorr [1396, 1397], как и другая схема [1183], тесно связан с уравнением (5). А уравнение (1) мож- но изменить так, чтобы получить схему, предложенную в [1630]. Оставшиеся уравнения - новые. Далее. Любую из этих схем можно сделать более DSA-подобной, определив r как r = (g k mod p) mod q Используйте то же уравнение подписи и сделайте уравнением проверки u 1 = a -1 b mod q u 2 = a -1 c mod q v = (( g y u u 1 2 * ) mod p) mod q (r mod q) a = g b y c mod p Существуют и две другие возможности подобных преобразований [740, 741]. Такие операции можно проде- лать с каждой из 120 схем, доведя общее число схем цифровой подписи, использующих дискретные логарифмы, до 480. Но и это еще не все. Дополнительные обобщения и изменения приводят более, чем к 13000 вариантам (не все из них достаточно эффективны) [740, 741]. Одной из приятных сторон использования RSA для цифровой подписи является свойство, называемое вос- становлением сообщения. Когда вы проверяете подпись RSA, вы вычисляете m. Затем вычисленное m сравни- вается с сообщением и проверяется, правильна ли подпись сообщения . В предыдущих схемах восстановить m при вычислении подписи невозможно, вам потребуется вероятное m, которое и используется в уравнении про- верки. Но, оказывается, можно построить вариант с восстановлением сообщения для всех вышеприведенных схем. Для подписи сначала вычислим r = mg k mod p и заменим m единицей в уравнении подписи. Затем можно восстановит уравнение проверки так, чтобы m могло быть вычислено непосредственно. То же самое можно предпринять для DSA-подобных схем: r = (mg k mod p) mod q Безопасность всех вариантов одинакова, поэтому имеет смысл выбирать схему по сложности вычисления . Большинство схем замедляет необходимость вычислять обратные значения . Как оказывается, одна из этих схем позволяет вычислять и уравнение подписи, и уравнение проверки без использования обратных значений, при этом еще и восстанавливая сообщение. Она называется схемой p-NEW [1184]. r = mg -k mod p s = k - r'x mod q m восстанавливается (и проверяется подпись) с помощью вычисления m = g s y r' r mod p В ряде вариантов одновременно подписывается по два-три блока сообщения [740], другие варианты можно использовать для слепых подписей [741]. Это значительная область для изучения. Все различные схемы цифровой подписи с использованием ди с- кретных логарифмов были объединены логическим каркасом. Лично я считаю, что это окончательно положит конец спорам между Schnorr [1398] и DSA [897]: DSA не является ни производной Schnorr, равно как и EIGa- mal. Все три алгоритма являются частными случаями описанной общей схемы, и эта общая схема незапатент о- вана. 20.5 ONG-SCHNORR-SHAMIR Эта схема подписи использует многочлены по модулю n [1219, 1220]. Выбирается большое целое число (знать разложение n на множители не обязательно). Затем выбирается случайное число k, взаимно простое с n, и вычисляется h, равное h = -k -2 mod n = -(k -1 ) 2 mod n Открытым ключом служат h и n; а закрытым - k. Чтобы подписать сообщение M, сначала генерируется случайное число r, взаимно простое с n. Затем вычис- ляется: S 1 = 1/2 (M/H +r) mod n S 2 = 1/2 (M/H -r) mod n Пара чисел S 1 и S 2 представляет собой подпись. Проверяя подпись, убеждаются, что S 1 2 + h*S 2 2 ? M (mod n) Описанный здесь вариант схемы основан на квадратичных многочленах . При его опубликовании в [1217] за успешный криптоанализ было предложено вознаграждение в $100. Небезопасность схемы была доказана [1255, 18], но это не остановило ее авторов. Они предложили модификацию алгоритма, основанную на кубических многочленах, также оказавшуюся небезопасной [1255]. Авторы предложили версию на базе многочленов че т- вертой степени, но была взломана и она [524, 1255]. Вариант, решающий эти проблемы, описан в [1134]. 20.6 ESIGN ESICN -это схема цифровой подписи, разработанная NTT Japan [1205, 583]. Утверждалось, что она не менее безопасна, чем RSA или DSA, и намного быстрее при тех же размерах ключа и подписи . Закрытым ключом служит пара больших простых чисел p и q. Открытым ключом является n, для которого n = p 2 *q H - это хэш-функция, применяемая к сообщению m, причем значение H(m) находится в пределах от 0 до n-1. Используется также параметр безопасности k, который будет вкратце рассмотрен. (1) Алиса выбирает случайное число x, меньшее pq. (2) Алиса вычисляет: w, наименьшее целое, которое больше или равно (H(m) - x k mod n)/pq s = x + ((w/kx k-1 mod p) pq (3) Алиса посылает s Бобу. (4) Для проверки подписи Боб вычисляет s k mod n. Кроме этого, он вычисляет a, наименьшее целое, которое больше или равно удвоенному числу битов n, деленному на 3. Если H(m) меньше или равна s k mod n, и ес- ли s k mod n меньше H(m)+2 a , то подпись считается правильной. Выполнив ряд предварительных вычислений, этот алгоритм можно ускорить . Эти вычисления могут быть выполнены в произвольный момент времени и никак не связаны с подписываемым сообщением . Выбрав x, Алиса может разбить этап (2) на два подэтапа. Сначала. (2a) Алиса вычисляет: u = x k mod n v = l/(kx k-1 ) mod p (2b) Алиса вычисляет: w= наименьшее целое, которое больше или равно (H(m) - u)/pq s = x + ((wv mod p) pq Для обычно используемых размеров чисел предварительные вычисления ускоряют процесс подписи на п о- рядок. Почти вся трудная работа выполняется именно на стадии предварительных вычислений . Обсуждение действий модульной арифметики, выполняемых при ускорении ESIGN, можно найти в [1625, 1624]. Этот алго- ритм можно расширить для работы с эллиптическими кривыми [1206]. Безопасность ESIGN Когда этот алгоритм был впервые предложен , k было выбрано равным 2 [1215]. Такая схема быстро была взломана Эрни Брикеллом (Ernie Brickell) и Джоном ДеЛаурентисом [261], которые распространили свое вскрытие и на случай k = 3. Модифицированная версия этого алгоритма [1203] была взломана Шамиром [1204]. Вариант, предложенный в [1204], был взломан в [1553]. ESIGN - это сегодняшняя реинкарнация алгоритмов из этого семейства. Попытка вскрыть ESIGN [963] оказалась безрезультатной. В настоящее время авторы рекомендуют использовать следующие значения k: 8, 16, 32, 64, 128, 256, 512 и 1024. Они также рекомендуют, чтобы p и q были не меньше 192 битов каждое, образуя n не менее, чем 576 би- тов в длину. (Я думаю, что n должно быть еще в два раза больше.) Авторы считают, что с такими значениями параметров, безопасность ESIGN равна безопасности RSA или Rabin. И выполненный ими анализ показывает, что скорость ESIGN намного выше, чем у RSA, EIGamal и DSA [582]. Патенты ESICN запатентован в Соединенных Штатах [1208], Канаде, Англии, Франции, Германии и Италии. Любой, кто хочет получить лицензию на алгоритм, должен обратиться в Отдел интеллектуальной собственности NTT (Intellectual Property Department, NTT, 1-6Uchisaiwai-cho, 1-chome, Chiyada-ku, 100 Japan). 20.7 Клеточные автоматы Совершенно новая идея, изученная Папуа Гуамом ( Papua Guam) [665], состоит в использовании в криптоси- стемах с открытыми ключами клеточных автоматов. Эта система все еще слишком нова и не прошла через тща- тельное изучение, но предварительное исследование показало, что у нее может быть такое же криптографически слабое место, как и у других систем [562]. Тем не менее, это многообещающая область исследований . Свойст- вом клеточных автоматов является то, что даже если они инвертируемы, невозможно вычислить предка прои з- вольного состояния, инвертировав правило нахождения потомка . Это выглядит очень похоже на однонапра в- ленную хэш-функцию с лазейкой. 20.8 Другие алгоритмы с открытым ключом За эти годы было предложено и вскрыто множество других алгоритмов с открытыми ключами. Алгоритм Matsumoto-lmai [1021] был вскрыт в [450]. Алгоритм Cade был впервые предложен в 1985 году, взломан в 1986 [774], и затем доработан в том же году [286]. Помимо этих вскрытий, существуют общие вскрытия, расклады- вающие многочлены над конечными полями [605]. К любому алгоритму, безопасность которого определяется композицией многочленов над конечными полями, нужно относиться со скептицизмом, если не с откровенным подозрением. Алгоритм Yagisawa объединяет возведение в степень mod p с арифметикой mod p-1 [1623], он был взломан в [256]. Другой алгоритм с открытым ключом, Tsujii-Kurosawa-Itoh-Fujioka-Matsumoto [1548] , также оказался небезопасным [948]. Небезопасной [717] была и третья система, Luccio-Mazzone [993]. Схема подписи на базе birational перестановок [1425] была взломана на следующий день после ее представления [381]. Несколько схем подписей предложил Тацуаки Окамото (Tatsuaki Okamoto): было доказано, что одна из них так же безопасна, как проблема дискретного логарифма, а другая - как проблема дискретного логарифма и проблема разложения на множители [1206]. Аналогичные схемы представлены в [709]. Густавус Симмонс (Gustavus Simmons) предложил использовать в качестве основы алгоритмов с открытыми ключами J-алгебру [1455, 145]. От этой идеи пришлось отказаться после изобретения эффективных методов разложения многочленов на множители [951]. Также были изучены и специальные полугруппы многочленов [1619, 962], но и это ничего не дало. Харальд Нидеррейтер (Harald Niederreiter) предложил алгоритм с откры- тым ключом на базе последовательностей сдвиговых регистров [1166]. Другой алгоритм использовал слова Линдона (Lyndon) [1476], а третий - prepositional исчисление [817]. Безопасность одного из недавних алгорит- мов с открытыми ключами основывалась на проблеме matrix cover [82]. Тацуаки Окамото и Казуо Ота (Kazuo Ohta) провели сравнение ряда схем цифровой подписи в [1212]. Перспективы создания радикально новых и различных алгоритмов с открытыми ключами неясны . В 1988 году Уитфилд Диффи отметил, что большинство алгоритмов с открытыми ключами основаны на одной из трех трудных проблем [492, 494]: 1. Рюкзак: Дано множество уникальных чисел, найти подмножество, сумма которого равна N. 2. Дискретный логарифм: Если p - простое число, а g и M - целые, найти x, для которого выполняется g x ?M (mod p). 3. Разложение на множители: Если N - произведение двух простых чисел, то лиьо (a) разложить N на множители, (b) для заданных целых чисел M и C найти d, для которого M d ? C (mod N), (c) для заданных целых чисел e и C найти M, для которого M e ? C (mod N), (d) для заданного целого числа x определить, существует ли целое число y, для которого x ? y 2 (mod N). Согласно Диффи [492, 494], проблема дискретных логарифмов была предложена Дж. Гиллом ( J. Gill), про- блема разложения на множители - Кнутом , а проблема рюкзака - самим Диффи. Эта узость математических основ криптографии с открытыми ключами немного беспокоит . Прорыв в реше- нии либо проблемы дискретных логарифмов, либо проблемы разложения на множители сделает небезопасными целые классы алгоритмов с открытыми ключами. Диффи показал [492, 494], что подобный риск смягчается двумя факторами: 1. Все операции, на которые сейчас опирается криптография с открытыми ключами - умножение, возведение в степень и разложение на множители - представляют собой фундаментальные арифметические явления . Веками они были предметом интенсивного математического изучения, и рост внимания к ним, вызванный применением в криптосистемах с открытыми ключами, увеличил, а не уменьшил наше доверие. 2. Наша возможность выполнять большие арифметические вычисления растет равномерно и сейчас позволяет нам реал и- зовывать системы с числами такого размера, чтобы эти системы были чувствительны только к действительно радикальным прорывам в разложении на множители, дискретных логарифмах или извлечении корней . Как мы уже видели, не все алгоритмы с открытыми ключами, основанные на этих проблемах, безопасны . Сила любого алгоритма с открытым ключом зависит не только от вычислительной сложности проблемы, леж а- щей в основе алгоритма. Трудная проблема необязательно реализуется в сильном алгоритме . Ади Шамир объ- ясняет это тремя причинами [1415]: 1. Теория сложности обычно связана с отдельными частными случаями проблемы. Криптоаналитик же часто получает большой набор статистически связанных проблем - различные шифротексты, заши ф- рованные одним и тем же ключом. 2. Вычислительная сложность проблемы обычно измеряется для худшего или среднего случаев . Чтобы быть эффективной в качестве способа шифрования, проблема должна быть трудной для решения по ч- ти во всех случаях. 3. Произвольную сложную проблему необязательно можно преобразовать в криптосистему, к тому же проблема должна позволить встроить в нее лазейку, знание которой и только оно делает возможным простое решение проблемы. Глава 21 Схемы идентификации 21.1 FEIGE-FIAT-SHAMIR Схема цифровой подписи и проверки подлинности, разработанная Амосом Фиатом ( Amos Fiat) и Ади Ша- миром (Adi Shamir), рассматривается в [566, 567]. Уриель Фейге (Uriel Feige), Фиат и Шамир модифицировали алгоритм, превратив его в доказательство подлинности с нулевым знанием [544, 545]. Это лучшее доказатель- ство подлинности с нулевым знанием. 9 июля 1986 года три автора подали заявку на получение патента США [1427]. Из-за возможного военного применения заявка была рассмотрена военными . Время от времени результатом работы Патентное бюро явл я- ется не выдача патента, а нечто, называемое секретным распоряжением . 6 января 1987 года, за три дня до исте- чения шестимесячного периода, по просьбе армии Патентное бюро издало такое распоряжение . Заявило, что " . . . раскрытие или публикация предмета заявки . . . может причинить ущерб национальной безопасности . . ." Авторам было приказано уведомить всех граждан США, которые по тем или иным причинам узнали о пров о- димых исследованиях, что несанкционированное раскрытие информации может закончиться двумя годами т ю- ремного заключения, штрафом $10,000 или тем и другим одновременно. Более того, авторы должны были со- общить Уполномоченному по патентам и торговым знакам обо всех иностранных гражданах, которые получили доступ к этой информации. Это было нелепо. В течение второй половины 1986 года авторы представляли свою работу на конференциях в Израиле, Европе и Соединенных Штатах . Они даже не были американским гражданами, и вся работа была выполнена в Институте Вейцмана (Weizmann) в Израиле. |