Теория чисел в криптографии (для школьников): Методические указания

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования «Оренбургский государственный университет» Кафедра прикладной математики

И.П. ВАСИЛЕГО

ТЕОРИЯ ЧИСЕЛ В КРИПТОГРАФИИ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Рекомендовано к изданию Редакционно-издательским советом государственного образовательного учреждения высшего профессионального образования «Оренбургский государственный университет»

Оренбург 2004

ББК 13 я 7 В 19 УДК 003.26 (07) Рецензент кандидат физико-математических наук, доцент кафедры прикладной математики ГОУ ОГУ Отрыванкина Т. М.

В 19

Василего И.П. Теория чисел в криптографии (для школьников): Методические указания. – Оренбург: ГОУ ОГУ, 2004. – 20 с.

Методические указания предназначены для школьников старших классов математических школ. Рассмотрены современные методы шифрования по открытому ключу и электронная подпись, а также прикладные аспекты основ теории чисел.

ББК 13 я 7

© И.П. Василего, 2004 © ГОУ ОГУ, 2004 2

Введение С давних пор и по наше время, люди скрывают секретные сообщения от других, преобразуя их в записи, лишённые всякого смысла и называемые шифровками. Метод преобразования сообщения в шифровку называют шифром. Процесс преобразования шифровки в сообщение называют расшифровкой. Ясно, что любой шифр должен содержать дополнительную информацию называемую ключом шифра, с помощью которого была бы возможна расшифровка. Наука о шифрах и методах их создания называется криптографией (или тайнописью). Возникновение криптографии теряется в глубине тысячелетий. Подробная история развития методов шифрования изложена в книге В.И. Нечаева: «Элементы криптографии. Основы защиты информации», Москва, Высшая школа, 1999г. Основой всякого шифра (системы шифрования) является правило (система правил) по которому каждая буква сообщения заменяется на букву, цифру или символ или какую-нибудь их комбинацию. В параграфе 1 данной работы приводятся некоторые сведения из теории чисел. Во втором параграфе показаны этапы усовершенствования шифра Юлия Цезаря: от простой замены буквы на букву до цифрового шифрования с помощью сравнений (раздела теории чисел). В параграфах 3, 4, 5, рассматриваются соответственно криптосистемы: без передачи ключей, с отрытым ключом и электронная подпись. Работа предназначена для школьников и студентов, интересующихся криптографией.

3

1 Некоторые сведения из теории чисел 1.1 Основные понятия Определение 1. Говорят, что а делится на b, если a = bq и q ∈ z . При этом а называют кратным числа b, а b- делителем числа а. Теорема 1 (о делении с остатком). Всякое целое а можно представить с помощью положительного целого числа b равенством вида a = bq + r , 0 ≤ r < b . Число q называется неполным частным, а число r-остатком от деления а на b. Определение 2. Всякое целое, делящее одновременно целые а, b называются их общим делителем. Определение 3. Наибольший из общих делителей чисел а и b называется общим наибольшим делителем и обозначается символом (a, b ) . Если (a, b ) =1, то целые а и b называют взаимно простыми. Теорема 2. Если a = bq + c , то (a, b ) = (b, c ) . Для отыскания (a, b ) при a > b применяется алгоритм Евклида, основанный на теореме 2. Алгоритм Евклида состоит в получении равенств вида: 0 < r1 < b a = bq 0 + r1

b = r1 q1 + r2

0 < r2 < r1

r = r2 q 2 + r3

0 < r3 < r2

................ rn − 2 = rn −1 q n −1 + rn

............... 0 < rn < rn −1

rn −1 = rn q n Тогда (a, b ) = rn - последнему не равному нулю остатку алгоритма Евклида. Пример. Найти с помощью алгоритма Евклида (2004, 1941) Решение. 2004 = 1941· 1 + 63 1941 = 63 · 30 + 51 53 = 51 · 1 + 12 51= 12 · 4 + 3 12 = 3 · 4 Итак (2004, 1941) = 3. Определение 4. Всякое целое, большее 1, имеющее только два положительных делителя, именно 1 и самого себя, называется простым. Заметим, что 1 не является простым числом. Среди первых 100 чисел простыми являются следующие 25 чисел: 2, 3, 5, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Теорема 3. Простых чисел бесконечно много. Теорема 4. Всякое целое, большее единицы, разлагается на произведение простых сомножителей и притом единственным способом. Обозначая буквами p1 , p 2 ,..., p k различные простые сомножители, а буквами α 1 , α 2 ,..., α k 4

