Введение

Сейчас жизнь устроена так, что между людьми происходит интенсивный обмен информацией, причем часто на громадные расстояния. Для этого земной шар опутали различными видами технических средств связи: телеграфом, телефоном, радио, телевидением и т.д. Люди давно поняли, что информация может быть настоящим сокровищем, и, поэтому, много усилий тратят на ее охрану и добывание. Без тайн не может быть не только государства, но даже малой общности людей - без них нельзя выиграть сражение или выгодно продать товар, одолеть своих политических противников в жесткой борьбе за власть или сохранить первенство в технологии. Тайны составляют основу науки, техники и политики любой человеческой формации. История хранит так много секретов, что просто удивительно, до чего людям они необходимы. Информация, которая нуждается в защите, возникает в самых разных жизненных ситуациях. Обычно в таких случаях говорят, что информация содержит тайну или является защищаемой,  конфиденциальной, секретной. Для наиболее типичных, часто встречающихся ситуаций такого типа введены даже специальные понятия: государственная тайна; • военная тайна;• коммерческая тайна; • юридическая тайна; • врачебная тайна и т.д.

.          Когда же надо защищать информацию?

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

 Зачем необходима защита информации?

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

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

Стеганография- набор средств и методов скрытия факта передачи сообщения.

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

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

Из истории криптографии.

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

Диск Энея. История криптографии связана с большим количеством дипломатических и военных тайн и окутана туманом легенд. Один из первых изобретателей шифров, известный по имени - греческий полководец Эней Тактика. Он создал простое, но очень удобное устройство - «диск Энея».( Слайд)

Это был небольшой диск, с просверленными вдоль его края отверстиями. Отверстия соответствовали буквам алфавита. Для того чтобы зашифровать текст, нить вдевали в эти отверстия так, чтобы по ходу нити последовательность отверстий была такой же, как у соответствующих им букв в тексте. Например, чтобы зашифровать слово «Иван», нить сначала продевали в отверстие, отвечающее букве И, затем в, и так далее. Когда получатель сообщения начинал вытягивать эту нить, то он мог прочитать все буквы, правда только в обратном порядке. Если сообщение было перехвачено, гонец легко мог его уничтожить, выдернув нить. Свой след в истории криптографии оставили многие хорошо известные исторические личности. В том числе кардинал Ришелье, король Генрих IV, Петр Великий и др. Петр I в 1712 году встречался с Лейбницем, чтобы уговорить его разработать проекты развития образования и государственного устройства в России.

Шифр «Сциталь». Этот шифр известен со времен войны Спарты и Персии против Афин. Спартанский полководец Лисандр получил от своего агента в стране персов шифрованное сообщение, которое позволило Лисандру опередить персов и разгромить их. Сообщение было написано на поясе официального гонца следующим образом: агент намотал пояс на сциталь (деревянный цилиндр определенного диаметра) и написал на поясе сообщение вдоль сциталя; потом он размотал пояс, и получилось, что поперек пояса в беспорядке написаны буквы. Гонец не догадывался, что узор в его красивом поясе на самом деле содержит зашифрованную информацию. Лисандр взял сциталь такого же диаметра, аккуратно намотал на него пояс и вдоль сциталя прочитал сообщение от своего агента.

Шифр Цезаря. Этот шифр реализует следующее преобразование открытого текста: каждая буква открытого текста заменяется третьей после неё буквой в алфавите. Например, открытый текст КРИПТОГРАФИЯ при таком способе шифрования преобразуется в шифротекст  НУЛТХСЁУГЧЛВ. Отметим, что Цезарь заменял букву третьей после неё буквой, но можно заменять и пятой, и какой-нибудь другой. Главное - чтобы тот, кому посылается шифрованное сообщение, знал величину сдвига

Применение математики

 Шифр Кардано.Одним из способов ведения секретной переписки является, так называемый способ «решётки». Его придумал Джироламо Кардано, известный римский математик.Желающие вести тайную переписку по этому способу готовят решётку, то есть бумажный квадрат с прорезанными окошечками. Окошечки размещены не произвольно, а в определенном порядке, который станет ясен из дальнейшего.

Пусть требуется послать товарищу такую записку:

Лёд тронулся. Командовать парадом буду я. Грузите апельсины бочках.

Математика-гимнастика ума

