Тема:
«Шифрование и дешифрование данных при помощисимметричныхкриптографических алгоритмов»
Алгоритмы шифрования и дешифрования данных широкоприменяются в компьютерной технике в системах сокрытия конфиденциальной икоммерческой информации от злонамеренного использования сторонними лицами.Главным принципом в них является условие, что передатчик и приемник заранеезнают алгоритм шифрования, а также ключ к сообщению, без которых информацияпредставляет собой всего лишь набор символов, не имеющих смысла.
Классическим примером таких алгоритмов являютсясимметричные криптографические алгоритмы, перечисленные ниже:
Подстановки:
· ПодстановкаЦезаря
· КвадратПолибия.
· «Тюремныйшифр»
· ШифрПлэйфера
· Двойнойквадрат· Метод переименования· Метод псевдослучайной инверсии
· ШифромГронсфельда
· Системашифрования Вижинера· Шифр Бофора
· Шифрс автоключом.
· Шифрмашины Энигма
Гаммирование:
· Шифргаммирования по Лемеру
· Конгруэнтныедатчики ПСЧ для гаммирования
· Целочисленныедатчики (ряд Фибоначчи) для гаммирования
· ДатчикиМ-последовательностей для гаммирования· Метод псевдослучайного гаммирования· Метод цепочечного гаммирования
Перестановки:· Простая перестановка· Одиночная перестановка по ключу
· Двойнаяперестановка
· Двойнаяперестановка столбцов и строк
· Перестановка“Магический квадрат”· Метод «спутанной шины»
· Многомернаяперестановка
· Шифр взбивания.
Рассмотрим примеры некоторых из них ниже. Простая перестановка
Простая перестановка без ключа — один изсамых простых методов шифрования. Сообщение записывается в таблицу по столбцам.После того, как открытый текст записан колонками, для образования шифровки онсчитывается по строкам. Для использования этого шифра отправителю и получателюнужно договориться об общем ключе в виде размера таблицы. Объединение букв вгруппы не входит в ключ шифра и используется лишь для удобства записинесмыслового текста. Одиночная перестановка по ключу
Более практический метод шифрования, называемыйодиночной перестановкой по ключу очень похож на предыдущий. Он отличается лишьтем, что колонки таблицы переставляются по ключевому слову, фразе или наборучисел длиной в строку таблицы.
Двойная перестановка
Для дополнительной скрытности можно повторношифровать сообщение, которое уже было зашифровано. Этот способ известен подназванием двойная перестановка. Для этого размер второй таблицы подбирают так,чтобы длины ее строк и столбцов были другие, чем в первой таблице. Лучше всего,если они будут взаимно простыми. Кроме того, в первой таблице можнопереставлять столбцы, а во второй строки. Наконец, можно заполнять таблицузигзагом, змейкой, по спирали или каким-то другим способом. Такие способызаполнения таблицы если и не усиливают стойкость шифра, то делают процессшифрования гораздо более занимательным.Двойнаяперестановка столбцов и строк
Кроме одиночных перестановокиспользовались еще двойные перестановки столбцов и строк таблицы с сообщением.При этом перестановки определялись отдельно для столбцов и отдельно для строк.В таблицу вписывался текст и переставлялись столбцы, а потом строки. Прирасшифровке порядок перестановок был обратный.
Перестановка “Магическийквадрат”
Магическими квадратами называются квадратныетаблицы со вписанными в их клетки последовательными натуральными числами от 1,которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали однои то же число. Подобные квадраты широко применялись для вписывания шифруемоготекста по приведенной в них нумерации. Если потом выписать содержимое таблицыпо строкам, то получалась шифровка перестановкой букв. На первый взглядкажется, будто магических квадратов очень мало. Тем не менее, их число оченьбыстро возрастает с увеличением размера квадрата. Так, существует лишь одинмагический квадрат размером 3 х 3, если не принимать во внимание его повороты.Магических квадратов 4 х 4 насчитывается уже 880, а число магических квадратовразмером 5 х 5 около 250000. Поэтому магические квадраты больших размеров моглибыть хорошей основой для надежной системы шифрования того времени, потому чторучной перебор всех вариантов ключа для этого шифра был немыслим.
В квадрат размером 4 на 4 вписывались числа от 1до 16. Его магия состояла в том, что сумма чисел по строкам, столбцам и полнымдиагоналям равнялась одному и тому же числу — 34. Впервые эти квадратыпоявились в Китае, где им и была приписана некоторая «магическая сипа».16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1
Шифрование по магическому квадрату производилосьследующим образом. Например, требуется зашифровать фразу: «Приезжаюсегодня». Буквы этой фразы вписываются последовательно в квадрат согласнозаписанным в них числам, а в пустые клетки ставится точка.16. 3 И 2 Р 13 Д 5 З 10 Е 11 Г 8 Ю 9 С 6 Ж 7 А 12 О 4 Е 15 Я 14 Н 1 П
После этого шифрованный текст записывается встроку:
БИРДЗЕГЮСЖАОЕЯНП
При расшифровывании текст вписывается в квадрат,и открытый текст читается в последовательности чисел «магическогоквадрата»
Программа должна генерировать «магическиеквадраты» и по ключу выбирать необходимый. Размер квадрата больше чем 3х3.Метод «спутанной шины»
Ключом является трехбайтовая последовательность.Этот ключ разбивается на 8 зон по 3 бита, каждая зона хранит адрес этого бита вновом байте (см. рис)
Байт 1 Байт 2 Байт 3
/>/>/>/>/> Бит1 Бит2 Бит3 Бит4 Бит5 Бит6 Бит7 Бит8
Для удобства реализации и для увеличения быстродействияметода можно использовать массив масок вместо сдвигов байт.
Многомерная перестановка
В 1991 г. В.М.Кузьмч предложил схемуперестановки, основанной на кубике Рубика. Согласно этой схеме открытый текстзаписывается в ячейки граней куба по строкам. После осуществления заданногочисла заданных поворотов слоев куба считывание шифртекста осуществляется постолбикам. Сложность расшифрования в этом случае определяется количеством ячеекна гранях куба и сложностью выполненных поворотов слоев. Перестановка,основанная на кубике Рубика, получила название объемной (многомерной)перестановки.
В 1992-1994 г.г. идея применения объемной перестановки для шифрования открытого текста получила дальнейшее развитие.Усовершенствованная схема перестановок по принципу кубика Рубика, в которойнаряду с открытым текстом перестановке подвергаются и функциональные элементысамого алгоритма шифрования, легла в основу секретной системы«Рубикон». В качестве прообразов пространственных многомерных структур,на основании объемных преобразований которых осуществляются перестановки, всистеме «Рубикон» используются трехмерные куб и тэтраэдр. Другойособенностью системы «Рубикон» является генерация уникальной версииалгоритма и ключа криптографических преобразований на основании некоторогосекретного параметра (пароля). Это обеспечивает как дополнительные трудностидля криптоанализа перехваченных сообщений нарушителем (неопределенностьпримененного алгоритма), так и возможность априорного задания требуемойкриптостойкости. Криптостойкость данной системы определяется длиной ключа,криптостойкостью отдельных функциональных элементов алгоритма криптографическихпреобразований, а также количеством таких преобразований.
Шифрвзбивания
Результат шифрования можно ощутимо улучшить, если вместоперестановки использовать линейное преобразование: s=L*t
где L — невырожденная матрица случайного линейного преобразованиябит, или, что то же самое, детерминант L не равен нулю. И хотя расшифровываниев этом случае придется осуществлять решением систем линейных уравнений, нокаждый бит шифровки начинает уже зависеть от каждого бита текста. Шифры наоснове этого преобразования называют скрамблерами или взбивалками. К сожалению,доля невырожденных матриц с увеличением их размера стремительно убывает.Детерминант матрицы L, как и ее элементы, может быть равен либо 0, либо 1. Еслиdet(L)=0, то матрица вырождена.
для матрицы, составленной из квадратных подматрицА, В, С и D, имеем:
¦А В¦
¦ ¦ =det(A)det(B)-det(C)-det(D)
¦C D¦
Для того, чтобы матрица L была невырожденной, случайной и прирасшифровании не нужно было производить много вычислений, американскимикриптографами был предложен алгоритм, легший в основу стандартногокриптографического преобразования DES. Суть его одного шага можно описатьследующей схемой. Входной блок данных делится пополам на левую L' и правую R'части. После этого формируется выходной массив так, что его левая часть L"представлена правой частью R' входного, а правая R" формируется как суммаL' и R' операцией XOR. Далее, выходной массив шифруется перестановкой сзаменой. Можно убедиться, что все проведенные операции могут быть обращены ирасшифровывание осуществляется за число операций, линейно зависящее от размераблока. В то же самое время, после нескольких таких взбиваний можно считать, чтокаждый бит выходного блока шифровки может зависеть от каждого бита сообщения. Сувеличением числа взбиваний порча единственного бита в шифровке делаетнечитаемой половину текста, что обусловлено побайтовой перестановкой. Если быперестановка была побитовая, то весь текст от ошибки в единственном битеперестал бы читаться.
'------программа шифрования взбиванием
DEFINT I-N: DEFSTR S
RANDOMIZE 231
CLS: LOCATE 1, 1
Lot = 5
s$ = ""
FOR i=1 TO 64:s$=s$+CHR$(65+25*RND):NEXT
PRINT s$; " — text": sav = s$
s$ = ""
FOR i=1 TO 192: s$=s$+CHR$(255*RND): NEXT
'---------------------шифрование
FOR i = 0 TO Lot
sc=MID$(ss,1+I*32,32)
l=2^i:sl="": r=""
FOR j = 1 TO 32
kg=ASC(MID$(sc, j, 1))
kl=ASC(MID$(s$, j, 1))
kr=ASC(MID$(s$, j+32,1))
sl = sl+ CHR$(kl XOR kr)
sr = sr+ CHR$(kr XOR kg)
NEXT
s$=sr+RIGHT$(sl,l)+LEFT$(sl,32-l)
NEXT
'----------------------порча бита
ss=CHR$(ASC(s$) XOR 4)+RIGHT$(s$,63)
'-----------------печать шифровки
FOR i =1 TO 64
k = ASC(MID$(s$, i, 1))
DEF SEG=47114: POKE 2*i-2, k: DEF SEG
NEXT
LOCATE 2, 65: PRINT " — code"
'---------------расшифровывание
FOR i = Lot TO 0 STEP -1
sc=MID$(s$, 1+i*32, 32): l=2^i
s$=RIGHT$ (s$ ,32- l)+MID$ (s$, 33,l)+LEFT$ (s$,32)
sl = "": sr = ""
FOR j = 1 TO 32
kg = ASC(MID$(sc, j, 1))
kl = ASC(MID$(ss, j, 1))
kr = ASC(MID$(ss, j+32, 1))
sl = sl+ CHR$(kl XOR kr XOR kg)
sr = sr+ CHR$(kr XOR kg)
NEXT
ss = sl+sr
NEXT
FOR i =1 TO 64
k = ASC(MID$(s$, i, 1))
DEF SEG=47124: POKE 2*i-2,k: DEF SEG
NEXT
LOCATE 3, 65: PRINT " — text"
n = 0
FOR i =1 TO 64
IF MID$ (s$, i, 1) =MID$(sav, i,1) THEN
LOCATE 4, i: PRINT "+";: n = n+I
ELSE
LOCATE 4, i: PRINT "-";
END IF
NEXT
LOCATE 6, 1: PRINT 64 — n; «errors»
END
Шифр Цезаря
Подстановка Цезаря является самым простымвариантом подстановки. Она относится к группе моноалфавитных подстановок.
При моноалфавитной замене каждой буквеалфавита открытого текста ставится в соответствие одна буква шифртекста изэтого же алфавита.
Определение. Подмножество Cm={Ck:0Јkm подстановок Ck: j®(j+k) (modm), 0Јk m, называется подстановкой Цезаря.
Подстановки приведены в Табл. 1. Стрелка (а) означает, что буква исходного текста (слева) шифруется припомощи C3 в букву шифрованного текста (справа).
Определение. Системой Цезаря называетсямоноалфавитная подстановка, преобразующая n-грамму исходного текста (x0, x1,..,xn-1) в n‑грамму шифрованного текста (y0 ,y1 ,...,yn-1) всоответствии с правилом
yi=Ck(xi),0Јi
Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯпосредством подстановки C3 преобразуется в еюыолхиврсеюивцнгкгрлб.
Таблица 1.Ааг Йам Тах Ыаю Бад Кан Уац Ьая Вае Лао Фач Эа_ Гаж Мап Хаш Юаа Даз Нар Цащ Яаб Еаи Оас Чаъ _ав Жай Пат Шаы Зак Рау Щаь Иал Саф Ъаэ
Основным недостатком рассмотренного методаявляется то, что статистические свойства открытого текста (частоты повторениябукв) сохраняются в шифртексте.
При своей несложности система легкоуязвима. Если злоумышленник имеет
1) шифрованный исоответствующий исходный текст или
2) шифрованный текствыбранного злоумышленником исходного текста, то определение ключа идешифрование исходного текста тривиальны.
Квадрат Полибия
Применительно к современному латинскому алфавитуиз 26 букв шифрование по этому квадрату заключалось в следующем. В квадратразмером 5x6 клеток выписываются все буквы алфавита, при этом буквы I,J неразличаются (J отождествляется с буквой I); A B C D E A A B C D E D F G H I K C L M N O P D Q R S T U E V W X Y Z
Шифруемая буква заменялась на координатыквадрата, в котором она записана. Так, B заменялась на AB, F на BA, R на DB ит.д. При расшифровании каждая такая пара определяла соответствующую буквусообщения. Ключом такого шифра являлось расположение букв в таблице к примеру5x5. Начальное расположение букв должно определяться ключом.
«Тюремный шифр»
В несколько измененном виде шифр Полибия получилсвоеобразное название «тюремный шифр». Для его использования нужнотолько знать естественный порядок расположения букв алфавита (как в указанномвыше примере для английского языка). Стороны квадрата обозначаются не буквами(ABCDE), а числами (12345). Число 3, например, передается путем тройного стука.При передаче буквы сначала «отстукивается число, соответствующее строке, вкоторой находится буква, а затем номер соответствующего столбца. Например,буква „F“ передается двойным стуком (вторая строка) и затем одинарным(первый столбец).
Отметим, что при произвольном расположении букв вквадрате возникает одно затруднение: либо нужно помнить отправителю иполучателю сообщения заданный произвольный порядок следования букв в таблице(ключ шифра), что вообще говоря затруднительно, либо иметь при себе запись этихбукв. Во втором случае появляется опасность ознакомления с ключом постороннихлиц. Поэтому в ряде случаев ключ составляется следующим образом. Беретсянекоторое „ключевое слово“, которое легко запомнить, например,»CRYPTOLOGY", удаляют из него повторы букв (получают«CRYPTOLOG») и записывают его в начальных клетках квадрата. Воставшиеся клетки записываются остальные буквы алфавита в естественном порядке.
A B C D E A C R Y P T B O L G A B C D E F H I E UV W X Z
В таком шифре ключом является указанное«ключевое слово» («пароль»).
ШифрПлэйфера (Биграммы)
Более эффективны обобщения подстановки Цезаря — шифр Хилла и шифрПлэйфера. Они основаны на подстановке не отдельных символов, а 2-грамм (шифрПлэйфера) или n-грамм (n-граммой называется последовательность из nсимволов алфавита.) (шифр Хилла). При более высокой криптостойкости онизначительно сложнее для реализации и требуют достаточно большого количестваключевой информации.
Наиболее известный шифр биграммаминазывается Playfair. Он применялся Великобританией в Первую мировую войну.Опишем его на примере той же самой таблицы. Открытый текст разбивался на парыбукв (биграммы) и текст шифровки строился из него по следующим двум оченьпростым правилам.
1. Если обе буквы биграммы исходноготекста принадлежали одной колонке таблицы, то буквами шифра считались буквы,которые лежали под ними. Так биграмма УН давала текст шифровки ВЧ. Если букваоткрытого текста находилась в нижнем ряду, то для шифра бралась соответствующаябуква из верхнего ряда и биграмма ОЯ давала шифр ШБ. (Биграмма из одной буквыили пары одинаковых букв тоже подчинялась этому правилу и текст ЕЕ давал шифрИИ).
2. Если обе буквы биграммы исходноготекста принадлежали одной строке таблицы, то буквами шифра считались буквы,которые лежали справа от них. Так биграмма ИВ давала текст шифровки КГ. Еслибуква открытого текста находилась в правой колонке, то для шифра браласьсоответствующая буква из левой колонки и биграмма ОМ давала шифр ДН.
Если обе буквы биграммы открытого тексталежали в разных рядах и колонках, то вместо них брались такие две буквы, чтобывся четверка их представляла прямоугольник. При этом последовательность букв вшифре была зеркальной исходной паре.Двойной квадрат
Шифровка биграммами, которую называют двойнойквадрат, открыл новый этап в криптографии. Двойной квадрат использует сразу дветаблицы, расположенные по горизонтали, а шифрование идет биграммами, как вшифре Playfair. Эти, казалось бы и не столь уж значительные изменения привели кпоявлению на свет новой криптографической системы ручного шифрования. Имеютсядве таблицы со случайно расположенными в них алфавитами. Для шифрованиясообщение разбивают на биграммы. Первая буква биграммы находится в левойтаблице, а вторая в правой. Затем, мысленно в таблице строится прямоугольниктак, чтобы буквы биграммы лежали в его противоположных вершинах. Другие двевершины этого прямоугольника дают буквы шифровки.
Метод переименования
Суть метода — создается таблица из 256 элементовс неодинаковыми значениями (по случайному закону). Каждый байт заменяетсяэлементом этой таблицы с индексом равным байту. После этого таблица вписываетсяв тело файла, а адрес таблицы в файле является ключом. Таким образом длина файлаувеличивается на 256 байт. Декодирование производится в обратном порядке.
Шифр Гронсфельда
Шифры сложной замены называют многоалфавитными, так как дляшифрования каждого символа исходного сообщения применяется свой шифр простойзамены. Шифр Гронсфельда тоже многоалфавитный шифр — в нем 10 вариантов замены.
Состоит в модификации шифра Цезаря числовым ключом. Для этого подсообщением пишут ключ. Если ключ короче сообщения, то его повторяют циклически.Шифровку получают будто в шифре Цезаря, но отсчитывая необязательно толькотретью букву по алфавиту, а ту, которая сдвинута на соответствующую цифруключа. Шифр Гронсфелвда имеет массу модификаций, претендующих на его улучшение,от курьезных, вроде записи текста шифровки буквами другого алфавита, донешуточных, как двойное шифрование разными ключами.
Кроме этих шифров, зачастую использовался шифр простой замены,заключающийся в замене каждой буквы сообщения на соответствующую ей буквушифра. Такой шифр, популярный среди школьников, является простым кодом ивскрытие его возможно при длине шифровки всего в 20-30 букв, а при длинахтекста свыше 100 символов представляет собой очень простую, но весьмаувлекательную задачу.
АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ
А АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ
Б _АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ
В Я_АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮ
Г ЮЯ_АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭ
…
Я ВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ_АБ
_ БВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ_А
Каждая строка в этой таблице соответствует одному шифру заменывроде шифра Юлия Цезаря для алфавита, дополненного пробелом. При шифрованиисообщения его выписывают в строку, а под ним ключ. Если ключ оказался корочесообщения, то его циклически повторяют. Шифровку получают, находя символ вколонке таблицы по букве текста и строке, соответствующей букве ключа. Этоточень распространенный вид шифра сохранился до наших дней.
В компьютере такая операция соответствуетсложению кодов ASCII символов сообщения и ключа по некоторому модулю. Кажется,что если таблица будет более сложной, чем циклическое смещение строк, то шифрстанет надежнее. Это действительно так, если ее менять почаще, например, отслова к слову. Но составление таких таблиц, представляющих собой латинскиеквадраты, где любая буква встречается в строке или столбце один раз, трудоемкои его стоит делать лишь на ЭВМ. Для ручного же многоалфавитного шифраполагаются лишь на длину и сложность ключа, используя приведенную таблицу,которую можно не держать в тайне, а это упрощает шифрование и расшифровывание.
Системышифрования Вижинера
Начнем с конечной последовательности ключа
k = (k0,k1 ,...,kn),
которая называется ключом пользователя, ипродлим ее до бесконечной последовательности, повторяя цепочку. Таким образом,получим рабочий ключ
k = (k0,k1 ,...,kn), kj = k(jmod r, 0 Ј j
Например, при r = Ґ и ключе пользователя 158 2 10 11 4 18 рабочий ключ будет периодической последовательностью:
15 8 2 10 11 4 18 15 8 2 10 11 4 18 15 8 2 10 114 18 ...
Определение. Подстановка Вижинера VIGkопределяется как
VIGk: (x0,x1, ...,xn-1) ® (y0,y1, ...,yn-1) = (x0+k,x1+k,...,xn-1+k).
Таким образом:
1) исходный текст x делится на r фрагментов
xi =(xi ,xi+r, ...,xi+r(n-1)),0 Ј ir;
2) i-й фрагмент исходного текста xiшифруется при помощи подстановки Цезаря Ck :
(xi ,xi+r, ...,xi+r(n-1)) ® (yi,yi+r, ...,yi+r(n-1)),
Вариант системы подстановок Вижинера при m=2называется системой Вернама (1917г).
В то время ключ k=(k0 ,k1 ,...,kк-1) записывалсяна бумажной ленте. Каждая буква исходного текста в алфавите, расширенномнекоторыми дополнительными знаками, сначала переводилась с использованием кодаБодо в пятибитовый символ. К исходному тексту Бодо добавлялся ключ (по модулю2). Старинный телетайп фирмы AT&T со считывающим устройством Вернама иоборудованием для шифрования, использовался корпусом связи армии США.
Очень распространена плохая с точки зрениясекретности практика использовать слово или фразу в качестве ключа для того,чтобы k=(k0 ,k1 ,...,kк-1) было легко запомнить. В ИС для обеспечениябезопасности информации это недопустимо. Для получения ключей должныиспользоваться программные или аппаратные средства случайной генерации ключей.
Пример. Преобразование текста с помощьюподстановки Вижинера (r=4)
Исходный текст (ИТ1):
НЕ_СЛЕДУЕТ_ВЫБИРАТЬ_НЕСЛУЧАЙНЫЙ_КЛЮЧ
Ключ: КЛЮЧ
Разобьем исходный текст на блоки по 4 символа:
НЕ_С ЛЕДУ ЕТ_В ЫБИР АТЬ_ НЕСЛ УЧАЙ НЫЙ_ КЛЮЧ
и наложим на них ключ (используя таблицуВижинера):
H+К=Ч, Е+Л=Р и т.д.
Получаем зашифрованный (ЗТ1) текст:
ЧРЭЗ ХРБЙ ПЭЭЩ ДМЕЖ КЭЩЦ ЧРОБ ЭБЮ_ ЧЕЖЦ ФЦЫН
Можно выдвинуть и обобщенную систему Вижинера. ЕЕможно сформулировать не только при помощи подстановки Цезаря.
Пусть x — подмножество симметрической группыSYM(Zm).
Определение. r-многоалфавитный ключ шифрованияесть r-набор p = (p0, p1, ..., pr-1) с элементами в x.
Обобщенная система Вижинера преобразует исходныйтекст (x0, x1 ,..., xn-1) в шифрованный текст (y0 ,y1 ,...,yn-1) при помощиключа p = (p0, p1, ..., pr-1) по правилу VIGk:(x0 ,x1 ,...,xn-1) ® (y0 ,y1 ,...,yn-1) = (p0(х0), p1(х1), ..., pn-1(xn-1)), гдеиспользуется условие pi = pi mod r .
Следует признать, что и многоалфавитныеподстановки в принципе доступны криптоаналитическому исследованию.Криптостойкость многоалфавитных систем резко убывает с уменьшением длины ключа.
Тем не менее такая система как шифр Вижинерадопускает несложную аппаратную или программную реализацию и при достаточнобольшой длине ключа может быть использован в современных ИС.
Шифры Бофора
Используют формулы:
Yi=CKi(xi)=(Ki-Xi)(modm) или
Yi=CKi(xi)=(Xi-Ki)(modm) i=0...n-1
Гомофоническая замена одному символу открытоготекста ставит в соответствие несколько символов шифртекста. Этот методприменяется для искажения статистических свойств шифртекста.
Таким образом, при гомофонической замене каждаябуква открытого текста заменяется по очереди цифрами соответствующего столбца.
Шифр с автоключом
При рассмотрении этих видов шифров становитсяочевидным, что чем больше длина ключа (например, в шифре Виженера), тем лучшешифр. Существенного улучшения свойств шифртекста можно достигнуть при использованиишифров с автоключом.
Шифр, в котором сам открытый текст илиполучающаяся криптограмма используются в качестве «ключа», называетсяшифром с автоключом. Шифрование в этом случае начинается с ключа, называемогопервичным, и продолжается с помощью открытого текста или криптограммы,смещенной на длину первичного ключа.
Шифр машины Энигма
При моделировании шифра машины Энигма на ЭВМможно достичь хорошей устойчивости при сравнительной простоте программы.Напомним, что эта машина представляла собой ряд вращающихся на одной осибарабанов с электрическими контактами, обеспечивающих множество вариантовпростой замены, определяемой текущим положением барабанов. В ранних моделяхбыло 5 барабанов, которые перед началом работы устанавливались по кодовомуслову, а в ходе шифрования они поворачивались при кодировании очередногосимвола как в счетчике электроэнергии. Таким образом, получался ключ заведомоболее длинный, чем текст сообщения. Слабость шифра:
1. Пять барабанов моглиобеспечить лишь около ста миллионов ключей, что позволяло их за день перебратьна ЭВМ. Если использовать не 25 латинских символов, а 256 кодов ASCII иувеличить число барабанов, то сложность раскалывания шифра существенновозрастет.
2. Набор барабанов был ограничени менялся ред- ко, что вызвало охоту англичан за их экземплярами в подводныхлодках. ЭВМ может для каждой шифровки использовать индивидуальные барабаны,генерируемые по ключу, а это опять-таки резко усложняет вскрытие шифра.
3. Наконец, можно сделатьдвижение барабанов хаотичным по случайной последовательности, тожевырабатываемой по ключу.
Число ключей такого шифра. Пусть длина периодапрограммного генератора случайных чисел равна 2**24. Восемь барабанов,генерируемые с помощью этого генератора, дадут вместе 2**192 вариантов ключа, аесли учесть еще варианты псевдослучайной последовательности, управляющейдвижением барабанов, то получится внушительная цифра в 2**216 вариантов ключа.Таким образом, довольно просто получить устойчивый шифр даже при использованиипрограммного генератора случайных чисел с периодом малой для криптографиидлины.
'----------имитация Энигмы
DEFINT I-N: DEFSTR S
CLS: RANDOM12E 231
DIM s(4, 32) AS STRING * 1
ns = 4
ss = «ААААААААААААААААААААААААААААА'
PRINT ss
'-----------ШИФРОВАНИЕ
x = RND(-231)
FOR i=0 TO ns
FOR j=0 TO 32:set(i,j) = CHR$(j):NEXT
FOR j=0 TO 32:SWAP s(i,j),s(i,32*RND):
NEXT
NEXT
s=»"
FOR i = 1 TO LEN(ss) 'шифрование символа
k=ASC (MID$ (ss ,i ,1)): IF k>32 THEN k=k-128
FOR j = 0 TO ns:k=ASC(set(j, k)):NEXT
IF k
PRINT CHR$ (k);: s = s + CHR$ (k)
k = ns * RND 'поворот колес
FOR j=0 TO 31:SWAP s(k,j),s(k,j+1):NEXT
FOR j=0 TO 32
s(k,j)=CHR$((ASC(set(k, j)) + 32) MOD 33)
NEXT
NEXT
PRINT
'----------РАСШИФРОВЫВАНИЕ
x = RND(-231)
FOR i=0 TO ns
FOR j=0 TO 32:s(i,j)=CHR$(j):NEXT
FOR j=0 TO 32:SWAP s(i,j),s(i,32*RND):NEXT
FOR j=0 TO 32
IF ASC (set (i, j))
m =j:n=ASC(s(i, j))
DO
k=ASC(s(i,n)):s(i,n)=CHR$(m OR 64)
m=n: n=k
LOOP UNTIL m = j
END IF
NEXT j
FOR j=0 TO 32
s(i,j)=CHR$(ASC(s(i,j)) AND 63)
NEXT
NEXT i
ss = s
FOR i = 1 TO LEN(ss)
k=ASC(MID$(ss,i ,1)): IF k>32 THEN k=k-128
FOR j=ns TO 0 STEP -1
k=ASC(s(j,k))
NEXT
IF k
PRINT CHR$ (k) ;
k = ns * RND 'поворот колес
FOR j = 0 TO 31: SWAP s(k,j),s(k,j+1):NEXT
FOR j = 0 TO 32
s(k,j)=CHR$((ASC(s(k,j))+32) MOD 33)
NEXT
NEXT i
END
для упрощения текста программы ключ задается лишьиз 3 бит числом 231 и используются лишь 5 барабанов.
Гаммирование
Суть метода состоит в том, что ключ к декодированиюбайта вычисляется на основе предыдущего байта. При этом сам ключ можетмодифицироваться от байта к байту. Алгоритм кодирования следующий :
1) вводим ключ;
2) производим с байтом файла одно из действий измножества {+,-,/>}(с игнорированием переноса);
3) полученный байт является ключом к следующемубайту файла ;
4) пока не дошли до конца файла, повторяем п.3.
Декодирование производится по аналогичному алгоритму.
Из простейших процедур, имитирующих случайные числа, наиболееупотребляем так называемый конгруэнтный способ, приписываемый Д.Х. Лемеру:
G(n+1)=KGn+C MOD M
В нем каждое последующее псевдослучайное числоG(n+1) получается из предыдущего Gn умножением его на К, сложением с С ивзятием остатка от деления на М. Весь фокус здесь в том, чтобы подобратьхорошие значения К, С и М. Например, выбрав закон генерации последовательностиG(N+1) = Ent (sqr(2)*Gn) на IBM PC при формате представления чисел с плавающейзапятой IEEE в 4 байта, получим псевдослучайные ряды, обязательнозаканчивающиеся циклами с периодами длиной всего лишь 1225 и 147 в зависимостиот начального заполнения. Разумнее вычисления вести в целых числах. Для нихбыло установлено, что при С=0 и М=2**N наибольший период М/4 достигается приK=3+8*i или K=5+8*i и нечетном начальном числе. При достаточно больших К рядпроизводит впечатление случайного.
Конгруэнтные датчики ПСЧ длягаммирования
Одним из хороших конгруэнтных генераторов является линейныйконгруэнтный датчик ПСЧ. Он вырабатывает последовательности псевдослучайныхчисел T(i), описываемые соотношением
T(i+1) = (A*T(i)+C)modm,
где А и С — константы, Т(0) — исходная величина, выбранная вкачестве порождающего числа. Очевидно, что эти три величины и образуют ключ.
Такой датчик ПСЧ генерирует псевдослучайные числа с определеннымпериодом повторения, зависящим от выбранных значений А и С. Значение mобычно устанавливается равным 2n, гдеn — длина машинного слова вбитах. Датчик имеет максимальный период М до того, как генерируемаяпоследовательность начнет повторяться. По причине, отмеченной ранее, необходимовыбирать числа А и С такие, чтобы период М был максимальным. Как показано Д.Кнутом, линейный конгруэнтный датчик ПСЧ имеет максимальную длину М тогда итолько тогда, когда С — нечетное, и Аmod 4 = 1.
Целочисленные последовательности
Интересный класс генераторов случайных чисел неоднократнопредлагался многими специалистами целочисленной арифметике, в частностиДжорджем Марсалиа и Арифом Зейманом. Генераторы этого типа основаны наиспользовании последовательностей Фибоначчи. Классический пример такойпоследовательности {0, 1, 1, 2, 3, 5, 8, 13, 21, 34...}. За исключением первыхдвух ее членов, каждый последующий член равен сумме двух предшествующих. Еслибрать только последнюю цифру каждого числа в последовательности, то получитсяпоследовательность чисел {0, 1, 1, 2, 5, 8, 3, 1, 4, 5, 9, 4...} Если этапоследовательность применяется для начального заполнения массива большой длины,то, используя этот массив, можно создать генератор случайных чисел Фибоначчи сзапаздыванием, где складываются не соседние, а удаленные числа. Марсалиа иЗейман предложили ввести в схему Фибоначчи «бит переноса», которыйможет иметь начальное значение 0 или 1. Построенный на этой основе генератор«сложения с переносом» приобретает интересные свойства, на ихосновании можно создавать последовательности, период которых значительнобольше, чем у применяемых в настоящее время конгруэнтных генераторов.
Датчики М-последовательностей
М-последовательности также популярны, благодаря относительнойлегкости их реализации.
М-последовательности представляют собой линейные рекуррентныепоследовательности максимального периода, формируемые k-разряднымигенераторами на основе регистров сдвига. На каждом такте поступивший битсдвигает k предыдущих и к нему добавляется их сумма по модулю 2. Вытесняемыйбит добавляется к гамме.
Строго это можно представить в виде следующих отношений:
r1:=r0 r2:=r1… rk-1:=rk-2
r0:=a0r1 Е a1 r2 Е… Е ak-2 rk-1
Гi:=rk-
Здесь r0r1 … rk-1 — kоднобитных регистров, a0a1 … ak-1 — коэффициенты неприводимого двоичного полинома степени k-1. Гi — i-езначение выходной гаммы.
Период М-последовательности исходяиз ее свойств равен 2k-1.
Другим важным свойством М-последовательности является объемансамбля, т.е. количество различных М-последовательностей для заданного k.Эта характеристика приведена в таблице:
k Объем ансамбля 5 6 6 8 7 18 8 16 9 48 10 60 16 2048 Методпсевдослучайного гаммирования
Этот метод похож на метод гаммирования, но к нему добавляется ещемодификация ключа. В данном случае ключ модифицируется по случайному закону поформуле
/>
где С mod 4 = 1,
N+1 — максимальное псевдослучайное число этого ряда,
/> - ключ для предыдущейитерации;
Ki- ключ для новой итерации.Методцепочечного гаммирования
Метод аналогичен методу гаммирования, но ключ изменяетсяпо-другому. Суть метода: имеется последовательность ключей (например, 16).Каждый ключ содержит в себе 12 разрядов ключевого числа для кодирования и 4разряда для указания следующего ключа в цепочке. После использования ключаберем новый по адресу, указанному в текущем ключе.
Список литературы
1. ГатчинЮ.А., Коробейников А.Г. Основы криптографических алгоритмов. Учебное пособие. — СПб.: СПбГИТМО(ТУ), 2002. — 29 с.
2. Главнаяредакция физико-математической литературы, 1974. 324с.
3. ИвановМ.А. Криптографические методы защиты информации в компьютерных системах исетях. – М.: КУДИЦ-ОБРАЗ, 2001, — 368 с.
4. КонП. Универсальная алгебра. — М.: Мир. — 1968. 351 с
5. КоробейниковА. Г. Математические основы криптографии. Учебное пособие. СПб: СПб ГИТМО (ТУ),2002. 41 с
6. ЛевинМаксим. Криптография. Руководство пользователя. — М.: Познавательная книгаплюс, 2001, — 320 с.
7. ЛевинМ. Криптография. Руководство пользователя. — М.: Познавательная книга плюс,2001, — 320 с.
8. МолдовянА.А., Молдовян Н.А., Советов Б.Я. Криптография. – СПб.: Издательство«Лань», 2001, — 224 с.
9. ПанасенкоС.П. Алгоритмы шифрования. Специальный справочник BHV-Санкт-Петербург, 2009. –576с.
10. СмирновВ.И. Курс высшей математики, том III, часть I – М:. Наука,
11. ЧмораА.Л. Современная прикладная криптография. 2-е изд. – М.: Гелиос, АРВ, 2002. –256 с. ил.