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



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

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

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

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

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

2012-2013 учебный годСОДЕРЖАНИЕ

ВВЕДЕНИЕ3

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Алгоритм RSA18

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

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

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

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

ЗАКЛЮЧЕНИЕ30

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первой и наиболее известной криптографической системой с открытым ключом была предложенная в 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=p1pk, где p1pk  — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.

Впервые в таком виде она сформулирована Гауссом в § 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) с помощью алгоритма Евклида.

a=1840, b=135

1840=135*13+85

q1 =13; r1 =85

135=85*1+50

q2 =1; r2 =50

85=50*1+35

q3 =1; r3 =35

50=35*1+15

q4 =1; r4 =15

35=15*2+5

q5 =2; r5 =5

15=5*3+0

q6 =3; r6 =0

НОД(1840,135)=5

НОД(a,b)=r5

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.

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

Если число 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.

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

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45



Страницы: Первая | 1 | 2 | 3 | ... | Вперед → | Последняя | Весь текст




sitemap sitemap