«О простых числах в информационной безопасности»

МБОУ «СОШ №143» г. Красноярска

Метапредметный проект «Криптография: алгоритм RSA»

Над проектом работали:, Князькина Татьяна Викторовна, учитель математики высшей категории  

 «О простых числах в информационной безопасности»

(выступление на конференции Научного общества учащихся)

2012-2013 учебный год

ВВЕДЕНИЕ        

1.        ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ КРИПТОГРАФИИ        

1.1.        Симметричные криптосистемы        

1.2.        Асимметричные криптосистемы        

2.  ТЕОРИЯ ЧИСЕЛ        

2.1. Основная теорема арифметики        

2.2. Алгоритм Евклида  нахождение НОД для целых чисел.        

2.3. Расширенный алгоритм Евклида        

2.4. Функция Эйлера        

2.5. Методы поиска простых чисел        

2.5.1. Решето Эратосфена        

2.5.2. Скатерть Улама        

2.5.3. Простые числа Мерсена        

2.5.4. Простые числа Ферма        

3. Алгоритм RSA        

3.1. Алгоритм создания открытого и секретного ключей RSA        

3.2. Шифрование и дешифрование: cхема RSA        

3.3. Примеры шифрования по схеме RSA.        

3.4. Криптоанализ RSA        

ЗАКЛЮЧЕНИЕ        

СПИСОК ЛИТЕРАТУРЫ        

ВВЕДЕНИЕ

        Защита информации или информационная безопасность была, есть и останется очень важной проблемой человеческого общества, поэтому для успешного решения данной проблемы необходимо опираться на опыт предков и использовать результаты их труда как фундамент для дальнейшего развития науки – криптологии.

        Криптология (kryptos - тайный, logos - наука) - наука, изучающая математические методы защиты информации путем ее преобразования [1]. Криптология разделяется на два направления - криптографию и криптоанализ. Цели этих направлений прямо противоположны. Криптография занимается поиском и исследованием математических методов преобразования информации. Сфера интересов криптоанализа - исследование возможности расшифровывания информации без знания ключей.

        Место криптографии сегодня везде, где используются электронные средства коммуникаций. Криптография становится обычным делом, и с расширением областей ее применения (цифровая подпись, подтверждение подлинности и целостности электронных документов, безопасность электронного бизнеса, защита информации, передаваемой через интернет, и др.) будет возрастать и ее роль. Всем нам потребуется познакомиться с криптографией, и в будущем она станет «третьей грамотностью» наравне со «второй грамотностью» — владением компьютером и информационными технологиями.

        Данная работа обобщает исследования, которые велись в 5 - 7 классах: «Криптография», «Алгоритм RSA».

        Целью проекта  является изучение математических методов, которые используются в криптосистемах. В рамках этой цели можно выделить следующие задачи проекта:

1. Ознакомиться с основными понятиями криптографии. Изучение основных принципов симметрических криптосистем. Изучение основных принципов асимметрических криптосистем.
2. Ознакомиться с методами теории чисел: простые числа и их свойства, алгоритмы нахождения простых чисел, расширенный алгоритм Евклида, функция Эйлера и ее свойства.
3. Реализация алгоритма RSA на примерах шифрование и дешифрование  различных сообщений по алгоритму RSA.
4. Обучить школьников шифрованию по схеме RSA.

1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ КРИПТОГРАФИИ

        Шифрование – это основное действие в криптографии. У процесса шифрования две стороны. Первая представляет собой процедуру маскировки исходного сообщения, или обычного текста. Правомочному получателю сообщения должна быть известна обратная процедура перевода шифровки в исходное сообщение.

        Шифрование - преобразовательный процесс: исходный текст, который носит также название открытого текста, заменяется шифрованным текстом (называемый также криптограммой) (Рис.1):.

Открытый текст

Криптограмма

Рис.1: Процесс шифрования: берем открытый текст и шифруем его при помощи криптосистемы, которая состоит из алгоритма и ключа шифра, затем отправляем полученную криптограмму получателю.

        Криптографическая система представляет собой набор преобразований открытого текста. Самые важные составляющие любого шифра – это:

1. общее правило, по которому преобразуется  исходный тест (алгоритм шифра);
2. конкретная особенность именно этой серии  шифрованных сообщений (так называемый ключ, т.е. информация, необходимая для шифрования и дешифрования текстов).

        Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный (рис. 2).

Исходныйтекст

Криптограмма

Рис.2: Процесс дешифрования: полученную криптограмму расшифровываем при помощи криптосистемы и получаем исходный текст.

        Криптография дает возможность преобразовать информацию таким образом, что ее прочтение (восстановление) возможно только при знании ключа.

        Существуют несколько способов, в соответствии с которыми могут классифицироваться криптографические системы. Например, существует такая классификация:

1.  криптосистемы с секретным ключом (симметричные);
2.  криптосистемы с открытым ключом (асимметричные).

        Рассмотрим их  подробнее.

1. Симметричные криптосистемы

        Криптографическая система называется криптосистемой с секретным ключом, если в ней любые две стороны, перед тем, как связаться друг с другом, должны заранее договориться между собой об использовании в дальнейшем некоторой секретной части информации, которая и называется секретным ключом. Особенностью симметричной криптосистемы является использование одного ключа, как для шифрования, так и для дешифрования (Рис.3).

Рис.3: Симметричные криптосистемы.

        Такой механизм секретного распределения ключей мог эффективно работать в прошлом, то есть в ситуации, когда криптография использовалась небольшим числом пользователей. В настоящее время, когда криптография стала общедоступной, было бы неразумно организовывать такую сеть, в которой каждой паре пользователей заранее предоставлялся бы их совместный секретный ключ, потому что тогда число таких ключей возрастало бы лавинообразно с увеличением числа пользователей.

        Итак, шифр можно считать симметричным, если для криптографического преобразования данных (после которого они теряют смысл для противника) применяются одни и те же преобразования, зависящие от одного и того же ключа. Все симметричные системы шифрования можно характеризовать по способам преобразований, выполняемых с открытым текстом. Рассмотрим два преобразования.

1. Первое преобразование приводит к тому, что все буквы исходного текста сохраняются, но меняется порядок их следования друг за другом.
2. При втором преобразовании все буквы исходного сообщения  заменяются на какие-то другие символы (каждая буква заменяется одним символом), но порядок их следования в тексте полностью сохраняется.

