В. Водолазкий Коммерческие системы шифрования: основные алгоритмы и их реализация Часть 2. Системы с открытым ключом "Каждый человек имеет право быть высокого мнения о себе, пока не станет знаменит..." Какой-то философ Аннотация: Обсуждаются принципы построения систем с открытым ключом. Детально описаны система распределения ключей Диффи-Хелмана и алгоритм RSA. Итак, перед вами вторая часть статьи, посвященной коммерческим алгоритмам шифрования. В прошлом номере [1] мы рассмотрели алгоритм шифрования DES, а сегодня поговорим о системах с открытым ключом. Но прежде чем приступить к описанию конкретных алгоритмов, нам придется ненадолго обратиться к теории. Однонаправленные функции Несмотря на то, что вся концепция криптографических систем с открытым ключом основана на однонаправленных функциях (one way functions), достаточно сложно дать точное определение этого класса функций с математической точки зрения. Попробуем применить менее формальный, но зато более понятный подход. А именно , функция f : x -> y , где х и у - произвольные множества, является однонаправленной, если для всех х (Е) Х легко вычислить функцию f(x), и в то же время для большинства y (Е) Y получить любое значение x (Е) X, такое что f(x) = y достаточно сложно (при этом полагают, что существует, по крайней мере, одно такое значение x). К сожалению, в настящее время математика не в состоянии дать нам ответ на вопрос, существуют ли таковые функции вообще или же это только красивая гипотеза. Тем не менее пытливым умам удалось обнаружить несколько зависимостей, которые могут быть использованы (и используются!) в качестве однонаправленных. Основной критерий причисления функции к классу однонаправленных очень прост - отсутствие эффективных алгоритмов обратного преобразования. Примеры? Пожалуйста! 1) Первый кандидат в однонаправленные функции - целочисленное умножение. В самом деле, вычислить произведение двух очень больших целых чисел (имеется в виду, с помощью ЭВМ, а не вручную) достаточно легко, но даже самый мощный компьютер с наилучшими известными на сегодняшний день алгоритмами не в состоянии факторизовать (разделить на сомножители) двухсотзначное число, которое является произведением двух сопоставимых по длине простых чисел. 2) Следующий характерный пример - это модульная экспонента с фиксированными основанием и модулем. Положим, что N и A - целые числа, такие что 1 < A < N. Далее, определим множество Zn: Z = { 0, 1, 2, ... N-1}. Тогда модульная экспонента с основанием A по модулю N представляет собой функцию: F 4a,n 0 : Z 4n 0 -> Z 4n 0, F 4a,n 0(m) = A 5m 0 MOD N. (1) Существуют эффективные алгоритмы, позволяющие достаточно быстро вычислить значение функции по формуле (1). Обратная функция известна под названием задачи о дискретном логарифмировании: для известных целых A,N, X найти некоторое целое число M, такое что A 5m 0 MOD N = X И хотя модульное возведение в степень может выполняться достаточно быстро, пока не удалось найти алгоритм, обеспечивающий вычисление дискретного логарифма за приемлемое время. В то же время не удалось и доказать, что такого алгоритма не существует. Исходя из этого, модульная экспонента отнесена к однонаправленным функциям условно, что, однако, не мешает с успехом использовать ее на практике. Необходимо отметить, что любая однонаправленная функция (ОНФ) отнесена к этому классу как бы условно. Как показала практика, как только алгоритм получает достаточно широкое распространение (обращаясь к эпиграфу, становится знаменит), сразу же у определенных групп лиц возникает желание найти обратную функцию, и, поскольку это желание подкрепляется солидными денежными призами, не уверенные в себе кандидаты в ОНФ оказываются на помойке. Так что, читатель, у тебя есть возможность отличиться и посрамить апологетов буржуйских коммерческих систем шифрования. Но вернемся к теме. Вторым важным классом функций, используемых в практике построения систем с открытым ключом, являются так называемые однонаправленные функции с черным ходом (trap door one way function). Для порядка введем определение. Функция f: X -> Y относится к классу однонаправленных функций с черным ходом в том случае, если она является однонаправленной и, кроме того, возможно эффективное вычисление инверсной функции, если известен "черный ход" (или, говоря по-русски, секретная строка, число или другая информация, ассоциирующаяся с данной функцией). "Достаточно запутанное определение", - подумает читатель и будет, как всегда, прав. Поэтому автор попробует пояснить сказанное примером. В качестве демонстрации функции с черным ходом мы рассмотрим все ту же модульную экспоненту с фиксированными показателем и модулем. Пусть M и N - целые числа, а Z 4n 0 определено так же, как и раньше. Тогда модульная экспонента с фиксированным показателем M представляет собой функцию: G 4m,n 0 : Z 4n 0 -> Z 4n или G 4m,n 0(A) = A 5m 0 MOD n. Для вычисления обратной функции нам необходимо извлечь из X корень M-й степени по модулю N, то есть для заданных целых чисел M, N и X найти некоторое целое число A, такое что A 5m 0 MOD n = X. Если числа M и N известны, достаточно легко вычислить Gm,n(A) для любого основания A. Основное отличие от задачи вычисления дискретного логарифма состоит в том, что известен эффективный алгоритм вычисления корня m-й степени из X по модулю N. Интересно отметить, что пока не известно, как эффективно реализовать этот алгоритм, если известны только M и N. Завершая наше "теоретическое" введение, еще раз отметим, что любители математики и особенно "высшей арифметики" - теории чисел - имеют непочатый фронт работ как в области поиска новых однонаправленных функций, так и в области отыскания эффективных алгоритмов обратных преобразований. В случае решения любой из этих задач вы сможете забыть об обдираловке с импозантным названием "Лотто "Миллион"". Миллионеры в эту "игру" не играют! За работу, господа! Система распределения ключей Диффи-Хелмана В традиционных криптографических системах (сразу вспоминается фильм "Семнадцать мгновений весны") каждая пара пользователей применяет один и тот же секретный ключ для шифрования и расшифровки сообщений. Стоп! Давайте-ка определимся с терминологией. Не отрываясь от примера: Юстас - зашифровывает, Алекс - расшифровывает, а старина Мюллер - дешифрует сообщение. Теперь можно продолжать. Это означает, что необходим надежный способ передачи ключа от одного пользователя к другому. Если пользователи меняют ключ достаточно часто, его доставка превращается в серьезную проблему. И более того, в традиционной криптографической системе просто невозможно передать информацию новому пользователю системы до тех пор, пока ему не будет по надежному каналу связи передан секретный ключ. И если спецслужбы как-то выходят из этой ситуации, то для коммерческих приложений это никуда не годится. И пытливая инженерная мысль нашла выход - была создана система распределения открытых ключей (public-key distribution system), позволяющая своим пользователям обмениваться секретными ключами по незащищенным каналам связи. Первой системой такого рода стала система Диффи-Хелмана, разработанная в 1976 году, построенная на задаче о дискретном логарифмировании. Предположим, что два пользователя, Алекс и Юстас, применяющие традиционную криптосистему, желают связаться друг с другом. Это означает, что они должны прийти к соглашению относительно ключа K, которым будут шифроваться сообщения. Давайте посмотрим, как система Диффи-Хелмана позволит обменяться ключом. Пусть N - некоторое большое целое число, а G - другое целое, такое что 1 7 , 0 G  7,  0N-1. Рассмотрим процедуру обмена ключами по шагам. 1. Вначале Алекс и Юстас достигают соглашения о значениях N и G (как правило, эти значения являются стандартными для всех пользователей системы). 2. Затем Алекс выбирает некоторое большое целое число X и вычисляет XX = G 5x 0 MOD N. Аналогичным образом Юстас выбирает число Y и вычисляет YY = G 5y 0 MOD N. После этого Алекс и Юстас обмениваются значениями XX и YY. (Мы считаем, что все данные, которые передаются по каналу связи, могут быть перехвачены злоумышленником - стариной Мюллером). Числа X и Y Алекс и Юстас хранят в секрете. 3. Получив от Юстаса число YY, Алекс вычисляет K 41 0 = YY 5x 0 MOD N, а Юстас K 42 0 = XX 5y 0 MOD N. Но (!) YY 5x 0 MOD N = G 5x*y 0 MOD N = XX 5y 0 MOD N, а следовательно, K 41 0 = K 42 0 = K. Это значение K и является ключом, который используется для шифрования сообщений. А что же старина Мюллер? Злоумышленник, перехвативший G, N, XX и YY, тоже должен определить значение ключа K. Очевидный путь для решения задачи состоит в вычислении значения X по G,N,XX или, по крайней мере, некоторого X^, такого что G 5x^ 0 MOD N = X, поскольку в этом случае YY 5x^ 0 MOD N = K. Однако это и есть задача дискретного логарифмирования в чистом виде, которая считается неразрешимой. Система Диффи-Хелмана позволяет двум пользователям прийти к соглашению относительно общего секретного ключа. Однако система никак не влияет на то, как потом будет шифроваться сама информация. И если Алекс хочет передать Юстасу секретное сообщение M, то после установления ключа по Диффи-Хелману может быть использована любая система шифрования. Но системы с открытым ключом создавались не только и даже не столько для решения задачи распределения ключей. При грамотном подходе возможно эффективное их использование для шифрования информации. Ведь, по определению, система с открытым ключом отличается тем, что тот, кто знает ключ для шифрования, не может дешифровать текст за практически приемлемое время. Рассмотрим, как же используются системы с открытым ключом. Пользователь Алекс имеет в своем распоряжении два алгоритма: E 4a 0 для шифрования и D 4a 0 для расшифровки сообщений. При этом алгоритм E 4a делается общедоступным, например, через использование каталога ключей, а алгоритм D 4a 0 хранится Алексом в секрете. Если Юстас или даже старина Мюллер хочет послать Алексу сообщение, он ищет в каталоге ключей алгоритм E 4a 0 и использует его для шифрования передаваемой информации. А вот расшифровать сообщение сможет только Алекс, поскольку алгоритм D 4a есть только у него. Очевидно, что E 4a 0 и D 4a 0 должны удовлетворять условию: D 4a 0(E 4a 0(M)) = M, для любого сообщения M. И снова, как и для традиционных криптосхем, требуется получить эффективные алгоритмы E 4a 0 и D 4a 0. При этом необходимо, чтобы алгоритм E 4a 0 представлял собой функцию с черным ходом, то есть знание алгоритма E 4a 0 не должно быть достаточным для реализации D 4a 0. Системы с открытым ключом могут быть реализованы только в том случае, если подобрана однонаправленная функция с черным ходом. При этом необходимо постоянно помнить, что доказательства однонаправленности не существует. А из этого, в свою очередь, следует, что при выборе кандидатов в однонаправленные функции следует соблюдать известную осторожность, подкрепленную результатами тщательного тестирования. Система RSA Первую и наиболее известную систему с открытым ключом разработали еще в 1978 году трое американцев: Ривест, Шамир и Адлеман. И по первым буквам фамилий авторов система получила свое название - RSA. Основа системы - функция модульного экспоненцирования с фиксированными модулем и показателем степени. Процедура шифрования-расшифровки в RSA реализуется следующим образом: 1. Выбираем два случайных больших простых числа P и Q и вычисляем N = P * Q. 2. Выбираем большое целое число D, являющееся взаимно простым с произведением (P-1)*(Q-1) (для подзабывших арифметику напомним, что взаимно простыми являются два числа, наибольший общий делитель которых равен 1 [2]). 3. Вычисляем число e, такое что [1, 1 7 ,  0e 7 ,  0(P-1)*(Q-1)] и e*D = 1 MOD (P-1)*(Q-1) 4. Обнародуем открытый ключ (алгоритм шифрования), состоящий из пары чисел (e,N). 5. Исходный текст (или отдельный символ сообщения) преобразуется в целое число M, такое что 0  7,  0М  7,  0N-1 (если текст слишком длинный, он разбивается на блоки соответствующей длины). 6. Текст шифруется в соответствии с алгоритмом: C = M 5e 0 MOD N. 7. Полученная криптограмма C расшифровывается с использованием личного ключа (D, N) по формуле: C 5D 0 = M 5e*D 0 = M mod N. Для того чтобы алгоритм RSA имел какую-то практическую ценность, необходимо иметь возможность без существенных вычислительных затрат генерировать большие простые числа, а также уметь вычислять значение ключа e. К счастью, такие алгоритмы существуют, а также разработаны быстрые алгоритмы для вычисления значения D. Однако автор статьи не претендует на исчерпывающее описание всех тонкостей быстрого счета и приглашает читателей попробовать свои силы. Редакция готова опубликовать эффективные алгоритмы поиска простых чисел и, более того, объявляет конкурс, но об этом в конце статьи. Теперь давайте рассмотрим пример реализации алгоритма RSA. Имейте в виду, что пример носит чисто учебный характер, хотя и отличается от "боевого" только малым (всего 2) числом разрядов в используемых ключах e и D. Итак, положим, P=47, Q=59. Тогда N = P*Q = 2773, а (P-1)*(Q-1) = 2668. Совершенно произвольно выберем D = 157. Вычислим e = 17. Теперь закодируем алфавит в виде: А = 01, Б = 02, .... Я = 33, <пробел> = 00, и тогда сообщение: ОТБЫВАЕМ ЗАВТРА будет представлено в виде : 1620 0229 0301 0614 0009 0103 2018 0100 Мы разбиваем все сообщение на блоки из четырех цифр и кодируем каждый блок. Например: C 41 0 = 1620 517 0 MOD 2773 = 2316 В результате мы получим: 2316 2137 0214 1412 2072 0850 0985 1952 Рассмотрим теперь обратное преобразование. Реальная польза от любого алгоритма шифрования может быть получена только в том случае, если имеется возможность адекватно восстановить исходный текст. Применительно к системе RSA это означает, что для заданных публичного (e,N) и личного (D,N) ключей для любого сообщения M, представленного целым числом в диапазоне [0,N-1], должно выполняться соотношение: C = M 5e 0 MOD N, тогда C 5D 0 = M MOD N. То есть для восстановления исходного текста необходимо вычислить модульную экспоненту, возведя зашифрованное значение Ci в степень D по модулю N. Замечания по применению Будьте осторожны при выборе чисел P и Q. Наиболее общие правила: эти простые (!) числа не должны лежать рядом: одно из них должно быть больше другого на несколько порядков, P-1 и Q-1 должны иметь как можно меньший наибольший общий делитель. Поскольку на сегодняшний день не найден алгоритм, позволяющий за приемлемое время разложить на сомножители двухсотзначное целое число, вы можете считать ваш выбор удачным, если P и Q - простые числа со 100 десятичныи цифрами и более [3]. Необходимо также иметь в виду наиболее очевидные пути взлома системы RSA: 1) Факторизация N. Как только злоумышленник сумеет разложить N на сомножители, он сможет вычислить F(N) = (P-1)*(Q-1), откуда легко определяется ключ D. 2) Вычисление F(N) без факторизации N. Если определено значение F(N), то ключ расшифровки D вычисляется достаточно просто. Кроме того, знание F(N) позволяет легко разложить на сомножители число N. В самом деле: P + Q = N - F(N) + 1 2 2 (P - Q) = (P + Q) - 4*N Q = 1/2 * [ (P + Q) - (P - Q)] После этого без каких бы то ни было проблем вычисляется ключ D. В помощь начинающим Когда автор готовил пример, то для того чтобы получить реальные числа пришлось написать небольшую программу на Бейсике (выбор языка объясняется тем, что самураи из фирмы Sharp не догадались поставить в свой калькулятор PC-1600 хотя бы Паскаль - прим. автора). Как ни странно, но эта программа (см. листинг) представляет собой определенный интерес, прежде всего, тем как организовано вычисление многоразрядных чисел. Поскольку быстрого алгоритма возведения в степень у автора не было, то применен алгоритм 6-го класса [2] - "перемножай в лоб". А поэтому : * * * * * Конкурс! * * * * * Редакция журнала "Монитор" объявляет конкурс на разработку лучшего алгоритма вычисления модульной экспоненты. Основные критерии : максимальная скорость вычислений и минимальная длина. Никаких ограничений на используемый язык программирования не предъявляется. Лучшие алгоритмы будут опубликованы на наших страницах. Литература 1. Монитор. - 1992. - N 6-7. 2. Математика: Учебник для 6 класса. - М.: Просвещение, 1991. 3. Trung Van Tran. Encipherment systems and autentication/ Доклад на конференции Kryptographie und Datensicherheit, 16.4 - 18.4.1991, Эссен, ФРГ. Листинг 10 REM ********************************* 20 REM Вычисление модульной экспоненты 30 REM (С) "Монитор" 1992 35 REM Версия для PC-1600 40 REM ********************************* 100 DIM T(100) 110 CLS 130 PRINT "Модульная экспонента" 140 CURSOR 1,2 150 PRINT "Введите модуль : "; 160 INPUT M 170 CURSOR 1,2 : PRINT " "; 180 CURSOR 1,2 190 PRINT "Степень : "; : INPUT P 210 CURSOR 1,2 : PRINT " "; 220 CURSOR 1,2 230 CURSOR 1,2 : PRINT "Число : "; : INPUT N 240 IF N=0 THEN STOP 300 FOR I=1 TO 20 310 T(I) = 0 : NEXT I : REM Очистка временного массива 320 H = 1 : REM Инициализация счетчика памяти 330 S = 1 : REM и счетчика шагов экспоненцирования 335 T(1) = 1 340 IF S = P THEN 500 :REM Если выполнены все умножения - выход 350 CURSOR 20,1 : PRINT S: REM Отображение текущего шага вычислений 352 Z = 0 420 FOR J = 1 TO 100 430 T(J) = T(J)*N+Z 440 IF T(J) < 10000 THEN 468 460 Z = T(J) \ 10000 : REM Целочисленное деление 465 T(J) = T(J) MOD 10000: GOTO 470 468 Z = 0 470 NEXT J 475 REM GOSUB 7000 : REM Отладочная печать промежуточного результата 480 S = S + 1: GOTO 340 500 REM GOSUB 7000 : REM Еще одна отладочная печать 510 REM -------------------------------- 520 REM -- Вычисление модуля числа -- 530 REM -------------------------------- 550 Z = 0 560 FOR V = 1 TO 100 570 Z = (T(101-V)+Z*10000) MOD M 580 NEXT V 590 R = Z 800 CURSOR 1,2: PRINT " "; 810 CURSOR 1,1: PRINT "Результат : ";R 820 G$ = INKEY$ 822 IF G$ = "N" THEN GOTO 825 ELSE GOTO 820 825 CURSOR 1,1: PRINT " "; 830 GOTO 230 7000 REM Вывод на принтер очень длинного целого числа 7010 CSIZE 1 7020 FOR V = 1 TO 30 7030 LPRINT T(31-V); 7040 NEXT V: LPRINT 7050 RETURN