WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 6 |
И. Л. Ерош ДИСКРЕТНАЯ МАТЕМАТИКА.

МАТЕМАТИЧЕСКИЕ ВОПРОСЫ КРИПТОГРАФИИ Учебное пособие 2001 УДК 512.54 E78 ББК 22.1 Ерош И. Л.

Е78 Дискретная математика. Математические вопросы криптографии: Учеб. пособие/СПбГУАП. СПб., 2001. 56 c.

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

Пособие ориентировано на студентов технических университетов, аспирантов и преподавателей дисциплины “Дискретная математика“ технических вузов.

Рецензенты:

кафедра радиосистем Санкт-Петербургского электротехнического университета;

канд. техн. наук доцент В. Н. Сасковец - © Санкт-Петербургский государственный университет аэрокосмического приборостроения, 2001 2 ВВЕДЕНИЕ Криптография – наука о тайнописи существует уже не одну тысячу лет. Однако до последнего времени она обслуживала правителей, военных, дипломатов. И только с середины 70-х годов начала оформляться в строгую математическую теорию (в связи с разработкой принципов открытого распределения ключей). Область применения современных криптографических систем не ограничивается как ранее межправительственными переговорами, а служит для защиты информационных потоков в банковских сетях, для организации выборов с использованием компьютерных сетей и других случаях.

Часто под термином криптография понимают действия легальных отправителей и получателей сообщений. Под термином криптоанализ понимают действия врага (незаконного перехватчика сообщений). Общая схема криптосистемы выглядит следующим образом (рис. 1).

Канал связи Отправитель Шифрование Дешифрование Получатель сообщения сообщений сообщений сообщения Враг (незаконный перехватчик сообщения) Рис. 1. Общая схема криптосистемы Введем некоторые символьные определения: pt – исходный текст;

E(pt) = ct – зашифрованный текст (криптотекст); D(ct) = pt – расшифрованный текст.

Зашифрование и расшифрование текстов производятся в рамках криптосистемы.

Криптосистема состоит из следующих компонентов:

1. Пространство исходных сообщений PT, которое содержит всевозможные исходные тексты pt.

2. Ключевое пространство K. Каждому ключу k в K соответствует алгоритм зашифрования Ek и расшифрования Dk. Если к сообщению pt применить Ek, а к результату Dk, то снова получим исходный текст pt, т.

е. Dk(Ek(pt)) = pt.

3. Пространство криптотекстов CT, т. е. набор всевозможных криптотекстов ct.

Элементами CT являются результаты применения к элементам PT методов шифрования Ek, где k пробегает все пространство K.

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

Мощность пространства ключей не должна быть очень маленькой, так как перехватчик не должен иметь возможности проверить все ключи. Часто пространство ключей K бесконечно. Как определить, является ли данная криптосистема хорошей Сэр Френсис Бекон сформулировал требования к криптосистемам:

1. По заданным Ek и исходному сообщению pt легко вычислить ct.

По заданным Dk и ct легко вычислить исходное сообщение pt.

2. Не зная Dk,, нельзя вычислить pt из криптотекста ct.

3. Криптотекст не должен вызывать подозрений, т. е. должен выглядеть естественно.

Нам представляется третье требование не очень важным, в первом требовании подразумевается, что для легальных пользователей криптосистема не должна быть очень сложной, а во втором – “невозможность” следует заменить на трудновычислимость.

1. ЭЛЕМЕНТЫ КЛАССИЧЕСКОЙ КРИПТОГРАФИИ 1.1. Древние криптографические системы Познакомимся с некоторыми старыми криптосистемами (даются в современной интерпретации) [2].

Система Цезаря Пусть требуется передать текстовое сообщение, написанное на английском языке (содержит 26 букв, пробелы игнорируются): WE GO TO CITY. Все буквы от A до Z нумеруются цифрами от 0 до 25 и в сообщении производится замена, например со сдвигом на три:

ABCDE F GHI J KL M N OP QR S T U V WXY Z DE F GHI J KL M NOP Q RS T U V WX Y Z AB C В этом случае исходный текст будет зашифрован как ZHJRWRFLWB.

Ключевое пространство системы Цезаря состоит из 26 чисел от 0 до и определяет сдвиг всех букв алфавита при заменах. Ek и Dk легко вычисляются одно из другого, так как Dk = E26–k. Множество замен {Ek}образует коммутативную группу сдвигов, причем Ek–1 = Dk Обобщением шифра Цезаря может служить шифр перестановок. Поскольку число перестановок 26 букв равно 26!, то пространство ключей такого шифра равно 26!, т. е. достаточно велико. Однако полное множество перестановок n элементов образует группу, т. е. по Ek просто и однозначно находится Dk Криптосистема Хилла Криптосистема основана на свойствах линейной алгебры. Все буквы английского алфавита кодируются цифрами, как и в предыдущем случае: A–0, B–1,..., Z –26. Матрица для шифрования M имеет размер dd. Все операции выполняются по модулю 26. Все сообщение разбивается на блоки длины d. Для работы криптосистемы необходимо, чтобы матрица M имела бы обратную.