Шифры первого типа получили название шифров перестановки, а второго типа – шифров замены. Подавляющее большинство исторических шифров либо относится к одному из этих типов, либо основано на их сочетании  (Рис.4).

Рис.4: Примеры симметричных криптосистем.

1. Асимметричные криптосистемы

        Проблема передачи ключа шифрования была решена в 1976 году, когда Уитфилд Диффи и Мартин Хеллман опубликовали статью «Новые пути криптографии», которая произвела в шифровальном сообществе настоящий бум.  Диффи и Хеллман в своей работе предложили  понятие криптографии с открытым ключом. Сходное понятие было независимо открыто Ральфом Мерклем.

        Основное наблюдение, которое, собственно, и привело к криптографии с открытым ключом, заключалось в следующем – тот, кто зашифровывает сообщение, не обязательно должен быть способен его расшифровывать. Асимметричные криптосистемы - это криптосистемы, у которых ключ шифрования не совпадает с ключом дешифровки. Один из ключей доступен всем (так делается специально) и называется открытым ключом, другой (секретный ключ) хранится только у его хозяина и неизвестен никому другому. С помощью одного ключа можно производить операции только в одну сторону. Если сообщение зашифровано с помощью одного ключа, то расшифровать его можно только с помощью другого. Имея один из ключей невозможно (очень сложно) найти другой ключ (Рис.5).

Рис.5: Асимметричные криптосистемы.

Рассмотрим  опять переписку Алисы и Боба. Общая схема шифрования с открытым ключом  выглядит следующим образом:

1. Боб создает пару ключей: один для шифрования (открытый), другой для дешифрования (секретный).
2. Боб публикует свой ключ шифрования, размещает его в открытом для всех доступе. Второй ключ, соответствующий открытому, сохраняется в секрете.
3. Если Алиса  собирается послать сообщение пользователю Бобу, она шифрует сообщение открытым ключом Боба.
4. Когда Боб получает сообщение, он дешифрует его с помощью своего личного (секретного) ключа. Другой получатель не сможет дешифровать сообщение, поскольку личный ключ Боба знает только Боб.

        Первой и наиболее известной криптографической системой с открытым ключом была предложенная в 1978 году так называемая система RSA. Ее название происходит от первых букв фамилий авторов Рональд Райвест (Ronald Linn Rivest), Ади Шамир (Adi Shamir), и Леонард Адлеман (Leonard Adleman), которые придумали ее во время совместных исследований в Массачусетском технологическом институте в 1977 году.         

        Для того чтобы работать с RSA мной были изучены следующие понятия из теории чисел: деление целых чисел с остатком, простые числа, решето Эратосфена, скатерть Улама, простые числа Мерсена, простые числа Ферма, взаимно-простые числа, наибольший общий делитель (НОД), алгоритм Евклида для нахождения НОД, расширенный алгоритм Евклида, соотношение Безу, функция Эйлера и ее свойства, основная теорема арифметики.

2.  ТЕОРИЯ ЧИСЕЛ

        Теория чисел - раздел математики, изучающий целые числа и их свойства. Теорию чисел многие ученые  называют «царицей математики». И действительно, вряд ли в какой-нибудь другой части математики встретится такое количество столь простых и изящных по формулировке, и столь трудных для решения задач. Мало какая область математики может похвастаться столь древней и славной историей. Сегодняшняя же теория чисел, называемая зачастую математиками попросту «арифметикой», вдобавок, еще и очень сложна по своим методам, почерпнутым из почти всех прочих математических наук.

        Рассмотрим понятия теории чисел, которые нам понадобятся.

        Определение.  Целые числа  - это множество {..., −3, −2, −1, 0, 1, 2 , 3,...}, которое будем обозначать Z.

        Определение.   Пусть a, b – целые числа. Целое число а делится на целое число b, если найдется такое целое число q, что а = qb.

        Деление с остатком. Всем с начальной школы знакома формула a:b=q (остаток r).

В теории чисел существует следующая теорема.

        Теорема деления. Для данного целого числа b, не равного нулю, всякое целое число,  а   единственным образом представимо в виде а = bq + r,  где  0 ≤ r <|b|, где число а  - делимое, число  b - делитель, число q называется неполным частным, число r – остатком от деления а на b.

        Следует заметить, что остаток – всегда есть число неотрицательное, а вот неполное частное может быть каким угодно целым числом.

        Определение.  Целое число d, делящее одновременно целые числа а, b, c, ... , k, называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем (НОД).

        Определение.  Натуральное число p, большее единицы, называется простым, если оно делится нацело только на 1 и на себя.

        Определение.  Целые числа a и b, называются взаимно простыми, если они не имеют никаких общих делителей, кроме 1, т.е НОД(a,b)=1.

        Составные числа – это натуральные числа, которые помимо единицы и самого себя имеют и другие натуральные делители.  Простые и составные числа очень важны в курсе математики. В этой теме немаловажное место занимает Основная теорема арифметики.

2.1. Основная теорема арифметики

        Основная теорема утверждает, что любое натуральное число, отличное от 1, может быть представлено в виде произведения простых чисел. Два разложения натурального числа на простые множители могут отличаться друг от друга лишь порядком сомножителей.         

        Основная теорема арифметики.  Каждое натуральное число n > 1 представляется в виде n=p1…pk, где p1…pk  — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.

         Впервые в таком виде она сформулирована Гауссом в § 16 его «Арифметических исследований», что не мешало, однако, его предшественникам неявно использовать ее. Как пишут Харди (Hardy) и Райт (Wright) в своей книге по теории чисел, «Гаусс первым превратил арифметику в систематическую науку».

        Доказательство основной теоремы арифметики опирается на так называемую лемму Евклида: если простое число p делит без остатка произведение двух целых чисел x · y, то p делит x или y.  Основная теорема арифметики позволяет легко и быстро находить наибольший общий делитель и наименьшее общее кратное двух чисел.

