История возникновения криптографии

Содержание

В в е д е н и е ……………………………………………………………………..3

1 История возникновения криптографии………………………………………4

2 Актуальность криптографических методов защиты информации…………5

     3 Основные термины…………………………………………………………….6

4 Симметричные криптосистемы……………………………………………….9

4.1 Классификация криптографических методов……………………………. 9

5 Системы подстановок………………………………………………………...11

5.1 Подстановка Цезаря………………………………………………………. 13

5.2 Многоалфавитные системы. Системы одноразового использования….. 15

5.3 Системы шифрования Вижинера ………………………………………….17

5.4 Гаммирование………………………………………………………………19

5.5 Криптосистемы на основе эллиптических уравнений …………………..20

Заключение…………………………………………………………………........21

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

 

 

 

 

 

 

 

 

 

                                                                                                                                                                                  

 

 

 

В в е д е н и е

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. История возникновения криптографии

Проблема защиты информации путем ее преобразования, исключающего ее прочтение, посторонним лицом волновала человеческий ум с давних времен. История криптографии - ровесница истории человеческого языка. Более того, первоначально письменность сама по себе была криптографической системой, так как в древних обществах ею владели только избранные. Священные книги Древнего Египта, Древней Индии тому примеры.

С широким распространением письменности криптография стала формироваться как самостоятельная наука. Первые криптосистемы встречаются уже в начале нашей эры. Так, Цезарь в своей переписке использовал уже более- менее систематический шифр, получивший его имя.

Бурное развитие криптографические системы получили в годы первой и второй мировых войн. Начиная с послевоенного времени и по нынешний день появление вычислительных средств ускорило разработку и совершенствование криптографических методов [5].

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

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

 

2.Актуальность криптографических методов защиты информации.

Почему проблема использования криптографических методов в информационных системах (ИС) стала в настоящий момент особо актуальна?

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

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

 

                                          3 Основные термины

Проблемой защиты информации путем ее преобразования занимается криптология (kr yp tos - тайный, log os - наука). Криптология разделяется на два направления - криптографию и криптоанализ . Цели этих направлений прямо противоположны.

Криптография занимается поиском и исследованием математических методов преобразования информации.

Сфера интересов криптоанализа - исследование возможности расшифровывания информации без знания ключей.

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

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

2. Криптосистемы с открытым  ключом.

3. Системы электронной  подписи.

4. Управление ключами.

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

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

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

Алфавит - конечное множество используемых для кодирования информации знаков.

Текст - упорядоченный набор из элементов алфавита [10].

В качестве примеров алфавитов, используемых в современных ИС можно привести следующие:

* алфавит Z33 - 32 буквы русского алфавита и пробел;

* алфавит Z256 - символы, входящие в стандартные коды ASCII и КОИ-8;

* бинарный алфавит - Z2 = {0,1};

* восьмеричный алфавит или шестнадцатеричный алфавит;

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

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

 

 

Рис. 1. Процедура шифрования файлов.

Ключ - информация, необходимая для беспрепятственного шифрования и дешифрования текстов.

Криптографическая система представляет собой семейство T преобразований открытого текста. Члены этого семейства индексируются, или обозначаются символом k; параметр k является ключом. Пространство ключей K - это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита.

Криптосистемы разделяются на: симметричные и с открытым ключом.

В симметричных криптосистемах и для шифрования, и для дешифрования используется один и тот же ключ [10].

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

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

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

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

· количество всех возможных ключей;

· среднее время, необходимое для криптоанализа.

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

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

Для современных криптографических систем защиты информации сформулированы следующие общепринятые требования:

· зашифрованное сообщение должно поддаваться чтению только при наличии ключа;

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

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

· знание алгоритма шифрования не должно влиять на надежность защиты;

· незначительное изменение ключа должно приводить к существенному изменению вида зашифрованного сообщения даже при использовании одного и того же ключа;

