Шифрование методом Вернама

В 1926 г. Гилберт Вернам предложил данный шифр для передачи зашифрованных сообщений по телеграфу.

Метод Вернама использует двоичное представление символов исходного текста. Каждый символ открытого текста кодируется двоичным числом определенной длины. Если длина алфавита не более 32 символов, то для кодирования символа достаточно 5 бит. При более длинных алфавитах можно использовать 6-ти, 7-ми и 8-ми битное кодирование.

Случайная последовательность двоичных ключей k заранее генерируется и записывается.

Схема передачи сообщений с использованием шифрования методом Вернама показана на рис.8. Шифрование исходного текста, предварительно преобразованного в последовательность двоичных символов x, осуществляется путем побитового сложения по модулю 2 (операция XOR) символов x с последовательностью двоичных ключей k:

y = x k. (3)

Рис. 8. Схема шифрования и расшифрования сообщений по методу Вернама

Расшифрование состоит в сложении по модулю 2 символов у шифртекста с той же последовательностью ключей k:

y k = x k  k = x. (4)

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

Следует отметить, что метод Вернама не зависит от длины последовательности ключей и позволяет использовать случайную последовательность ключей. Однако при реализации метода Вернама возникают серьезные проблемы, связанные с необходимостью доставки получателю такой же последовательности ключей, как у отправителя, либо с необходимостью безопасного хранения идентичных последовательностей ключей у отправителя и получателя. Эти недостатки системы шифрования Вернама были преодолены при шифровании методом гаммирования.

Роторные машины

В 20-х годах XX века были изобретены роторные машины – электромеханические устройства, автоматизирующие процесс шифрования. Принцип работы таких машин основан на многоалфавитной замене символов исходного текста по длинному ключу согласно версии шифра Вижинера.

Главной деталью роторной машины является ротор (или колесо) с проволочными перемычками внутри. Ротор представляет собой небольшой диск, на каждой стороне которого расположены равномерно по окружности m электрических контактов, где m - число знаков алфавита. Каждый контакт на передней стороне диска соединен с одним из контактов на задней стороне. В результате электрический сигнал, представляющий знак, будет переставлен в соответствии с тем, как он проходит через ротор от передней стороны к задней. Например, на рис. 9 буква «А» в первом роторе преобразуется в букву «Е».

Рис. 9. Пример работы банка роторов

Роторы объединяют в банк роторов таким образом, чтобы выходные контакты одного ротора касались входных контактов следующего ротора. При этом электрический импульс от нажатой клавиши с буквой исходного текста, входящий с одного конца банка роторов, будет переставляться каждым из роторов, до тех пор, пока не покинет банк. Например, если роторы установлены без сдвигов, то есть контакты на передней стороне всех дисков соответствуют символам алфавита, то возможна замена буквы «А» на букву «М», представленная на рис. 9. Сначала входной сигнал, соответствующий букве «А», попадет на входной контакт диска соответствующий букве «А», затем по проволочной связи импульс придет в контакт «Е», откуда перейдет в соответствующий контакт второго диска и так далее до последнего ротора, который заменит сигнал буквы «Б» на выходной сигнал, соответствующий позиции буквы «М» (рис. 9). Подобная статическая система роторов обеспечивает всего одну замену для каждого символа, однако если хотя бы один диск начинает вращаться, то число возможных замен каждого символа увеличивается до числа знаков в алфавите (m). Если вращаются все диски, то максимальный период замен роторной машины составит mⁿ, где n – число роторов. Например, если m=32 и n=6, то повтор порядка замен роторной машины произойдет только после шифрования ≈ 10 ⁶ символов.

При повороте ротора из одного положения в другое замена, которую он осуществляет, будет изменяться. В общем случае порядок проведения этой замены можно записать в виде C ^-j, π, C ^j, где π - подстановка, реализуемая ротором в его начальном положении; C ^j – циклический сдвиг на j позиций вперед по алфавиту; C^-j – циклический сдвиг на j позиций назад по алфавиту.

Например, если начальная подстановка первого ротора π (Ю) = «О» (рис. 10) и ротор сдвигается на две позиции (j = 2), то буква открытого текста «А» будет против того контакта ротора, который используется для представления символа «Ю», а буква «О», заменяющая в роторе букву «Ю», окажется против того контакта, который используется для представления шифрованного символа «Р». Таким образом, результирующая подстановка Т(А) = «Р» при j = 2. Для этого же сдвига ротора буквы открытого текста «Б», «В», «Г», «Д», «Е» будут зашифрованы соответственно буквами «Ю», «З», «П», «Т», «Й» (рис. 10). Преобразование импульсов во втором и последующих дисках роторной машины производится аналогично.