2.2. Алгоритм Евклида  нахождение НОД для целых чисел.

        Рассмотрим следующую задачу: даны два целых неотрицательных числа а и b. Требуется найти их наибольший общий делитель, т.е. наибольшее число, которое является делителем одновременно и a, и b.

        Эту задачу уже более 2000 лет решают с помощью алгоритма Евклида. Данный алгоритм был впервые описан в книге Евклида "Начала" (около 300 г. до н.э.).  Алгоритм Эвклида действует следующим образом. Разделим a на b с остатком; назовем этот остаток r1. Если r1 0, то разделим b на r1 остатком; пусть r2 — остаток второго деления. Аналогично, если r2 0, то разделим r1 на r2  и получим новый остаток r3 и т.д. Будем повторять до тех пор, пока мы  не получим нулевого остатка; наименьший ненулевой остаток является наибольшим общим делителем чисел a и b. Сформулируем алгоритм более строго.        

        Пусть a и b — целые числа, не равные одновременно нулю, и последовательность чисел a, b, r1> r2> r3>… >rn определена тем, что каждое rk — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

a = bq1 + r1    b = r1q2 + r2    r1 = r2q3 + r3   …  rk  = rk+1qk+2 + rk+2  …

 rn-2=qnrn-1+rn  rn−1 = rnqn

Тогда НОД(a,b), наибольший общий делитель a и b, равен rn, последнему ненулевому члену этой последовательности НОД(a,b)=rn .

        Пример 1. Вычислить НОД(1840, 135) с помощью алгоритма Евклида.

Все вычисления представлены в таблице 1. НОД(1840,135)=5

Таб. 1: Вычисление НОД(1840, 135) с помощью алгоритма Евклида.

2.3. Расширенный алгоритм Евклида

        У алгоритма Эвклида есть еще один вариант. Достоинство нового варианта в том, что наибольший общий делитель — лишь часть  выходных данных. Пусть a и b — натуральные числа, а r — их  наибольший общий делитель. Расширенный алгоритм Эвклида подсчитывает не только r, но и два целых числа c и d таких,  что r =d *a+c*b. Отметим, что если d оказывается положительным, то c — отрицательное, и наоборот.  Лучше всего вычислять эти числа, добавив некоторые инструкции в обычный алгоритм Эвклида так, чтобы r, c и d подсчитывались одновременно. Именно поэтому новая процедура называется расширенным алгоритмом Эвклида.

        Формулы для остатков ri из алгоритма Евклида могут быть переписаны следующим образом:

r1=a -bq1  r2=b - r1q2 =b-q2 (a –bq1) =b(1+ q1q2)-aq2  … rn =d *a+c*b .

Тогда НОД(a,b)=rn =d *a+c*b, где d и с – целые числа.

        Это представление наибольшего общего делителя называется соотношением Безу или линейным представлением НОД, а числа d и c — коэффициентами Безу.

Пример 2. Выписать соотношение Безу для чисел 1840 и 135 с помощью расширенного алгоритма Евклида.  Воспользуемся таблицей 1.

НОД(1840,135)=5=35-15*2=5-2*(50-35)=35-2*50+2*35=3*35-2*50=3*(85-50)-2*50=3*85-        

-3*50-2*50=3*85-5*50=3*85-5*(135-85)=3*85-5*135+5*85=8*85-5*135=8*(1840-13*135)-5*135=8*1840-13*8*135-5*135=8*1840-109*135=8*a+(-109)*b

Соотношение Безу или линейное представление НОД для данного примера

НОД(a,b)=rn =d *a+c*b=8*a+(-109)*b.

2.4. Функция Эйлера

        Мне также понадобится функция, которая была названа в честь великого математика Леонарда Эйлера, который впервые использовал ее в своих работах по теории чисел.

        Функция Эйлера (m), где m — натуральное число, равна количеству натуральных чисел, не больших m и взаимно простых с ним.

Пример 3.  Пусть  m=15. Выпишем все натуральные числа меньшие либо равные 15 и выделим жирным шрифтом взаимно простые с 15: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.         Нетрудно посчитать, что  (15)=8.

Выпишем некоторые свойства функции Эйлера.

1. Если число m  простое, (m)=m-1.
2. Если числа p и q  взаимно просты, то (pq)=(p) (q).

        Например, 15 можно представить как произведение взаимно простых чисел 3 и 5, тогда по свойству 2  (15)= (5*3)= (5)*(3). Так как 3 и 5 простые числа, то воспользуемся свойством 1 и получим (15)= (5*3)= (5)* (3)=(5-1)(3-1)=4*2=8.

        Таким образом, из свойств 1 и 2 вытекает свойство 3, которые мы будем использовать в алгоритме RSA:

1. Если числа p и q просты, то (pq)=(p-1) (q-1).

2.5. Методы поиска простых чисел

        Всякий, кто изучает простые числа, бывает очарован и одновременно ощущает собственное бессилие. Определение простых чисел так просто и очевидно; найти очередное простое число так легко; разложение на простые сомножители – такое естественное действие. Почему же простые числа столь упорно сопротивляются нашим попыткам постичь порядок и закономерности их расположения? Может быть, в них вообще нет порядка, или же мы так слепы, что не видим его?

                                    Ч. Узерелл «Этюды для программистов».

        Ни одному другому разделу теории чисел не свойственно столько загадочности и изящества, как разделу, занимающемуся изучением простых чисел — непокорных упрямцев, упорно не желающих делиться ни на какое целое число, кроме единицы и самих себя. В теории чисел  много проблем, формулировка которых достаточна проста, но решение не поддавалось или не поддаётся до сих пор многим поколениям математиков. Значительная часть таких проблем связана с распределением простых чисел в натуральном ряду. Некоторые задачи, относящиеся к теории распределения простых чисел, формулируются настолько просто, что понять их может и ребенок. Тем не менее они настолько глубоки и далеки от своего решения, что многие математики считают их вообще неразрешимыми.

        В разные периоды человеческой истории многие выдающиеся математические умы напрягались в поиске ответа на простой вопрос: как часто встречаются простые числа в натуральном ряду? Конкретнее: сколько существует простых чисел, меньших заданного натурального числа n ? Вопрос, казалось бы, простой и понятный, но точного ответа на него до сих пор не знает никто. Развитие математической мысли показало, что задача точного вычисления функции (n) -  количества простых чисел, не превосходящих n, является чрезвычайно трудной. Но разгадка тайн природы является благородным и увлекательным занятием, поэтому изучение с разных сторон функции (n) продолжается во всем математическом мире.

         Большие заслуги в области изучения простых чисел принадлежат русским  математикам.

