Пример решения Шифр Виженера+++

Описание

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

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

Таблица Виженера для английского алфавита

Таблица Виженера для русского алфавита

Таблица Виженера используется для зашифрования и расшифрования. Таблица имеет два входа:

  • верхнюю строку подчеркнутых символов, используемую для считывания очередной буквы исходного открытого текста;
  • крайний левый столбец ключа.

Последовательность ключей обычно получают из числовых значений букв ключевого слова.

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

Шифр Виженера онлайн: шифрование, расшифровка

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

Реализация

Исходники

Для начала подключим требуемые библиотеки

#include «stdafx.h» #include <iostream> #include <string> #include <conio.h> #include «locale.h» #include <fstream>

и объявим необходимые переменные

setlocale(LC_ALL,»Russian»);//русская локаль int i,j,index, index_key, index_message, number; // find_key — флажок найденного индекса строки // find_message — — флажок найденного индекса столбца int find_key=0, find_message=0, count_a, count_b, success=0; //строка исходного текста string message; //Строка — ключ string key = «asd»; // строка, образованная повтором ключа string repeat_key = «»; // строка алфавита string alpha=»abcdefghijklmnopqrstuvwxyz»; // таблица виженера char table[26][26];

Заполняем таблицу Виженера.

Складывая номера строки и столбца ячейки таблицы, мы получаем индекс элемента в массиве, хранящем символы алфавита. Значение элемента массива копируем в текущую ячейку.

for(i=0; i<26; i++) for(j=0;j<26;j++) { index=i+j; if(index>=26) index=index%26; table[i][j]=alpha[index]; }

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

repeat_key=»»; message=»»; ifstream file(«C:\\input.txt»); while(file) { file>>message; } cout<<message<<endl; for (i = 0; i < message.length(); i++) { repeat_key += key[i % key.length()]; }

Для расшифровки находим символ на пересечении столбца с символом из текста и строки с символом из ключа.

for(i=0; i<message.length(); i++) { count_a=0; while(count_a<26 && (find_key==0)) { if(repeat_key[i]==table[0][count_a]) { index_key=count_a; find_key=1; } count_a++; } find_key=0; count_b=0; while(count_b<26 && (find_message==0)) { if(message[i]==table[count_b][0]) { index_message=count_b; find_message=1; } count_b++; } find_message=0; cout<<table[index_message][index_key]; }

Дешифровка

repeat_key=»»; message=»»; ifstream file1(«C:\\output.txt»); while(file1) { file1&rt;&rt;message; } file1.close(); // составим строку из повторов ключа длиной равной длине сообщения for (i = 0; i < message.length(); i++) { repeat_key += key[i % key.length()]; } for(i=0; i<message.length(); i++) { count_a=0; count_b=0; while(count_a<26 && (find_key==0)) { if(repeat_key[i]==table[count_a][0]) { index_key=count_a; find_key=1; } count_a++; } find_key=0; while(count_b<26 && (find_message==0)) { if(message[i]==table[index_key][count_b]) { index_message=count_b; find_message=1; } count_b++; } find_message=0; cout<<table[0][index_message]; } cout<<endl; } break;
comments powered by HyperComments

Взлом полиалфавитных шифров

Шифр Виженера

 

Шифр Виженера (фр. Chiffre de Vigenère) — метод полиалфавитного шифрования буквенного текста с использованием ключевого слова.

Этот метод является простой формой многоалфавитной замены. Шифр Виженера изобретался многократно. Впервые этот метод описал Джован Баттиста Беллазо (итал. Giovan Battista Bellaso) в книге La cifra del. Sig. Giovan Battista Bellaso в 1553 году, однако, в XIX веке получил имя Блеза Виженера, французского дипломата.

Защита ячеек шифром Виженера

Метод прост для понимания и реализации, он является недоступным для простых методов криптоанализа.

 

Описание

В шифре Цезаря каждая буква алфавита сдвигается на несколько позиций; например в шифре Цезаря при сдвиге +3, A стало бы D, B стало бы E и так далее. Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Для зашифровывания может использоваться таблица алфавитов, называемая tabula recta или квадрат (таблица) Виженера. Применительно к латинскому алфавиту таблица Виженера составляется из строк по 26 символов, причём каждая следующая строка сдвигается на несколько позиций. Таким образом, в таблице получается 26 различных шифров Цезаря. На каждом этапе шифрования используются различные алфавиты, выбираемые в зависимости от символа ключевого слова. Например, предположим, что исходный текст имеет вид: ATTACKATDAWN

 

