Стройникова Е.Д., Походенько Н.Д.

Белорусский государственный университет информатики и радиоэлектроники, Беларусь

 

О РЕАЛИЗАЦИИ КРИПТОСИСТЕМЫ ЭЛЬ-ГАМАЛЯ

 

О реализации криптосистемы Эль-Гамаля

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

Для данной работы была выбрана криптосистема Эль-Гамаля и на её основе создана программа шифрования и дешифрования файлов, предназначенная для широкого круга пользователей.

 

Криптосистема Эль­-Гамаля

Криптосистема  Тахира Эль-Гамаля является криптосистемой с открытым ключом, альтернативной системе RSA, и при равной длине ключа обеспечивает ту же криптостойкость. (На данный момент не существует единого мнения по поводу  предпочтительности  того  или  иного  метода.)  Этот  метод  нашёл применение  в  нашумевшей  системе  Pretty good privacy  (PGP), где с помощью него  осуществляется  управление  ключами.  Алгоритм цифровой подписи DSA,   разработанный  NIST  (National Institute of Standard and Technology) и являющийся  частью  стандарта  DSS, частично опирается на рассмотренный метод.

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

Основу криптосистемы составляют числа  p и a, где p – большое простое число, a–первообразный корень в циклической группе (ℤ/pℤ*,•). Числа p и a не представляют секрета и общедоступны.

­Пользователь A, желающий принимать криптограммы от пользователя B, случайным образом генерирует секретный ключ x (x∈ℤ/pℤ*) и вычисляет открытый ключ .

Если пользователь B хочет зашифровать открытый текст M и отправить его A, то он генерирует случайное b (b∈ℤ/pℤ*) и вычисляет сеансовый ключ

 

 

и криптограмму

.

 

Вместо простого умножения открытого сообщения M на yb возможна его зашифровка с помощью симметричного алгоритма (например, AES) [4] на ключе yb. Пара чисел (α,β) представляют собой содержание шифрованного послания. Если сообщений несколько, то они должны быть зашифрованы на разных сеансовых ключах, иначе, вскрыв одно из них, злоумышленник вычислит остальные по соотношению: 

.

 

Пользователь A, получив зашифрованное сообщение, восстанавливает его:

 

.

 

В данной работе рассматривается практическая реализация вышеописанного метода, и приводятся некоторые алгоритмы, использованные в программе.

 

Вычисление большого простого числа p

Имея большое простое число S, можно построить гораздо большее простое число N [6]. Выберем для этого случайным образом чётное число R на промежутке S ≤ R ≤ 4S+2 и положим N=SR+1. Затем проверим число N на отсутствие малых простых делителей. При этом осуществляется пробное деление на 303 малых простых делителя, что позволяет обнаружить 85% составных чисел. Затем число N, если оно выдержало пробное деление, испытываем 50 раз с помощью теста Рабина-Миллера. Если в ходе проверки выяснится, что N–составное число, следует выбрать новое значение R и опять повторить  вычисления. Если число N проходит тест, то оно  является простым с вероятностью большей, чем . Предполагается, что эта вероятность достаточно велика, чтобы считать N простым числом.

При этом в силу выбора R, число N  удовлетворяет неравенству N>S2. Заменив теперь число S на найденное число N и повторив с этим новым S все указанные выше действия, можно построить ещё большее простое число. Начав с какого-нибудь простого числа (например, ) и повторив указанную процедуру достаточное число раз, можно построить простые числа нужной величины.

Чтобы гарантировать безопасность протокола, необходимо строить  простое число p не менее 1024 бит, еще лучше 2048 бит и более. Кроме того, чтобы не дать криптоаналитику возможности применить специальные методы решения задачи дискретного логарифмирования, нужно позаботиться о том, чтобы число p – 1 имело большой простой делитель q, близкий к числу (p – 1)/2.

Поэтому сначала по рассмотренному методу строится большой простой делитель q (не менее 2048 бит), и лишь затем среди первых членов арифметической прогрессии  2qn+1 находится простое число p. Число p будет найдено при  [1] c.363.

 

Вероятностный алгоритм проверки нечётного числа n>1 на простоту (тест Рабина-Миллера)