1. П.Л. Чебышев (1821-1894) доказал, что между любым натуральным числом, вдвое большим данного (например, 2 и 4, 3 и 6, 10 и 20 и т.д.) всегда имеется хотя бы одно простое число.
2.  И.М. Виноградов(1891-1983) установил, что любое достаточно большое нечетное число можно представить в виде суммы трех простых чисел, например:

                          7 =  2 + 2 + 3,  9 = 3 + 3 + 3,  15  = 3 + 5 + 7 = 5 + 5 + 5 .

        Сама проблема получения простых чисел занимает ключевое место в математике, на ней основаны некоторые криптографические алгоритмы, например RSA.

2.5.1. Решето Эратосфена

        Очевидно, что любое простое число, не равное 2, является нечетным. Существуют признаки делимости целых чисел на различные простые числа, например, чтобы число делилось на 3 и 9 достаточно, чтобы сумма его цифр делилась на 3 и 9 соответственно. Чтобы число делилось на 5, достаточно, что его последняя цифра была 0 или 5.

        Такие частные признаки делимости можно использовать, если нужно уменьшить множество кандидатов проверки на простоту или отсечь заведомо составные числа. Альтернативным способом получения простых чисел является решето Эратосфена, приписываемое древнегреческому ученому Эратосфену Киренскому, жившему примерно в 276 - 194 г. до н.э. Так как во времена Эратосфена писали на восковых табличках и не вычеркивали, а "выкалывали" цифры, то табличка после описанного процесса напоминала решето. Поэтому метод Эратосфена для нахождения простых чисел получил название "решето Эратосфена".

Рис. 6. Решето Эратосфена

        Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому.

Алгоритм Эратосфена для нахождения всех простых чисел не больше заданного числа n.

1. Выписать подряд все целые числа от 2 до n:  2, 3, 4, …, n.
2. Пусть переменная p изначально равна двум — первому простому числу: p=2.
3. Вычеркнуть из списка все числа от 2p до n, делящиеся на p, то есть, числа 2p, 3p и т.д.
4. Найти первое не вычеркнутое число, большее чем p, и присвоить значению переменной p это число.
5. Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n 
6. Все не вычеркнутые числа в списке — простые числа.

         Таким образом, для нахождения множества простых до заранее выбранной верхней границы n  мы сначала вычеркиваем все четные числа кроме 2, затем выписываем последовательность всех нечетных чисел от 3 до n. Затем выбираем первое число в списке, т.е. тройку, и оставляя его в списке, вычеркиваем все кратные 3, начиная с 6. Потом переходим ко второму числу списка (пятерке) и вычеркиваем его кратные, оставив саму пятерку и т.д., пока не дойдем до конца списка. В оставшемся списке будут только простые числа.

        Мартин Гарднер [7] предложил следующую «конструкцию» решета Эратосфена. Выпишем все целые числа от 1 до 100 в виде прямоугольной таблицы, изображенной на рис. 6.  Вычеркнем все числа, кратные 2, за исключением самой двойки, проведя вертикальные черты во втором, четвертом и шестом столбцах. Вычеркнем все числа, кратные 3 (сама тройка остается), проведя вертикальную черту в третьем столбце. Следующее за 3 невычеркнутое число равно 5. Чтобы вычеркнуть числа, кратные 5, проведем диагонали, идущие вниз и влево. Оставшиеся в таблице  числа, кратные 7, вычеркнем, проведя диагонали с наклоном вправо и вниз. Числа 8, 9 и 10 — составные, их кратные уже были вычеркнуты раньше. Наша работа по составлению списка простых чисел, не превосходящих числа 100, на этом заканчивается. Итак, все числа, кроме 26, не закрашенных, просеялись сквозь решето. Осталось лишь 26 простых чисел. Математики предпочитают говорить, что осталось лишь 25  первых простых чисел, поскольку многие важные теоремы формируются проще, если 1 не считать простым числом.

        Решето Эратосфена работает как своего рода вычислительная машина. И, значит, вот что изобрел великий грек: он изобрел счетную машину. Простые числа располагаются на числовом ряду весьма причудливым образом, но, создав Решето Эратосфена достаточно большого размера, мы отсеем (построим) их ВСЕ без исключения. Все они окажутся в дырках совершенно правильного геометрически Решета!

        2.5.2. Скатерть Улама

        В зависимости от расположения целых чисел простые числа могут образовывать тот или иной узор. Однажды математику Станиславу М. Уламу пришлось присутствовать на одном очень длинном и очень скучном, по его словам, докладе. Чтобы как-то развлечься, он начертил на листке бумаги вертикальные и горизонтальные линии и хотел было заняться составлением шахматных этюдов, но потом передумал и начал нумеровать пересечения, поставив в центре 1 и двигаясь по спирали против часовой стрелки. Без всякой задней мысли он обводил все простые числа кружками. Вскоре, к его удивлению, кружки с поразительным упорством стали выстраиваться вдоль прямых. На рисунке показано, как выглядела спираль. Это заинтересовало Улама, и позже он вместе с Майроном Л. Стейном и Марком Б. Уэллсом продолжил это исследование на ЭВМ MANIAC Лос-Аламосской лаборатории, использовав магнитную ленту, на которой были записаны 90 млн простых чисел. Скатерть Улама представляет из себя спираль чисел натурального ряда, на которой отмечены клетки, соответствующие простым числам.

2.5.3. Простые числа Мерсена

        Числа Мерсенна - это числа, преставимые в виде 2n-1. Особый интерес представляют простые числа Мерсена, которые получаются при n=2, 3, 5, 7, 13, 17, 19, 41, 47, 61, 89, 107, 127, ... Эта последовательность начинается так:

3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607, 536870911, 2147483647

Наибольшим известным простым числом по состоянию на февраль 2011 года является 243112609 − 1. Оно содержит 12 978 189 десятичных цифр и является простым числом Мерсенна (M43112609). Его нашли 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS. Это же число является наибольшим среди всех известных простых чисел. На сегодняшний день неизвестно: конечно ли число простых чисел Мерсена.