· структурные элементы алгоритма шифрования должны быть неизменными;

· дополнительные биты, вводимые в сообщение в процессе шифрования, должен быть полностью и надежно скрыты в шифрованном тексте;

· длина шифрованного текста должна быть равной длине исходного текста;

· не должно быть простых и легко устанавливаемых зависимостью между ключами, последовательно используемыми в процессе шифрования;

· любой ключ из множества возможных должен обеспечивать надежную защиту информации;

· алгоритм должен допускать как программную, так и аппаратную реализацию, при этом изменение длины ключа не должно вести к качественному ухудшению алгоритма шифрования [10].

 

 

 

 

 

 

 

 

 

 

 

 

 

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

4.1 Классификация криптографических методов

Все многообразие существующих криптографических методов можно свести к следующим классам преобразований:

 

 

Перестановки

 

 
Рис.1.1.Классы преобразований симметричных криптосистем.

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

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

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

Блочные шифры собой последовательность (с возможным повторением и чередованием) основных методов преобразования, применяемую к блоку (части) шифруемого текста. Блочные шифры на практике встречаются чаще, чем “чистые” преобразования того или иного класса в силу их более высокой криптостойкости [8].

Перестановкой s набора целых чисел (0,1,...,N-1) называется его переупорядочение. Для того чтобы показать, что целое i перемещено из позиции i в позицию s(i), где 0 £(i) < n , будем использовать запись

s=(s(0), s(1),..., s(N-1)).

Число перестановок из (0,1,...,N-1) равно n !=1*2*...*(N-1)*N. Введем обозначение s для взаимно-однозначного отображения (гомоморфизма) набора S={s 0 ,s 1 ,...,s N-1 }, состоящего из n элементов, на себя.

s: S ® S

s: s i ®s s (i) , 0 £ i < n

Будем говорить, что в этом смысле s является перестановкой элементов S. И, наоборот, автоморфизм S соответствует перестановке целых чисел (0,1,2,.., n -1).

Криптографическим преобразованием T для алфавита Zm называется последовательность автоморфизмов: T={T(n) :1£n<¥}

T(n) : Zm,n ®Zm,n , 1£n<¥

Каждое T(n) является, таким образом, перестановкой n -грамм из Zm,n .

Поскольку T(i) и T(j) могут быть определены независимо при i¹j, число криптографических преобразований исходного текста размерности n равно (mn )! .Оно возрастает непропорционально при увеличении m и n : так, при m =33и n =2 число различных криптографических преобразований равно 1089!. Отсюда следует, что потенциально существует большое число отображений исходного текста в шифрованный [9].

 

 

 

 

 

 

 

 

                                     5 Системы подстановок

Определение. Подстановкой p на алфавите Zm называется автоморфизм Zm , при котором буквы исходного текста t замещены буквами шифрованного текста p(t):

Zm - Zm ; p: t -p(t).

Набор всех подстановок называется симметрической группой Zm è будет в дальнейшем обозначаться как SYM(Zm ).

Утверждение SYM(Zm ) c операцией произведения является группой, т.е. операцией, обладающей следующими свойствами:

Замкнутость : произведение подстановок p1 p2 является подстановкой:

p: t-p1 (p2 (t)).

Ассоциативность : результат произведения p1 p2 p3 не зависит от порядка расстановки скобок:

(p1 p2 )p3 =p1 (p2 p3 )

Существование нейтрального элемента : постановка i, определяемая как i(t)=t, 0£t<m, является нейтральным элементом SYM(Zm ) по операции умножения: ip=pi для "pÎSYM(Zm ).

Существование обратного : для любой подстановки p существует единственная обратная подстановка p-1 , удовлетворяющая условию

pp-1 =p-1 p=i.

Число возможных подстановок в симметрической группе Zm называется порядком SYM(Zm ) и равно m! .

Определение. Ключом подстановки k для Zm называется последовательность элементов симметрической группы Zm :