Предположим, что число n простое. Тогда по малой теореме Ферма для всех целых чисел c, не кратных n, имеем: . Квадратный корень из  может принимать лишь значения ±1, поскольку только они удовлетворяют сравнению . Вычислим последовательно квадратные корни

 

,     ,    …, ,

пока не получим нечётное число . И если на некотором шаге мы получим вычет, не равный 1, то  он должен быть равен –1 (иначе мы получаем противоречие предположению, что n– простое число). Если квадратный корень, предшествующий 1, будет равен –1, то предположение о простоте n остаётся в силе. Сведём полученные результаты в следующий вероятностный тест.

1.     Определить q и t, где , число  q нечётное.

2.     Выбрать случайное число a из интервала 1 < c < n.  Положить ,  . При b = 1 завершить алгоритм с результатом              «Число n вероятно простое».

3.     Пока b ≠ 1 (mod n) и , вычислять  и  .             Если  ,то результат: «Число n  составное»; иначе результат: «Число n вероятно простое».

Результат «Число n  составное» теста Рабина-Миллера является безусловным. Составные числа n, удовлетворяющие тесту при некотором c называются сильно псевдопростыми по основанию c. М. Рабин доказал теорему о том, что число оснований c, 2 ≤  c ≤  n, по которым данное составное число  является псевдопростым, гораздо меньше, чем n/4 ([2], п.4.5.4, упражнение 22). Отсюда следует, что при k-кратном повторении теста для различных оснований c1, …, ck сильное псевдопростое число будет распознано, как простое с вероятностью, меньшей чем 4–k. На практике в качестве оснований c вместо случайных чисел удобнее брать малые простые числа 2, 3, 5, 7, …, что значительно ускоряет возведение основания c в степень q.

Кроме того, на практике тест Рабина-Миллера ведёт себя гораздо лучше, поскольку реальная вероятность ошибки в большинстве случаев значительно ниже, чем это гарантирует теорема Рабина.

 

 

Вычисление первообразного корня в (ℤ/pℤ*,•)

Определить примитивный корень по модулю p, то есть число a, множество степеней которого , i=0,1, …, p – 2, совпадает с ℤ/pℤ*, можно следующим алгоритмом (см.[2], п.3.2.1.2, теорема C). Предполагается, что известно разложение на простые множители числа p – 1 – порядка мультипликативной группы ℤ/pℤ* (в нашем случае p – 1=2qn, поэтому достаточно разложить на простые множители число n): , где k–число различных простых делителей p – 1.

1.     Выбрать случайное целое a из интервала [0, p – 1] и положить .

2.     Вычислить  , где pi –простой делитель числа p – 1.

3.     Если t=1, то вернуться на шаг 1. Иначе положить . При i≤k вернуться на шаг 2. При i>k результат: a.

 

Генерация случайных чисел

Хороший обзор на эту тему желающие найдут в книге [2].

Для генерации случайных чисел при построении большого простого числа p и первообразного корня a в (ℤ/pℤ*,•) удобно использовать генератор линейных конгруэнтных последовательностей псевдослучайных чисел. По заданному начальному значению X0 элементы последовательности определяются из линейного рекуррентного соотношения:

 

.

 

Качество таких последовательностей зависит от выбора параметров a,b и m. Выбор в качестве m степени двойки обладает преимуществом с точки зрения вычисления на компьютере, придется обходиться без младших двоичных разрядов результатов, т.к. они характеризуются меньшей случайностью, чем старшие разряды.

Выбор чисел a и m влияет на периодичность последовательности: поскольку элементы последовательности могут принимать конечное число, а именно m, различных значений, последовательность начнёт повторяться самое позднее на (m+1)-м элементе, т.е. последовательность входит в цикл.

Существует критерий, позволяющий создавать псевдослучайные последовательности  с максимальной длинной цикла.

1.     НОД(b,m)=1.

2.     Если  t|m, то p|( a – 1) для любого простого числа t.

3.     Если 4|m , то 4|( a – 1).

Доказательство и дополнительные подробности [2], п. 3.2.1.2.

Напр., если a=6364136223846793005 и m=264  ([2], стр. 102–104), то линейная конгруэнтная последовательность будет иметь максимальную длину периода, равную m.

 

Генерация случайных ключей