2.5.4. Простые числа Ферма

        Числа вида  впервые начал изучать Пьер Ферма, поэтому эти числа называются числами Ферма. Он высказал гипотезу, что все эти числа являются простыми, но не смог ни доказать, ни опровергнуть это утверждение. Первые 5 чисел Ферма действительно являются простыми: F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537.

        Гипотеза Ферма о простоте чисел Fn была отвергнута в 1732 г. другим выдающимся математиком Леонардом Эйлером (1707-1783) , который нашел разложение шестого числа Ферма:

+ 1 = 4 294967 297 = 641 6 700 417

3. Алгоритм RSA

3.1. Алгоритм создания открытого и секретного ключей RSA

1. Выберем два простых числа p и q.
2. Вычисляется их произведение m= pq, которое называется модулем.
3. Вычисляется значение функции Эйлера от числа m:  (m)=(p-1)(q-1)
4. Выбирается целое число e (1(m)), взаимно простое со значением функции (m).  
5. Ищется линейное представление НОД (e, (m)) =1=de+c(m) и вычисляется число d. (Обычно, оно вычисляется при помощи расширенного алгоритма Евклида. ).

Пара (e,m) публикуется в качестве открытого ключа RSA.

Пара (d,m) играет роль секретного ключа RSA и держится в секрете. Делители p и q можно либо уничтожить либо сохранить вместе с секретным ключом.

3.2. Шифрование и дешифрование: cхема RSA

        В схеме RSA сообщением являются целые числа лежащие от  0 до m-1. Опишем процесс шифрования. Исходный текст должен быть переведен в числовую форму, этот метод считается известным. В результате этого текст представляется в виде одного большого числа. Затем полученное число разбивается на части (блоки) так, чтобы каждая из них была числом в промежутке от  0 до m-1. Процесс шифрования одинаков для каждого блока. Поэтому мы можем считать, что блок исходного текста представлен числом a.

Алгоритм шифрования

1. Взять открытый ключ (e,m) . 
2. Взять открытый текст  0  a m-1
3. Получить криптограмму b: b=aemod m
4. Передать шифрованное сообщение b.

Алгоритм дешифрования

1. Принять зашифрованное сообщение b. 
2. Применить свой секретный ключ (d,m) для расшифровки сообщения:  a=bd mod m. 

3.3. Примеры шифрования по схеме RSA.

Пример 1.

1. Выбираем два простых числа p=17 и q=5.
2. Вычислим их произведение m= pq=17*5=85.
3. Вычислим значение функции Эйлера:  (85)=(p-1)(q-1)=16*4=64

1. Выбирается целое число e=5, взаимно простое с (m)=64.  

Пара (e,m)=(5,85) - открытый ключ RSA.

1. Найдем линейное представление НОД(e, (m)) при помощи расширенного алгоритма Евклида.  

Найдем НОД: 64=5*12+4 5=4*1+1 4=1*4+0НОД(5,64)=1

        Найдем соотношение Безу: 1=5-4*1=5-(64-5*12)=5*13-64*1.

Отсюда НОД (5, 64) =1=d*5+c*64 = 13*5+(-1)*64 и d = 13.

Пара (d,m)=(13,85) – секретный ключ RSA

Алгоритм шифрования

1. Возьмем  открытый ключ (e,m)=(5,85) . 
2. Возьмем открытый текст  a=7.
3. Получить криптограмму b: b=ae mod m=75 mod 85=16807 mod 85=62 
4. Передать шифрованное сообщение b=62.

Алгоритм дешифрования

1. Принять зашифрованное сообщение b=62. 
2. Применить свой секретный ключ (d,m)=(13,85) для расшифровки сообщения:

a=bd mod m=6213 mod 85=200028539268669788905472 mod 85=7

Пример 2.  Зашифруем фразу «Математика – царица наук».

        Для простоты предположим, что текст сообщения содержит только слова, записанные заглавными буквами. Таким образом, сообщение, в конечном счете, — последовательность  букв и пробелов. Первый шаг состоит в замене каждой буквы сообщения числом, которое выбирается из квадрата Полибия.

Таблица 2. Квадрат Полибия с русским алфавитом.

Квадрат Полибия^[1], изобретенный во  II веке до н.э., не вышел из  употребления до сих пор. Устроен он так: все (или почти все) буквы алфавита располагаются в квадрате или в прямоугольнике соответствующего размера, для русского 5*6. после этого каждая буква кодируется двумя числами – номером строки и номером столбца, в которых она расположена. Конечно буквы можно (и даже нужно!) располагать не по порядку, тогда шифр становиться гораздо сложнее. В таблице 2 приведен квадрат Полибия с русским алфавитом. Тогда  шифруемая фраза будет: 31114116311141232511274511352345111732114225.

        Теперь зашифруем это число по схеме RSA. Для уменьшения вычислений выпишем все буквы фразы без повторений:

Используя открытый ключ (5,85)  из примера 1 зашифруем все числа из второй строки таблицы:

315 mod 85 = 28629151 mod 85 = 46

115 mod 85 = 161051 mod 85 = 61

415 mod 85 = 115856201 mod 85 = 11

165 mod 85 = 1048576 mod 85 = 16

235 mod 85 = 6436343 mod 85 = 58

255 mod 85 = 9765625 mod 85 = 60

455 mod 85 = 184528125 mod 85 = 10

355 mod 85 = 52521875 mod 85 = 35

325 mod 85 = 33554432 mod 85 = 2

425 mod 85 = 130691232 mod 85 = 77

275 mod 85 = 14348907 mod 85 = 57

175 mod 85 = 1419857 mod 85 = 17

В результате получим следующую таблицу.

Теперь можно записать полученную криптограмму:

46611116466111586061571061355810611702617760

Для расшифровки данную криптограмму надо разбить на блоки из двухзначных чисел и применить секретный ключ RSA (13, 85) :

4613 mod 85 = 15441948546310791168 mod 85 = 31

6113 mod 85 = 161915287432152755657581 mod 85 = 11

1113 mod 85 = 34522712143931 mod 85 = 41

1613 mod 85 = 4503599627370496 mod 85 = 16

5813 mod 85 = 84055070416556869132288 mod 85 = 23