Наложив решётку на листок бумаги, мы пишем сообщение букву за буквой в окошечках решётки. Так как окошек 16, то сначала помещается только часть записки. Сняв решётку, мы увидим запись, представленную на рисунке. Здесь ничего засекреченного пока нет. Но это только начала; записка в таком виде не останется. Поворачиваем решетку по часовой стрелке на четверть оборота. При новом положении решетки все ранее написанные буквы закрываются, а окошечках появляется чистая бумага. В них пишут следующие 16 букв секретного сообщения. Если теперь убрать решетку, получим запись, показанную на следующем рисунке:  Такую запись не поймет не только посторонний человек, но и сам писавший, если позабудет текст своего сообщения.

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

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

Адресат наложит свою решётку на текст, обратив её цифрой 1 вверх, и выпишет те буквы, которые появятся в окошечках. Это будут первые 16 букв сообщения. После четырёх поворотов записка будет прочтена.

Число различных решёток чрезвычайно велико. Все решётки, какие можно изготовить для 64 клеточного квадрата, отмечены на рисунке. Можно выбрать для окошечек любые 16 клеток, заботясь лишь о том, чтобы в числе взятых клеток не было двух с одинаковыми номерами. Для той решётки, которую использовал, были взяты следующие номера клеток: 2, 4, 5, 14, 9, 11, 7, 16, 8, 15, 3, 12, 10, 6, 13, 1. Ни один номер не повторяется.

Подсчитаем математически, сколько может существовать разных решеток. Клетку 1 можно взять в качестве окошка в 4-х местах. В каждом случае можно присоединить клетку 2, взяв её также в 4-х местах. Следовательно, два окошка можно наметить 4 х 4, т.е. 16 способами. Три окошка - 4х4х4=64 способа. Таким образом, устанавливаем, что 16 окошек можно набрать 416 способами (произведение 16 четверок). Число это превышает 4000 миллионов. Если даже считать наш расчёт преувеличенным на несколько сот миллионов (так как неудобно пользоваться решетками с примыкающими друг к другу окошечками, и эти случаи надо исключить), то все же остается несколько тысяч миллионов решеток.

Однако оба участника переписки должны быть начеку, чтобы противник не перехватил решётку. Лучше всего не хранить решетку, а вырезывать её при получении письма и уничтожать сразу после прочтения. Но как запомнить расположение окошек? Здесь опять нам на помощь приходит математика. Будем обозначать окошки цифрой 1, а остальные клетки цифрой 0. Тогда первый ряд клеток решетки получит такое обозначение:

01010010,

или, отбросив передний нуль, - 1010010.

Остальные ряды, если отбросить передние нули обозначаются так:

1000

10100010

10000

1000100

10001000

100010

10001

Чтобы упростить запись этих чисел, будем считать, что они записаны не по десятичной системе, а по «двоичной». Это значит, что единица, стоящая справа, больше соседней не в 10 раз, а только в 2 раза. Единица в конце числа означает как обычно простую единицу, на предпоследнем месте означает двойку, на третьем с конца - четверку, на четвертом - восьмерку, на пятом - шестнадцать и т.д.

То есть число 1010010, обозначающее расположение окошек первого ряда, в десятичной системе будет равно 64+16+2=82, потому что нули указывают на отсутствие единиц данного разряда.

Число 1000 заменится в десятичной системе числом 8. И далее:

101000102 = 128+32+2 = 16210

100002= 1610

10001002= 64+4 = 6810

100010002= 128+8 = 13610

1000102 = 32 + 2 = 3410

100012 = 16 + 1 = 1710

Запомнить числа 82, 8, 162, 16, 68, 136, 34, 17 не так уж трудно. А, зная их всегда можно получить ту первоначальную группу чисел, из которой они получены и которые прямо указывают расположение окошечек в решетке.

Как это делается, покажем на примере первого числа - 82. Разделим его на 2, чтобы узнать, сколько в нем двоек; получим 41; остатка нет, - значит, на последнем месте, в разряде простых единиц, должно быть 0. Полученное число двоек 41, делим на 2, чтобы узнать, сколько в нашем числе четверок:

41 : 2 = 20, остаток 1.

Это значит, что в разряде двоек, т.е. на предпоследнем месте, имеется цифра 1.

Далее делим 20 на 2, чтобы узнать сколько в нашем числе восьмерок:

20 : 2 = 10, остатка нет, - значит на месте четверок стоит 0.

10 : 2 = 5, остаток равен нуля, на месте восьмерок 0.

5 : 2 = 2, остаток 1: в разряде 16-к цифра 1.

