LINEBURG


страница 1
(всего 3)

ОГЛАВЛЕНИЕ

След. стр. >>

Министерство образования Российской Федерации

Санкт-Петербургский государственный институт точной
механики и оптики (технический университет)




Ю.А.Гатчин, А. Г. Коробейников




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

Учебное пособие




Санкт-Петербург 2002
2


УДК 511
Ю.А.Гатчин, А. Г. Коробейников. Основы криптографических алгоритмов
Учебное пособие. СПб: ГИТМО (ТУ), 2002. 29 с.


В учебном пособии рассматриваются основы современных
математических криптографических алгоритмов, фундаментом которых
является прикладная теория чисел.
Рассмотрены криптосистемы с секретным ключом (одноключевые,
симметричные или классические), а также криптосистемы с открытым
ключом (асимметричные). Кроме того, представлены основные положе-
ния криптографического протокола "электронная подпись". В каждом раз-
деле рассмотрены примеры на соответствующие темы.
Предназначено для студентов, обучающихся по специальности
0754 "Комплексная защита объектов информатизации".


Илл. – 3, список литературы – 8 наим.




? Cанкт-Петербургский государствен-
ный институт точной механики и оптики
(технический университет), 2002
? Ю.А.Гатчин, А.Г. Коробейников 2002
3


ВВЕДЕНИЕ
Математическая криптография возникла как наука о шифровании
информации, т.е. как наука о криптосистемах. В классической шенноновс-
кой модели системы секретной связи имеют два полностью доверяющих
друг-другу участника, которым необходимо передавать между собой ин-
формацию, не предназначенную для третьих лиц. Такая информация на-
зывается конфиденциальной или секретной. Отсюда возникает задача
обеспечения конфиденциальности, т.е. защита секретной информации от
противника. Эта задача, по крайней мере исторически, – первая задача
криптографии. Она традиционно решается с помощью криптосистем.
При обмене информацией между участниками часто возникает
ситуация, когда информация не является конфиденциальной, но важен
факт поступления сообщений в неискаженном виде, т.е. наличие гарантии,
что никто сумеет не подделать сообщение. Такая гарантия называется
обеспечением целостности информации и составляет вторую задачу крип-
тографии.
Для предотвращения угрозы контроля за источниками информации
(откуда пересылаются сообщения) необходима система контроля за досту-
пом к ресурсам, которая должна удовлетворять двум, казалось бы, взаим-
но исключающим требованиям. Во – первых, всякий желающий должен
иметь возможность обратиться к этой системе анонимно, а во – вторых,
при этом все же доказать свое право на доступ к ресурсам. Примером мо-
гут служить бумажные купюры. Если ресурсом является некоторый товар,
то наличие у покупателя достаточного количества купюр является доказа-
тельством его права на доступ к ресурсу. С другой стороны, хотя каждая
бумажная купюра и имеет уникальный номер, отслеживать купюры по но-
мерам практически невозможно, т.е. определить, кто ее использовал и в
каких платежах, практически невозможно. Аналог этого свойства в
криптографии называется неотслеживаемостью. Обеспечение неотслежи-
ваемости –третья задача криптографии.
Если задача обеспечения конфиденциальности решается с по-
мощью криптосистем, то для обеспечения целостности и неотслеживае-
мости разрабатываются криптографические протоколы.
В первой части кратко рассмотрена история криптографии и её
основные понятия. Приведены основные классические шифры, такие как,
шифр Цезаря, маршрутная транспозиция, таблица Виженера, одноразовый
блокнот и т.д.
Во второй части изучаются основные свойства диофантова уравне-
ния и метод его решения при помощи алгоритма Евклида. Рассмотрена
криптосистема без передачи ключей.
4


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