6013 mod 85 = 130606940160000000000000 mod 85 = 25

1013 mod 85 = 10000000000000 mod 85 = 45

3513 mod 85 = 118272717781982421875 mod 85 = 35

213   mod 85 = 8192 mod 85 = 32

7713 mod 85 = 3344871416191195940889917 mod 85 = 42

5713 mod 85 = 67046038752496061076057 mod 85 = 27

1713 mod 85 = 9904578032905937 mod 85 = 17

Получим исходное сообщение в виде числа: 31114116311141232511274511352345111732114225,

разбив которое на двузначные числа, можно восстановить исходный текст по квадрату Полибия.

Пример 3. Зашифруем фразу  Дэвида Кана^[2]: «… История криптографии…- это история человечества». Для простоты предположим, что текст сообщения содержит только слова, записанные заглавными буквами. Таким образом, сообщение, в конечном счете, — последовательность букв и пробелов. Первый шаг состоит в замене каждой буквы сообщения числом, которое выбирается из таблицы 3.

Таблица 3. Кодирование букв алфавита двузначными числами.

        Проделав эту процедуру, мы получим число, возможно очень большое,  если сообщение было длинным. В нашем случае мы получим число:

4218272824261841442026182528241326103018184243392824441826282426184144331521241215331527281210.

        Теперь нам нужно разбить численное представление сообщения на кусочки, каждый из которых —  натуральное число, не превосходящее m.

        Создадим секретный и открытый ключ RSA:

1. Выбираем два простых числа p=3  и  q=23.
2. Вычислим их произведение m= pq=3*23=69.
3. Вычислим значение функции Эйлера:   (85)=(p-1)(q-1)=22*2=44
4. Выбирается целое число e=7, взаимно простое с (m)=44.  

Пара (e,m)=(7,69) - открытый ключ RSA.

1. Найдем линейное представление НОД(e, (m)) при помощи расширенного алгоритма Евклида.   Найдем НОД: 44=7*6+2 7=2*3+1 2=1*2+0 НОД(7,44)=1

        Найдем соотношение Безу: 1=7-2*3=7-(44-7*6)*3=7-44*3+7*6*3=19*7+(-3)*44

        Отсюда  НОД (7, 44) =1=d*7+c*44 = 19*7+(-3)*44 и d = 19.

Пара (d,m)=(19,69) – секретный ключ RSA.

187 mod 69 =612220032 mod 69 = 6

277 mod 69 =10460353203 mod 69 = 54

287 mod 69 =13492928512 mod 69 = 40

267 mod 69 =8031810176 mod 69 = 2

247 mod 69 =4586471424 mod 69 = 24

417 mod 69 =194754273881 mod 69 = 29

207 mod 69 =1280000000 mod 69 = 44

257 mod 69 =6103515625 mod 69 = 13

137 mod 69 =62748517 mod 69 = 55

107 mod 69 =10000000 mod 69 = 37

307 mod 69 =21870000000 mod 69 = 51

397 mod 69 =137231006679 mod 69 = 18

337 mod 69 =42618442977 mod 69 = 60

157 mod 69 =170859375 mod 69 = 57

217 mod 69 =1801088541 mod 69 = 33

127 mod 69 =35831808 mod 69 = 39

427 mod 69 =230539333248 mod 69 = 15

437 mod 69 =271818611107 mod 69 = 67

447 mod 69 =319277809664 mod 69 = 56

Полученная криптограмма:

150654402402062956440206444025550237510606156756184024560654402402062956605733243957605754403937

        Пример 4. Зашифруем фразу  Рене́ Дека́рта: «Мало иметь хороший ум, главное – хорошо его применять».  Закодируем буквы согласно таблице №3 .

 22 10 21 24 44 18 22 15 28 38 44 31 24 26 24 34 18 19  44 29 22 45 44 13 21 10 12 23 24 15 44 43 44 31 24 26 24 34 24 44 15 13 24 44 25 26 18 22 15 23 41 28 38 46

        Создадим секретный и открытый ключ RSA:

1. Выбираем два простых числа p=13  и  q=89.
2. Вычислим их произведение m= pq=13*89=1157.
3. Вычислим значение функции Эйлера:  (1027)=(p-1)(q-1)=12*88=1056
4. Выбирается целое число e=31, взаимно простое с (m)= 1056 .

Пара (e,m)=(31,1157) - открытый ключ RSA.

1. Найдем линейное представление НОД(e, (m)) при помощи расширенного алгоритма Евклида.   Найдем НОД:

1056=31*34+2  31=2*15+1 2=2*1+0 НОД(31,1056)=1.

1. Найдем соотношение Безу: 1=31-2*15=31-(1056-31*34)*15=31*511-15*1056.

Отсюда  НОД (31, 1056) =1=31*d-c*1056=31*511-15*1056 и d = 511.

Пара (d,m)=(511,1157) – секретный ключ RSA.

        Теперь нам нужно разбить численное представление сообщения на кусочки, каждый из которых —  натуральное число, не превосходящее m=1157: 

221-021-244-418-221-528-384-431-242-624-341-819-442-922-454-413-211-012-232-415-444-344- 312-426-243-424-441-513-244-425-261-822-152-341-283-846

        Для расчетов  воспользуемся программой MathCad. Данная программа позволяет вычислять большие степени и находить остаток от целочисленного деления. Я воспользовалась следующей программой.

01231 mod 1157 =675

02131 mod 1157 =1032

15231 mod 1157 =308

21131 mod 1157 =419

 22131 mod 1157 =143

23231 mod 1157 =795

24231 mod 1157 =668

24331 mod 1157 =165

24431 mod 1157 =127

24431 mod 1157 =127

26131 mod 1157 =326

28331 mod 1157 =1076

31231 mod 1157 =182

34131 mod 1157 =887

34431 mod 1157 =215

38431 mod 1157 =994

41331 mod 1157 =621

41531 mod 1157 =155

41831 mod 1157 =24

42431 mod 1157 =837

42531 mod 1157 =958

42631 mod 1157 =491

43131 mod 1157 =830

44131 mod 1157 =584

44231 mod 1157 =325

44431 mod 1157 =622

45431 mod 1157 =961

51331 mod 1157 =748