Человек, посылающий сообщение, записывает ключевое слово («LEMON») циклически до тех пор, пока его длина не будет соответствовать длине исходного текста:

LEMONLEMONLE

Первый символ исходного текста A зашифрован последовательностью L, которая является первым символом ключа. Первый символ L шифрованного текста находится на пересечении строки L и столбца A в таблице Виженера. Точно так же для второго символа исходного текста используется второй символ ключа; то есть второй символ шифрованного текста X получается на пересечении строки E и столбца T. Остальная часть исходного текста шифруется подобным способом.

Исходный текст: ATTACKATDAWN

Ключ: LEMONLEMONLE

Зашифрованный текст: LXFOPVEFRNHR

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

Если буквы A—Z соответствуют числам 0—25, то шифрование Виженера можно записать в виде формулы:

Расшифровка:

Криптоанализ

Шифр Виженера «размывает» характеристики частот появления символов в тексте, но некоторые особенности появления символов в тексте остаются.

Главный недостаток шифра Виженера состоит в том, что его ключ повторяется. Поэтому простой криптоанализ шифра может быть построен в два этапа:

· Поиск длины ключа. Можно анализировать распределение частот в зашифрованном тексте с различным прореживанием. То есть брать текст, включающий каждую 2-ю букву зашифрованного текста, потом каждую 3-ю и т. д. Как только распределение частот букв будет сильно отличаться от равномерного (например, по энтропии), то можно говорить о найденной длине ключа.

· Криптоанализ. Совокупность l-шифров Цезаря (где l — найденная длина ключа), которые по отдельности легко взламываются.

Тесты Фридмана и Касиски могут помочь определить длину ключа.

 

Метод Касиски

 

В 1863 году Фридрих Касиски был первым, кто опубликовал успешный алгоритм атаки на шифр Виженера, хотя Чарльз Беббидж разработал этот алгоритм уже в 1854 году. В то время когда Беббидж занимался взломом шифра Виженера, Джон Холл Брок Твейтс представил новый шифр в «Journal of the Society of the Arts»; когда Беббидж показал, что шифр Твейтса является лишь частным случаем шифра Виженера, Твейтс предложил ему его взломать. Беббидж расшифровал текст, который оказался поэмой «The Vision of Sin» Альфреда Теннисона, зашифрованной ключевым словом Emily — именем жены поэта.

Тест Касиски опирается на то, что некоторые слова, такие как «the» могут быть зашифрованы одинаковыми символами, что приводит к повторению групп символов в зашифрованном тексте. Например: сообщение, зашифрованное ключом , не всегда одинаково зашифрует слово «crypto»:

 

Ключ: ABCDEF AB CDEFA BCD EFABCDEFABCD

Исходный текст: CRYPTO IS SHORT FOR CRYPTOGRAPHY

Шифрованный текст: CSASXT IT UKSWT GQU GWYQVRKWAQJB

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

Ключ: ABCDAB CD ABCDA BCD ABCDABCDABCD

Исходный текст: CRYPTO IS SHORT FOR CRYPTOGRAPHY

Шифрованный текст: CSASTP KV SIQUT GQU CSASTPIUAQJB

Более длинные сообщения делают тест более точным, так как они включают в себя больше повторяющихся сегментов зашифрованного текста.

Тест Фридмана

 

Тест Фридмана (иногда называемый каппа-тестом) был изобретен Вильямом Фридманом в 1920 году. Фридман использовал индекс совпадения, который измеряет частоты повторения символов, чтобы взломать шифр. Зная вероятность того, что два случайно выбранных символа текста совпадают (примерно 0,067 для англ. языка) и вероятность совпадения двух случайно выбранных символов алфавита (примерно 1 / 26 = 0,0385 для англ. языка), можно оценить длину ключа как:

Из наблюдения за частотой совпадения следует:

где С — размер алфавита (26 символов для англ. языка), N — длина текста, и — наблюдаемые частоты повторения символов зашифрованного текста. Однако, это только приблизительное значение, точность которого увеличивается при большем размере текста. На практике это было бы необходимо для перебора различных ключей приближаясь к исходному.

 

Частотный анализ

