Криптография с открытым ключом

 

Шифрование. Адресат A шифрует свой текст t и отправляет его адресату B. B дешифрует сообщение от A и получает исходный текст t. Адресат A должен выполнить следующее:

1. Получить открытый ключ (n,e) адресата B.
2. С помощью какого-либо метода M, который публикуется, представить своё письмо t как сообщение в виде натурального числа m из сегмента [0, n-1].
3. Вычислить шифротекст c = m^e (mod n).
4. Отправить свой шифротекст c адресату B.

 

Дешифрование. Чтобы извлечь текст t из шифротекста c, адресат B должен выполнить следующее:

1. Взять свой секретный ключ a и вычислить сообщение m = c^a (mod n).
2. Вычислить текст t адресата A с помощью метода M.

 

Пример.

Адресат A пишет письмо t = KAL адресату B.

Вычисление  ключей. Адресат B выполняет следующее:

1. Выбирает два разных простых числа p = 5783, q = 5647.
2. Вычисляет n = pq =32656601 и функцию Эйлера φ = (p - 1)(q - 1) = 32645172.
3. Выбирает случайное число e = 3051835 (1, φ) с нод(e, φ) = 1.
4. С помощью расширенного алгоритма Евклида находит такое a = 13331995 (1, φ), что ea ≡ 1 (mod φ).
5. Открытый ключ адресата B есть пара чисел (n = 32656601, e = 3051835). Секретный ключ адресата B есть число a =13331995  .

Шифрование. Адресат А выполняет следующее:

1. Получает открытый ключ (n = 32656601, e = 3051835) адресата B.
2. Представляет свой текст t = KAL в виде натурального числа m из [0, n-1] с помощью 27-ричной системы счисления следующим образом. Нумеруются буквы алфавита:

 

пробел	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

 

U	V	W	X	Y	Z
21	22	23	24	25	26

 

   Текст KAL представляется в виде числа m = 12 * 27² + 1 * 27 +12 = 8059

3. Шифрует своё сообщение m = 8059 числом c = m^e (mod n) = 8059^3051835 (mod 32656601) = 726893.
4. Посылает свой шифротекст c адресату B.

 

Дешифрование. Чтобы дешифровать шифротекст c от A, адресат B выполняет следующее:

1. Находит (с помощью своего секретного ключа a) число m = c^a (mod n) = 726893^13331995 (mod 32656601) = 8059.
2. Представляет число m в 27-ричной системе счисления: m = (11 1 12)₂₇ и получает исходный текст KAL.

 

Замечание. Криптографическая стойкость криптосистемы RSA основана на трудной практической осуществимости проблемы факторизации больших чисел. На практике для криптографической стойкости модуль n задаётся двоичным числом с 1024 и более двоичными разрядами.

Текст t в компьютере представляется бинарным массивом, который рассматривается как бинарная запись некоторого числа m. Предложенный выше способ представления текста числом носит иллюстративный характер и выбран из желания оперировать небольшими числами. 

Все вышеперечисленные  вычисления и рассуждения отражены в пункте 5.1, который представляет собой код соответствующей MathCAD – программы. 

2. Электронная цифровая подпись RSA с возвратом сообщения

Зашифровать и расшифровать сообщение с помощью  криптосистемы RSA (R. Rivest, A. Shamir, L. Adleman) с электронной подписью. Простые числа p и q взять из задачи 29. В качестве исходного текста взять три первых латинских буквы своей фамилии.

     p = 324733,   q = 27061,   t = KAL.

Алгоритм:

Вычисление  ключей. Каждый адресат создает открытый ключ и ему соответствующий секретный ключ. Адресат должен выполнить следующее.

     1. Выбрать два больших различных  случайных простых числа p и q примерно одного размера.

     2.  Найти n = p ∙ q и функцию Эйлера φ = φ(n) = (p − 1)(q − 1).

     3.  Взять случайное число  e, 1 < e < φ, такое, что нод(e, φ) = 1.

     4.  Найти такое целое a (1, φ), что ea ≡ 1 (mod φ). С помощью расширенного алгоритма Евклида найти то единственное целое a, 1 < d < φ, для которого ea ≡ 1 (mod φ).

     5. Открытый ключ адресата есть  пара чисел (n, e). Секретный ключ адресата есть число a. 

     Вычисление подписи. Адресат А подписывает свой текст t. Любой адресат B может проверить подпись A и извлечь из нее текст t. Адресат A должен выполнить следующее.

