Простые числа и их использование в криптографии

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Мусохранов М.М. 1

---

1МБОУ «Лицея №9 имени К.Э. Циолковского г. Калуги

Рылова И.Г. 1

---

1МБОУ «Лицея №9 имени К.Э. Циолковского г. Калуги

Работа в формате PDF

345.8 KB

Автор работы награжден дипломом победителя II степени

Диплом школьникаСвидетельство руководителя

Введение

Предлагаемая вашему вниманию исследовательская работа посвящена простым числам и использованию их в кодировании. Данная тема заинтересовала меня, когда я стал изучать простые числа. Больше всего меня удивил тот факт, что ученые всего мира до сих пор активно ищут их. Так проект Great Internet Mersenne Prime Search, перед которым стоит задача поиска большого числа простых чисел особо редкого вида, недавно открыл самое большое простое число, известное на сегодняшний день. В нем 23 249 425 цифр — это достаточно, чтобы заполнить книгу из 9000 страниц. Для сравнения: количество атомов во всей наблюдаемой Вселенной оценивается в число с не более чем сотней знаков. Новое число, которое записывается как 2⁷⁷²³²⁹¹⁷-1 (два в 77 232 917-й степени минус один), было обнаружено волонтером, который посвятил 14 лет вычислительного времени этому поиску! Но зачем нам знать число, которое растягивается на 23 миллиона знаков? Ведь самые важные числа для нас — это те, которые мы используем для количественного описания нашего мира? Так, да не так. На сегодняшний день большие простые числа повсеместно используются в нашей повседневной жизни, например, в кредитных картах и персональных компьютерах, поэтому постоянно существует потребность в новых простых числах (чем больше, тем лучше) для генерации секретных кодов. Эта информация меня поразила, поэтому и стала темой моего исследования.

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

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

Задачи исследования: для достижения поставленной цели нам необходимо решить следующие задачи:

Изучить найденную литературу по данному вопросу.

Выяснить значение терминов «простое число», «криптография», «RSA»

Найти примеры и изучить применение простых чисел в кодировании.

Приобрести навыки научно-исследовательской работы.

Распространить свой опыт кодирования с помощью простых чисел среди учащихся 5 классов.

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

Определение простого числа.

Простые числа представляют собой одно из самых интересных математических явлений, которое привлекает к себе внимание ученых и простых граждан на протяжении уже более двух тысячелетий. Несмотря на то, что сейчас мы живем в век компьютеров и самых современных информационных программ, многие загадки простых чисел не решены до сих пор, есть даже такие, к которым ученые не знают, как подступиться [2].

Простые числа — это, как известно еще из курса элементарной арифметики, те натуральные числа, которые делятся без остатка только на единицу и самое себя. Простые числа называют «кирпичами» в здании математики, «атомами» математики и «генетическим кодом» числа, потому что любое составное число может быть представлено в виде единственно возможного произведения простых чисел. Эта теорема была сформулирована Евклидом и известна как «основная теорема арифметики». Следовательно, простые числа являются первичными элементами, из которых построены все числа. Так же как атомы образуют молекулы. Простые числа образуют составные числа. Интересные факты. Во-первых, число 1 имеет только один делитель: само это число. Поэтому его не относят ни к составным числам, ни к простым. Во-вторых, единственным четным числом, относящимся к простым, является, естественно, двойка. Любое другое четное число сюда попасть попросту не может, так как кроме себя и единицы, делится еще и на два.

Имеет ли этот ряд конец? Этот вопрос поставлен в IX книге «Начал» Евклид и там же дает ответ на него - «За каждым простым числом может быть указано еще одно, большее простое число – ряд простых чисел бесконечен» [1].

Способы нахождения простых чисел.

Выделение простых чисел является сложной задачей математики. Ученые на протяжении многих веков пытаются найти формулу, которая позволила бы из множества натуральных чисел выписать простые. Первый, кто занимался этой задачей, был великий математик древности Эратосфен (рис. 1), живший почти 2 300 лет назад [4].

Рис. 1. Великий математик древности Эратосфен

Он придумал такой способ: записал все числа от единицы до какого-то числа, а потом вычеркнул единицу, которая не является ни простым, ни составным числом, затем вычеркивал через одно все числа, идущие после 2 (числа, кратные двум, т.е. 4,6,8 и т.д.). Первым оставшимся числом после 2 было 3. Далее вычеркивались через два все числа, идущие после трех (числа, кратные 3, т.е. 6, 9, 12, и т.д.), в конце концов оставались невычеркнуыми только простые числа: 2, 3, 5, 7, 11, 13,… Поскольку во времена Эратосфена писали на восковых дощечках, а вместо того, чтобы числа вычеркивать, дощечку в нужном месте прокалывали, то способ получил название “решето Эратосфена”.

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