3...3 15... -Например, M = M =.

2...5 20..... Исходное сообщение HELP определяется двумя векторами H 7 L P1 = = ; P2 = =.



E 4 P Из уравнений MP1 = C1 8 ; MP2 = C2 19, что соответствует шиф рованному сообщению HIAT.

Расшифровать сообщение можно умножением обратной матрицы М–на С1 и С2.

Криптосистема Ришелье Эта система относится к группе методов называемых “информация среди мусора”. Для шифрования сообщений используется лист картона с прорезями, например:

X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X Картон с прорезями накладывается на лист бумаги и в прорези вписывается сообщение. Затем картон снимается и в остальные клеточки вписывается “мусор”, который полностью затеняет ранее написанный текст. Так для примера можно написать сообщение:

I L O V E Y O U I H A V E Y O U D E E P U N D E R M Y S K I N M Y L O V E L A S T S F O R E V E R I N H Y P E R S P A C E Оно выглядит совершенно невинно. Но если наложить картон с прорезями, получим зловещее сообщение YOU KILL AT ONCE.

Известны различные разновидности криптосистемы Ришелье. В частности, картон с прорезями можно взять в виде квадратной матрицы, а прорези в картоне можно сделать так, чтобы при последовательных поворотах на 90, 180 и 270 градусов буквами заполнялись все клеточки.

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

Существуют многоалфавитные подстановки. Простейшим примером многоалфавитной подстановки может служить следующая. Исходное сообщение поделено на блоки по три буквы в каждом. При шифровании первая буква каждого блока становится третьей, а вторая и третья становятся соответственно первой и второй. Так, сообщение LETUSGOTOFRANCE станет ETLSGUTOORAFCEN. Система легко обобщается. Пусть длина блока равна d, тогда число вариантов блоковой замены равно d! В некоторых случаях в одноалфавитных системах криптотекст использует алфавит, отличный от алфавита исходного текста. Например, шифр замены букв может иметь такой вид:

A: B: C: J K L: S T U D: E: F: M N O V W X G: H: I: P Q R Y Z Тогда исходное сообщение WE TALK ABOUT IT MANY TIMES будет выглядеть так:

.

..

:

: : :

..

.

: : : :

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

Считается, что одной из самых древних криптосистем является система Полибия. Рассмотрим квадрат замен (доска Полибия):

A B C D E A A B C D E B F G H I K C L M N O P D Q R S T U E V W X Y Z Каждая буква представляется в криптотексте парой букв, соответствующих ее координатам. Так, например, сообщение HALLOW будет представлено как BCAACACACDEB. В нашей классификации система Полибия есть одноалфавитная система замен. Буква J исключена, для того чтобы получить квадрат. Алфавит шифротекста уже алфавита исходного текста.

Аффинная криптосистема Эта система определяется двумя целыми числами a и b, причем 0 a, b 25, (a, 26) = 1. Буква заменяется на a+ b mod 26. Для a = 3 и b = 5 получаем следующие замены букв:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z F I L O R U X A D G J M P S V Y B E H K N Q T W Z C Условие взаимной простоты a и 26 обеспечивает взаимную однозначность отображения.

Подсчитаем, сколько разных ключей имеется в приведенной аффинной системе. Число a может принимать следующие значения: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25. Независимо от значения a число b принимает 26 значений (от 0 до 25). Случай a = 1; b= 0 следует исключить. Тогда общее число ключей равно 311. В таком простейшем случае криптоаналитику не потребуется много времени для подбора ключа.

Система Цезаря с ключевым словом Она является одноалфавитной системой замены и определяется некоторым числом a и ключевым словом (фразой) с возможным повторением букв. Пусть система задана числом a = 8 и фразой: HOW MANY ELKS. Как и ранее выписываются подряд все буквы латинского алфавита и под буквой, стоящей на 8 месте, без пробелов пишется ключевая фраза. Оставшиеся буквы первой строки в алфавитном порядке дописываются далее с циклическим переносом:

08 A B C D E F G H I J K L M N O P Q R S T U V WX Y Z P Q R T U V X Z H0 WMA NYE L K S B C D F G I J Простейшая защита против атак криптоаналитика, основанных на подсчете частот появления различных букв в текстах, используется в криптосистеме омофонов (HOMOPHONES), которая также является одноалфавитной. Буквы исходного сообщения имеют несколько замен, причем число замен каждой буквы пропорционально вероятности ее появления в тексте сообщения.