Как только длина ключа становится известной, зашифрованный текст можно записать во множество столбцов, каждый из которых соответствует одному символу ключа. Каждый столбец состоит из исходного текста, который зашифрован шифром Цезаря; ключ к шифру Цезаря является всего-навсего одним символом ключа для шифра Виженера, который используется в этом столбце. Используя методы, подобные методам взлома шифра Цезаря, можно расшифровать зашифрованный текст. Усовершенствование теста Касиски, известное как метод Кирхгофа, заключается в сравнении частоты появления символов в столбцах с частотой появления символов в исходном тексте для нахождения ключевого символа для этого столбца. Когда все символы ключа известны, криптоаналитик может легко расшифровать шифрованный текст, получив исходный текст. Метод Кирхгофа не применим, когда таблица Виженера скремблирована, вместо использования обычной алфавитной последовательности, хотя тест Касиски и тесты совпадения всё ещё могут использоваться для определения длины ключа для этого случая.

Варианты

Вариант running key (бегущий ключ) шифра Виженера когда-то был невзламываемым. Эта версия использует в качестве ключа блок текста, равный по длине исходному тексту. Так как ключ равен по длине сообщению, то методы предложенные Фридманом и Касиски не работают (так как ключ не повторяется). В 1920 году Фридман первым обнаружил недостатки этого варианта. Проблема с running key шифра Виженера состоит в том, что криптоаналитик имеет статистическую информацию о ключе (учитывая, что блок текста написан на известном языке) и эта информация будет отражаться в шифрованном тексте. Если ключ действительно случайный, его длина равна длине сообщения и он использовался единожды, то шифр Виженера теоретически будет невзламываемым, фактически этот вариант будет уже шифром Вернама-Виженера, на которую доказана абсолютная криптостойкость.

Виженер фактически изобрёл более стойкий шифр — шифр с автоключом. Несмотря на это, «шифр Виженера» ассоциируется с более простым многоалфавитным шифром. Фактически эти два шифра часто путали, называя их le chiffre indechiffrable. Беббидж фактически взломал более стойкий шифр с автоключом, в то время когда Касиски издал первое решение взлома многоалфавитного шифра с фиксированным ключом. Метод Виженера зашифровки и расшифровки сообщений иногда относится к «варианту Битфорда». Его отличие от шифра Битфорда, изобретенного сэром Френсисом Битфордом, который, тем не менее, подобен шифру Виженера, заключается в использовании немного измененного механизма шифрования и таблиц.

Несмотря на очевидную стойкость шифра Виженера, он широко не использовался в Европе. Большее распространение получил шифр Гронсфилда, созданный графом Гронсфилдом, идентичный шифру Виженера, за исключением того, что он использовал только 10 различных алфавитов (соответствующих цифрам от 0 до 9). Преимущество шифра Гронсфилда состоит в том, что в качестве ключа используется не слово, а недостаток — в небольшом количестве алфавитов. Шифр Гронсфилда широко использовался по всей Германии и Европе, несмотря на его недостатки.

 


Взлом полиалфавитных шифров

 

Проще всего взломать полиалфавитный шифр, зная его период, то есть число используемых моноалфавитных шифров. Тогда, выбрав буквы, соответствующие каждому из моноалфавитных шифров, можно к каждому из них применить так называемый частотный анализ (или какой-нибудь другой метод взлома моноалфавитных шифров). Метод основан на том, что каждая буква в произвольном тексте появляется с вполне определенной частотой, а значит, посмотрев частоты появления тех или иных букв, можно узнать, как происходит замена. Одним из методов нахождения периода полиалфавитных шифров является метод, предложенный Фредериком Касиски в 1836 году. Он заключается в том, что в зашифрованном тексте находятся одинаковые сегменты длины не меньше, чем три буквы, затем вычисляются расстояния между первыми буквами соседних сегментов. Оказывается, предполагаемый период является кратным наибольшему общему делителю для этих расстояний.

Список литературы:

 

А. В. Яковлев, А. А. Безбогов, В. В. Родин, В. Н. Шамкин «Криптографическая защита информации».

 

Э. М. Габидулин «Курс лекций по Защите Информации»

 

А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черёмушкин «Основы криптографии»

 

 


Криптоанализ шифра Виженера

⇐ Предыдущая12

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

1. Были изобретены несколько методов, чтобы найти длину ключа. Один метод рассмотрим ниже. В так называемом тесте Казиского (Kasiski)криптоаналитик в зашифрованном тексте ищет повторные сегменты по крайней мере из трех символов. Предположим, что найдены два сегмента, и расстояние между ними d. Криптоаналитик предполагает, что m делит d, где m — длина ключа. Если можно найти больше повторных сегментов с расстоянием d1, d2, …., dn, тогда НОД(d1, d2, …., dn….)/ m. Это предположение логично, потому что если два символа одинаковы и (k = 1, 2…) — символы, выделенные в исходном тексте, то одинаковы и символы, выделенные в зашифрованном тексте. Криптоаналитик использует сегменты по крайней мере из трех символов, чтобы избежать случаев, где символы имеют один и тот же ключ. Пример 4.20 может помочь нам п онять эти рассуждения.

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

Пример

Предположим, что мы перехватили следующий зашифрованный текст:

LIOMWGFEGGDVWGHHCQUCRHRWAGWIOWQLKGZETKKMEVLWPCZVG’TH VTSGXQOVGCSVETQLTJSUMVWVEUVLXEWSLGFZMVVWLGYHCUSWXQH — KVGSHEEVFLCFDGVSUMPHKIRZDMPHHBVWVWJWIXGFWLTSHGJOUEEHH- VUCFVGOWICQLIJSUXGLW

Тест Казиского на повторение сегментов на три символа приводит к результатам, показанным в таблице 4.4.

Таблица 4.4.

Тест Казиского для примера 4.19

Комбинация Первое расстояние Второе расстояние Разность
JSU
SUM
VWV
MPH

Наибольший делитель — 4, что означает длину ключа, пропорциональную 4. Сначала пробуем m = 4. Делим зашифрованный текст на четыре части. Часть C1 состоит из символов 1, 5, 9…; часть C2 состоит из символов 2, 6, 10…, и так далее. Используем статистическую атаку каждой части отдельно. Перебираем расшифровывающиеся части по одному символу одновременно, чтобы получить целый исходный текст.

С1 LWGW CRAO KTEP GTQC TJVU EGVG UQGE CVPR PVJG TJEU GCJG
P1 jueu apym ircn eroa rhts thin ytra hcie ixst hcar rehe
C2 IGGG QHGW GKVC TSOS QSWV WFVY SHSV FSHZ HWWF SOHC OQSL
P2 usss ctsl swho feae ceih cete soec atnp nkhe rhck esex
C3 OFDN URWQ ZKLZ HGVV LUVL SZWH WKHF DUKD HVIW HUHF WLUW
P3 lcae rotn whiw edss irsi irh eteh retl tiid eatr airt
C4 MEVN CWIL EMWV VXGE TMEX LMLC XVEL GMIM BWHL GEVV ITX
P4 iard yseh aisr rtca piaf pwte thec arha esft erec tpt

Если исходный текст не имеет смысла, попробуем с другим m.

В рассматриваемом случае исходный текст имеет смысл (читаем по столбцам).

Julius Caesar used a cryptosystem in his wars, which is now referred to as Caesar chipper. It is an additive chipper with the key set to three. Each character in the plaintext is shift three characters to create ciphertext.

Перевод этого текста приведен ниже.

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

Частотный анализ

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

Шифр Виженера

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

Распределение букв очень сильно зависит от типа теста: проза, разговорный язык, технический язык и т.п.

 

 

Таблицы распределения букв
В русском языке
Буква Частота Буква Частота Буква Частота
а 0.062 л 0.035 ц 0.004
б 0.014 м 0.026 ч 0.012
в 0.038 н 0.053 ш 0.006
г 0.013 о 0.090 щ 0.003
д 0.025 п 0.023 ы 0.016
е 0.072 р 0.040 ъ, ь 0.014
ж 0.007 с 0.045 э 0.003
з 0.016 т 0.053 ю 0.006
и 0.062 у 0.021 я 0.018
й 0.010 ф 0.002 разделитель 0.174
к 0.028 х 0.009    
В английском языке
Буква Частота Буква Частота Буква Частота
a 0.0804 b 0.0154 c 0.0306
d 0.0399 e 0.1251 f 0.0230
g 0.0196 h 0.0549 i 0.0726
j 0.0016 k 0.0067 l 0.0414
m 0.0253 n 0.0709 o 0.0760
p 0.0200 q 0.0011 r 0.0612
s 0.0654 t 0.0925 u 0.0271
v 0.0099 w 0.0192 x 0.0019
y 0.0173 z 0.0009    

 

Используя частотный анализ текста, расшифруйте следующее сообщение: «ТПБЙ АБРЮЙ ЕДТБПРЛМ, ЦРМ Т ЙМОБ ТМАВ ПМИБЛВЮ, В Т ОБЗБ НОБПЛВЮ. НМНОМЯМТВТ ББ ЛВ ТЗСП, ЙМГЛМ МЧСРЕРЫ ЛБ НОМПРМ ЛБНОЕЮРЛЪЖ ТЗСП, В ЛВПРМЮЧСЭ КМОБЦЫ ТМ ОРС. ЦВПРМ АБРЕ ДВАСЙЪТВЭРПЮ ЛВА РБЙ, НМЦБЙС ЙМОБ ПМИБЛМБ, ЗВЗ РСАВ НМНВАВБР ПМИЫ Е МРЗСАВ МЛВ ЯБОБРПЮ?»

Используя частотный анализ текста, расшифруйте следующее сообщение: «ЗЯЗ ГВ НОЕЮРКМ ТЪЖРЕ ЮПКЪЙ БКЁЙ КЯ НОЕОМБС Е КЯПИЯБЕРЫПЮ ФМОМЩЕЙ ТЕБМЙ, НОВЗОЯПКМЖ НМАМБМЖ Е АМИСЛЪЙ КВЛМЙ. ПЯЙМВ ЗОЯПЕТМВ – ЕЙВККМ ИЯДСОКМВ КВЛМ. ЕЙ РЯЗ БЯТКМ ИЭЛСЭРПЮ ИЭБЕ, ЦРМ БЯГВ НОЕБСЙЯИЕ КЯДТЯКЕВ ХТВРЯ, – КВЛВПКМ-АМИСЛМЖ.»

Используя частотный анализ текста, расшифруйте следующее сообщение: «ХЯХХ ДРЛХХЯ –АРНЧЮЭШВЯ СБЗПХ ЁЪРПОВБ РРЗГК, ВЖНЦТОЮХВ ЦАФУМДЫНЯ ШЬЕГЕС. АРЪДЖФТУЯ МТ ГЙЁУФТРРЗЫ ДЦЗЯ-ЦОМСЗАВПДЁЪ РВЙНАР. МЩЗЭЬ ГЕПШГ ЦЧСС НВЧЯЮЯ ХЪНЛ КВТТАМ. ТХКНАПИД ФХХНЛЩЫ СРНЫВЪДЖФТ РТ НУЩРСРЪГР СМЧУЕ, ЕСЦРЭВЯРЙЙШС ООТУ НЕ АНАГ ПО УАЛБУУ ДФЩОДАМЫП. ЬЪУРЗ ОАРДЩЖ ЦЗЧУЧИ ОГЯЪДЖФТ ЕРЯАЩЫХ УЪСУИЗ Ы ЫЕЭГБСФАМТ. УУЁГ МЕНУФТ АХЪЖЭТВВКЧЮЕ ЩЕЯМБ ВДГИНГГШИ Д ВЗЦХ ТЪТЬАДИКОЮАК ТФРВМЗЦ –ЯЦЗУЪКРНДЙЮУЯ Ф ЭЕДЕПТ ТУЖХЪЧПОИ Ы ШЕЕГПНРЙ АЧЬШКСХ, ПРЧСЫ ЯЧЧЗЭНР ПЯЦРГОЛШИ ПА РЧТЙЁ Н ЛКМЕЛДЫУВЦ ЧЕЁНЗЭД Н ЕСЭТЖПДАЮУ ЖРФЖВЮШЫЭНЖВ Ц ЮЕУ, Б ДГУЁСЩУ МАСЁЮЦАСОО НЕГАЩПХ.»


⇐ Предыдущая12


Дата добавления: 2017-02-11; просмотров: 163 | Нарушение авторских прав


Похожая информация:


Поиск на сайте:


На главнуюДругие шифрыХеш-функцииДля отзывов

Есть такой шифр — шифр Цезаря. Это частный случай аффинной системы подстановок. Суть шифра Цезаря — каждый символ текста заменяется на некоторый другой, причём одинаковые символы заменяются одинаково. Если данный символ — k-ый в N-символьном алфавите, то он заменяется (k + C) mod N — ым символом алфавита. Нумерация символов начинается с нуля — не очень привычно для не прогеров, но что поделать… Здесь C — ключ шифра.

Допустим, C = 2, алфавит русский. Зашифруем слово ЯМА. Буква Я имеет номер 32 (не 33, хотя мы не убивали букву Ё). (32 + 2) mod 33 = 1, то есть берём букву Б (внимание: буква А имеет нулевой номер). Буква М заменяется на то, что стоит в алфавите на две позиции справа. Для всех адекватных людей это буква О. Буква А заменяется, как уже можно было додуматься, на В. Болучается шифртекст БОВ. Хорошо, хоть не боров!

Другое дело, что вряд ли Цезарь додумался бы до такого примера, но он и прогать-то не умел. А также не знал нормального русского языка и компах ничего не понимал.

Криптография: Шифр Виженера и его реализация на Delphi.

К чему эта вся ерунда? Зададимся вопросом. А что, если взять несколько ключей C и циклически их применять? Например, первый символ сдвигать на 1 позицию, второй вообще не сдвигать, третий сдвигать на 3, четвёртый — снова на 1, пятый не сдвигать. Ну и так далее, пока всё не зашифруем. То как раз-таки и будет шифр Виженера. Только обычно ключ задают не группой чисел (в только что выданном примере был бы набор {1, 0, 3}), а в виде слова. Вместо каждой C записывается символ, который стоит C-ым в алфавите (нумерация опять с нуля). То есть вместо {1, 0, 3} ключом мы пишем слово БАГ (А — символ номер 0, Б — 1, Г — 3). Итак, в шифре Виженера мы имеем дело с последовательностью сдвигов, циклически повторяющейся.

Теперь примерчик по шифру Виженера. Алфавит — русский. Пусть ключевым словом является БАГ (программисты меня поймут). Зашифруем слово ВЕДРО.

*******
В сдвигаем на 1 позицию, получаем Г.
Е никуда не сдвигаем и вообще оставляем в покое.
Д сдвигаем на 3 позиции. Если не дискриминировать букву Ё, вместо Д будет Ж.
Р меняется на С — то есть следующую по алфавиту букву.
О остаётся на месте.
*******
ВЕДРО превращается в ГЕЖСО.

Алфавит: АБВ…ЕЁЖ…Я
Открытый текст В Е Д Р О
Применение ключа Б А Г Б А
Сдвиг 1 0 3 1 0
Шифрованный текст Г Е Ж С О

Такой ключ чисто для простоты примера, вообще не очень хорошо, когда ключ короткий, и при том часть букв ещё и не сдвигается. В приведённом примере по сути поочерёдно брались 3 правила цифра Цезаря. Другое дело, что этот фокус придумал явно не он, даже по названию шифра ясно.

Теперь покажем шифр Виженера на примере помудрёнее. Русский алфавит плюс пробел (34 символа в итоге), ключ БЕГ, шифруем текст МЫ ЗА РОДИНУ.

Алфавит: АБВ…ЕЁЖ…Я_
Открытый текст М Ы _ З А _ Р О Д И Н У
Применение ключа Б Е Г Б Е Г Б Е Г Б Е Г
Сдвиг 1 5 3 1 5 3 1 5 3 1 5 3
Шифрованный текст Н _ В И Е В С У Ж Й Т Ц

Сначала текущий символ ключа — Б (сдвиг 1), потому М сдвигаем на 1 и получаем Н. Потом берём символ ключа Е (сдвиг 5) и применяем к Ы (символ номер 28, если А считать нулевым), (28 + 5) mod 34 = 33, то есть получаем пробел. Теперь на очереди символ ключа Г (сдвиг 3), шифруем пробел (номер 33): (33 + 3) mod 34 = 2, то есть это В, ибо А имеет номер 0. Далее опять переходим к началу ключа, то есть Б (сдвиг 1). Шифруем З, меняя на следующую букву (так как сдвиг = 1). В итоге получаем И. И так далее.

Шифр Виженера тем сильнее, чем длиннее ключ, меньше в нём символов номер ноль, больше символов в алфавите.

Если все символы ключа одинаковые, то это совсем слабый ключ, а шифр Виженера вырождается в шифр Цезаря.

А как же расшифровывать? Если верно, что q = (k + C) mod N, то k = (q — C + N) mod N. Здесь k — номер текущего символа открытого текста в алфавите, С — текущий сдвиг из нашего ключевого набора, q — номер полученного символа шифртекста в алфавите, N — количество символов в алфавите, нумеруемом с нуля. И так для каждого символа.

А что делать, если в тексте есть пробелы? Или заменить их чем-то, или включить в алфавит. Так же можно сделать со всем знаками препинания.

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

Для любителей заумных слов: шифр Цезаря можно считать частным случаем шифра Виженера. Но при этом шифр Цезаря — шифр простой замены, а шифр Виженера — шифр сложной замены (если угодно, многоалфавитный шифр).

Перед вами программная реализация шифра Виженера онлайн. Можно побаловаться немного… Только одно предостережение — если ввели алфавит большими буквами, вводите ключ и текст такими же, если мелкими — то такими же и всё остальное

Алфавит

Ключ

Открытый текст

Шифрованный текст

copyright © Исканцев Н.В., 2011

На главную

Взлом простых шифров

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

Взлом шифра Цезаря

Суть шифра Цезаря очень проста. Мы просто заменяем каждый символ алфавита на следующий или предыдущий на n позиций.

Взлом полиалфавитных шифров

Например, для n = 3.

— a -> c — b -> d — … — x -> a — z -> b

Таким образом, сообщение будет зашифровано как .

Лингвисты подсчитали насколько часто каждый символ алфавита встречается в текстах определенного языка. Например, в английском языке символ E встречается чаще остальных (12.702%). Применяя частотный анализ находим наиболее часто встречающийся в шифротексте символ. Т.е. если чаще всего в шифротексте встречается символ K — то, наиболее вероятно, что при шифровании E переходит в K, значит n = 6.

Зная n и метод шифрования ничего не стоит заменить каждый символ шифротекста на его n-го предшественника в алфавите и получить исходный текст. Либо можно продолжить работать с частотами символов: взять второй по частоте символ в шифротексте и заменить его на A. И так далее, до победного конца. Данный метод можно использовать для пар, троек и больших сочетаний символов.

Примером использования шифра Цезаря является Unix утилита ROT13, которая осуществляет шифрование сдвигом символа на 13 позиций. Так как в английском языке 26 букв — двухкратное применение ROT13 возвращает исходный текст.

Взлом шифра Виженера

В шифре Виженера каждый символ открытого текста складывается по модулю длины алфавита с символом ключа. Для английского языка символы складываются по модулю (+ mod 26). Если ключ короче шифруемого сообщения — он дублируется столько раз, сколько необходимо. Например, шифрование сообщения ключом будет иметь вид:

HOUSTONWEHAVEAPROBLEM NEVERMORENEVERMORENEV ——————— USPWKABNIUEQIRBFFFYIH

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

Взлом шифра Виженера ненамного сложнее взлома шифра Цезаря. Допустим, нам известна длина ключа n = |key|, тогда рассмотрим символы на позициях 0, n-1, 2n-1…. Как и в случае с шифром Цезаря, можно предположить, что наиболее часто встречающимся символом будет зашифрованная E. Тогда, сложив по модулю E с наиболее частым символом мы получим первый символ ключа. Повторим для второго и последующих символов ключа. Зная ключ — дешифруем сообщение. В случаях, когда длина ключа неизвестна — просто выполним указанную процедуру для ключа длины 1, 2, …, n пока не будет получен связный текст.

Взлом одноразового шифроблокнота

Взлом шифра с правильным использованием одноразового шифроблокнота невозможен. Идея шифра с одноразовым шифроблокнотом состоит в том, чтобы сложить исходное сообщение со случайной строкой. Данный шифр обладает абсолютной криптографической стойкостью и не может быть взломан при наличии у взломщика одного лишь шифротекста. Почему этот метод практически не используется? Для дешифрования зашифрованного сообщения необходимо знать ключ. Ключ может быть использован только один раз. При этом длина ключа равна длине сообщения. А если мы можем передать ключ — почему бы вместо этого не передать сообщение?

В случае, если один ключ был использован для шифрования нескольких сообщений — например m1 и m2 все, что необходимо сделать взломщику — сложить их шифротексты по модулю.

c1 = key ^ m1 c2 = key ^ m2 c1 ^ c2 = m1 ^ m2

Естественные языки достаточно избыточны, поэтому имея эту информацию, можно восстановить оригинальные сообщения m1 и m2. Например, зная что в ASCII кодировке XOR пробела с символами A-Z окажется в диапазоне [33, 58], можно получить символы открытого текста. Чем больше у взломщика сообщений зашифрованых одним ключом — тем проще осуществить взлом шифра.


Добавить комментарий

Закрыть меню