Случайные последовательности, используемые в криптографических задачах, должны быть такими, чтобы без знания некоторой дополнительной (секретной) информации их невозможно было восстановить по нескольким заданным элементам. Нарушитель не должен иметь возможности воспроизвести криптографический ключ или последовательность ключей, полученных с помощью псевдослучайной последовательности. Поэтому  использовать линейный конгруэнтный генератор для нахождения ключей неприемлемо. Вместо него лучше использовать хорошо зарекомендовавший себя генератор Л.Блюм (L. Blum), М. Блюма (M. Blum) и М. Шуба (M. Shub)[3], далее генератор BBS, основанный на результатах теории сложности.

Пусть k и m –простые числа такие, что , их произведение – число n, число X–взаимно простое с n. Вычислив , получаем начальный элемент X0 последовательности чисел, получаемых рекуррентным возведением в квадрат:

.

В качестве случайного числа рассматриваем младший бит элемента Xi. Полученная таким образом случайная последовательность битов является безопасной с точки зрения криптографии: предсказать следующий бит по предыдущим можно только при условии, что известны делители k и m числа n. Если же эти два числа хранятся в секрете, то для предсказания последующих битов с вероятностью, большей ½, или для восстановления неизвестных отрезков последовательности нужно разложить на множители число n. В основе безопасности генератора BBS лежат те же принципы, что и в криптосистеме RSA. Генератор BBS работает медленно, т.к. для каждого бита приходится возводить в квадрат по модулю большого целого числа, однако при генерации ключей это не принципиально.

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

 

Возведение большого числа в степень по модулю

Требуется вычислить . Для решения этой задачи представим показатель e в системе исчисления по основанию , т.е. .

Найдём необходимую степень по следующему алгоритму:

1.     Вычислить и занести в таблицу предвычислений значения степеней c с нечетными показателями, не превосходящими основания : , , , …,.

2.     Если en–1 = 0 , то  положить.                                                                 Если en–1 ≠ 0 , то представить en–1 в виде , где u – нечётное; положить  (значение взять из таблицы).                             В обоих случаях положить .

3.     Если ei=0, то положить , путём t-кратного возведения s в квадрат по модулю p.                             Если ei ≠ 0 , то представить ei  в виде , где u–нечётное; положить , затем  и, наконец, .

4.     Положить ; при  вернуться на шаг3.

5.     Результат s.

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

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

Во избежание многократного нахождения представления  для одного и того же численного значения  на шаге 3, желательно заранее вычислить упомянутые представления всех  ().

Численное значение t определяется из соображений оптимальности. (Если вычисления, как у автора, производятся с  показателями длиной  2048 бит, то следует положить t=6.) 

Пример

В качестве исходного сообщения был взят следующий текст:

Прежде чем браться за взлом любой криптограммы,

полезно убедиться в том, что информация, которую

планируется получить, действительно стоит усилий,

затрачиваемых на её вскрытие.

Большие числа представляются в программе массивами элементов 16-битного беззнакового типа. Элемент с нулевым индексом содержит число 16- битных разрядов числа.

Построение простых чисел q и p в среднем занимает 55,487 секунды. Сперва было найдено число q. Его длина составила 2161 бит. Затем было найдено простое число p, где р-1=2qn, длиной в 2171 бит при n=634.

p=27  5018  1003  3841  8770  9469  8402  7791  3046  3367  3125  5432  8976  9808  0545         1115  2399  2957  6308  8945  8432  9860  1464  9913  7756  2268  5916  1292  3238  9008         6021  7850  0866  7208  2130  7499  7491  0846  8197  2914  2628  3173  3477  0918  0977         7729  6798  1857  8042  9300  7396  2805  2876  7836  5680  0078  1393  3732  1796  0324         7875  2036  8619  1065  5689  4145  6999  1132  4071  5703  9877  8295  7786  1995  3428         1815  1440  6671  4153  7107  8992  5606  2501  0799  1191  2981  3969  3587  3247  2389         1260  5574  0656  2499  2696  1174  1352  0538  3329  7713  5354  9320  9042  8394  0196         2469  3777  0029  3574  2394  8620  1622  8953  1839  0495  7394  9288  3632  8289  2633         4306  3028  9649  5356  4578  6104  3778  6046  7242  0435  0388  5823  6393  5598  5146         4500  5883  8317  7952  3499  1213  9720  5810  7824  5061  9408  2215  8006  1421  3108         7602  6099  0927  1234  4014  8901            1859  4708  7657  4077  4112  1504  5640  9589.