Наконец, делим 2 на 2 и узнаём, что в числе одна 64-ка: в этом разряде должна быть 1, а в разряде 32-к - 0.

Итак, все цифры искомого числа определились:  1010010. Так как здесь всего 7 цифр, а в каждом ряду решетки 8 клеток, то ясно, что один нуль впереди был опущен, и в расположении окошек в первом ряду определяется цифрами: 01010010, то есть окошки имеются на 2, 4 и 7 местах.

Так же восстанавливается расположение окошек и в прочих рядах.

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

Матричный способ шифрования

Рассматриваемый шифр можно отнести к шифрам замены.

Для начала составим таблицу, в которой каждой букве русского алфавита будут соответствовать числа, взятые по порядку от 1 до 33 (34 - символ пробела )

Зашифруем следующую фразу: «агент б крот»

Заменим каждый символ этого сообщения соответствующим числом из таблицы: 1 4  6 15 20 34 2 34 12 18 16 20.

Составим из этих чисел три квадратных матрицы второго порядка:

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

Возьмём в качестве шифра квадратную матрицу второго порядка:

3    2

4    3

Ключом будет служить матрица, обратная матрице - шифру. Чтобы её найти нам понадобятся некоторые знания из алгебры матриц.

Понятие матрицы тесно связано с понятием систем линейных уравнений. Рассмотрим систему двух линейных уравнений с двумя неизвестными:

a11x1+a12x2 = b1;

a21x1+a22x2 = b2;

Коэффициенты при неизвестных составляют квадратную таблицу

        ,        ,

называемую матрицей из двух строк и двух столбцов. Числа a11, a12, a21, a22 называются элементами матрицы. Диагональ матрицы, составленная из элементов a11, a22, называется главной диагональю. Квадратная матрица второго порядка называется единичной, если элементы главной диагонали равны единице, а остальные элементы равны нулю:

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

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

              ▪                   =

Произведение прямой и обратной матрицы равно единичной матрице.

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

                 ▪                   =              

                                                       Б

                                     =                ,

Получим две системы линейных уравнений:

     3b11+2b21 = 1;                    3b12+2b22=0;

       4b11+3b21  = 0;                  4b12+3b22=1.

Решая полученные системы найдём элементы матрицы ключа:

b11=3, b12= -2, b21= - 4, b22=3.

Итак, мы получили ключ, с помощью которого получатель сможет расшифровать секретное сообщение.

Нам осталось зашифровать это сообщение. Сделаем это, умножив исходные матрицы на матрицу - шифр.

              ▪                   =

              ▪                   =

              ▪                   =

Таким образом, мы передадим адресату следующий набор чисел:

19 14 78 57 196 142 142 106 108 78 128 92.

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

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

Криптосистема RSA.

Криптосистема RSA, предложенная в 1977 году Ривестом, Шамиром и Адлеманом, предназначена для шифрования и цифровой подписи. В настоящее время RSA является наиболее распространенной криптосистемой . Статус де-факто послужил причиной включения криптосистемы RSA в принятые ранее криптографические стандарты. Так, финансовый стандарт США ANSI X9.30 предусматривал использование федерального стандарта цифровой подписи DSS. Выпущенная позднее версия стандарта ANSI X9.31 была дополнена криптосистемой RSA. Последний является так же частью многих официальных стандартов, в частности международных стандартов ISO 9796 и ITU-T X.509, SWIFT, французского финансового стандарта ETABAC 5, австралийского стандарта управления ключами AS2805.6.5.3. Криптосистема RSA широко применяется в составе различных стандартов и протоколов Internet, включая PEM, S/TIME, PEM-MIME, S-HTTP и SSL.

Возможно ли использование RSA в России? С точки зрения правовых норм это исключено – RSA не входит ни в один из действующих на территории России криптографических стандартов. Отметим, что стандарты двухключевого шифрования и управления ключами в России также пока не приняты. Таким образом, разработчик криптографических приложений поставлен перед выбором: построить схему управления ключами по методу полной матрицы, экспоненциального ключевого обмена Диффи-Хеллмана или воспользоваться методом цифрового конверта (шифрование сеансового ключа при помощи двухключевого криптоалгоритма).