52831 mod 1157 =148

62431 mod 1157 =624

81931 mod 1157 =663

82231 mod 1157 =1121

84631 mod 1157 =716

92231 mod 1157 =714

В результате получим RSA-криптограмму.

143-1032-127-24-143-148-994-830-668-624-887-663-325-714-961-621-419-675-795-155-622-215-182-491-165-837-584-748-127-958-326-1121-308-887-1076-716

Для расшифровки применим секретный ключ RSA: d=511,m=1157.

675511 mod 1157 = 012 

1032511 mod 1157 = 021 

308511 mod 1157 = 152 

419511 mod 1157 = 211 

143511 mod 1157 = 221 

795511 mod 1157 = 232 

668511 mod 1157 = 242 

165511 mod 1157 = 243 

127511 mod 1157 = 244 

127511 mod 1157 = 244 

326511 mod 1157 = 261 

1076511 mod 1157 = 283 

182511 mod 1157 = 312 

887511 mod 1157 = 341 

215511 mod 1157 = 344 

994511 mod 1157 = 384 

621511 mod 1157 = 413 

155511 mod 1157 = 415 

24511 mod 1157 = 418 

837511 mod 1157 = 424 

958511 mod 1157 = 425 

491511 mod 1157 = 426 

830511 mod 1157 = 431 

584511 mod 1157 = 441 

325511 mod 1157 = 442 

622511 mod 1157 = 444 

961511 mod 1157 = 454 

748511 mod 1157 = 513 

148511 mod 1157 = 528 

624511 mod 1157 = 624 

663511 mod 1157 = 819 

1121511 mod 1157 = 822 

716511 mod 1157 = 846 

714511 mod 1157 = 922 

        В результате расшифровки получим текст: 221-021-244-418-221-528-384-431-242-624-341-819-442-922-454-413-211-012-232-415-444-344- 312-426-243-424-441-513-244-425-261-822-152-341-283-846 , разбив который на двузначные числа, можно восстановить исходный текст по таблице 3.

        Пример 5.  Зашифруем фразу Пьера Гассенди «Если мы действительно что-то знаем, то мы знаем это благодаря изучению математики». Закодируем текст по квадрату Полибия (таб. 2):

1636262311315311151624364113411626573233114641332741331722321116314717413331532232111631175441331226111433151135561723224246163223553111411631114123252337

Создадим секретный и открытый ключ RSA:

1. Выбираем два простых числа p=3  и  q=41.
2. Вычислим их произведение m= pq=3*41=123.
3. Вычислим значение функции Эйлера:   (123)=(p-1)(q-1)=2*40=80.
4. Выбирается целое число e=17, взаимно простое с (m)=80.

Пара (e,m)=(17,123) - открытый ключ RSA.

1. Найдем линейное представление НОД(e, (m)) при помощи расширенного алгоритма Евклида.   Найдем НОД:

80=17*4+12  17=12*1+5   12=5*2+2  5=2*2+1  2=2*1+0  НОД(17,80)=1

1. Найдем соотношение Безу:
2. 1=5-2*2=5-(12-5*2)*2=5-12*2+5*2*2=-12*2+5*5=-12*2+(17-12*1)*5=

=-12*2+17*5-12*1*5=17*5-12*7=17*5-(80-17*4)*7=17*5-80*7+17*4*7=-80*7+17*33

Отсюда  НОД (17, 80) =1= -80* c+ 17* d=-80*7+17*33 и d =33.

Пара (d,m)=(33,123) – секретный ключ RSA.

Разобьем текст на блоки двузначных чисел и зашифруем его, использую открытый ключ.

1617mod 123 =10

2617mod 123 =101

3617mod 123 =102

2317mod 123 =86

3117mod 123 =64

5317mod 123 =116

1517mod 123 =63

2417mod 123 =117

4117mod 123 =41

1317mod 123 =70

5717mod 123 =51

3217mod 123 =32

3317mod 123 =84

4617mod 123 =103

2717mod 123 =27

2217mod 123 =106

1717mod 123 =47

5417mod 123 =111

2117mod 123 =90

1117mod 123 =110

1417mod 123 =14

3517mod 123 =56

5617mod 123 =104

4217mod 123 =42

5517mod 123 =55

3717mod 123 =16

4717mod 123 =26

2517mod 123 =31

        Получим данную RSA-криптограмму:

10-102-101-86-47-63-116-47-63-10-102-41-70-86-41-10-101-51-32-84-47-103-41-84-27-41-84-47-106-32-110-10-63-26-47-41-84-47-63-116-47-106-32-110-10-63-47-90-101-110-14-84-63-110-56-104-47-86-106-42-103-10-32-86-55-47-63-110-41-10-63-110-41-86-31-86-16

        Для расшифровки применим секретный ключ RSA: d=33, m=123

1033 mod 123 = 16 

10133 mod 123 = 26 

10233 mod 123 = 36 

8633 mod 123 = 23 

6433 mod 123 = 31 

11633 mod 123 = 53 

6333 mod 123 = 15 

11733 mod 123 = 24 

4133 mod 123 = 41 

7033 mod 123 = 13 

5133 mod 123 = 57 

3233 mod 123 = 32 

8433 mod 123 = 33 

10333 mod 123 = 46 

2733 mod 123 = 27 

10633 mod 123 = 22 

4733 mod 123 = 17 

11133 mod 123 = 54 

9033 mod 123 = 21 

11033 mod 123 = 11 

1433 mod 123 = 14 

5633 mod 123 = 35 

10433 mod 123 = 56 

4233 mod 123 = 42 

5533 mod 123 = 55 

1633 mod 123 = 37 

2633 mod 123 = 47 

3133 mod 123 = 25 

В результате расшифровки получим текст

1636262311315311151624364113411626573233114641332741331722321116314717413331532232111631175441331226111433151135561723224246163223553111411631114123252337, разбив который на двузначные числа можно восстановить его по квадрату Полибия.

3.4. Криптоанализ RSA

        Проблема различения простых и составных чисел и разложения последних в их главные факторы, как известно, является одной из самых важных и полезных в арифметике. Далее, достоинство самой науки требует, чтобы все возможные средства были исследованы для решения этой проблемы, столь изящной и настолько знаменитой.

 Карл Фридрих Гаусс         «Арифметические исследования» (1801)

        Почему же тогда систему RSA трудно взломать? Ведь для нахождения р и q всего-то и надо, что разложить на множители число m. Однако, если каждое из простых чисел содержит

