Оценка вычислительной сложности

Ключи какой длины следует использовать?

Для практической реализации алгоритмов RSA, Эль Гамаля, Диффи-Хеллмана полезно знать оценки трудоемкости разложения простых чисел различной длины, сделанные Шроппелем.

lo g _{10 n}	Число операций	Примечания
	1.4*10¹⁰	Раскрываем на суперкомпьютерах
	2.3*10¹⁵	На пределе современных технологий
	1.2*10²³	За пределами современных технологий
	2.7*10³⁴	Требует существенных изменений в технологии
	1.3*10⁵¹	Не раскрываем

В конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. Для этого с помощью сети Интернет было задействовано 1600 компьютеров.

В конце 1999 года за 8 недель был разложен на множители ключ длиной 768 бит. Для разложения использовалась компьютеры локальной сети Массачусетского Технологического университета. Руководитель проекта заявил, что теперь, используя ИНТЕРНЕТ, возможно такой ключ разложить на множители в среднем за неделю.

Сами авторы RSA рекомендуют использовать следующие размеры модуля n:

· 1024 бит - для частных лиц;

· 2048 бит - для коммерческой информации;

· 4096 бит - для особо секретной информации.[3]

Третий немаловажный аспект реализации RSA - вычислительный. Ведь приходится использовать аппарат длинной арифметики. Если используется ключ длиной k бит, то для операций по открытому ключу требуется О(k²) операций, по закрытому ключу - О(k³) операций, а для генерации новых ключей требуется О(k⁴) операций.

Пример расчёта по алгоритму 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 в кольце вычетов R₂₈₈

E=1/D(mod M) => DE=G(mod M) = 241´E = 1(mod 288)

Решение Диафантова ур-ия 1-го порядка: E = (-1)⁽ⁿ^-1)´G´P₍_n_-1)(mod M)

Поиск n: Ведётся по следующему алгоритму:

1. n=1, Z₁=M, X₁=D

2. n=n+1, h_n=Z_n div X_n, Y_n=Z_n mod X_n

3. Z_(n+1) = X_n, X_(n+1) = Yn

4. Если Y_n¹0 переход на 2

5. Конец

n	Z	X	Y = Z mod X	H = Z div X	P_i=H_i´P_i-1+P_i-2(mod M) _




					49 – P₄ искомый результат
			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

B¹=143

B²=143²(mod 323) = 100

B⁴=143⁴(mod 323) = 100²(mod 323) = 310

B⁸=143⁸(mod 323) = 310²(mod 323) = 169

B¹⁶=143¹⁶(mod 323) = 169²(mod 323) = 137

B³²=143³²(mod 323) = 137²(mod 323) = 35

B⁶⁴=143⁶⁴(mod 323) = 35²(mod 323) = 256

B¹²⁸=143¹²⁸(mod 323) = 256²(mod 323) = 290

Шифрование: С=B^D(mod N) = 143²⁴¹(mod 323) = 143¹²⁸´143⁶⁴´143³²´143¹⁶´143(mod 323) = 290´256´35´137´143(mod 323) = 262

Расшифровка: B = C^E(mod N) = 262⁴⁹(mod 323) = 143

Исследование работы двухключевых алгоритмов шифрования на примере криптосистемы Эль-Гамаля

Цель работы

Изучить основные принципы шифрования с открытым ключом. Освоить алгоритм Эль-Гамаля. Изучить математические принципы на которых основан этот алгоритм.

Домашнее задание

Изучить алгоритм шифрования Эль Гамаля в соответствии с пунктом 3.6 данного методического руководства.

Записать вариант, соответствующий четырём младшим цифрам номера студенческого билета в виде (n₄n₃n₂n₁).

По таблице простых чисел (?) выбрать простое число. Номер числа P = 55+n₁.

Вычислить случайное число W=(n₂+1)´10;

Вычислить случайный секретный ключ X=(n₃+1)´9

Вычислить случайное число K=(n₄+1)´11;

Выполнить шифрование

Выполнить расшифровывание

Все вычисления должны быть занесены в протокол в виде?

Таблица 3.1 Шифрование по алгоритму Эль Гамаля

Наименование величины	Домашнее задание	Лабораторное задание
Простое число P
Случайное число W<P-1
Секретный ключ X<P-1
Открытый ключ Y=W^X(mod P)
Исходное сообщение M
Случайное число K<P-1
Шифрование: R=Y^K(mod P) Z=W^K(mod P) C=M xor R
Расшифровывание: R=Z^X(mod P) M=C xor R