Оценка вычислительной сложности
Ключи какой длины следует использовать?
Для практической реализации алгоритмов RSA, Эль Гамаля, Диффи-Хеллмана полезно знать оценки трудоемкости разложения простых чисел различной длины, сделанные Шроппелем.
| log10 n | Число операций | Примечания |
| 1.4*1010 | Раскрываем на суперкомпьютерах | |
| 2.3*1015 | На пределе современных технологий | |
| 1.2*1023 | За пределами современных технологий | |
| 2.7*1034 | Требует существенных изменений в технологии | |
| 1.3*1051 | Не раскрываем |
В конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. Для этого с помощью сети Интернет было задействовано 1600 компьютеров.
В конце 1999 года за 8 недель был разложен на множители ключ длиной 768 бит. Для разложения использовалась компьютеры локальной сети Массачусетского Технологического университета. Руководитель проекта заявил, что теперь, используя ИНТЕРНЕТ, возможно такой ключ разложить на множители в среднем за неделю.
Сами авторы RSA рекомендуют использовать следующие размеры модуля n:
· 1024 бит - для частных лиц;
· 2048 бит - для коммерческой информации;
· 4096 бит - для особо секретной информации.[3]
Третий немаловажный аспект реализации RSA - вычислительный. Ведь приходится использовать аппарат длинной арифметики. Если используется ключ длиной k бит, то для операций по открытому ключу требуется О(k2) операций, по закрытому ключу - О(k3) операций, а для генерации новых ключей требуется О(k4) операций.
Пример расчёта по алгоритму RSA
P=17, Q=19
N=PQ=17´19=323
M=j(N)=(P-1)´(Q-1)=16´18=288
Проверка НОД(D,M) = 1 по алгоритму Евклида.
D=241.
Расчёт E обратного D в кольце вычетов R288
E=1/D(mod M) => DE=G(mod M) = 241´E = 1(mod 288)
Решение Диафантова ур-ия 1-го порядка: E = (-1)(n-1)´G´P(n-1)(mod M)
Поиск n: Ведётся по следующему алгоритму:
1. n=1, Z1=M, X1=D
2. n=n+1, hn=Zn div Xn, Yn=Zn mod Xn
3. Z(n+1) = Xn, X(n+1) = Yn
4. Если Yn¹0 переход на 2
5. Конец
| n | Z | X | Y = Z mod X | H = Z div X | Pi=Hi´Pi-1+Pi-2(mod M) _ | ||||
| 49 – P4 искомый результат | |||||||||
| 0 – Конец |
DIV – делить на цело
E = (-1)(5-1) ´ 49 (mod 288)= 49[4]
Откр. Ключ (D=241, N=323)
Секр. Ключ (E=49, N=323)
Сообщение В=143
D = 241 = 128+64+32+16+1
B1=143
B2=1432(mod 323) = 100
B4=1434(mod 323) = 1002(mod 323) = 310
B8=1438(mod 323) = 3102(mod 323) = 169
B16=14316(mod 323) = 1692(mod 323) = 137
B32=14332(mod 323) = 1372(mod 323) = 35
B64=14364(mod 323) = 352(mod 323) = 256
B128=143128(mod 323) = 2562(mod 323) = 290
Шифрование: С=BD(mod N) = 143241(mod 323) = 143128´14364´14332´14316´143(mod 323) = 290´256´35´137´143(mod 323) = 262
Расшифровка: B = CE(mod N) = 26249(mod 323) = 143
Исследование работы двухключевых алгоритмов шифрования на примере криптосистемы Эль-Гамаля
Цель работы
Изучить основные принципы шифрования с открытым ключом. Освоить алгоритм Эль-Гамаля. Изучить математические принципы на которых основан этот алгоритм.