кратности их вхождения в а, получим каноническое разложение числа а на соα множители: a = p1α1 ⋅ p 2α 2 ⋅ ..... ⋅ p k k . Определение 5. Функция ϕ(m ), определенная на множестве натуральных чисел называется функцией Эйлера, если значение ϕ(m ) равно числу натуральных чисел не превышающих m и взаимно простых с m , а ϕ(1) = 1 . Если m > 1 имеет разложение на простые множители вида  1  1   1  α  1 − ...1 − m = p1α1 ⋅ p 2α 2 ⋅ ..... ⋅ p k k , то ϕ(m ) = m1 − p p p  1  2   k  Пример. Вычислить ϕ(180 ) Решение. 180 = 22 · 32 · 5. Следовательно 1 2 4  1  1  1  ϕ(180 ) = 1801 − 1 − 1 −  = 180 ⋅ ⋅ ⋅ = 48 . 2  3  5  2 3 5  1.2 Разложение числа в конечную цепную дробь

Пусть a > 0, m > 0 и (a, m ) = 1 . Применяя к дроби имеем

a = mq 0 + a1 m = a1 q1 + a 2 a1 = a 2 q 2 + a 3

a алгоритм Евклида m

(1) (2 ) (3)

........................................ (k ) a k − 2 = a k −1 q k −1 + a k a k −1 = a k ⋅ q k + 0

(k + 1)

a a 1 = q0 + 1 = q0 + . m m m a m 1 = q1 + 2 = q1 + Из равенства (2) имеем a1 a1 a1 a2 Откуда a 1 = q0 + 1 m q1 + a1 a2

Из равенства (1) имеем

(*)

5

Из равенства (3) имеем

a a a1 1 = q2 + 3 = q2 + . Подставляя 1 в раa2 a2 a2 a2 a3

венство (*) имеем

a = q0 + m

1

q1 +

1

q2 +

a2 a3

Продолжая этот процесс для оставшихся равенств, получим

a = q0 + m

1 q1 +

1 q3 +

1 q4 +.

.

..

+

1

1 qk Правую часть этого равенства называют конечной цепной дробью и обозначаa ют ее [q 0 , q1 , q 2 ,..., q k ] . Итак, получили разложение числа в конечную цепm a ную дробь = [q 0 , q1 , q 2 ,..., q k ] . m 985 Пример. Разложить число в цепную дробь при помощи алгоритма 533 Евклида. 985 алгоритм Евклида получим: Решение. Применяя к числу 533 985 = 533 · 1 + 452 533 = 452 · 1 + 81 452 = 81 · 5 + 47 81 = 47 · 1 + 34 47 = 34 · 1 + 13 34 = 13 · 2 + 8 13 = 8 · 1 + 5 8=5·1 + 3 5=3·1 + 2 3=2·1 + 1 2=1·2 q k −1 +

6

Тогда

985 = [1,1,5,1,1,2,1,1,1,1,2]. 533 1.3 Подходящие дроби и их вычисление

Дроби вида δ 0 = q 0 , δ1 = q 0 +

1 , δ 2 = q0 + q1

1

,....

1 q1 + q2

называются

a . Подходящими m

подходящими дробями к цепной дроби [q 0 , q1 , q 2 ,..., q k ] = дробями к цепной дроби [1,1,5,1,1,2,1,1,1,1,2] являются 1 1 2 δ 0 = 1 = , δ1 = 1 + = , δ 2 = 1 + 1 1 1

δ10 = 1 +

1 1 1+ 5

, δ3 = 1 +

1

,.......,

1

1+

5+

1 1

1 1

1+

1

5+

1

1+

1

1+

1

2+

1

1+

1

1+ 1+

1

1 2 Вывод рекуррентной формулы вычисления подходящей дробей основан P на простой идее представления подходящей дроби δ k в виде k . Qk q P (q 0 = p 0 ; Q0 = 1) δ 0 = q0 = 0 = 0 1 Q0 1 q0 + q1 q1 q 0 + 1 q1 P0 + P−1 P 1 δ1 = q 0 + = = = = 1 (P−1 = 1, Q−1 = 0 ) q1 ⋅ 1 + 0 q1Q0 + Q−1 Q1 1 q1 1+

