Шифр Цезаря

Подстановка Цезаря является самым простым вариантом подстановки. Она относится к группе моноалфавитных подстановок.

При моноалфавитной замене каждой букве алфавита открытого текста ставится в соответствие одна буква шифртекста из этого же алфавита.

Определение. Подмножество C_m={C _k: 0Ј k <m} симметрической группы SYM(Z_m), содержащее m подстановок C _k: j®(j+ k) (mod m), 0Ј k < m, называется подстановкой Цезаря.

Подстановки приведены в Табл. 1. Стрелка (а) означает, что буква исходного текста (слева) шифруется при помощи C₃ в букву шифрованного текста (справа).

Определение. Системой Цезаря называется моноалфавитная подстановка, преобразующая n-грамму исходного текста (x0, x1,..,xn-1) в n‑грамму шифрованного текста (y0,y1,...,yn-1) в соответствии с правилом

y_i=C _k (x_i), 0Јi<n.

Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством подстановки C₃ преобразуется в еюыолхиврсеюивцнгкгрлб.

Таблица 1.

Основным недостатком рассмотренного метода является то, что статистические свойства открытого текста (частоты повторения букв) сохраняются в шифртексте.

При своей несложности система легко уязвима. Если злоумышленник имеет

1) шифрованный и соответствующий исходный текст или

2) шифрованный текст выбранного злоумышленником исходного текста, то определение ключа и дешифрование исходного текста тривиальны.

1.4 Квадрат Полибия

Применительно к современному латинскому алфавиту из 26 букв шифрование по этому квадрату заключалось в следующем. В квадрат размером 5x6 клеток выписываются все буквы алфавита, при этом буквы I,J не различаются (J отождествляется с буквой I);

Шифруемая буква заменялась на координаты квадрата, в котором она записана. Так, B заменялась на AB, F на BA, R на DB и т.д. При расшифровании каждая такая пара определяла соответствующую букву сообщения. Ключом такого шифра являлось расположение букв в таблице к примеру 5x5. Начальное расположение букв должно определяться ключом.

1.5 Шифр Гронсфельда

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

Состоит в модификации шифра Цезаря числовым ключом. Для этого под сообщением пишут ключ. Если ключ короче сообщения, то его повторяют циклически. Шифровку получают будто в шифре Цезаря, но отсчитывая необязательно только третью букву по алфавиту, а ту, которая сдвинута на соответствующую цифру ключа. Шифр Гронсфелвда имеет массу модификаций, претендующих на его улучшение, от курьезных, вроде записи текста шифровки буквами другого алфавита, до нешуточных, как двойное шифрование разными ключами.

Кроме этих шифров, зачастую использовался шифр простой замены, заключающийся в замене каждой буквы сообщения на соответствующую ей букву шифра. Такой шифр, популярный среди школьников, является простым кодом и вскрытие его возможно при длине шифровки всего в 20-30 букв, а при длинах текста свыше 100 символов представляет собой очень простую, но весьма увлекательную задачу.

АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ

А АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ

Б _АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ

В Я_АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮ

Г ЮЯ_АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭ

.......

Я ВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ_АБ

_ БВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ_А

Каждая строка в этой таблице соответствует одному шифру замены вроде шифра Юлия Цезаря для алфавита, дополненного пробелом. При шифровании сообщения его выписывают в строку, а под ним ключ. Если ключ оказался короче сообщения, то его циклически повторяют. Шифровку получают, находя символ в колонке таблицы по букве текста и строке, соответствующей букве ключа. Этот очень распространенный вид шифра сохранился до наших дней.

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

1.6 Шифр машины Энигма

При моделировании шифра машины Энигма на ЭВМ можно достичь хорошей устойчивости при сравнительной простоте программы. Напомним, что эта машина представляла собой ряд вращающихся на одной оси барабанов с электрическими контактами, обеспечивающих множество вариантов простой замены, определяемой текущим положением барабанов. В ранних моделях было 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 < 32 THEN k = k+ 128

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)) < 64 THEN

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<32 THEN k=k+128

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.7 Гаммирование

Суть метода состоит в том, что ключ к декодированию байта вычисляется на основе предыдущего байта. При этом сам ключ может модифицироваться от байта к байту. Алгоритм кодирования следующий:

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 и нечетном начальном числе. При достаточно больших К ряд производит впечатление случайного.

1.8 Целочисленные последовательности

Интересный класс генераторов случайных чисел неоднократно предлагался многими специалистами целочисленной арифметике, в частности Джорджем Марсалиа и Арифом Зейманом. Генераторы этого типа основаны на использовании последовательностей Фибоначчи. Классический пример такой последовательности {0, 1, 1, 2, 3, 5, 8, 13, 21, 34...}. За исключением первых двух ее членов, каждый последующий член равен сумме двух предшествующих. Если брать только последнюю цифру каждого числа в последовательности, то получится последовательность чисел {0, 1, 1, 2, 5, 8, 3, 1, 4, 5, 9, 4...} Если эта последовательность применяется для начального заполнения массива большой длины, то, используя этот массив, можно создать генератор случайных чисел Фибоначчи с запаздыванием, где складываются не соседние, а удаленные числа. Марсалиа и Зейман предложили ввести в схему Фибоначчи "бит переноса", который может иметь начальное значение 0 или 1. Построенный на этой основе генератор "сложения с переносом" приобретает интересные свойства, на их основании можно создавать последовательности, период которых значительно больше, чем у применяемых в настоящее время конгруэнтных генераторов.