 |
Порядок выполнения самостоятельной работы
|
|
|
|
1. Выберете текст для шифрования длиной не более 8 символов.
2. Используйте заданный алфавит для шифровки для первых 4-х
алгоритмов
Таблица 4.3.
| А | Б | В | Г | Д | Е | Ж | З | И | Й | К | Л | М | Н | О | П | Р | С | Т |
| У | Ф | Х | Ц | Ч | Ш | Щ | Ъ | Ы | Ь | Э | Ю | Я | , | . | ! | ? | ||
3. Зашифруйте текст четырьмя алгоритмами:
- алгоритмом Цезаря, К=4;
- алгоритмом простой перестановки, К=3142;
- алгоритмом простой моноалфавитной замены, а=2, К=4;
- алгоритмом Гамильтона, К1= 40231576; К2= 46201573.
- алгоритмом гаммирования.
4. Зашифруйте осмысленное слово длиной не более 8 символов любым
методом из пяти заданных, отдайте на расшифровку
вместе с ключом (ключами).
5. Возьмите зашифрованный текст, ключ шифрования.
6. Дешифруйте переданный текст, подобрав алгоритм.
Решение.
Алгоритм Цезаря
| Л | Ю | Б | Л | Ю | О | Т | Ч | И | З | Н | У | Я | ||
| П | . | Е | П | . | ? | Т | Ц | Ы | М | Л | С | Ч | ? | ! |
Алгоритм простой перестановки
| Л | Ю | Б | Л | Ю | О | Т | Ч | И | З | Н | У | Я | |||
| Б | Л | Л | Ю | О | Ю | Т | З | Ч | Н | И | Я | У |
Алгоритм моноалфавитной замены
| Л | Ю | Б | Л | Ю | О | Т | Ч | И | З | Н | У | Я | |||
| Р | |||||||||||||||
| С | |||||||||||||||
| Ъ | Ь | Ж | Ъ | Ь | Д | О | Ф | Х | Ю | Ж | Ю |
Алгоритм Гамильтона
| Л | Ю | Б | Л | Ю | О | Т | Ч | И | З | Н | У | Я | |||
| Ю | Л | Л | Ю | Т | О | У | Я | З | Ч | И | Н |
|
|
|
Пусть для расшифровки передан текст ЛБАСРЕНТ с ключом К=40231576, наличие восьмизначного ключа может говорить об алгоритме шифрования Гамильтона или алгоритме простой перестановки, применяем последний алгоритм, получаем осмысленное слово БРАСЛЕТЫ.
Алгоритм гаммирования
Пример 5.5. Пусть задан текст «ядома» закодировать его и перслать зашифрованным по каналу связи на основе алгоритма гаммирования.
Решение. Сначала построим таблицу, в которой представим буквы числами по системе кодировки ASCII (см. табл. 4.1.) и числа представим затем в двоичной системе счисления, получим:
Таблица 4.4.
| 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | ||
| я | |||||||||
| д | |||||||||
| о | |||||||||
| м | |||||||||
| а |
Теперь обратимся к генератору псевдослучайных чисел (линейному конгруэнтному методу).
Выберем четыре числа [4]:
m — модуль, m > 0;
a — множитель, 0 £ a < m;
c — приращение, 0 £ с < m;
Х0 — начальное значение, 0 £ Х0 < m.
Последовательность случайных чисел {Хn} можно получить, полагая
| Хn+1 = (a Хn + c) mod m, n ³ 0 | (4.6) |
Эта последовательность называется линейной конгруэнтной последовательностью. Например, для m = 10 и Х0 = a = c = 7 получим последовательность
7, 6, 9, 0, 7, 6, 9, 0, …
Здесь отражен факт, что конгруэнтная последовательность всегда образует петли, т.е. обязательно существует цикл, повторяющийся бесконечное число раз. Это свойство является общим для всех последовательностей вида Xn+1 = f(Xn), где f — функция, преобразующая конечное множество само в себя. Повторяющиеся циклы называют периодами. Задача генерации случайных последовательностей состоит в использовании относительно длинного периода, что связано с выбором довольно большого m, так как период не может иметь больше m элементов.
|
|
|
Воспользуемся формулой (5.6) и создадим гамму шифра:
x0=7; а =3; с =11; m = 33, получим ряд чисел:
{ 7,32, 8, 2, 17, …} оставим из них только 5 и переведем их в двоичную систему счисления, получим:
Таблица 4.5.
| 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | ||
Сложим исходный текст, представленный в двоичном виде с гаммой шифра по модулю 2:
Таблица 4.6.
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | ||||||||||||||||||||||||
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | ||||||||||||||||
Пояснения к таблице 4.6. Первая строка это код входного текста в двоичной системе счисления, вторая строка это гамма шифра в двоичной системе счисления, третья строка это сложение по модулю 2 этих строк, результат зашифрованный текст, который идет по открытому каналу связи, четвертая строка это дешифрованный текст на гамме шифра с известным алгоритмом генерирования случайных чисел (линейным конгруэнтным методом) с известными х0, a, с, m.
Контрольные вопросы
1. Охарактеризуйте направление «криптография». Что называют криптографическим ключом?
2. Проклассифицируйте традиционные алгоритмы шифрования. Кратко охарактеризуйте эти классы.
|
|
|
3. Охарактеризуйте методы шифрования Цезаря, простую моноалфавитную замену, простую перестановку, перестановки Гамильтона.
Вычисление контрольной суммы сообщения
Цель работы – изучить алгоритм вычисления контрольной суммы сообщения и научиться применять его в задачах.
Алгоритм вычисления контрольной суммы
Рассмотрим алгоритм вычисления контрольной суммы (КС).
КС — способ цифровой идентификации некоторой последовательности данных, который заключается в вычислении контрольного значения её кода.
С точки зрения математики КС является типом хэш-функции, используемой для вычисления контрольного кода (КК). КК есть небольшое количество бит внутри большого блока данных, например, сетевого пакета, применяемого для обнаружения ошибок при передаче или хранении информации. Результат вычисления КС добавляется в конец блока данных непосредственно перед началом передачи или сохранения данных на каком -либо носителе информации. Впоследствии он проверяется для подтверждения целостности переданной информации. Популярность КС обусловлена тем, что подобная проверка просто реализуема в двоичном цифровом оборудовании, легко анализируется, и хорошо подходит для обнаружения общих ошибок, вызванных наличием шума в каналах передачи данных.
Принцип КС основан на использовании свойств двоичного многочлена, в виде которого представляется исходная битовая последовательность блока данных. При этом каждый бит такой последовательности соответствует одному из полиномиальных коэффициентов. Например, десятичное число 90 (1011010 в двоичной записи) соответствует многочлену следующего вида:
P (x) = 1 * x 6 + 0 * x 5 + 1 * x 4 + 1 * x 3 + 0 * x 2 + 1 * x 1 + 0 * x 0
Подобным же образом в виде многочлена может быть представлен любой из блоков обрабатываемых данных.
При вычислении контрольного кода по методу КС используется свойство поведения многочленов, позволяющее выполнять с ними любые арифметические действия. Контрольный код рассчитывается, как остаток от деления по модулю 2 многочлена, полученного из исходной битовой последовательности на некоторый другой заранее определённый многочлен (такой многочлен называется порождающим или примитивным).
|
|
|
| R (x) = P (x) * xr mod G (x) | (5.1) |
где
R (x) — контрольный код многочлена P (x).
P (x) — исходный многочлен.
G (x) — порождающий многочлен.
r — степень порождающего многочлена.
Применим алгоритм к поиску КС, если задано:
Р(х) = 90, х = 2.
Пусть G (x)= 1 * x 3 + 0 * x 2 + 1 * x 1 + 0 * x 0 – этот полином скрыт от передачи и не изменен.
r=3, G (x) = 8 + 0 + 2 + 0 = 10. Тогда, согласно формуле получим:
R (x) = 90 * 2 r mod 10=90*8 mod 10 = 720 mod 10 = 0.
Продолжим решение и внесем изменение в передаваемую информацию, изменив только один последний бит, получим число 91 (1011011 в двоичной записи) соответствует многочлену следующего вида:
P (x) = 1 * x 6 + 0 * x 5 + 1 * x 4 + 1 * x 3 + 0 * x 2 + 1 * x 1 + 1 * x 0
Далее действуем по аналогии с выше рассмотренными действиями. Получим:
Р(х) = 91, х = 2.
Пусть G (x)= 1 * x 3 + 0 * x 2 + 1 * x 1 + 0 * x 0
r=3, G (x) = 8 + 0 + 2 + 0 = 10. Тогда, согласно формуле получим:
R (x) = 91 * 2 r mod 10=91*8 mod 10 = 728 mod 10 = 8.
Как видно из решения, что при любом нарушении целостности информации меняется ее контрольная сумма, а значит будет обнаружена ошибка передачи данных.
|
|
|