7

  1  1   q1 + q 0 + 1  q1 +  ⋅ P0 + P−1 q2  q 2  1   δ 2 = q0 + = = = 1     1 1 q1 + q +  ⋅ 1 + 0  q1 +  ⋅ Q0 + Q−1 q 2  1 q 2  q  2  q ⋅ P q + P0 + q 2 P−1 q (q P + P−1 ) + P0 q P + P0 P = 1 0 2 = 2 1 0 = 2 1 = 2 q1 ⋅ Q0 q 2 + Q0 + q 2 Q−1 q 2 (q1Q0 + Q−1 ) + Q0 q 2 Q1 + Q0 Q2 и так далее и вообще при n ≥ 0 имеем q n Pn −1 + Pn − 2 P = n , где P−1 = 1, Q−1 = 0 q n Qn −1 + Qn − 2 Qn q P + P− 2 q 0 + P− 2 При n = 0 имеем δ 0 = 0 −1 = , но δ 0 = q 0 , поэтому потребуем q 0 Q−1 + Q− 2 0 + Q− 2 еще: P− 2 = 0, Q− 2 = 1. Таким образом, при n ≥ 0 числители и знаменатели подходящих дробей к цепa ной дроби = [q 0 , q1 , q 2 ,..., q k ] вычисляются по формулам m δn =

Pn = q n Pn −1 + Pn − 2 при условии, что P− 2 = 0, P−1 = 1 Qn = q n Qn −1 + Qn − 2 при условии, что Q− 2 = 1, Q−1 = 0 Ради удобства, вычисления оформим в виде таблицы 1: Таблица 1 n qn Pn Qn

-2

-1

0 1

1 0

0 q0 P0 Q0

1 q1 P1 Q2

2 q2 P2 Q2

· · · ·

· · · ·

Из определения подходящей дроби, следует, что q k =

(a, m ) = 1 , то

Pk = a, Qk = m .

k-1 qk-1 Pk-1 Qk-1

k qk Pk Qk

Pk a = . Так как Qk m

Можно показать, что Pk ⋅ Qk −1 − Pk −1Qk = (− 1)k −1 . Умножая это равенство на

(− 1)k −1 получим: (− 1)k −1 ⋅ Pk

⋅ Qk −1 − Pk −1 ⋅ (− 1)k −1 ⋅ Qk = (− 1)2 k − 2 = 1 Учитывая, что Pk = a, Qk = m имеем

(− 1)k −1 ⋅ Qk −1 ⋅ a − m ⋅ (− 1)k −1 Pk −1 = 1 Пример. Найти подходящие дроби к цепной дроби 8

(*)

985 = [1,1,5,1,1,2,1,1,1,1,2]. 533 Решение. Вычисления {Pn } и {Qn } сведем в таблицу 2. Таблица 2 n qn Pn Qn

-2

-1

0 1

1 0

0 1 1 1

1 1 2 1

2 5 11 6

3 1 13 7

4 1 24 13

5 2 61 33

6 1 85 46

7 1 146 79

8 1 231 125

9 1 377 204

10 2 985 533

1.4 Сравнения и их свойства Определение 5. Если а и b – два целых числа и их разность a − b делится на целое положительное число m , то говорят, что а сравнимо с b по модулю m и при этом пишут a ≡ b(mod m ) . Исходя из определения, запись a ≡ b(mod m ) означает, что a − b = mk или a = b + mk , k ∈ z (**). в виде b = mq1 + r , 0 ≤ r < m , то Если представить «b » a = mq1 + r + mk = m(q1 + k ) + r . Таким образом, при делении чисел а и b на модуль m получаем один и тот же остаток r . Примеры. 1) 47 ≡ 11(mod 9 ) означает, что 47 = 11 + 9 ⋅ 4 2) − 11 ≡ 13(mod 8) означает, что - 11 = 13 + 8 ⋅ (- 3) 3) 63 ≡ 0(mod 21) означает, что 63 = 0 + 21 ⋅ 3 4) 19 ≡ 1(mod 2 ) означает, что 19 = 1 + 2 ⋅ 8 Основные свойства сравнений