С первого взгляда видно, что простые числа совершенно непредсказуемы. Например, между 1 и 100 простых чисел больше, чем между 101 и 200. Всего в первой тысяче 168 простых чисел. Можно предположить, что если продолжить нашу таблицу, то с каждой тысячей количество простых чисел будет увеличиваться. Но это не так. Уже известно, что, например, среди тысячи чисел между 10100 и 10100 + 1000 находится лишь два простых числа. И эти числа состоят более чем из ста цифр!

Таблица 1

Простые числа из первой тысячи натуральных чисел

Рис.2. Древнегреческий математик Евклид

Теорема Евклида: «Первых простых чисел существует больше любого указанного числа их».

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

Mp = 2p - 1

где р — другое простое число.

До 1750 года было найдено всего 8 простых чисел Мерсенна: М2, М3, М5, М7, М13, М17, М19, М31. То, что М31 - простое число, доказал в 1750 году Л. Эйлер. В 1876 году французский математик Эдуард Люка установил, что число М127=170141183460469231731687303715884105727 - простое. В 1883 г. сельский священник Пермской губернии И.М.Первушин доказал, что число М61=2305843009213693951 является простым. Позднее было установлено, что числа М89 и М107 простые. 12 простых чисел Мерсена были вычислены с помощью только карандаша и бумаги, а для вычисления следующих уже использовались механические настольные счетные машины.

Масштабный проект по поиску простых чисел GIMPS был запущен в 1997 году, и ныне считается самым длительным непрерывным процессом распределённых вычислений в истории человечества: он продолжается уже почти 20 лет. Сейчас в пиковые моменты в GIMPS участвует 360.000 процессоров с суммарной производительностью 150 трлн операций в секунду. За время работы GIMPS участники этого проекта нашли 14 простых чисел Мерсенна. Последнее из них 274 207 281-1 было обнаружено 07 января 2016 года. Всего на данный момент известно 49 простых чисел Мерсена. В списке самых больших простых чисел, известных на сегодняшний день, десять первых мест занимают числа Мерсенна.

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

Применение простых чисел в криптографии.

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

В 1975 г. Уитфилду Диффи и Мартину Хеллману, в то время работавшим в Стэнфордском университете, пришла в голову идея асимметричного шифрования, или «шифрования с открытым ключом». Эта система основана на специальных математических функциях, называемых «односторонними функциями с потайным входом», которые позволяют зашифровывать текст, но делают расшифровку практически невозможной без знания используемого кода. Идея состоит в том, что каждый пользователь имеет пару ключей: открытый и закрытый. Если мы хотим отправить кому-то сообщение, мы зашифровываем это сообщение с помощью открытого ключа — то есть ключа, известного всем. Но только человек, имеющий соответствующий закрытый ключ, может расшифровать это сообщение. Одним из преимуществ такого метода является то, что закрытый ключ никогда не передается и поэтому его не нужно постоянно менять в целях безопасности. Идея метода не совсем проста, но мы можем пояснить ее с помощью аналогии. Представьте себе большой магазин, где продаются сотни тысяч банок с краской разного цвета. Возьмем две любые банки и смешаем краску в разных количествах. Пока все просто. Теперь, если мы покажем кому-нибудь получившийся цвет и попросим «расшифровать», какое количество каких красок использовалось изначально, на такой вопрос будет очень трудно ответить. Именно так работают односторонние функции с потайным входом, которые легко применить в одном направлении, но практически невозможно — в обратном.

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

В августе 1977 г. знаменитый американский писатель и популяризатор науки Мартин Гарднер озаглавил свою колонку по занимательной математике в журнале Scientific American так: «Новый вид шифра, на расшифровку которого потребуются миллионы лет» [3]. После объяснения принципа системы шифрования с открытым ключом он показал само зашифрованное сообщение и открытый ключ N, используемый в этом шифре:

Гарднер призвал читателей попробовать расшифровать сообщение, используя предоставленную информацию, и даже дал подсказку: для решения необходимо разложить число N на простые множители р и q. Более того, Гарднер назначил приз в размере $100 (приличная сумма на тот момент) тому, кто первым получит правильный ответ. Каждый, кто захочет побольше узнать о шифре, писал Гарднер, может обратиться к создателям шифра — Рону Ривесту, Ади Шамиру и Лену Адлеману из Лаборатории информации Массачусетского технологического института. Правильный ответ был получен лишь через 17 лет. Он стал результатом сотрудничества более чем 600 человек. Ключами оказались р = 32769132993266 709549961988190834461413177642967992942539798288533 и q = 3490529510847650949147849619903898133417764638493387843990820577, а зашифрованная фраза звучала так: «Волшебные слова — это брезгливый ягнятник».

Алгоритм, представленный Гарднером, известен как RSA — буквенная аббревиатура от фамилий Rivest (Ривест), Shamir (Шамир) и Adleman (Адлеман). Это первое практическое применение придуманной Диффи системы шифрования с открытым ключом, которая повсеместно используется и по сей день. Надежность ее практически гарантирована, потому что процесс расшифровки является невероятно сложным, почти невозможным делом.

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

Представим, что один человек, зашифровав важную информацию, установил на нее пароль (P) равный одному из простых делителей числа (А), сказав другому человеку, что число (А) содержит только два простых делителя и дав ему ключ для расшифровки – число (B), являющееся вторым делителем числа (А). Не трудно понять, что для расшифровки необходимо разделить А на B, чтобы получить пароль Р. Например в элементарном варианте А=111, ключ B=3 тогда пароль равен А/B=37.

Допустим, число А попало к злоумышленнику, и он знает условие о том, что А состоит из 2-х простых делителей. При условии, что А=111 злоумышленнику не составит особого труда даже в уме взломать пароль. Теперь представим ситуацию, когда число А состоит из 2 простых чисел, каждое из которых состоит из тысячи цифр… Если злоумышленник не знает ключа (одного из делителей), для факторизации числа А, состоящего из двух тысяч цифр, ему потребуется, как минимум, суперкомпьютер и большое количество времени его работы!!! Если попытаться попытается разложить произведение — даже при помощи самого быстрого суперкомпьютера — это не получится. Просто не существует такого алгоритма, который справился бы с этой задачей за время жизни Вселенной.

Для применения алгоритма RSA требуется построить открытый и секретный ключи следующим образом.

1. Выбрать два больших простых числа, p и q.

2. Найти их произведение n = p • q и значение ϕ =(р-1)-(q-1)

3. Выбрать число e (1 < e < ϕ), которое не имеет общих делителей с ϕ .

4. Найти число d, которое удовлетворяет условию d • е = k⋅ϕ + 1 для некоторого целого k.

5. Пара значений (e, n) — это открытый ключ RSA (его можно свободно публиковать), а пара (d, n) — это секретный ключ.

Передаваемое сообщение нужно сначала представить в виде последовательности чисел в интервале от 0 до n -1. Для шифрования используют формулу

C = Т^e mod n

где Т — число исходного сообщения,

(e, n) — открытый ключ,

С — число закодированного сообщения, а запись С ^e mod n обозначает остаток от деления x e на n.

Расшифровка сообщения выполняется по формуле

Т = C^d mod n

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

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

Где применяют алгоритм RSA на практике? Криптосистема RSA используется в самых различных продуктах, на различных платформах и во многих отраслях. В настоящее время криптосистема RSA встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Также ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении RSA алгоритм применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании. Кроме того, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Internet, в том числе S/MIME, SSL и S/WAN, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах. На осень 2000 года технологии с применением алгоритма RSA были лицензированы более чем 700 компаниями.

Технологию шифрования RSA BSAFE используют около 500 миллионов пользователей всего мира. Так как в большинстве случаев при этом используется алгоритм RSA, то его можно считать наиболее распространенной криптосистемой общего (public) ключа в мире и это количество имеет явную тенденцию к увеличению по мере роста Internet.

На начало 2001 года криптосистема RSA являлась наиболее широко используемой асимметричной криптосистемой (криптосистемой открытого (public) ключа) и зачастую называется стандартом де факто. Вне зависимости от официальных стандартов существование такого стандарта чрезвычайно важно для развития электронной коммерции и вообще экономики. Единая система открытого (public) ключа допускает обмен документами с электронно-цифровыми подписями между пользователями различных государств, использующими различное программное обеспечение на различных платформах; такая возможность насущно необходима для развития электронной коммерции. Распространение системы RSA дошло до такой степени, что ее учитывают при создании новых стандартов. При разработке стандартов цифровых подписей, в первую очередь в 1997 был разработан стандарт ANSI X9.30, поддерживающий Digital Signature Standard (стандарт Цифровой подписи). Годом позже был введен ANSI X9.31, в котором сделан акцент на цифровых подписях RSA, что отвечает фактически сложившейся ситуации, в частности, для финансовых учреждений.

Проведение анкетирования

Для того, чтобы выяснить знают ли ученики 5-х классов о применение простых чисел в кодирование, об алгоритме RSA, а также выявить количество учеников, использующих ежедневно технологию шифрования RSA, я решил провести опрос. Опрос проводился посредством анкетирования. В опросе приняли участие 21 учащийся из 5-х классов МБОУ «Лицей №9 имени К.Э. Циолковского» г. Калуги.

Респондентам были заданы вопросы, представленные в таблице 2.

Таблица 2

Вопросы для проведения анкетирования

Результаты анкетирования представлены ниже.

Рис. 3. Диаграмма опроса учеников 5 класса,

где ось ординат — это количество опрошенных учеников, ось абсцисс – это вопросы представленные в табл.2.

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

Шифрование с помощью алгоритма RSA

С целью повышения осведомленности учеников 5-х классов о применении простых чисел в кодировании, я решил попробовать зашифровать с помощью алгоритма RSA фразу «Приветствую участников конференции» (вычисления сведены в таблицу 3) и познакомить одноклассников с алгоритмом шифрования:

Выбираю два простых числа p и q, p = 7 и q = 13

Вычисляю произведение n = p*q = 7*13 = 91

Вычисляю функцию Эйлера φ(n)= (p-1)*(q-1) = (7-1)*(13-1) = 72

Выбираю произвольное целое e: 0 < e < n взаимно простое с значением функции Эйлера φ(n). Пусть e = 5. Пара чисел (e, n) объявляется открытым ключом шифра.

В моем примере (e, n) = (5, 91).

Вычисляю целое число d из соотношения

(d*e) mod φ(n) = 1

(Операция mod вычисляет остаток от целочисленного деления двух чисел).

Это соотношение означает, что результатом деления произведения чисел e и d на значение функции Эйлера должно быть число 1. Поэтому d можно рассчитать по формуле:

d = (k* φ(n) +1) / e.

Придавая k последовательно значения 1, 2, 3,.. до тех пор, пока не будет получено целое число d.

Подбор k я проводил в табличном процессоре Excel.

Вычисляю число d:

d = (k* 72 +1) / 5,

при k = 1, d – не целое, при k = 2, d = 29. Получаю закрытый ключ шифра (d, n) = (29, 91).

Процедуры шифрования и дешифрования выполняются по следующим формулам:

C = Т^e mod n = Т⁵ mod 91

Т = C^d mod n = C²⁹ mod 91

где Т, C - числовые эквиваленты символов открытого и шифрованного сообщения (см. табл.4).

Таблица 3

Сводная таблица процедуры создания ключей

Таблица 4

Кодирование фразы «Приветствую участников конференции».

Буквы в фразе «Приветствую участников конференции» заменены на числовые эквиваленты из таблицы 3.

Расчеты проводил с помощью электронных таблицExcel и занесены в таблицу 5.

Таблица 5

Вычисление шифрограммы

Нужно отметить, что кодирование с помощью алгоритма RSA было довольно сложно в понимании для учеников 5-го класса, но при этом вызвало неподдельный интерес.

Выводы

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

Исследование в корне изменило мое представление о простых числах и их значении в современном мире. Полученные знания о простых числах как основы современной криптографии заставили по-новому взглянуть на способы шифрования информации. В перспективе мне было бы интересно более подробно изучить и другие способы шифрования и защиты.

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

Список литературы

Гальперин Г. Просто о простых числах // Квант, 1987. – №4. С. 9-14.

Мир математики: в 40 т. Т.2: Жуан Гомес. Математики, шпионы и хакеры. Кодирование и криптография. / Пер. с англ. – М.: Де Агостини, 2014. – 144 с.

Мир математики: в 40 т. Т.3: Грисан Энрике. Простые числа. Долгая дорога к бесконечности. / Пер. с англ. – М.: Де Агостини, 2014с144 с.

Росанова К. А., Воронцова Я. О., Гаврилова А. М., Шмелева О. В. Эти сложные простые числа! // Юный ученый. — 2016. — №6.1. — С. 40-41.