1. Каким – либо методом M (который публикуется) представить свой текст t в виде целого числа m, 1 < m < n – 1.
2. Найти число w = R(m) с помощью открытой функции

R : [0, n – 1] → M_R , где M_R есть некоторое числовое множество, например,

R(m) = m*m, где a*b есть результат приписывания слова b к слову a. Тогда M_R = {w = m*m: m [0, n – 1]}.

     3.  Найти число s = w ^a(mod n).

     4.  Отправить подписанный шифротекст s адресату В. 

     Проверка подписи и вычисление сообщения. Чтобы проверить подпись s адресата A и извлечь из нее сообщение m, адресат B должен выполнить следующее.

1. Получить открытый ключ (n, e) адресата A.
2. Найти число w = s ^e(mod n).
3. Проверить, что w M_R . Если нет, отвергнуть подпись s.
4. Найти число m = R^–1(w).
5. С помощью метода M найти отправленный текст t.

Решение:

   Адресат A подписывает свой текст t. Любой адресат B может проверить подпись A.

     Вычисление ключей. Адресат А выполняет следующее.

     1.  Выбирает разные простые  числа p = 324733,   q = 27061.

     2.  Находим n = p ∙ q = 324733 * 27061 = 8787599713 и функцию Эйлера

φ = φ(n) = (p − 1)(q − 1) = 324732 * 27060 = 8787247920.

     3.  Выбирает случайное число  e = 23, 1 < e < φ, с нод(e, φ) = 1.

     4. С помощью расширенного алгоритма  Евклида находит то единственное  целое a = 1910271287 (1, φ), которое удовлетворяет сравнению ea ≡ 1 (mod φ).

     5. Открытый ключ для А есть пара (n = 8787599713, e = 23). Секретный ключ для А есть число a = 1910271287.

     Вычисление подписи.  Адресат А подписывает свой текст t = KAL и выполняет следующее.

1. Представим свой текст t = KAL числом каким – либо методом M, например, в 27 – ричной системе счисления числом 

m = 11 * 27² +1 * 27 + 12 = 8058.

Нумеруются  буквы алфавита: 

пробел	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18

 

S	T	U	V	W	X	Y	Z
19	20	21	22	23	24	25	26

 

2. Вычисляет w = R(m) = R(8058) = 8058*8058 =80588058.

     3.  Вычисляет подпись

  s = w ^a(mod n) = 80588058^1910271287 (mod 8787599713) = 4604486656.

     4.  Отправляет подписанный шифротекст s адресату В. 

     Проверка подписи  и вычисление сообщения.  Адресат B получает от A подписанный шифротекст s и делает следующее.

1. Получить открытый ключ (n = 8787599713, e = 23) адресата A.
2. С помощью открытого ключа (n, e) адресата А вычисляет:

  w = s ^e(mod n) = 4604486656²³ (mod 13374982717) = 80588058.

3. Так как w =80588058=8058*8058 и M_R  , то B принимает

подпись А.

4. Вычисляет  m = R^–1(w) = 8058.
5. Представляет число  m = (8058)₁₀   в 27 – ричной системе счисления

m = (11 1 13)₂₇ и получает исходный текст t = KAL.

Все вышеперечисленные  вычисления и рассуждения отражены в пункте 5.2, который представляет собой код соответствующей MathCAD – программы.

3. Электронная цифровая подпись RSA с hash-функцией

Теоретическое введение:

Криптографическая хэш-функция h — это функция, определенная на битовых строках произвольной длины со значениями в строках  битов фиксированной длины. Ее значение часто называют хэш-кодом или  хэш-значением. В информатике тоже используются своего рода хэш-функции, но важное отличие криптографических хэш-функций от стандартных состоит в том, что первые должны быть односторонними. Другими словами, должно быть невозможно в вычислительном отношении по элементу Y из множества значений хэш-функции подобрать такой х из области определения, при котором h(x) = Y. Другая характеризация односторонних хэш-функций — сказать о них, что они защищены от восстановления прообразов. Применение криптографических хэш-функций позволяет создать схему подписи RSA без восстановления сообщения, что намного эффективней для длинных сообщений.

Задача  №24.6

       Зашифровать и расшифровать сообщение с помощью криптосистемы RSA (R. Rivest, A. Shamir, L. Adleman) хэш-функцией. Простые числа p и q взять из задачи 29. В качестве исходного текста взять три первых латинских буквы своей фамилии.