Шпаргалка: Шпаргалки по криптографии

на 2 проблемах: проблеме разложения большого числа на простые множители и

проблеме дискретного логарифмирования. Собственно, для шифрования используется

алгоритм RSA (Rivest-Shamir-Adleman), разработанный в 1977 году математиками

Роном Райвестом (R. Rivest), Ади Шамиром (A. Shamir) и Леонардом Аделманом

(L. Adleman). Используется не только для шифрования, но и для формирования ЭЦП.

Схема примерно такая:

Абонент А, желающий вступить в переписку, ЗАРАHЕЕ:

- вырабатывает различные простые числа p, q, примерно равной разрядности,

и вычисляет n=p*q;

- генерирует случайное числе e < n и вычисляет d, такое что

e*d == 1(mod ф(n)); (ф(n) - функция Эйлера)

- рассылает открытый ключ (e,n);

- сохраняет в тайне секретный ключ (p, q, d).

Абонент B, желающий ЗАШИФРОВАТЬ сообщение для абонента А, выполняет следующие

действия:

- открытый текст разбивается на блоки, каждый из которых представляется как

число m, 0 <= m <= (n-1), и преобразуется в блок c, 0 <= c <= (n-1),

шифрованного текста с = E(n,e,m) = m^e (mod n).

Для РАСШИФРОВАHИЯ абонент А выполняет следующие действия:

- вычисляет m' = E(n,d,c) = c^d (mod n).

A2:

Если приводить к фундаментальным математическим

проблемам, то все существующие алгоритмы с открытым ключём стремятся

построить таким образом что бы они были похожи на полиномиальные для

владельца секретного ключа и на NP-полные проблемы для всех остальных.

В [1.2, pp. 461-482] приведено

9 таких систем (ну, скажем, популярные ныне элипические кривые это просто

смена конечного поля, ещё парочку можно свести к другим, но 6 принципиально

разных алгоритмов имеется).