1. КЛАССИЧЕСКИЕ ШИФРЫ И ОСНОВНЫЕ
ПОНЯТИЯ
1.1. ИЗ ИСТОРИИ КРИПТОГРАФИИ
Термин криптография (тайнопись) ввел Д. Валлис. Потребность
шифровать и передавать шифрованные сообщения возникла очень давно.
Так, еще в V-IV вв. до н. э. греки применяли специальное шифрующее
устройство. По описанию Плутарха, оно состояло из двух палок одинако-
вой длины и толщины. Одну оставляли себе, а другую отдавали отъезжа-
ющему. Эти палки называли скиталами. Когда правителям нужно было
сообщить какую-нибудь важную тайну, они вырезали длинную и узкую,
вроде ремня, полосу папируса, наматывали ее на свою скиталу, не остав-
ляя на ней никакого промежутка, так чтобы вся поверхность палки была
охвачена этой полосой. Затем, оставляя папирус на скитале в том виде,
как он есть, писали на нем все, что нужно, а написав, снимали полосу и
без палки отправляли адресату. Так как буквы на ней разбросаны в бес-
порядке, то прочитать написанное можно только при помощи соответст-
вующей скиталы, намотав на нее без пропусков полосу папируса.
Аристотелю принадлежит способ дешифрования этого шифра. На-
до изготовить длинный конус и, начиная с основания, обертывать его лен-
той с шифрованным сообщением, постепенно сдвигая ее к вершине. В ка-
кой-то момент начнут просматриваться куски сообщения. Так можно оп-
ределить диаметр скиталы.
В Древней Греции (II в. до н. э.) был известен шифр, называемый
квадрат Полибия. Это устройство представляло собой квадрат 5 х 5,
столбцы и строки которого нумеровали цифрами от 1 до 5. В каждую
клетку этого квадрата записывалась одна буква. (В греческом варианте од-
на клетка оставалась пустой, в латинском – в одну клетку помещали две
буквы i и j.) В результате каждой букве отвечала пара чисел и шифрован-
ное сообщение превращалось в последовательность пар чисел.
Пример 1. 13 34 22 24 44 34 15 42 22 34 43 45 32
Это сообщение записано при использовании латинского варианта квад-
рата Полибия, в котором буквы расположены в алфавитном порядке.
("Cogito, ergo sum" – лат, "Я мыслю, следовательно существую"). ¦
В 1 в. н.э. Ю. Цезарь во время войны с галлами, переписываясь со
своими друзьями в Риме, заменял в сообщении первую букву латинского
алфавита (А) на четвертую (D), вторую (В) – на пятую (Е), наконец, по-
следнюю – на третью:
? ABCDEFGHI J KLMNOPQRSTUVWXYZ
? DEFGHI J KLMNOP QRSTUVWXYZABC
Пример 2. Донесение Ю. Цезаря Сенату об одержанной им победе
над Понтийским царем выглядело так:
6


YHQL YLGL YLFL("Veni, vidi, vici" – лат. "Пришел, увидел, победил") .¦
Император Август (1 в. н. э.) в своей переписке заменял первую
букву на вторую, вторую – на третью и т. д., наконец, последнюю – на
первую:
? ABCDEFGHI J KLMNOPQRSTUVWXYZ
? BCDEFGHI J KLMNOPQRSTUVWXYZA
Пример 2. Любимое изречение императора Августа выглядело так:
GFTUJOB MFOUF ("Festina lente" – лат. "Торопись медленно") .¦
Квадрат Полибия, шифр Цезаря входят в класс шифров, называе-
мых подстановка или простая замена, т.е. Это такой шифр, в котором
каждой букве алфавита соответствует буква, цифра, символ или какая-
нибудь их комбинация.
В известных рассказах “Пляшущие человечки” Конан Дойля и “Зо-
лотой жук” Эдгара По используемые шифры относятся к указанному
классу шифров. В другом классе шифров – перестановка – буквы сооб-
щения каким-нибудь способом переставляются между собой. К этому
классу принадлежит шифр скитала.

1.2. МАРШРУТНАЯ ТРАНСПОЗИЦИЯ

К классу перестановка относится шифр маршрутная транспозиция
и его вариант постолбцовая транспозиция. В каждом из них в данный
прямоугольник [n?m] сообщение вписывается заранее обусловленным
способом, а столбцы нумеруются или обычным порядком следования, или
в порядке следования букв ключа – буквенного ключевого слова.
Пример 3. В первом прямоугольнике столбцы нумеруются в обыч-
ном порядке следования – слева направо, а во втором – в порядке следова-
ния букв слова “Пушкин”. Используя расположение букв этого ключа в
алфавите, получим набор чисел [4 5 6 2 1 3]:
4 5 6 2 1 3
1 2 3 4 5 6
д е л а д а
д е л а д а
в н о м и н
в н о м и н
у в ш и х д
у в ш и х д
н е й п р е
н е й п р е
д а н ь я с
д а н ь я с
т а р и н ы
т а р и н ы
г л у б о к
г л у б о к
о й а б в г
о й а б в г

