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

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

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

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

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

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

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

Ознакомиться с основными понятиями криптографии. Изучение основных принципов симметрических криптосистем. Изучение основных принципов асимметрических криптосистем.

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

Реализация алгоритма RSA на примерах шифрование и дешифрование различных сообщений по алгоритму RSA.

Обучить школьников шифрованию по схеме RSA.

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

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

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

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

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

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

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

общее правило, по которому преобразуется исходный тест (алгоритм шифра);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Боб создает пару ключей: один для шифрования (открытый), другой для дешифрования (секретный).

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

Если Алиса собирается послать сообщение пользователю Бобу, она шифрует сообщение открытым ключомБоба.

Когда Боб получает сообщение, он дешифрует его с помощью своего личного (секретного) ключа. Другой получатель не сможет дешифровать сообщение, поскольку личный ключ Боба знает только Боб.

Первой и наиболее известной криптографической системой с открытым ключом была предложенная в 1978 году так называемая система RSA. Ее название происходит от первых букв фамилий авторов Рональд Райвест (RonaldLinnRivest), Ади Шамир (AdiShamir), и Леонард Адлеман (LeonardAdleman), которые придумали ее во время совместных исследований в Массачусетском технологическом институте в 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=p₁…p_k, где p₁…p_k  — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.

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

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

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

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

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

Пустьa иb — целые числа, не равные одновременно нулю, и последовательность чиселa, b,r₁> r₂>r₃>… >r_nопределена тем, что каждое r_k — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

a = bq₁ + r₁ b = r₁q₂+ r₂r₁ = r₂q₃ + r₃…r_k = r_k+1q_k+2+ r_k+2 …

r_n-2=q_nr_n-1+r_nr_n−1= r_nq_n

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

Пример 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подсчитывались одновременно. Именно поэтому новая процедура называется расширенным алгоритмом Эвклида.

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

r₁=a -bq₁r₂=b - r₁q₂ =b-q₂ (a –bq₁) =b(1+ q₁q₂)-aq₂ …r_n =d *a+c*b .

ТогдаНОД(a,b)=r_n =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)=r_n =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.

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

Если число m простое, (m)=m-1.

Если числа 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:

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

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

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

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

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

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

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

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