Недостатки существующего не одно десятилетие метода полной матрицы хорошо известны. Протокол Диффи-Хеллмана предполагает двусторонний обмен открытыми ключами и наличие сертификатов у отправителя и получателя сообщений. В случае односторонней аутентификации (сертификат имеется только у одной из сторон) предпочтение отдается последнему методу. В этой ситуации выбор RSA вполне оправдан – метод цифрового конверта на базе криптоалгоритма RSA описан в стандарте PKCS и применяется в протоколе SSL и других стандартах Internet (PEM, PEM-MIME и т.д.).

RSA многие годы противостоит интенсивному криптоанализу. Криптостойкость RSA основана на трудоемкости разложении на множители (факторизации) больших чисел. Открытый и секретный ключи являются функциями двух больших (100 ~ 200 двоичных разрядов или даже больше) простых чисел. Предполагается, что задача восстановления открытого текста по шифротексту и открытому ключу эквивалентна задаче факторизации.

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

n=pq.

Далее случайным образом выбирается ключ шифрования e, такой, что e и φ(n)=(p-1)(q-1) являются взаимно простыми числами. Наконец расширенный алгоритм Евклида используется для вычисления ключа дешифрования d, такого, что

ed=1 mod φ(n).

Другими словами,

d=e-1 mod φ(n).

        Заметим, что d и n – так же взаимно простые числа. Числа e и n – открытый ключ, а d – секретный. Два простых числа p и q хранятся в секрете. Для шифрования сообщения m необходимо выполнить его разбивку на блоки, каждый из которых меньше n (для двоичных данных выбирается самая большая степень числа 2, меньшая n). То есть если p и q – 100-разрядные простые числа, то n будет содержать около 200 разрядов. И каждый блок сообщения mi должен иметь такое же число разрядов. (Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, тобы гарантировать, что блоки всегда будут меньше n.) Зашифрованное сообщение c будет состоять из блоков ci той же самой длины. Шифрование сводиться к вычислению

ci=mie mod n.

При дешифровании для каждого зашифрованного блока ci вычисляется

mi=cid mod n.

Последнее справедливо, так как

Cid=(mie)e=mied=mikφ(n)+1=mi*mi kφ(n)=mi*1=mi.

Все вычисления выполняются по модулю n.

        Отметим, что сообщение может быть зашифровано с помощью d, а дешифровано с помощью e, возможен любой выбор.

        Рассмотрим короткий пример. Если

p=47 и q=71, то n=pq=3337.

Ключ e не должен иметь общих множителей с

φ(n)=46*70=3220.

Выберем (случайное) e равным 79. В этом случае d=79-1 mod 3220 = 1019. Опубликуем e и n, сохранив в секрете d. Для шифрования сообщения

m=6882326879666683

сначала разобьем его на блоки. Для выбранных параметров ограничимся блоками по три десятичных разряда. Сообщение разбивается на шесть блоков mi:

m1=688

m2=232

m3=687

m4=966

m5=668

m6=003

Первый блок шифруется как 68879 mod 3337 = 1570 = c1. Выполняя те же операции для последующих блоков, создадим шифротекст сообщения:

c=15702756209122762423158.

Для дешифрования нужно выполнить возведение в степень, используя ключ дешифрования 1019:

15701019 mod 3337 = 688 = m1.

Аналогично восстанавливается оставшаяся часть сообщения.

Эффективность реализации

        Существует много публикаций, затрагивающих тему аппаратных реализаций RSA.

        Быстродействие аппаратной реализации RSA примерно в 1000 раз ниже, чем быстродействие аппаратной реализации DES. Быстродействие СБИС-реализации RSA с 512-битовым модулем – 64 Кбит/сек. Существуют также микросхемы RSA, которые оперируют с 1024-битовыми числами. В настоящее время разрабатываются микросхемы, которые, используя 512-битовый модуль, приблизятся к рубежу 1 Мбит/сек. Производители так же реализуют RSA в интеллектуальных карточках, однако производительность этих реализаций невысока. Программная реализация DES примерно в 100 раз быстрее программной реализации RSA. Эти оценки могут незначительно могут незначительно меняться в зависимости от используемых технологий, но RSA никогда не достигнет производительности симметрических алгоритмов.

        Шифрование RSA выполняются намного эффективнее, если правильно выбрать значение e. Чаще всего используются 3, 17 или 65537 = 216+1 – двоичное представление этого числа содержит только две единицы, поэтому для возведения в степень нужно выполнить лишь 17 умножений. Стандарт X.509 рекомендует число 65537, PEM – 3, PKCS#1 – 3 или 65537. Использование в качестве e любого из указанных значений (при условии, что сообщение дополняются случайными числами) не влияет на криптостойкость, даже если одно и то же значение e используется группой пользователей. Операции с секретным ключом можно ускорить при помощи китайской теоремы об остатках, если сохранить значения p и q, а так же заранее по секретному и открытому ключам вычислить вспомогательные значения: d mod (p-1), d mod (q-1) и q-1 mod p.