1 Каждое целое число сравнимо с самим собой по любому модулю. 2 a ≡ b(mod m ) равносильно b ≡ a(mod m ) 3 Числа, сравнимые с одним и тем же числом, сравнимы между собой по данному модулю. 4 Сравнения по одному и тому же модулю можно почленно складывать, вычитать и перемножать. Следствия из 4-го свойства: 4.1 к частям (из частей) сравнения можно прибавлять (вычитать) одно и то же число. 4.2 части сравнения можно умножать на одно и то же число. 4.3 Части сравнения можно возводить в одну и ту же натуральную степень. 4.4 к любой (из любой) части сравнения можно прибавлять (вычитать) число, кратное модулю. 5 Части сравнения можно делить на их общий делитель, взаимно простой с модулем. 9

6 Части сравнения и модуль, можно делить (умножать) на одно и то же число. 1.5 Решение сравнений первой степени

Ограничимся решением сравнения вида: ax ≡ 1(mod m ) при (a, m ) = 1 . Приведем два способа решения этого уравнения. По определению сравнения имеем ax − 1 = my, x, y ∈ z , или ax − my = 1, x, y ∈ z . В пункте 1.3 было рассмотрено равенство (*):

( a ((− 1) a ((− 1)

) ( ) − 1 = m((− 1) ) ≡ 1(mod m)

)

a (− 1)k −1 Qk −1 − m (− 1)k −1 ⋅ Pk −1 = 1 ⇔ k −1

Qk −1

k −1

Qk −1

k −1

)

⋅ Pk −1 = 1 или

Таким образом x ≡ (− 1)k −1 ⋅ Qk −1 (mod m ) Пример 1. Решите уравнение 985 ⋅ x ≡ 1(mod 533) . Решение. Из рассмотренного ране примера (смотри таблицу № 2) следует, что k = 10, Qk −1 = Q9 = 204 и поэтому решением уравнения является

x ≡ (− 1)9 ⋅ 204(mod 533) или x ≡ −204(mod 533) или x + 204 = 533 ⋅ t , t ∈ z . При t = 0, x = −204 . Проверим это решение 985 ⋅ (− 204 ) = −200940 = 533(− 377 ) + 1 ≡ ≡ 1(mod 533) . Пример 2. Решите уравнение 1201x ≡ 1(mod 57106 ) .

Решение. Решение имеет вид x ≡ (− 1)k −1 ⋅ Qk −1 (mod 57106 ) . Для нахождения Qk −1 к числу 1201/57106 применим алгоритм Евклида: 1201 = 57106 · 0 + 1201 57106 = 1201 · 47 +659 1201 = 659 · 1 +542 659 = 542 · 1 +117 542 = 117 · 4 + 74 117 = 74 · 1 + 43 74 = 43 · 1 +31 43 = 43 · 1 + 12 31 = 12 · 2 + 7 12 = 7 · 1 + 5 7=5·1+2 5 = 2 · 2 +1 2=1·2+0 Получим цепную дробь [0,47,1,1,4,1,1,1,2,1,1,2,2] из которой следует, что k = 12 . Вычисление Qk −1 = Q11 проведем с помощью таблицы 3.

10

Таблица 3 - - 0 1 2 3 4 5 6 7 8 9 10 11 12 2 1 0 47 1 1 4 1 1 1 2 1 1 2 2 1 0 1 47 48 95 428 523 951 1474 3899 5373 9272 23917 57106

n qn Qn

Отсюда Q11 = 23917 и x ≡ (− 1)11 ⋅ 23917(mod 57106 ) ≡ −23917(mod 57106 ) Второй способ решения сравнения ax ≡ 1(mod m ) связан с теоремой Эйлера: если m > 1 и (a, m ) = 1 , то a ϕ (m ) ≡ 1(mod m ) . Запишем последнее сравнение в виде a ⋅ a ϕ( m ) −1 ≡ 1(mod m ) . Отсюда при m>1 и (a,m)=1 следует, что x ≡ a ϕ( m) −1 (mod m) является решением сравнения ax ≡ 1(mod m ) . Пример 3. Решить уравнение 9 x ≡ 1(mod 34 ). Решение. m=34>1, a=9, (a,m)=1. Учитывая, что т=21·171 найдем значение 1  1  функции Эйлера ϕ(34) = 341 − 1 −  = 16 . Тогда решение сравнения имеет 2  17   вид: х ≡ 915 (mod 34 ) или х ≡ 9 8 ⋅ 9 4 ⋅ 9 2 ⋅ 9(mod 34 ) . Так как 9 ≡ −25(mod 34 ) , то по свойству 4.3 имеем