В результате вычислений, потребовавших 4,63 секунды, было получено значение a=2 первообразного корня в (ℤ/pℤ*,•). Далее, за 1,34 секунды был выбран секретный 2048-битный ключ x и вычислен открытый ключ y.   

      x=3122  1329  6169  8432  0515  0701  5949  3108  5771  1010  2499  7773  2714  1181  8703         6016  0111  9367  0835  7506  8765  4862  1438  8769  2031  0693  8342  7049  3214  9556         2596  1517  7953  1112  7712  6109  8017  6830  7847  7800  2627  6909  3817  6363  5390         6741  3395  5138  9005  0914  3053  8098  5146  0845  8354  4534  0719  6178  5659  8928         3914  0213  6806  0026  0245  1546  6355  5357  2645  5534  0582  8256  9347  7848  2772         1680  4552  8827  2329  9089  3265  3834  6853  1941  3021  3808  0513  2567  5281  0146         0744  9627  6797  8034  3867  6749  2818  9861  8231  3119  4349  1823  4524  2264  2471         5081  8631  5995  8624  9622  0921  9970  5118  4779  8453  4597  0944  4265  3963  2100         6730  8366  6629  9989  3703  2432  9027  5703  7671  0400  8606  5272  5078  8708  7645         6530  8574  6169  2039  8437  7228  0693  7590  9095  1926  3499  4243  1206  7195  7027         2200  1942  3779  3435

 

     y=11      9309  1182  1803  3159  8067  4670  1775  9543  8887  7335  0255  3388  0219  8456         5492  8177  0794  7563  4525  6232  8089  3337  3980  0560  9245  2575  2252  9742  6273         3661  1153  0273  6853  8760  8396  3835  2461  5037  7082  3840  4267  3213  4332  5476         8533  9734  9354  9127  8041  1134  4184  4395  4946  1245  1406  6299  2613  7550  5278         6958  4477  2635  4901  0531  9674  7561  5604  4828  7560  7245  8473  4774  0551  6993         1804  1901  1896  4186  4513  7939  8784  8635  0219  0478  0024  9284  6398  5124  2427         8245  8963  8775  0004  5902  2050  7273  0740  5931  8203  9027  0114  4249  5605  9231         5251  7115  7402  2512  2491  2396  6982  3766  3843  5040  8138  7740  2769  9543  6642         9486  0318  5997  1267  5633  5119  3101  2226  0958  3374  7707  6823  9448  4610  0488         8387  5870  1143  1004  9093  7775  1040  3860  4030  2310  6626  1965  8796  4815  1598         4236  4825  6808  7110  1497  4323  0294  7366  7503  8690  8702  7599  6366  2540.

Программа зашифровала исходный текст, предварительно разбитый на фрагменты по 2048 бит, за 2,76 секунды. Расшифровка сообщения потребовала 0,76 секунд. В результате расшифровки был получен текст, по форме и содержанию полностью совпадающий с исходным. С помощью программы может быть зашифрован файл любого типа.

Ожидается, что данная работа будет полезной всем интересующимся криптографией на первых шагах ее изучения.

 

Литература

1.     Вельшенбах М. Криптография на C и С++ в действии. Учебное пособие.- М.: Издательство Триумф, 2004.- 464 с.

2.     Кнут Д.Э. Искусство программирования. Получисленные алгоритмы. Т2.- М.: Издательство Вильямс, 2004.- 832 с.

3.     Молдовян Н.А., Молдовян А.А. Введение в криптосистемы с открытым ключом: Проблематика криптографии; элементы теории чисел; двухключевые криптосистемы и др.: Учебное пособие для вузов.- СПб.: Издательство БВХ–Петербург, 2005.- 288 с.

4.     Молдовян Н.А., Молдовян А.А., Еремеев М.А. Криптография. От примитивов к синтезу алгортимов.- СПб.: Издательство БХВ–Петербург, 2004.- 448 с.

5.     Петров А.А. Компьютерная безопасность. Компьютерные методы защиты. М.: Издательство ДМК, 2000.- 448 с.

6.     Ященко В.В.  Введение в криптографию. М.: МЦНМО, 2000.- 288 с.