Криптостойкость RSA

        Предполагается, что криптостойкостью RSA зависит от проблемы разложения на множители больших чисел. Однако никогда не было доказано математически, что нужно разложить n на множители, чтобы восстановить m по c и e. Не исключено, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел. Так же можно атаковать RSA, угадав значение (p-1)(q-1). Однако этот метод не проще разложения n на множители. Доказано, что при использовании RSA раскрытие даже нескольких битов информации по шифротексту не легче, чем дешифрования всего сообщения. Самой очевидной атакой на RSA является разложение n на множители. Любой противник сможет получить открытый ключ e и модуль n. Чтобы найти ключ дешифрования d, противник должен разложить n на множители. Криптоаналитик может перебирать все возможные d, пока не подберет правильное значение. Но подобная силовая атака даже менее эффективна, чем попытка разложения n на множители. В 1993 г. Был предложен метод кирптоанализа, основанный на малой теореме Ферма. К сожалению, этот метод оказался медленнее разложения на множители. Существует еще одна проблема. Большинство общепринятых тестов устанавливает простоту числа с некоторой вероятностью. Что произойдет, если p или q окажется составным? Тогда у модуля n будет три или более делителей. Соответственно некоторые делители будут меньше рекомендованной величины, что, в свою очередь, открывает возможности для атаки путем факторизации модуля. Другая опасность заключается в генерации псевдопростых чисел (чисел Кармайкла), удовлетворяющих тестам на простоту, но при этом не являющихся простыми. Однако вероятность генерации таких чисел пренебрежимо мала. На практике, последовательно применяя набор различных тестов на простоту, можно свести вероятность генерации составного числа до необходимого минимума.

Итоги по безопасности

        На основании известных атак можно сформулировать следующие ограничения при использовании RSA:

• знание одной пары показателей шифрования/дешифрования для данного модуля позволяет злоумышленнику разложить модуль на множители;
• знание одной пары показателей шифрования/дешифрования для данного модуля позволяет злоумышленнику вычислить другие пары показателей, не расладывая модуль на множители;
• в криптографических протоколах с использованием RSA общий модуль использоваться не должен. (Это являеться очевидным следствием предыдущих двух пунктов.);
• для предотвращения раскрытия малого показателя шифрования сообщения должны быть дополнены («набиты») случайными значениями;
• показатель дешифрования должен быть большим.

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

Криптосистема ЭльГамаля.

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

        Для генерации пары ключей сначала выбираются простое число p и два случайных числа, g и x; оба этих числа должны быть меньше p. Затем вычисляется

y=gx mod p.

Открытым ключом являются y, g и p. И g, и p можно сделать общими для группы пользователей. Секретным является x.

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

        Чтобы подписать сообщение M, сначала выбирается случайное число k, взаимно простое с p-1. Затем вычисляется a=gk mod p, и с помощью расширенного алгоритма Евклида из уравнения

M=(xa+kb) mod (p-1)

находиться b. Подписью является пара чисел: a и b. Случайное значение k должно храниться в секрете. Для проверки подписи необходимо убедиться, что

yaab mod p = gM mod p.

Каждая новая подпись требует нового значения k, и это значение должно выбираться случайным образом. Если злоумышленник раскроет k, используемое Алисой, он сможет раскрыть секретный ключ Алисы x. Если злоумышленник сможет получить два сообщения, подписанные при помощи одного и того же k, он сможет раскрыть x, даже не зная k.

        Рассмотрим простой пример. Выберем p=11 и g=2. Пусть секретный ключ x=8. Вычислим

y=gx mod p = 28 mod 11 = 3.

Открытым ключом являются y=3, g=2 и p=11. Чтобы подписать M=5, сначала выберем случайное число k=9. Убедимся, что gcd(9,10)=1. Далее вычислим

a=gk mod p = 29 mod 11 = 6,

и затем с помощью расширенного алгоритма Евклида найдем b из уравнения

5=(8*6+9*b) mod 10.

Решение: b=3, а подпись представляет собой пару: a=6 и b=3. Для проверки подписи убедимся, что yaab mod p = gM mod p:

3663 mod 11 = 25 mod 11.

