Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Практические реализации Для последовательности из шести элементов нетрудно решить задачу рюкзака, даже если последовател ь- ность не является сверхвозрастающей. Реальные рюкзаки должны содержать не менее 250 элементов . Длина каждого члена сверхвозрастающей последовательности должна быть где-то между 200 и 400 битами , а длина модуля должна быть от 100 до 200 битов. Для получения этих значений практические реализации используют генераторы случайной последовательности . Вскрывать подобные рюкзаки при помощи грубой силы бесполезно . Если компьютер может проверять мил- лион вариантов в секунду, проверка всех возможных вариантов рюкзака потребует свыше 10 46 лет. Даже мил- лион машин, работающих параллельно, не успеет решить эту задачу до превращения солнца в сверхновую зве з- ду. Безопасность метода рюкзака Взломали криптосистему, основанную на проблеме рюкзака, не миллион машин, а пара криптографов . Сна- чала был раскрыт единственный бит открытого текста [725]. Затем Шамир показал, что в определенных обсто я- тельствах рюкзак может быть взломан [1415, 1416]. Были и другие достижения - [1428, 38, 754, 516, 488] - но никто не мог взломать систему Мартина-Хеллмана в общем случае. Наконец Шамир и Циппел (Zippel) [1418, 1419, 1421] обнаружили слабые места в преобразовании, что позволило им восстановить сверхвозрастающую последовательность рюкзака по нормальной . Точные доказательства выходят за рамки этой книги, но их хор о- ший обзор можно найти в [1233, 1244]. На конференции, где докладывались эти результаты, вскрытие было продемонстрировано по стадиям на компьютере Apple II [492, 494]. Варианты рюкзака После вскрытия оригинальной схемы Меркла-Хеллмана было предложено множество других систем на принципе рюкзака: несколько последовательных рюкзаков, рюкзаки Грэм-Шамира (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. Иностранные патенты на алгоритм рюкзака Меркла- Хеллмана Страна Номер Дата получения Бельгия 871039 5 апреля 1979 года Нидерланды 7810063 10 апреля 1979 года Великобритания 2006580 2 мая 1979 года Германия 2843583 10 мая 1979 года Швеция 7810478 14 мая 1979 года Франция 2405532 8 июня 1979 года Германия 2843583 3 января 1982 года Германия 2857905 15 июля 1982 года Канада 1128159 20 июля 1982 года Великобритания 2.006580 18 августа 1982 года Швейцария 63416114 14 января 1983 года Италия 1099780 28 сентября 1985 года 19.3 RSA Вскоре после алгоритма рюкзака Меркла появился первый полноценный алгоритм с открытым ключом , ко- торый можно использовать для шифрования и цифровых подписей : RSA [1328, 1329]. Из всех предложенных за эти годы алгоритмов с открытыми ключами RSA проще всего понять и реализовать. (Мартин Гарднер (Martin Gardner) опубликовал раннее описание алгоритма в своей колонке "Математические игры" в Scientific American [599].) Он также является самым популярным. Названный в честь трех изобретателей - Рона Ривеста (Ron Rivest), Ади Шамира (Adi Shamir) и Леонарда Эдлмана (Leonard Adleman) - этот алгоритм многие годы проти- востоит интенсивному криптоанализу. Хотя криптоанализ ни доказал, ни опроверг безопасность RSA, он, по сути, обосновывает уровень доверия к алгоритму . Безопасность RSA основана на трудности разложения на множители больших чисел . Открытый и закрытый ключи являются функциями двух больших (100 - 200 разрядов или даже больше) простых чисел. Предполагает- ся, что восстановление открытого текста по шифротексту и открытому ключу эквивалентно разложению на множители двух больших чисел. Для генерации двух ключей используются два больших случайных простых числа , p и q. Для максимальной безопасности выбирайте p и q равной длины. Рассчитывается произведение: n = p q Затем случайным образом выбирается ключ шифрования e, такой что e и (p-1)(q-1) являются взаимно про- стыми числами. Наконец расширенный алгоритм Эвклида используется для вычисления ключа дешифриров а- ния d, такого что ed = 1 (mod (p-1)(q-1)) Другими словами d = e -1 mod ((p-1)(q-1)) Заметим, что d и n также взаимно простые числа. Числа e и n - это открытый ключ, а число d - закрытый. Два простых числа p и q больше не нужны. Они должны быть отброшены, но не должны быть раскрыты . Для шифрования сообщения m оно сначала разбивается на цифровые блоки, меньшие n (для двоичных дан- ных выбирается самая большая степень числа 2, меньшая n). То есть, если p и q - 100-разрядные простые числа, то n будет содержать около 200 разрядов, и каждый блок сообщения m i должен быть около 200 разрядов в длину. (Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями сл е- ва, чтобы гарантировать, что блоки всегда будут меньше n. Зашифрованное сообщение c будет состоять из бло- ков c i той же самой длины. Формула шифрования выглядит так c i = m i e mod n Для расшифровки сообщения возьмите каждый зашифрованный блок c i и вычислите m i = c i d mod n Так как c i d = (m i e ) d = m i ed = m i k(p-1)(q-1)+1 = m i m i k(p-1)(q-1) = m i *1 = m i ; все (mod n) формула восстанавливает сообщение. Это сведено в 17-й. Табл. 19-2. Шифрование RSA Открытый ключ: n произведение двух простых чисел p и q (p и q должны храниться в секрете) e число, взаимно простое с (p-1)(q-1) Закрытый ключ: d e -1 mod ((p-1)(q-1)) Шифрование: c = m e mod n Дешифрирование: m = c d mod n Точно также сообщение может быть зашифровано с помощью d, а зашифровано с помощью e, возможен любой выбор. Я уберегу вас от теории чисел, доказывающей, почему этот алгоритм работает. В большинстве книг по криптографии этот вопрос подробно рассмотрен . Короткий пример возможно поможет пояснить работу алгоритма . Если p = 47 и q = 71, то n = pq = 3337 Ключ e не должен иметь общих множителей (p-1)(q-1)= 46*70 =3220 Выберем (случайно) e равным 79. В этом случае d = 79 -1 mod 3220 = 1019 При вычислении этого числа использован расширенный алгоритм Эвклида (см. раздел 11.3). Опубликуем e и n, сохранив в секрете d. Отбросим p и q. Для шифрования сообщения m = 6882326879666683 сначала разделим его на маленькие блоки . Для нашего случая подойдут трехбуквенные блоки . Сообщение разбивается на шесть блоков m i : m l = 688 m 2 = 232 m 3 = 687 m 4 = 966 m 5 = 668 m 6 = 003 Первый блок шифруется как 688 79 mod 3337 = 1570 = c l Выполняя те же операции для последующих блоков, создает шифротекст сообщения : c = 1570 2756 2091 2276 2423 158 Для дешифрирование нужно выполнить такое же возведение в степень, используя ключ дешифрирования 1019: 1570 1019 mod 3337 = 688 = m l Аналогично восстанавливается оставшаяся часть сообщения . Аппаратные реализации 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. Не все из них доступны в свободной продаже . Табл. 19-3. Существующие микросхемы RSA Компания Тактовая частота Скорость передачи в Бодах на 512 бит Тактовые циклы для шифрования 512 бит Технология Битов на микросхему Количество транзисторов Alpha Techn. 25 МГц 13K 0.98 М 2 микрона 1024 180000 AT&T 15 МГц 19K 0.4 М 1.5 микрона 298 100000 British Telecom 10 МГц 5.IK 1 М 2.5 микрона 256 ----- Business Sim. Ltd. 5 МГц 3.8K 0.67 М Вентильная матрица 32 ----- CalmosSyst-Inc. 20 МГц 2.8K 0.36 М 2 микрона 593 95000 CNET 25 МГц 5.3K 2.3 М 1 микрон 1024 100000 Cryptech 14 МГц 17K 0.4 М Вентильная матрица 120 33000 Cylink 30 МГц 6.8K 1.2 М 1.5 микрона 1024 150000 GEC Marconi 25 МГц 10.2K 0.67 М 1.4 микрона 512 160000 Pijnenburg 25 МГц 50K 0.256 М 1 микрон 1024 400000 Sandia 8 МГц IOK 0.4 М 2 микрона 272 86000 Siemens 5 МГц 8.5K 0.03 М 1 микрон 512 60000 Скорость RSA Аппаратно RSA примерно в 1000 раз медленнее DES. Скорость работы самой быстрой СБИС-реализации RSA с 512-битовым модулем - 64 килобита в секунду [258]. Существуют также микросхемы, которые выполн я- ют 1024-битовое шифрование RSA. В настоящее время разрабатываются микросхемы, которые, используя 512- битовый модуль, приблизятся к рубежу 1 Мбит/с. Возможно, они появятся в 1995 году. Производители также применяют RSA в интеллектуальных карточках, но эти реализации медленнее . Программно DES примерно в 100 раз быстрее RSA. Эти числа могут незначительно измениться при измен е- нии технологии, но RSA никогда не достигнет скорости симметричных алгоритмов . В 15-й приведены примеры скоростей программного шифрования RSA [918]. Табл. 19-4. Скорости RSA для различных длин модулей при 8-битовом от- крытом ключе (на SPARC II) 512 битов 768 битов 1024 бита Шифрование 0.03 с 0.05 с 0.08 с Дешифрирование 0.16 с 0.48 с 0.93 с Подпись 0.16 с 0.52 с 0.97 с Проверка 0.02 с 0.07 с 0.08 с Программные Speedups Шифрование RSA выполняется намного быстрей, если вы правильно выберете значение e. Тремя наиболее частыми вариантами являются 3, 17 и 65537 (2 16 + 1). (Двоичное представление 65537 содержит только две единицы, поэтому для возведения в степень нужно выполнить только 17 умножений .) X.509 советует 65537 [304], PEM рекомендует 3 [76], а PKCS #l (см. раздел 24.14) - 3 или 65537 [1345]. Не существует никаких про- блем безопасности, связанных с использованием в качестве e любого из этих трех значений (при условии, что вы дополняете сообщения случайными числами - см. раздел ниже), даже если одно и то же значение e использу- ется целой группой пользователей. Операции с закрытым ключом можно ускорить при помощи китайской теоремы от остатках, если вы сохр а- нили значения p и q, а также дополнительные значения: d mod (p - 1), d mod (q - 1) и q -1 mod p [1283, 1276]. Эти дополнительные числа можно легко вычислить по закрытому и открытому ключам . Безопасность RSA Безопасность RSA полностью зависит от проблемы разложения на множители больших чисел . Технически, это утверждение о безопасности лживо. Предполагается, что безопасность RSA зависит от проблемы разложе- ния на множители больших чисел. Никогда не было доказано математически, что нужно разложить n на множи- тели, чтобы восстановить m по c и e. Понятно, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел . Я не слишком волнуюсь об этом. Также можно вскрыть RSA, угадав значение (p-1)(q-1). Это вскрытие не проще разложения n на множители [1616]. Для сверхскептиков: доказано, что некоторые варианты RSA также сложны, как и разложение на множители (см. раздел 19.5). Загляните также в [361, где показано, что раскрытие даже нескольких битов информации по зашифрованному RSA шифротексту не легче, чем дешифрирование всего сообщения . Самым очевидным средством вскрытия является разложение n на множители. Любой противник сможет по- лучить открытый ключ e и модуль n. Чтобы найти ключ дешифрирования d, противник должен разложить n на множители. Современное состояние технологии разложения на множители рассматривалось в разделе 11.4. В настоящее время передним краем этой технологии является число, содержащее 129 десятичных цифр . Значит, n должно быть больше этого значения. Рекомендации по выбору длины открытого ключа приведены в разделе 7.2. Конечно, криптоаналитик может перебирать все возможные d, пока он не подберет правильное значение . Но такое вскрытие грубой силой даже менее эффективно, чем попытка разложить n на множители. Время от времени появляются заявления о том, что найден простой способ вскрытия RSA, но пока ни одно из подобных заявлений не подтвердилось . Например, в 1993 году в черновике статьи Вильяма Пейна (William Payne) был предложен метод, основанный на малой теореме Ферма [1234]. К сожалению, этот метод оказался медленнее разложения на множители Существует еще один повод для беспокойства . Большинство общепринятых алгоритмов вычисления простых чисел p и q вероятностны, что произойдет, если p или q окажется составным? Ну, во первых, можно свести ве- роятность такого события до нужного минимума . И даже если это произойдет, скорее всего такое событие будет сразу же обнаружено - шифрование и дешифрирование не будут работать . Существует ряд чисел, называемых числами Кармайкла (Carmichael), которые не могут обнаружить определенные вероятностные алгоритмы пои с- ка простых чисел. Они небезопасны, но чрезвычайно редки [746]. Честно говоря, меня бы это не обеспокоило. Вскрытие с выбранным шифротекстом против RSA Некоторые вскрытия работают против реализаций RSA. Они вскрывают не сам базовый алгоритм, а на д- строенный над ним протокол. Важно понимать, что само по себе использование RSA не обеспечивает безопас- ности. Дело в реализации. Сценарий 1: Еве, подслушавшей линии связи Алисы, удалось перехватить сообщение c, шифрованное с по- мощью RSA открытым ключом Алисы. Ева хочет прочитать сообщение. На языке математики, ей нужно m, для которого m = c d Для раскрытия m она сначала выбирает первое случайное число r, меньшее n. Она достает открытый ключ Алисы e. Затем она вычисляет x = r e mod n y = xc mod n t = r -1 mod n Если x = r e mod n, то r = x d mod n. Теперь просит Алису подписать y ее закрытым ключом, таким образом расшифровав y. (Алиса должна под- писать сообщение, а не его хэш сумму.) Не забывайте, Алиса никогда раньше не видела y. Алиса посылает Еве u = y d mod n Теперь Ева вычисляет tu mod n = r -1 y d mod = r -1 x d c d mod n = c d mod n = m И Ева получает m. Сценарий 2: Трент - это компьютер-нотариус. Если Алиса хочет заверить документ, она посылает его Тренту. Трент подписывает его цифровой подписью RSA и отправляет обратно. (Однонаправленные хэш- функции не используются, Трент шифрует все сообщение своим закрытым ключом .) Мэллори хочет, чтобы Трент подписал такое сообщение, которое в обычном случае он он никогда не подп и- шет. Может быть это фальшивая временная метка, может быть автором этого сообщения является другое лицо . Какой бы ни была причина, Трент никогда не подпишет это сообщение, если у него будет возможность выбора . Назовем это сообщение m'. Сначала Мэллори выбирает произвольное значение x и вычисляет y = x e mod n. e он может получить без труда - это открытый ключ Трента, который должен быть опубликован, чтобы можно было проверять подписи Трента. Теперь Мэллори вычисляет m = ym' mod n и посылает m Тренту на подпись. Трент возвращает m d mod n. Now Мэллори вычисляет (m d mod n)x -1 mod n, которое равно n' d mod n и является подписью m'. На самом деле Мэллори может использовать множество способов решить подобную задачу [423, 458, 486]. Слабым местом, которое используют такие вскрытия, является сохранение мультипликативной структуры входа при возведении в степень. То есть: (xm) d mod n = x d m d mod n Сценарий!: Ева хочет, чтобы Алиса подписала m 3 . Она создает два сообщения, m l и m 2 , такие что m 3 = m 1 m 2 (mod n) Если Ева сможет заставить Алису подписать m l и m 2 , она может вычислить подпись для m 3 : m 3 d = (m l d mod n) (m 2 d mod n) Мораль: Никогда не пользуйтесь алгоритмом RSA для подписи случайных документов, подсунутых вам п о- сторонними. Всегда сначала воспользуйтесь однонаправленной хэш-фунцией . Формат блоков ISO 9796 предот- вращает это вскрытие. Вскрытие общего модуля RSA При реализации RSA можно попробовать раздать всем пользователям одинаковый модуль n, но каждому свои значения показателей степени e и d. К сожалению, это не работает. Наиболее очевидная проблема в том, что если одно и то же сообщение когда-нибудь шифровалось разными показателями степени (с одним и тем же модулем), и эти два показателя - взаимно простые числа (как обычно и бывает), то открытый текст может быть раскрыт, даже не зная ни одного ключа д ешифрирования [1457]. |