больше 100 цифр, то время и ресурсы, необходимые для разложения числа m на множители, таковы, что взламывание кода становится очень трудным. Таким образом, ловушка в системе

RSA заключается в том, что умножение чисел р и q для получения числа m — простая операция, тогда как обратная задача — разложение числа m на множители для получения р и q — практически неразрешима. Другими словами, мы очень хорошо понимаем, как взломать RSA, однако на практике взлом не реализуем. Не следует забывать, однако, что препятствие носит чисто технологический характер: можно представить себе, что в один прекрасный день развитие компьютеров или изобретение лучших способов разложения на множители сделают

систему RSA устаревшей. Подтверждение этому был получено при взломе системы RSA-129.

        В 1977 году в том же номере Scientific American, где был опубликован алгоритм RSA,  известный математик и учёный Мартин Гарднер по согласию авторов алгоритма, опубликовал математическую задачу, получившую название RSA-129. В ней он написал пару чисел (e, m) — открытый ключ, где длина числа m составляла 129 десятичных знаков:

m=114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541, а е=9007, и само зашифрованное сообщение: 96861375462206147714092225435588290575999112457431987469512093081629822514 5708356931476622883989628013391990551829945157815154.

        Дешифровавшему сообщение он обещал вознаграждение в $100, которые он положил в банк под 2% годовых. По подсчётам аналитиков, для разложения такого огромного числа на множители при существовавших алгоритмах факторизации и мощности тех компьютеров, потребуется 20.000 лет непрерывной работы (Рон Ривест предполагал 40 квадрильён лет для числа в 125 знаков).

        В 1994 году молодой криптограф американской армии Арьен Ленстра разработал алгоритм, позволяющий за разумное время найти разложение на простые множители числа до 130 цифр. Сам Ленстра не обладал необходимыми вычислительными мощностями, и тогда он предложил через Интернет добровольцам выделить часть своего процессорного времени на благо математики. Это был один из первых в истории больших проектов, использующих распределённые вычисления. К решению задачи присоединилось 600 человек, предоставив 1600 компьютеров: кроме самых обычных компьютеров участие приняли 3 суперкомпьютера. Далее, в дело вступил метеорологический суперкомпьютер, выделенный самому Ленстре, который за 220 дней непрерывной работы разложил на множители 129-значное число m. Ответ оказался таким:

p=3490529510847650949147849619903898133417764638493387843990820577

q=32769132993266709549961988190834461413177642967992942539798288533

Длины чисел p и q оказались 64 и 65 знаков соответственно. Фраза, зашифрованная Мартином Гарднером, была такая: "The Magic Words are Squeamish Ossifrage", что переводится «Магические слова – брезгливый стервятник». Из $100 по процентам за 17 лет получилось примерно $140, которые и были переданы в фонд свободного программного обеспечения.

        Алгоритм RSA тесно связан с задачами теории чисел, которые просто формулируются, но сложно решаются.

1. Как эффективно раскладывать данное целое число на множители?
2. Как доказывать, что данное целое число простое?
3. Открытый ключ в системе шифрования RSA — очень большое число. В практических  приложениях используются числа с более, чем 200 знаками. Как можно работать с такими большими числами?

ЗАКЛЮЧЕНИЕ

        Криптография сегодня – это наука об обеспечении безопасности данных или, как говорят, информационной безопасности. Шифрование – это основное действие в криптографии, шифрование – это преобразование данных в такую форму или представление, что понять смысл передаваемых или хранимых данных, не обладая специальной дополнительной информацией (криптографическими ключами), невозможно. По определению ISO – международной организации, разрабатывающей стандарты для открытых систем, задачами обеспечения защиты информации являются:

1. Обеспечение конфиденциальности информации (защита передаваемой информации от доступа и копирования любым, кроме того, кому доступ определен системой защиты либо непосредственно источником информации).
2. Защита информации от искажения (сохранение целостности передаваемой информации таким образом, что принимающая сторона имеет возможность определять, была ли изменена информация в процессе передачи).
3. Аутентификация сообщений и пользователей (и идентификация как возможность ведения записей в системе, специальная подпись документов, которые могут стать определяющими в споре об авторстве передаваемой информации).
4. Признание авторства (аналогично аутентификации, с той лишь разницей, что доказательство авторства проводится в случае, когда источник информации отрицает факт передачи информации).

        Все эти задачи решаются с помощью применения методов и средств криптографической защиты информации. Криптография существует уже несколько столетий, но только несколько десятилетий как всемирно признанная научная область деятельности. Эти годы являются периодом интенсивного развития как закрытых, так и открытых исследований в различных областях математики с точки зрения применения ее в криптографии.

        Основные результаты работы:

1. изучены основные виды симметрических криптосистем: шифры замены и шифры перестановки;
2. изучены основные принципы асимметрических криптосистем;  
3. изучены понятия и методы теории чисел: основная теорема арифметики, расширенный алгоритм Евклида, простые числа и их свойства, алгоритмы нахождения простых чисел; разобран алгоритма RSA;
4. приведено 5 примеров шифрования и дешифрования  высказываний великих математиков по алгоритму RSA;
5. проведены уроки в математических классах, на которых учащиеся были обучены схеме  RSA.

СПИСОК ЛИТЕРАТУРЫ

1. Коутинхо С. Введение в теорию чисел. Алгоритм RSA. М.: Постчаркет, 2001. - 328 с.
2. Коробейников А. Г, Ю.А.Гатчин. Математические основы криптологии. Учебное пособие. СПб: СПб ГУ ИТМО, 2004. – 106 с
3. Аршинов М. Н. Коды и математика.    М. Наука. 1983 г.
4. Шифры и математика // Математический клуб «Кенгуру». Выпуск № 14 (6-8 классы), 2006.
5. Интернет ресурс: http://ru.wikipedia.org
6. Криптография, основы безопасности передачи данных. Интернет ресурс: http://www.chhm.net/
7. Гарднер М. Математические досуги. М.:  «Мир», 1972.  -  496 стр.