(

)

9 2 ≡ 625(mod 34 ) или 9 2 ≡ 13(mod 34 ) 9 4 ≡ 169(mod 34 ) или 9 4 ≡ (−1)(mod 34 )

9 8 ≡ 1(mod 34 ) . Таким образом x ≡ 19(mod 34 ) .

x ≡ 1(− 1) ⋅ 13(− 25)(mod 34 ),

x ≡ 325(mod 34 )

или

11

2 Переход от шифра с простой заменой к цифровому шифрованию с помощью сравнений В I в.н.э. Юлий Цезарь во время войны с галлами при передаче сообщений друзьям в Рим шифровал их с помощью правила заданного таблицей 4. Таблица 4 Буква сообщения Буква шифровки

A B C D E F G H I

K L M N O U K L M N O P Q R X

D E F G H I J

J

P V S Y

Q W T Z

R X U A

S Y V B

T Z W C

Это правило каждую букву латинского алфавита заменяет на третью, следующую за ней по порядку букву, а последние три буквы Х, Y, Z заменяет соответственно буквами A, B, C. Сообщение Цезаря Сенату о победе над понтийским царем, без учета знаков препинания: «Veni vidi vici» с помощью этого правила преобразуется в шифровку: «YHQL YLGL YLFL». Очевидно, ключом шифра является правило заданное таблицей 5. Таблица 5 Буква шифровки Буква сообщения

A B C D E F G H I J

K L M N O P V X Y Z A B C D E F G H I J K L M S

R W O T

S X P U

T Y Q V

Усовершенствуем шифр Юлия Цезаря, для этого выполним последовательно: 1) заменим каждую букву латинского алфавита её порядковым номером а алфавите. 2) порядковый номер от 1 до 23 увеличим на 3, а номера 24, 25, 26 уменьшим на 23. Тогда эти два правила шифра можно задать таблицей 6. Таблица 6 Буква A B CD E F G H I сообщения

J

Порядковый номер

1 2

3 4

5 6 7

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Цифра шифровки

4 5

6 7

8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 1 2 3

12

8

9

K L M N O P R S T U V W X Y Z

U Z R W

Теперь сообщение Цезаря «veni vidi vici» с помощью усовершенствованного цифра Цезаря преобразуется в шифровках «25 8 17 12 25 12 7 12 25 12 6 12». Ключом усовершенствованного шифра Цезаря является правило заданное таблицей 7. Таблица 7 Цифра шифровки

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Буква со- X Y Z A B C D E F G H I J K L M N O P Q общения R S T U V W Если сообщить всем знающим латинский язык первое правило этого шифра, то каждый из них сможет записать свой сообщение в виде последовательности натуральных чисел от 1 до 26. Шифровка таких сообщений будет получена с помощью правила 2 заданного таблицей 8. Таблица 8 Цифра сообщения

1 2 3 4 5 6 7

8

9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Цифра шифровки

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 1 2 3

Расшифровка будет проводиться с помощью правила, заданного таблицей 8. Но таблица 8 задает функцию q областям определения и значений которой являются натуральные числа от 1 до 26. k + 3, при k = 1,23 Зададим эту функцию аналитически q (k ) =  k − 23, при k ∈ {24,25,26} Таким образом, правило 2 шифра Цезаря, задается функцией q(k) для любого натурального k от 1 до 26. Тогда ключ этого шифра можно задать функцией q (k ) − 3, q (k ) ∈ {4,5,6,...,26} k = q (k ) + 23, q (k ) ∈ {1,2,3} Представим функцию q(k) в виде q (k ) = (k + 3) − 26t для k = 1,23; t = 0 , для k = 24,25,26; t = 1 но это означает, что q (k ) ≡ k + 3(mod 26 ) . Таким образом, число k из сообщения, заменяется числом q(k) сравнимым с числом k+3 по модулю 26. 13