Шифрование/дешифрование

        Некоторая модификация позволяет использовать криптосистему для шифрования/дешифрования сообщений.

        Для шифрования сообщения M сначала выбирается случайное число k, взаимно-простое с p-1. Затем вычисляются:

a=gk mod p,

b=ykM mod p.

Пара (a,b) является шифротекстом. Отметим, что шифротекст в два раза длиннее открытого текста.

        Для дешифрования (a,b) вычисляются

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

Хеш-функции

        Односторонняя функция H применяется к сообщению произвольной длины M и возвращает значение h=H(M) фиксированной длины m. Многие функции позволяют значение фиксированной длины по входным данным произвольной длины, но однонаправленные (или односторонние) хеш-функции обладают рядом дополнительных свойств:

• зная M, легко вычислить h;
• при заданном h задача нахождения M, для которого H(M)=h, должна быть вычислительно-трудоемкой;
• при заданном M задача нахождения другого сообщения M’, для которого H(M)=H(M’), должна быть вычислительно трудоемкой.

        Смысл применения однонаправленных хеш-функций и состоит в обеспечении для M уникального значения – «отпечатка пальца» сообщения. Если Алиса подписала M цифровой подписью с использованием хеш-функции H(M), а боб может создать другое сообщение M' отличное от M, для которого H(M)=H(M'), то Боб сможет утверждать, что Алиса подписала сообщение M'. В некоторых приложениях необходимо выполнение дополнительного требования, называемого устойчивостью к коллизиям. Смысл данного требования заключается в том, что задача нахождения двух случайных сообщений M и M', для которых H(M)=H(M’), должна быть вычислительно-трудоемкой (с экспоненциальным объемом перебора).

        Следующий протокол, впервые описанный Юваловым, показывает, как Алиса может воспользоваться коллизиями для обмана Боба.

1. Алиса готовит две версии контракта: одну, выгодную для Боба, и другую, приводящую его к банкротству.
2. Алиса вносит несколько незначительных изменений в каждый документ и вычисляет хеш-функции. (Этими изменениями могут быть действия, подобные следующим: замена одного пробела комбинацией пробелов, вставка одного - двух пробелов перед возвратом каретки и так далее. Производя или не производя по одному изменению в каждой из 32 строк, Алиса может Легко получить 232 различных документов.)
3. Алиса сравнивает хеш-значения для каждого изменения в каждом из двух документов, разыскивая пару, для которой эти значения совпадают. (Если выходом хеш-функции является 64-битное значение, Алиса, как правило, сможет найти совпадающую пару выполнив 232 сравнений.) Таким образом, она получает два документа, дающих одинаковое значение хеш-функции.
4. Алиса получает подписанную Бобом выгодную для него версию контракта, используя протокол, в котором он подписывает только значение хеш-функции.
5. Спустя некоторое время, Алиса подменяет контракт, подписанный Бобом, другим, которого он не подписывал. Теперь она может убедить арбитра в том, что Боб подписал другой контракт.

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

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

Федеральный стандарт СШФ – SHS (алгоритм SHA)

        Национальный Институт Стандартов США при участии АНБ разработал алгоритм вычисления хеш-функции SHA, используемый в алгоритме цифровой подписи DSA стандарта DSS.

        Для любого входного сообщения длиной меньше 264 битов SHA выдает 160-битовый «дайджест» сообщения. Далее «дайджест» подается на вход DSA, который вычисляет подпись для сообщения. Подписывание «дайджеста» вместо сообщения часто повышает эффективность процесса, так как «дайджест» намного меньше, чем само сообщение. Тот же «дайджест» сообщения должен быть получен тем, кто проверяет подпись. При использовании SHA задача поиска сообщения, соответствующего данному «дайджесту», или двух различных сообщений с одинаковым «дайджестом» является вычислительно-трудоемкой. Любые изменения сообщения, произошедшие во время передачи, с очень высокой вероятностью приведут к изменению «дайджеста», и подпись не пройдет проверку.

Стандарт России – ГОСТ Р 34.11-94

        Разработанная российскими криптографами хеш-функция описана в стандарте ГОСТ 34.11-94. В ней используется блочный шифр ГОСТа 28147-89, хотя теоретически может использоваться любой блочный шифр с 64-битным блоком и 256-битным ключом. Хеш-функция выдает 256-битное значение.

        Еще стоит отметить такие известные хеш-функции, как MD2, MD4, MD5 и RIPEMD-160.