Криптоанализ шифра Виженера: путем подсчета числа совпадений, методом Казиски
Пример 2.3
Шифр Віженера
Пример 2.2
Пакет "Mathematica" позволяет очень легко найти в данной строке подстроку с заданными свойствами. Например, для того, чтобы узнать, где в данной строке находится подстрока длины 6, в которой 1-я буква совпадает с 4-й, а 2-я — с 5-й (как в латинском слове "quoque"), можно использовать функции If, StringTake, StringLength, Do и Print пакета "Mathematica" следующим образом для шифртекста . :
ciphertext = "xyuysuyifvyxi"
Do[If[StringTake[ciphertext, {i + 1}] == StringTake[ciphertext,
{i+4}] Ù StringTake[ciphertext, {i + 2}] ==
StringTake[ciphertext, {i + 5}],
Print[i + 1, "", StringTake[ciphertext, {i + 1, i + 6}]]],
{i, 0, StringLength[ciphertext] - 6}]
|| uysuyi
Шифр Виженера (названная в честь Блеза де Виженера, который в 1586 г. в своем "Трактате о шифрах" описал более сложную версию подобной системы) состоит из периодически применяемых шифров Цезаря. В приведенном ниже примере ключом является слово длины . В этом слове буква с номером определяет частичный шифр Цезаря, т.е. используется для шифрования букв открытого текста с номерами
Отождествим с { . Для шифрования и дешифрования весьма удобна так называемая таблица Виженера (см. табл. 2.3).
Таблица 2.3. Таблица Виженера англ.
Используя ключ , выполняем следующее шифрование:
Из-за избыточности английского языка эффективный размер ключевого пространства существенно сократится, если в качестве ключей выбирать лишь осмысленные слова. Если же брать в качестве ключей имена родственников, как это было проделано в примере, то безопасность шифрования будет сведена практически к нулю.
Таблица Виженера для русского алфавита
Ключ | а | б | в | г | д | е | ж | З | и | й | К | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я |
а | б | в | г | д | е | ж | з | и | й | К | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | |
б | в | г | д | е | ж | з | и | й | к | Л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | |
в | г | д | е | ж | з | и | й | к | л | М | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | |
г | д | е | ж | з | и | й | к | л | м | Н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | |
д | е | ж | з | и | й | к | л | м | н | О | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | |
е | ж | з | и | й | к | л | м | н | о | П | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | |
ж | з | и | й | к | л | м | н | о | п | Р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | |
з | и | й | к | л | м | н | о | п | р | С | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | |
и | й | к | л | м | н | о | п | р | с | Т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | |
й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | |
к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | |
л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | |
м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | |
н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | |
о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | |
п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | |
р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | |
с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | |
т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | |
у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | т | |
ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | |
х | ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | |
ц | ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | |
ч | ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | |
ш | щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | |
щ | ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | |
ь | ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | |
ы | ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | |
ъ | э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | |
э | ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | |
ю | я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | |
я | а | б | в | г | д | е | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ь | ы | ъ | э | ю |
Реализация в пакете "Mathematica" сложения двух букв, определяемого в таблице Виженера, аналогична приведенной выше реализации шифра Цезаря.
AddTwoLetters[a_,b_]:=
FromCharacterCode[Mod[(ToCharacterCode[a] - 97) +
(ToCharacterCode[b] - 97), 26] + 97]
Используя функции StringTake и StringLength пакета "Mathematica" и определенную выше функцию AddTwoLetters, можно реализовать шифрование в криптосистеме Виженера следующим образом:
plaintext="typehereyourplaintextinsmallletters";
key="keyword";
ciphertext=" ";
Do[ciphertext=ciphertext<>
AddTwoLetters[StringTake[plaintext,{i}],
StringTake[key,{Mod[i-1,StringLength[key]]+1}]],
{i,1,StringLength[plaintext]}];
ciphertext
|| dcnavvuocmqfgokmlpsowsrqiocovirpsiv
Более формальное описание криптосистемы Виженера дается следующим образом:
где
Вместо периодического использования шифров Цезаря в криптосистеме Виженера можно, разумеется, применить и произвольных простых замен. Такая система является примером, так называемой многоалфавитной замены. Несколько веков не было эффективного способа взлома этой системы, в основном, из-за отсутствия техники определения длины ключа . Ведь если удается определить , то можно сгруппировать буквы для каждого из интервала и найти (например, частотным анализом) свою замену для каждой из этих групп по отдельности. В 1863 г. прусский офицер Фридрих В. Казиски указал статистический метод нахождения длины ключа.