Для расшифровки воспользуемся сравнением: k ≡ q (k ) − 3(mod 26 ), 1 ≤ q (k ) ≤ 26 . Обобщением усовершенствованного шифра Цезаря является шифр q~ определяемый сравнением: q~ (k ) ≡ (a (k ) + f (k ) )(mod 26 ), 1 ≤ q~ (k ) ≤ 26 где {a (k )} - определенной длины цифровые сообщения; { f (k )} - случайная последовательность из множества натуральных чисел от 1 до 26, той же длины, что и передаваемые сообщения. Последовательность { f (k )} называют ключом шифра q~ (k ) . Пример. Зашифруем сообщение 22 5 14 9 22 9 4 9 22 9 3 9 Цезаря о победе взяв в качестве ключа случайную последовательность такой же длины { f (k )}={6 5 19 20 9 14 1 12 5 14 20 5}. Решение. {a k } = {22 5 14 9 22 9 4 9 22 9 3 9}. Из определения сравнения имеем q~ (k ) = (a (k ) + f (k ) ) − 26t , t ∈ z . Тогда q~(1) = (22 + 6) − 26 ⋅ 1 = 2 q~(5) = (22 + 9) − 26 = 5 q~(9)=(22 + 5) − 26=1 q~(2) = (5 + 5) − 26 ⋅ 0 = 10 q~(6) = (9 + 14) − 26 ⋅ 0=23 q~(10)=(9 + 14) −26 ⋅ 0=23 q~(3) = (14 + 19) − 26 ⋅ 1 = 7 q~(4) = (9 + 20) − 26 ⋅ 1 = 3

q~(7) = (4 + 1) − 26 ⋅ 0 = 5 q~(11)=(3 + 20)−26 ⋅ 0=23 q~(8) = (9 + 12) − 26 ⋅ 0 = 21 q~(12)=(9 + 5) −26 ⋅ 0=14

Отсюда шифровка имеет вид: {q~(k )} = {2 10 7 3 5 23 5 21 1 23 23 14}. Для расшифровки воспользуемся сравнением a(k ) ≡ ( g~ (k ) − f (k ))(mod 26 ), 1 ≤ a(k ) ≤ 26 На практике чаще всего шифровка m1 сообщения m с ключом α находится с помощью сравнения m1 ≡ m α (mod r ), 0 ≤ m1 < r причем сообщение m разбивается на куски длины r.

14

3 Шифровка открытым ключом Этот способ шифровки в наше время получил наибольшее распространение. Алгоритм выполнения его таков: 1) получатель сообщений А генерирует отрытый ключ (пару чисел rA и α ). Для этого: а) получатель А выбирает два больших простых числа p1 , p 2 ; б) находит первое число открытого ключа rA = p1 ⋅ p 2 ; в) находит значение функции Эйлера  1  1   = ( p1 − 1)( p 2 − 1) ; 1 − ϕ(rA ) = p1 p 2 1 − p p  1  2  г) находит случайно второе число α открытого ключа, удовлетворяющее условиям: 0 < α < ϕ(rA ) и (α, ϕ(rA )) = 1 (числа α и ϕ(rA ) взаимно простые) 2) Получатель сообщений А находит секретный ключ а, как решение сравнения первой степени a ≡ α −1 (mod ϕ(rA )) или aα ≡ 1(mod ϕ(rA )), 0 < α < rA . 3) Получатель А сообщает открытый ключ (rA , α ) всем желающим отправить ему сообщение. 4) Отправитель В разбивает сообщение на куски (слова) mi длиной менее log 2 rA разрядов и шифрует их с помощью сравнений C i ≡ (mi )α (mod rA ) и отправляет получателю А. 5) А расшифровывает сообщение с помощью секретного ключа а: Pi ≡ (C i )a (mod rA ) Пример. Пусть получатель сообщения А подобрал два простых числа p1 = 7 и p 2 = 23 . Тогда rA = p1 ⋅ p 2 = 7 ⋅ 23 = 161, ϕ(rA ) = ϕ(161) = (7 − 1)(23 − 1) = 6 ⋅ 22 = 132 . Случайное число α = 7 удовлетворяет условиям 0 < 7 < 132 и (7,132 ) = 1. Теперь получатель сообщения А находит секретный ключ а решая, сравнение a ⋅ 7 ≡ 1(mod 132 ), 0 < a < 132 . Тогда

a ≡ (− 1)k −1 Qk −1 (mod m ) = (− 1)k −1 Qk −1 (mod 132 ) ,

где Qk −1 - знаменатель предпоследней подходящей дроби разложения

7 в 132

цепную дробь. Применяя алгоритм Евклида имеем: 7=132 · 0 +7 132 = 7 · 18 + 6 7 = 6 · 1 +1 15

6=1·6+0 Получим цепную дробь Qk −1 = Q3−1 = Q2 . Таблица 9 n qn Qn