И.М. Виноградов(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.

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

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

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

Выписать подряд все целые числа от 2 до n: 2, 3, 4, …, n.

Пусть переменная p изначально равна двум — первому простому числу: p=2.

Вычеркнуть из списка все числа от 2p до n, делящиеся на p, то есть, числа 2p, 3p и т.д.

Найти первое не вычеркнутое число, большее чем p, и присвоить значению переменной p это число.

Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n

Все не вычеркнутые числа в списке — простые числа.

Таким образом, для нахождения множества простых до заранее выбранной верхней границы 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. Простые числа Мерсена

Числа Мерсенна - это числа, преставимые в виде 2ⁿ-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 года является 2^43112609 − 1. Оно содержит 12 978 189 десятичных цифр и является простым числом Мерсенна (M_43112609). Его нашли 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS. Это же число является наибольшим среди всех известных простых чисел. На сегодняшний день неизвестно: конечно ли число простых чисел Мерсена.

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

Числа вида впервые начал изучать Пьер Ферма, поэтому эти числа называются числами Ферма. Он высказал гипотезу, что все эти числа являются простыми, но не смог ни доказать, ни опровергнуть это утверждение. Первые 5 чисел Ферма действительно являются простыми: F₀ = 3, F₁ = 5, F₂ = 17, F₃= 257, F₄ = 65537.

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

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

3. Алгоритм RSA

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

Выберем два простых числаp и q.

Вычисляется их произведениеm=pq, которое называется модулем.

Вычисляется значение функции Эйлера от числа m: (m)=(p-1)(q-1)

Выбирается целое число e (1<e<(m)), взаимно простое со значением функции(m).

Ищется линейное представлениеНОД (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.

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

Взятьоткрытый ключ(e,m) .

Взятьоткрытый текст 0 am-1

Получитькриптограммуb:b=a^emodm

Передать шифрованное сообщениеb.

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

Принять зашифрованное сообщение b.

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

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

Пример 1.

Выбираем два простых числаp=17 и q=5.

Вычислим их произведениеm=pq=17*5=85.

Вычислим значение функции Эйлера: (85)=(p-1)(q-1)=16*4=64

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

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

Найдем линейное представлениеНОД(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

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

Возьмем открытый ключ(e,m)=(5,85) .

Возьмемоткрытый текст a=7.

Получить криптограммуb:b=a^emodm=7⁵mod 85=16807 mod85=62

Передать шифрованное сообщениеb=62.

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

Принять зашифрованное сообщение b=62.

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

a=b^dmod m=62¹³mod 85=200028539268669788905472 mod85=7

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

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

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

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

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

31⁵mod 85 = 28629151 mod 85 = 46

11⁵mod 85 = 161051 mod 85 = 61

41⁵mod 85 = 115856201 mod 85 = 11

16⁵mod 85 = 1048576 mod 85 = 16

23⁵mod 85 = 6436343 mod 85 = 58

25⁵mod 85 = 9765625 mod 85 = 60

45⁵mod 85 = 184528125 mod 85 = 10

35⁵mod 85 = 52521875 mod 85 = 35

32⁵mod 85 = 33554432 mod 85 = 2

42⁵mod 85 = 130691232 mod 85 = 77

27⁵mod 85 = 14348907 mod 85 = 57

17⁵mod 85 = 1419857 mod 85 = 17

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

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

46611116466111586061571061355810611702617760

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

46¹³mod 85 = 15441948546310791168 mod 85 = 31

61¹³mod 85 = 161915287432152755657581 mod 85 = 11

11¹³mod 85 = 34522712143931 mod 85 = 41

16¹³mod 85 = 4503599627370496 mod 85 = 16

58¹³mod 85 = 84055070416556869132288 mod 85 = 23

60¹³mod 85 = 130606940160000000000000 mod 85 = 25

10¹³mod 85 = 10000000000000 mod 85 = 45

35¹³mod 85 = 118272717781982421875 mod 85 = 35

2¹³mod 85 = 8192 mod 85 = 32

77¹³mod 85 = 3344871416191195940889917 mod 85 = 42

57¹³mod 85 = 67046038752496061076057 mod 85 = 27

17¹³mod 85 = 9904578032905937 mod 85 = 17

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

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

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

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

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

4218272824261841442026182528241326103018184243392824441826282426184144331521241215331527281210.

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

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

Выбираем два простых числаp=3 и q=23.

Вычислим их произведениеm=pq=3*23=69.

Вычислим значение функции Эйлера: (85)=(p-1)(q-1)=22*2=44

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

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

Найдем линейное представлениеНОД(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.

18⁷mod 69 =612220032 mod 69 = 6

27⁷mod 69 =10460353203 mod 69 = 54

28⁷mod 69 =13492928512 mod 69 = 40

26⁷mod 69 =8031810176 mod 69 = 2

24⁷mod 69 =4586471424 mod 69 = 24

41⁷mod 69 =194754273881 mod 69 = 29

20⁷mod 69 =1280000000 mod 69 = 44

25⁷mod 69 =6103515625 mod 69 = 13

13⁷mod 69 =62748517 mod 69 = 55

10⁷mod 69 =10000000 mod 69 = 37

30⁷mod 69 =21870000000 mod 69 = 51

39⁷mod 69 =137231006679 mod 69 = 18

33⁷mod 69 =42618442977 mod 69 = 60

15⁷mod 69 =170859375 mod 69 = 57

21⁷mod 69 =1801088541 mod 69 = 33

12⁷mod 69 =35831808 mod 69 = 39

42⁷mod 69 =230539333248 mod 69 = 15

43⁷mod 69 =271818611107 mod 69 = 67

44⁷ 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:

Выбираем два простых числаp=13 и q=89.

Вычислим их произведениеm=pq=13*89=1157.

Вычислим значение функции Эйлера: (1027)=(p-1)(q-1)=12*88=1056

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

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

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

1056=31*34+2 31=2*15+1 2=2*1+0 НОД(31,1056)=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. Данная программа позволяет вычислять большие степени и находить остаток от целочисленного деления. Я воспользовалась следующей программой.

012³¹ mod 1157 =675

021³¹ mod 1157 =1032

152³¹ mod 1157 =308

211³¹ mod 1157 =419

221³¹ mod 1157 =143

232³¹ mod 1157 =795

242³¹mod 1157 =668

243³¹mod 1157 =165

244³¹mod 1157 =127

244³¹mod 1157 =127

261³¹mod 1157 =326

283³¹mod 1157 =1076

312³¹mod 1157 =182

341³¹mod 1157 =887

344³¹mod 1157 =215

384³¹mod 1157 =994

413³¹mod 1157 =621

415³¹mod 1157 =155

418³¹mod 1157 =24

424³¹mod 1157 =837

425³¹mod 1157 =958

426³¹mod 1157 =491

431³¹mod 1157 =830

441³¹mod 1157 =584

442³¹mod 1157 =325

444³¹mod 1157 =622

454³¹mod 1157 =961

513³¹mod 1157 =748

528³¹mod 1157 =148

624³¹mod 1157 =624

819³¹mod 1157 =663

822³¹ mod 1157 =1121

846³¹ mod 1157 =716

922³¹ 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.

675⁵¹¹mod 1157 = 012

1032⁵¹¹mod 1157 = 021

308⁵¹¹mod 1157 = 152

419⁵¹¹mod 1157 = 211

143⁵¹¹mod 1157 = 221

795⁵¹¹mod 1157 = 232

668⁵¹¹mod 1157 = 242

165⁵¹¹mod 1157 = 243

127⁵¹¹mod 1157 = 244

127⁵¹¹mod 1157 = 244

326⁵¹¹mod 1157 = 261

1076⁵¹¹mod 1157 = 283

182⁵¹¹mod 1157 = 312

887⁵¹¹mod 1157 = 341

215⁵¹¹mod 1157 = 344

994⁵¹¹mod 1157 = 384

621⁵¹¹mod 1157 = 413

155⁵¹¹mod 1157 = 415

24⁵¹¹mod 1157 = 418

837⁵¹¹mod 1157 = 424

958⁵¹¹mod 1157 = 425

491⁵¹¹mod 1157 = 426

830⁵¹¹mod 1157 = 431

584⁵¹¹mod 1157 = 441

325⁵¹¹mod 1157 = 442

622⁵¹¹mod 1157 = 444

961⁵¹¹mod 1157 = 454

748⁵¹¹mod 1157 = 513

148⁵¹¹mod 1157 = 528

624⁵¹¹mod 1157 = 624

663⁵¹¹mod 1157 = 819

1121⁵¹¹mod 1157 = 822

716⁵¹¹mod 1157 = 846

714⁵¹¹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:

Выбираем два простых числа p=3 и q=41.

Вычислим их произведениеm=pq=3*41=123.

Вычислим значение функции Эйлера: (123)=(p-1)(q-1)=2*40=80.

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

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

Найдем линейное представлениеНОД(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=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.

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

16¹⁷mod 123 =10

26¹⁷mod 123 =101

36¹⁷mod 123 =102

23¹⁷mod 123 =86

31¹⁷mod 123 =64

53¹⁷mod 123 =116

15¹⁷mod 123 =63

24¹⁷mod 123 =117

41¹⁷mod 123 =41

13¹⁷mod 123 =70

57¹⁷mod 123 =51

32¹⁷mod 123 =32

33¹⁷mod 123 =84

46¹⁷mod 123 =103

27¹⁷mod 123 =27

22¹⁷mod 123 =106

17¹⁷mod 123 =47

54¹⁷mod 123 =111

21¹⁷mod 123 =90

11¹⁷mod 123 =110

14¹⁷mod 123 =14

35¹⁷mod 123 =56

56¹⁷mod 123 =104

42¹⁷mod 123 =42

55¹⁷mod 123 =55

37¹⁷mod 123 =16

47¹⁷mod 123 =26

25¹⁷mod 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

10³³mod 123 = 16

101³³mod 123 = 26

102³³mod 123 = 36

86³³mod 123 = 23

64³³mod 123 = 31

116³³mod 123 = 53

63³³mod 123 = 15

117³³mod 123 = 24

41³³mod 123 = 41

70³³mod 123 = 13

51³³mod 123 = 57

32³³mod 123 = 32

84³³mod 123 = 33

103³³mod 123 = 46

27³³mod 123 = 27

106³³mod 123 = 22

47³³mod 123 = 17

111³³mod 123 = 54

90³³mod 123 = 21

110³³mod 123 = 11

14³³mod 123 = 14

56³³mod 123 = 35

104³³mod 123 = 56

42³³mod 123 = 42

55³³mod 123 = 55

16³³mod 123 = 37

26³³mod 123 = 47

31³³mod 123 = 25

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

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

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

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

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

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

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

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

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

В 1977 году в том же номере ScientificAmerican, где был опубликован алгоритм 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 тесно связан с задачами теории чисел, которые просто формулируются, но сложно решаются.

Как эффективно раскладывать данное целое число на множители?

Как доказывать, что данное целое число простое?

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

ЗАКЛЮЧЕНИЕ

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

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

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

Аутентификация сообщений и пользователей (и идентификация как возможность ведения записей в системе, специальная подпись документов, которые могут стать определяющими в споре об авторстве передаваемой информации).

Признание авторства (аналогично аутентификации, с той лишь разницей, что доказательство авторства проводится в случае, когда источник информации отрицает факт передачи информации).

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

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

изучены основные виды симметрических криптосистем: шифры замены и шифры перестановки;

изучены основные принципы асимметрических криптосистем;

изучены понятия и методы теории чисел: основная теорема арифметики, расширенный алгоритм Евклида, простые числа и их свойства, алгоритмы нахождения простых чисел; разобран алгоритма RSA;

приведено 5 примеров шифрования и дешифрования высказываний великих математиков по алгоритму RSA;

проведены уроки в математических классах, на которых учащиеся были обучены схеме RSA.

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

Коутинхо С. Введение в теорию чисел. Алгоритм RSA. М.: Постчаркет, 2001. - 328 с.

Коробейников А. Г, Ю.А.Гатчин. Математические основы криптологии. Учебное пособие. СПб: СПб ГУ ИТМО, 2004. – 106 с

Аршинов М. Н. Коды и математика. М. Наука. 1983 г.

Шифры и математика // Математический клуб «Кенгуру». Выпуск № 14 (6-8 классы), 2006.

Интернет ресурс: http://ru.wikipedia.org

Криптография, основы безопасности передачи данных. Интернет ресурс: http://www.chhm.net/

Гарднер М. Математические досуги. М.: «Мир», 1972. - 496 стр.

1Поли́бий (Рολιβιος, лат.  Polybius, ?201 до н. э., Мегалополь, Аркадия — ?120 до н. э.) — греческий историк, государственный деятель и военачальник, писатель

2 Дэвид Кан (англ.David Kahn) — писатель и криптограф США, автор фундаментального труда по истории криптографии «Взломщики кодов», консультант Конгресса США по вопросам криптографии.

32