В первом случае шифрованный текст найдем, если будем выписы-
вать буквы очередного столбца в порядке следования столбцов (прямом
или обратном), во втором, – если будем выписывать буквы столбца в по-
рядке следования букв ключа. Таким образом, будем иметь:
7


1) двундтго енвеаалй лошйнруа амипьибб дихрянов андесыкг;
2) дихрянов амипьибб андесыкг двундтго енвеаалй лошйнруа. ¦
Термин “шифр” арабского происхождения. В начале XV в. арабы
опубликовали энциклопедию “Шауба Аль-Аща”, в которой есть специаль-
ный раздел о шифрах. В этой энциклопедии указан способ раскрытия
шифра простой замены. Он основан на различной частоте повторяемости
букв в тексте. В этом разделе есть перечень букв в порядке их повторяе-
мости на основе изучения текста Корана. Заметим, что в русском тексте
чаще всего встречается буква “О”, затем буква “Е” и на третьем месте сто-
ят буквы “И” и “А”. Более точно: на 1000 букв русского текста в среднем
приходится 90 букв “О”, 72 буквы “Е” или “Ё”, 60 букв “И” и “А” и т.д.
Неудобство шифров типа подстановка (простая замена) в случае
использования стандартного алфавита очевидно. Таблица частот встречае-
мости букв алфавита позволяет определить одни или несколько символов,
а этого иногда достаточно для дешифрования всего сообщения (“Пля-
шущие человечки” Конан Дойля или “Золотой жук” Эдгара По). Поэтому
обычно пользуются разными приемами, чтобы затруднить дешифрование.
Для этой цели используют многобуквенную систему шифрования – сис-
тему, в которой одному символу отвечает одна или несколько комбинаций
двух и более символов. Другой прием – использование нескольких алфа-
витов. В этом случае для каждого символа употребляют тот или иной ал-
фавит в зависимости от ключа, который связан каким-нибудь способом с
самим символом или с его порядком в передаваемом сообщении.

1.3. ТАБЛИЦА ВИЖЕНЕРА

В процессе шифрования (и дешифрования) используется таблица
Виженера, которая устроена следующим образом: в первой строке выпи-
сывается весь алфавит, в каждой следующей осуществляется циклический
сдвиг на одну букву. Так получается квадратная таблица, число строк ко-
торой равно числу столбцов в алфавите. Чтобы зашифровать какое-нибудь
сообщение, поступают следующим образом. Выбирается слово – лозунг и
подписывается с повторением над буквами сообщения.
Чтобы получить шифрованный текст, находят очередной знак ло-
зунга, начиная с первого в вертикальном алфавите, а ему соответствую-
щий знак сообщения в горизонтальном.
Пример 4. Таблица 1, составлена из 31 буквы русского алфавита
(без букв Ё и Ъ).
Выбираем лозунг – математика. Находим столбец, отвечающий
букве "м" лозунга, а затем строку, соответствующую букве "к". На пересе-
чении выделенных столбца и строки находим букву "ц". Так продолжая
дальше, находим весь шифрованный текст.
математикаматематикаматема
криптографиясер ьезнаянаука
8


таблица 1
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я
Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А
В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б
Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В
Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г
Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д
Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е
З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж
И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З
Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И
К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й
Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К
М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л
Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М
О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н
П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О
Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П
С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р
Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С
У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т
Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У
Х Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф
Ц Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х
Ч Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц
Ш Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч
Щ Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш
Ь Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ
Ы Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь
Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы
Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э
Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю



ц р ь ф я о хш кф фя д к э ь ч пч а л н т шц а¦
Наконец, к сообщению можно применять несколько систем шиф-
рования.

1.4. МОДИФИЦИРОВАННЫЙ ШИФР ЦЕЗАРЯ

Аббат Тритемеус – автор первой печатной книги о тайнописи (1518
г.) – предложил несколько шифров и среди них шифр, который можно
считать усовершенствованием шифра Цезаря. Этот шифр устроен так. Все
буквы алфавита нумеруются по порядку (от 1 до 31 в русском варианте).
Затем выбирают какое-нибудь слово, называемое "ключом", и подписыва-
ют под сообщением с повторением.
Чтобы получить шифрованный текст, складывают номер очеред-
ной буквы с номером соответствующей буквы ключа. Если полученная
сумма больше 31, то из нее вычитают 31. В результате получают последо-
вательность чисел от 1 до 31. Вновь заменяя числа этой последовательнос-
ти соответствующими буквами, получают шифрованный текст. Разбиваем
этот текст на группы одной длины, получают шифрованное сообщение.
Пример 5. Выбираем ключевое слово "Пособие". Составляем сооб-
щение "сессия начинается в конце семестра"
сессия начина етсявк онцесе местра
по с о б и е п о с о б и е п о с о б и е п о с о б и е п о
9