1.2. Многоалфавитные системы Система Плайфейра (PLAYFAIR) Система названа в честь барона Плайфейра. Буквы английского алфавита, среди которых отсутствует J, упорядочиваются в виде квадрата 55, например S Y D W Z R I P U L H C A X F T N O G E B R M Q V Квадрат используется для зашифрования и расшифрования по следующим правилам.

1. Исходный текст делится на блоки по 2 буквы в каждом. Текст имеет четную длину и в нем не должно быть блоков, содержащих одинаковые буквы. Если эти требования не выполнены, текст модифицируется (даже в ущерб правилам грамматики). Например, AL LM EN; KI SS ME; WH ER EA RE YO U. Первый текст допустим, второй содержит в блоке 2 одинаковые буквы, третий имеет нечетную длину.

2. Если пара букв блока не попадает в одну строку или столбец, то эта пара шифруется парой букв прямоугольника. Если же пара букв попадает в одну строку или столбец, то она шифруется буквами со сдвигом вправо (в строке) или вниз (в столбце). Так, AL шифруется FP;





LM–PV; EN–TO.

Зашифруем криптотекст CR YP TO EN IG MA–HI DI NG TO UN DO. EN IG MA – шифровальная машина, на которой была основана криптосистема, используемая немцами во время ВОВ.

При циклическом смещении строк и столбцов квадрата Плайфейра получаем эквивалентный квадрат. Известны модификации квадрата Плайфейра: прямоугольники размером 44; 39 и с иным способом замены.

Система Плайфейра с ключевым словом Она строится следующим образом: выбирается ключевое слово без повтора букв и записывается в первых строках квадрата, а затем выписываются оставшиеся буквы в алфавитном порядке. Так, для ключевой фразы: HOW MANY ELKS получаем квадрат для шифрования:

H O W M A N Y E L K S B C D F G I P Q R T U V X Z Многоалфавитная система Виженера (1523–1596).

Квадрат Виженера выглядит следующим образом:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Система Виженера подобна системе Цезаря, в которой ключ меняется от шага к шагу. Квадрат Виженера используется как для зашифрования, так и для расшифрования. Для зашифрования читаем исходное сообщение из строк и ключей системы Цезаря из столбцов. Так, для исходного сообщения PURPLE и ключевого слова CRYPTO находим пересечение P-строки и C-столбца, получаем R. Криптотекст имеет вид: RLPEES. Для расшифрования находим, в какой строке в C- столбце лежит R Получаем P.

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

Если сообщение длиннее ключевого слова, то последнее периодически повторяется. Если известен период повторения, то криптоанализ сводится к криптоанализу одноалфавитных систем. В 1860 г. немецким криптоаналитиком Ф.У. Казизки был изобретен метод для вскрытия периодических криптосистем с неизвестным периодом. Метод Казизки выявляет период с помощью обнаружения одинаковых слов в криптотексте.

Криптосистема AUTOKLAVE (приписываемая математику 16 века Дж. Кардано, известному своими формулами для решения уравнений 3 и 4-й степени) Система является дальнейшей модификацией системы Виженера.

Исходное сообщение с некоторым сдвигом само является и ключом шифровки. В следующем сообщении ключ равен 6:

Сообщение: A I D S I S T R A N S M I T T E DT H RO U GH Ключ: A I D S I S TRA N SM I T T E DT Ключ используется, как в системе Виженера для подстановки Цезаря для каждой буквы. Пустые символы в начале ключа могут заполняться циклическим концом сообщения или ключевым словом. Так для ключевого слова IMMUNE получаем следующее начало для криптотекста:

Сообщение: A I D S I S T R A N SM I T T E D T H R O U GH Ключ: I MMU N E A I D S I S T R A N SM I T T E D T Криптотекст: I U P M V W T Z D F A E B K T R V F P K H Y J A В другом варианте модификации системы AUTOKLAVE в качестве ключа используется криптотекст, записанный после ключевого слова.

В данном случае предыдущий пример будет зашифрован следующим образом:

Сообщение: A I D S I S T R A N S M I T T E D T H R OU GH Ключ: I M M U N E I U P M V WB L P Z N I J E I D O B Криптотекст: I U P MVW B L P Z N I J E I D Q BQ VWXW I Для криптоанализа последней версии криптоаналитику достаточно только найти длину ключа.

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

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

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

Первая пара букв сообщения шифруется первым квадратом, вторая – вторым, третья – третьим, затем четвертая – опять первым и т. д.

Система “кодовая книга” (CODE BOOK).

Pages:     || 2 | 3 | 4 | 5 |   ...   | 6 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.