Положение контактов в начальном положении (без сдвига)

Входной сигнал

…

Подстановка без сдвига (π)

…

Положение контактов после сдвига на 2 позиции (j=2)

Входной контакт (результат операции C ^-2)

…

Выходной контакт (результат операции π)

…

Выходной сигнал (результат операции C ²)

…

Рис. 10. Схема формирования подстановки при сдвиге ротора (j =2)

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

Простейшее из возможных движений ротора – это движение по принципу одометра, которое использовалось в немецкой машине Enigma во время второй мировой войны. При шифровании одного знака последний диск поворачивается на одну позицию. Когда этот (или любой другой) диск переместится на m позиций и совершит полный оборот, колесо, расположенное перед ним (по ходу сигнала), передвинется на одну позицию, и процесс будет повторяться.

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

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

Варианты заданий

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

1. Зашифровать и расшифровать русскоязычное сообщение со знаками препинания с помощью шифра Альберти (длина алфавита равна 35). Ключом (изменяемым параметром) является алфавит замены и начальный сдвиг алфавитов. Величина шага относительного сдвига фиксирована и равна 3.

2. Зашифровать и расшифровать русскоязычное сообщение с пробелами и без знаков препинания с помощью шифра Альберти. Ключом является алфавит замены, формируемый по ключевому слову, и величина шага относительного сдвига. Величина начального сдвига фиксирована и равна 4.

3. Зашифровать и расшифровать сообщение, содержащее любые символы кодовой таблицы ASCII, с помощью шифра Альберти. Алфавит замены должен быть сгенерирован случайным образом и сохранен в файле. Ключом является величина начального сдвига и величина шага относительного сдвига.

4. Зашифровать и расшифровать англоязычное сообщение, содержащее пробелы и знаки препинания (длина алфавита 30), с помощью шифра Альберти. Ключом является алфавит замены, который формируется по ключевому слову и величина шага относительного сдвига. Величина начального сдвига фиксирована и равна 5.

5. Зашифровать и расшифровать англоязычное сообщение с пробелами и без знаков препинания с помощью шифра Альберти. Ключом является алфавит замены, который формируется по ключевому слову и величина начального сдвига. Величина шага относительного сдвига фиксирована и равна 2. Сдвигать алфавит замены нужно после шифрования каждого слова.

6. Зашифровать и расшифровать русскоязычное сообщение со знаками препинания с помощью шифра Тритемия (длина алфавита равна 35). Ключом является алфавит замены, формируемый по ключевому слову.

7. Зашифровать и расшифровать русскоязычное сообщение с пробелами и без знаков препинания с помощью шифра Тритемия (длина алфавита равна 33). Ключом является алфавит замены, формируемый случайным образом.

8. Зашифровать и расшифровать англоязычное сообщение с пробелами и знаками препинания, с помощью шифра Гронсфельда. Реализовать двойное шифрование с двумя разными числовыми ключами.

9. Зашифровать и расшифровать сообщение, содержащее любые символы кодовой таблицы ASCII, с помощью шифра Гронсфельда. Реализовать тройное шифрование с двумя разными числовыми ключами (зашифровать с первым ключом, затем применить операцию расшифрования со вторым ключом и снова зашифровать с первым ключом).

10. Зашифровать и расшифровать сообщение, содержащее любые символы кодовой таблицы ASCII, с помощью шифра Вижинера. Длина ключа должна быть не менее 5 символов.

11. Зашифровать и расшифровать русскоязычное сообщение с пробелами и без знаков препинания с помощью шифра Вижинера. Реализовать двойное шифрование с двумя разными числовыми ключами. Длина каждого ключа должна быть не менее 7 символов.

12. Зашифровать и расшифровать англоязычное сообщение, содержащее пробелы и знаки препинания (длина алфавита 30), с помощью шифра Вижинера. Ключом является начальный алфавит замены, который формируется случайным образом и ключевое слово.

13. Зашифровать и расшифровать русскоязычное сообщение, содержащее пробелы и знаки препинания (длина алфавита 35) с помощью шифра Вижинера. Ключом является начальный алфавит замены, формируемый по ключевому слову, и ключевое слово метода Вижинера.

14. Зашифровать и расшифровать англоязычное сообщение, содержащее пробелы (длина алфавита 27), с помощью шифра Вижинера. Реализовать тройное шифрование с двумя разными ключевыми словами (зашифровать с первым ключом, затем применить операцию расшифрования со вторым ключом и снова зашифровать с первым ключом).

15. Зашифровать и расшифровать русскоязычное сообщение, содержащее пробелы и знаки препинания (длина алфавита 36) с помощью шифра «двойной квадрат» Уитстона. Ключом является порядок букв и число строк в таблицах.

16. Зашифровать и расшифровать англоязычное сообщение, содержащее пробелы и знаки препинания (длина алфавита 30) с помощью шифра «двойной квадрат» Уитстона. Ключом является порядок букв, задаваемый ключевыми словами, и число строк в таблицах.

17. Зашифровать и расшифровать русскоязычное сообщение, содержащее пробелы и знаки препинания (длина алфавита 35) с помощью шифра «двойной квадрат» Уитстона. Размер каждой таблицы 5х7. Ключом является порядок букв, задаваемый датчиком случайных чисел.

18. Зашифровать и расшифровать русскоязычное сообщение без пробелов и без знаков препинания (длина алфавита 32) с помощью шифра «двойной квадрат» Уитстона. Размер каждой таблицы 8х4. Ключом является: порядок букв, задаваемый ключевыми словами.

19. Зашифровать и расшифровать русскоязычное сообщение, содержащее пробелы и знаки препинания (длина алфавита 35) с помощью одноразовой системы шифрования. Ключом является большой фрагмент текста (не менее длины сообщения).

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

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

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

23. Зашифровать и расшифровать сообщение, содержащее символы кодовой таблицы ASCII с помощью шифра Вернама. Ключом является набор случайных символов общей длиной не менее 10.

24. Зашифровать и расшифровать сообщение, содержащее символы кодовой таблицы ASCII с помощью шифра Вернама. Ключом является набор случайных битов общей длиной не менее 32.

25. Зашифровать и расшифровать англоязычное сообщение с пробелами с помощью шифра Вернама (5 бит на символ). Ключом является набор случайных букв латинского алфавита общей длиной не менее 10.

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

27. Зашифровать и расшифровать русскоязычное сообщение без пробелов и знаков препинания с помощью шифра Вернама (5 бит на символ). Ключом является набор случайных ASCII символов общей длиной равной длине сообщения (при измерении в битах).

28. Зашифровать и расшифровать русскоязычное сообщение с пробелами с помощью имитатора роторной машины, которая состоит из двух дисков. При выборе ключа используется 5 дисков с различными заменами. Роторы вращаются по принципу одометра. Начальные позиции роторов могут изменяться.

29. Зашифровать и расшифровать англоязычное сообщение с пробелами (длина алфавита 27) с помощью имитатора роторной машины, которая состоит из трех дисков. Порядок установки дисков может изменяться. После шифрования каждого символа шаг перемещения третьего ротора – 1, второго – 2, первого – 5. Изначально роторы устанавливаются без смещения.

30. Зашифровать и расшифровать англоязычное сообщение с пробелами (длина алфавита 27) с помощью имитатора роторной машины, которая состоит из двух дисков. При выборе ключа используется 3 диска с различными заменами. После шифрования каждого символа шаг перемещения второго ротора – 4, первого – 7. Начальные позиции роторов могут изменяться.

31. Зашифровать и расшифровать русскоязычное сообщение с пробелами и знаками препинания с помощью имитатора роторной машины, которая состоит из двух дисков. Для второго диска являются запрещенными 3 позиции, которые входят в состав ключа. Роторы вращаются по принципу одометра. Первый диск устанавливается в начальную позицию со смещением 5, второй – со смещением 1.

32. Зашифровать и расшифровать русскоязычное сообщение с пробелами и знаками препинания (длина алфавита 35) с помощью имитатора роторной машины, которая состоит из трех дисков. Первый ротор вращается с шагом 6 после каждого полного оборота второго ротора. Второй и третий роторы вращаются по принципу одометра. Установка роторов в начальные позиции производится по буквам ключевого слова.

33. Зашифровать и расшифровать сообщение, состоящее из цифр и пробелов (длина алфавита 11), с помощью имитатора роторной машины, которая состоит из четырех дисков. Роторы вращаются по принципу одометра. Установка роторов в начальные позиции производится по цифрам четырехзначного числа.

34. Зашифровать и расшифровать сообщение, состоящее из цифр (длина алфавита 10), с помощью имитатора роторной машины, которая состоит из трех дисков. После шифрования каждого символа шаг перемещения третьего ротора – 1, второго ротора – 3, первого ротора – 7. Изначально роторы устанавливаются без смещения.

35. Зашифровать и расшифровать сообщение, состоящее из цифр, с помощью имитатора роторной машины, которая состоит из трех дисков. Для второго диска является запрещеной 1 позиция, для третьего – 3 позиции. Роторы вращаются по принципу одометра, но в разные стороны. Изначально роторы устанавливаются без смещения.

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