Шифруем, разбиваем текст на группы длины 6, и получаем шифро-
ванное сообщение:
в фд а и и у р з ь э в о ш в о ф щ р ц э х б ч ы з ь ш б п ¦
Чтобы получить шифрованный текст, складывают номер очеред-
ной буквы с номером соответствующей буквы ключа. Если полученная
сумма больше 33, то из нее вычитают 33. В результате получают последо-
вательность чисел от 1 до 33. Вновь заменяя числа этой последовательнос-
ти соответствующими буквами, получают шифрованный текст. Разбивал
этот текст на группы одной длины (например, по 5), получают шифрован-
ное сообщение.
Если под ключом шифра понимать однобуквенное слово “В” (в
русском варианте), то мы получим шифр Цезаря.
Пример 6. Для сообщения из примера 5, получим:
фиффлв ргьлрг ихфввн трщифи пифхуг¦

1.5. ОДНОРАЗОВЫЙ БЛОКНОТ

Почти все используемые на практике шифры характеризуются как
условно надежные, поскольку они могут быть раскрыты в принципе при
наличии неограниченных вычислительных возможностей. Абсолютно на-
дежные шифры нельзя разрушить даже при наличии неограниченных вы-
числительных возможностей. Доказательство существования и единствен-
ности абсолютно надежного шифра получил К.Шеннон с помощью разра-
ботанного им теоретико-информационного метода исследования шифров.
Таким образом, единственный абсолютно надежный шифр, который ис-
пользуется на практике, это так называемый одноразовый блокнот, в ос-
нове которого лежит та же идея, что и шифре Цезаря. Рассмотрим его
основную идею.
В русском варианте число символов расширенного алфавита, т.е.
совокупности букв, а также знаков препинания и пробела между словами,
равно 44. Занумеровав все символы расширенного алфавита числами от 0
до 43, можно рассматривать любой передавамый текст, как последова-
тельность {an} чисел множества А={0,1,2,…,43}. Имея случайную после-
довательность {cn} из чисел множества А той же длины что и передавае-
мый текст (ключ), складываем по модулю 44 число an передаваемого текс-
та с соответствующим числом cn ключа
an+cn?bn(mod 44), 0? bn ? 43,
получим последовательность {bn} знаков шифрованного текста.
Чтобы получить передаваемый текст, можно воспользоваться тем
же ключом:
an?bn-c(mod 44), 0? an ? 43.
У двух абонентов, находящихся в секретной переписке, имеются
два одинаковых блокнота, составленных из отрывных страниц, на каждой
из которых напечатана таблица со случайными числами или буквами, т.е.
10


случайная последовательность чисел из множества А. Таблица имеет
только две копии: одна используется отправителем, другая – получателем.
Отправитель свой текст шифрует указанным выше способом при помощи
первой страницы блокнота. Зашифровав сообщение, он уничтожает ис-
пользованную страницу и отправляет его второму абоненту. Получатель
шифрованного текста расшифровывает его и также уничтожает использо-
ванный лист блокнота. Нетрудно видеть, что одноразовый шифр нераск-
рываем в принципе, так как символ в тексте может быть заменен любым
другим символом и этот выбор совершенно случаен.
11


2. ДИОФАНТОВЫ УРАВНЕНИЯ
2.1. ДИОФАНТОВО УРАВНЕНИЕ ПЕРВОЙ СТЕПЕНИ

Рассмотрим задачу отыскания целочисленного решения уравнения:
ax-my=1, (2.1)
где наибольший общий делитель (НОД) a и m равен 1, т.е. НОД(a,m)=1,
a>0, m>0.
Для решения этой задачи число a/m обращают в конечную цепную
дробь при помощи алгоритма Евклида:
a=mq0+a1,
m=a1q1+a2,
a1=a2q2+a3,
a2=a3q3+a4,
………………………….
ak-2=ak-1qk-1+ak,
ak-1=ak+1qk+0;
Цепная дробь имеет вид: a/m = [q0,q1,q2,…qk], а последовательности
{Pn} и {Qn} числителей и знаменателей подходящих дробей к цепной дро-
би определяются рекуррентно:
P-2=0, P-1=1;
Q-2=1, Q-1=0;

страница 1
(всего 3)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign