Мбоу «сош №143» г. Красноярска Метапредметный проект «Криптография: алгоритм rsa»

МБОУ «СОШ №143» г. Красноярска
Метапредметный проект «Криптография: алгоритм RSA»

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проблема передачи ключа шифрования была решена в 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.

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