7 = [0,18,1,6] . С помощью таблицы 9 находим 132

-2

-1

1

0

0 0 1

1 18 18

2 1 19

3 6 132

Итак, Q2 = 19 и следовательно а ≡ (− 1)2 ⋅ 19(mod 132 ) или а ≡ 19(mod 132 ) . Так как 0 <19< 132, то а = 19 - секретный ключ получателя А. Получатель А сообщает открытый ключ (132, 7). Отправитель В шифрует секретное сообщение m1 = 3 < 132 с помощью сравнения c1 ≡ 3 7 (mod 161), 0 < c1 < 161 или c1 ≡ 2187(mod 161) . Так как 2187 = 161 ⋅ 1 + 94 , то c1 = 94 . Отправитель В посылает шифровку получателю сообщений А. Получатель А расшифровывает это сообщение своим секретным ключом a = 19 с помощью сравнения m 2 ≡ 9419 (mod 161), 0 < m 2 < 161 . Найдем m 2 . 9419 ≡ 9416 ⋅ 94 2 ⋅ 94 Так как 94 ≡ −67(mod 161)

94 2 ≡ 142(mod 161)

94 4 ≡ 39(mod 161)

94 8 ≡ 72(mod 161)

9416 ≡ 32(mod 161) ,

то 9419 ≡ 32 ⋅ 142(− 67 ) . Учитывая, что 32 ⋅ 142 ≡ 36 , то

9419 ≡ 36 ⋅ (− 67 )(mod 161) или 9419 ≡ −157(mod 161) . Таким образом m 2 ≡ −157(mod 161) или m 2 ≡ 3(mod 161), m 2 = 3 , т.е. получатель А получил секретное сообщение m1 = 3 . Шифр с открытым ключом можно использовать для организации многосторонней секретной связи между участниками А1 , А2 ,..., Аn . Для этого каждый участник Ai генерирует свой открытый (ri , α i ) и секретный a i ключи, а затем сообщает всем партнерам свой открытый ключ или печатают телефонную книгу, имеющую вид: A1 : r1 , α 1

A2 : r2 , α 2 ............... An : rn , α n 16

Пусть участник A1 решает послать сообщение m участнику A2 и пусть 0 < m < r2 иначе сообщение делят на слова длины r2 . A1 шифрует m открытым ключом участника A2 который есть в телефонной книге, и находит m1 ≡ m α 2 (mod r2 ), 0 < m1 < r2 A2 расшифровывает сообщение своим секретным ключом: m 2 ≡ m1 (mod r2 ), 0 < m 2 < r2 и получает m 2 = m .

17

4 Электронная подпись Предложенная выше система организации многосторонней секретной связи неудобна тем, что получатель сообщения не знает, кто является отправителем сообщения. Рассмотрим систему «электронная подпись», лишенную этого недостатка. Пусть A1 собирается послать сообщение m партнеру A2 и замечая, что r1 < r2 он шифрует сообщение m сначала своим секретным ключом: m1 ≡ m a1 (mod r1 ), 0 < m1 < r1 ,

а

потом

открытым

ключом A2 :

m 2 ≡ m1 α 2 (mod r2 ), 0 < m 2 < r2 . Партнер A2 получив шифрованную телеграмму m 2 и замечая, что r1 < r2 , расшифровывает ее, пользуясь сначала своим секретным ключом a 2 : m3 ≡ m 2 a2 (mod r2 ), 0 < m3 < r2 , а потом открытым ключом A1 : m 4 ≡ m3 α1 (mod r1 ), 0 < m 4 < r1

и получает m 4 = m . Таким образом, лицо A2 получает сообщение от лица A1 . Докажем этот факт. Так как m3 ≡ m 2 a2 (mod r2 ) и m 2 ≡ m1α 2 (mod r2 ) , то m3 ≡ m1 a2α 2 (mod r2 ) , где a 2 α 2 ≡ 1(mod ϕ(r2 )) . Если (m1 , r2 ) = 1, то по теореме Эйлера m1 a2α 2 ≡ m1 (mod r2 ) , то есть m3 ≡ m1 (mod r2 ) . Но 0 < m3 < r2 , 0 < m1 < r1 < r2

следовательно

m3 ≡ m1 .

Имеем

m 4 ≡ m3 α1 ≡ m1α1 = m α1a1 (mod r1 ),

где

α 1 a1 ≡ 1(mod ϕ(r1 )) . Если (m, r1 ) = 1, то m α1a1 (mod r1 ) ≡ m(mod r1 ). Так как 0 < m 4 < r1 и 0 < m < r1 , то m 4 = m . Если же A1 собирается послать сообщение m партнеру A2 и при этом r1 > r2 , то он шифрует сообщение m сначала открытым ключом A2 , а потом

своим секретным ключом a1 : m1 ≡ m α 2 (mod r2 ), 0 < m1 < r 2 ,

m 2 ≡ m1 α1 (mod r1 ), 0 < m1 < r 1 . Партнер A2 получив шифрованную телеграмму m 2 и замечая, что r1 > r2 , расшифровывает ее, пользуясь сначала открытым ключом партнера A1 ,

а потом своим секретным ключом: m3 ≡ m 2 α1 (mod r1 ), 0 < m3 < r 1

m 4 ≡ m3 α 2 (mod r2 ), 0 < m 4 < r 2 и получает m 4 = m . Итак, лицо A2 получает сообщение от лица A1 . 18

Пример. Пусть банкир В и вкладчик W договорились опубликовать телефонную книгу. Для этого банкир В выбрал простые числа 7 и 13, а вкладчик W выбрал простые числа 11 и 23. Тогда rB = 7 ⋅ 13 = 91 , а rW = 11 ⋅ 23 = 253 ; ϕ(rB ) = 6 ⋅ 12 = 72 , ϕ(rW ) = 10 ⋅ 22 = 220 . Так как 0< 5 < 72 и (5; 72) = 1, 0 < 31 < 220 и (31;220 ) = 1, то α B = 5, α W = 31. Итак, 91, 5 – открытые ключи банкира, а 220, 31 – открытые ключи вкладчика. Решая сравнение 5 ⋅ a B ≡ 1(mod 72 ) и 31 ⋅ aW ≡ 1(mod 220 ) найдем, что a B = 29, aW = 71 . Действительно, 5 ⋅ 29 − 1 = 144 = 72 ⋅ 2 , 31 ⋅ 71 − 1 = 2200 = 220 ⋅ 10 . Итак, 29 и 71 секретные ключи соответственно банкира и вкладчика. Теперь открытая телефонная книга имеет вид: B : rB = 91, α B = 5; W : rW = 253, α W = 31; Вкладчик W посылает сообщение m = 41 банкиру B и замечая, что rB < rW , шифрует его сначала открытым ключом 5 банкира, а потом своим секретным ключом 71: m1 ≡ m 5 ≡ 415 ≡ 6(mod 91);

m 2 ≡ 6 71 ≡ 94(mod 253). Банкир, получив шифровку m 2 = 94 и замечая, что rB < rW , расшифровывает ее, пользуясь сначала открытым ключом вкладчика, а потом своим секретным ключом: m3 ≡ 94 31 ≡ 6(mod 253), m 4 ≡ 6 29 ≡ 41(mod 91) . Так как 41 < 91, то банкир делает вывод, что 41 и есть сообщение этого вкладчика. В заключении заметим, что при практическом применении шифров с открытым ключом в качестве простых чисел p1 и p 2 используют числа содержащие 125 и более цифр в десятичной записи. В результате вскрыть этот шифр оказывается невозможно, потому что произведение p1 ⋅ p 2 содержало бы более 250 цифр в десятичной записи, а обратная задача разложения этого числа на простые множители p1 и p 2 потребовало бы сотен лет работы самого лучшего компьютера.

19

Список использованных источников 1 Болл У., Коксетер Г. Математические эссе и развлечения. – М.: Мир, 1986. 2 Виленкин Н.Я. Математика и шифры //Квант. – 1977. - № 8. 150 с. 3 Виноградов И.М. Основы теории чисел. – М: Наука, 1981. – 176 с. 4 Кнут Д. Искусство программирования для ЭВМ. – Т.2 – М.: Мир, 1977. – 724 с. 5 Кострикин А.И. Введение в алгебру. М.: Наука, 1994. – 496 с. 6 Нечаев В.И. Элементы криптографии. Основы защиты информации. – М.: Высш.шк. 1999. – 109 с. 7 Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2001. – 304 с. 8 Кудреватов Г.А. Сборник задач по теории чисел. – М.: Просвещение, 1970. – 128 с.

20