Foxtools v.2.0

Взлом шифра

Шифр Цезаря может быть легко взломан даже в случае, когда взломщик знает только зашифрованный текст. Можно рассмотреть две ситуации:

1. Взломщик знает (или предполагает), что использовался простой шифр подстановки, но не знает, что это — схема Цезаря.
2. Взломщик знает, что использовался шифр Цезаря, но не знает значение сдвига.

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

Распределение букв в типичном образце текста на английском языке имеет характерный и предсказуемый вид. Шифр Цезаря «поворачивает» это распределение, и возможно определить сдвиг, проверяя график частот для каждого из возможных сдвигов

Во втором случае взлом шифра является даже более простым. Существует не так много вариантов значений сдвига (26 для английского языка), все они могут быть проверены методом грубой силы.
Один из способов сделать это — выписать отрывок зашифрованного текста в столбец всех возможных сдвигов — техника, иногда называемая как «завершение простого компонента».
Рассмотрим пример для зашифрованного текста «EXXEGOEXSRGI»; открытый текст немедленно опознается глазом в четвертой строке.

Другой способ применения этого метода — это написать алфавит под каждой буквой зашифрованного текста, начиная с этой буквы. Метод может быть ускорен, если использовать заранее подготовленные полоски с алфавитом. Для этого нужно сложить полоски так, чтобы в одной строке образовался зашифрованый текст, тогда в некоторой другой строке мы увидим открытый текст.

Другой подход к применению метода грубой силы для взлома — проверить частоты встречаемости букв. Изобразив диаграммой частоты встречания букв в зашифрованном тексте, и зная ожидаемое распределение букв для обычного текста на рассматриваемом языке, можно легко определить сдвиг, взглянув на смещение некоторых характерных черт на диаграмме. Этот метод известен как частотный анализ. Например, в тексте на английском языке частота букв E, T, (обычно наиболее частых), и Q, Z (обычно более редких) особенно различаются. Этот процесс можно автоматизировать, сделав, чтобы компьютерная программа оценивала, насколько хорошо фактическое распределение частот соответствует ожидаемому распределению. Например, может использоваться критерий хи-квадрат.

Для обычного текста на естественном языке, скорее всего, будет только один вариант декодирования. Но, если использовать очень короткие сообщения, то возможны случаи, когда возможны несколько вариантов расшифровки с различными сдвигами. Например зашифрованный текст «MPQY» может быть расшифрован как «aden» так и как «know» (предполагая, что открытый текст написан на английском языке). Точно также «ALIIP» можно расшифровать как «dolls» или как «wheel»; «AFCCP» как «jolly» или как «cheer» (см. также расстояние единственности).

Многократное шифрование никак не улучшает стойкость, так как применение шифров со сдвигом a и b эквивалентно применению шифра со сдвигом a + b. В математических терминах шифрование с различными ключами образует группу.

Теоретические сведения

Для начала мы изучим один из простейших шифров — шифр Цезаря, названный в честь римского императора. В этом шифре каждая буква текста заменяется на другую, которая находится на фиксированное число букв дальше в алфавите. Это фиксированное число букв называется ключом. Так, ключ 1 переводит букву латиницы C в букву D, а Z — по циклу в A. Если ключ равен 3, то буква C перейдет в F, а Z — в C. 

Примеры: используем шифр Цезаря с ключом на слове .

Ключ = 7, слово = computer

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

«Математизируем» шифр Цезаря. Обозначим незашифрованный текст буквой p, а pi — буква в тексте p, которая находится на позиции с номером i. Назовем секретный ключ буквой k, с — зашифрованный текст, а ci — буква в шифрованном тексте, которая находится на позиции i. Тогда вычислить каждую букву шифра можно по формуле: 

Привыкайте к такой формализации, она позволяет программировать алгоритм и выражает смысл шифра точно и сжато.

Если ключ k = 13 а изначальный текст p — «Be sure to drink your Ovaltine!», вот какой шифр мы получим:

Обратите внимание, O (первая буква в шифрованном тексте) смещена на 13 позиций от буквы B (первая буква в оригинальном тексте). То же самое с буквой r (вторая буква в шифровке) смещена на 13 букв от e (вторая буква в оригинале)

Третья буква в шифровке, f, смещена на 13 букв от s (третья в оригинале), тут мы ходим по кругу от z до a.

Шифр Цезаря с ключом 13 имеет специальное название ROT13. Он симметричный: применив его дважды, мы вернемся к изначальному тексту. Конечно, есть еще и ROT26, этот вообще супер-секьюрный, но только если вы нечётко выражаете свои мысли =). 

Зачем мне знания о криптографии?

Предположим, криптография очень нужна, но пусть ей займутся дядьки с усами математики. Зачем же мне знания по криптографии?

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

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

Шифры и компьютеры — новое качество шифрования

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

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

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

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

Enigma

Enigma — это полевая шифровальная машина немецкой армии, которая также использовалась многими странами как в административных, военных, так и в коммерческих целях. Она была создана в 1920 году, за 13 лет до прихода Гитлера к власти и почти за два десятилетия до ВМВ.

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

Шифр Цезаря

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

Современным вариантом шифра Цезаря является шифр ROT13, в котором каждая буква простого текста перемещается на 13 символов, в результате чего получается шифр (секретный текст). Почему 13? Латинский алфавит состоит из 26 символов, сдвиг на 13 — это половина алфавита, и в результате функция ROT13 является собственной обратной функцией. Проще говоря, сегодня мы используем ту же самую технику (тот же самый алгоритм) для шифрования и расшифровки сообщений.

Еврейский Атбаш

Создатели этого простого базового шифра не вписали себя на страницах истории, известно только, что этот метод написания зашифрованного сообщения использовался в древности, приблизительно 500 лет до н.э. Известно также, что этот шифр имеет ивритское происхождение, что отражается и в его названии.

В еврейском алфавите первая и вторая буквы — это Алеф и Бет, а последние две буквы — Шин и Тау. Замена в шифре Atba происходила очень просто: первая буква алфавита заменялась последней, вторая — предпоследней и так далее. Отсюда и название: A-T B-S, Алеф переходит в Тау, Бет переходит в Шин.

Из-за такого способа перестановки букв, этот шифр иногда называют «зеркальным». Конечно, «взломать» его тривиально просто и большинство из нас смогли бы сделать это без помощи компьютера.

дешифратор любых шифров

Иногда… когда смотришь на поисковые запросы, то искреннее удивляешься: что у тебя в голове!? Ты откуда прилител!? Тебе ведомо слово логика!?

дешифратор любых шифров

В мире столько различных шифров, что я даже представить себе не могу, какой объем должен быть программы, чтобы охватить все шифры!

Как по зашифрованному тексту можно определить способ шифрования!?

Логично предположить, что на каждый шифр, который существует, будет существовать отдельная страница, с соответствующим алгоритмом шифрования и дешифровки(если это обратимое шифрование…)

Еще пара поисковых запросов на тему:

Система Цезаря с ключевым словом

Система
шифрования Цезаря с ключевым словом
является одноалфавитной системой
подстановок. Особенностью этой системы
является использование ключевого слова
для смещения и изменения порядка символов
в алфавите подстановок.

Задача7.Зашифровать
сообщение SENDMORE
MONEY
по системе Цезаря с ключевым словом
DIPLOMAT.

Решение. Выберем некоторое число k,
0k< 25. Пустьk=5. Ключевое слово
записывается во вторую строку под
буквами алфавита, начиная с буквы,
числовой код которой совпадает с
выбранным числом k:

Оставшиеся
буквы алфавита (те, которых нет в ключевом
слове) записываются во вторую строку
после ключевого слова в алфавитном
порядке, т. е. в слове DIPLOMAT
есть буква А,
но нет буквы В,
следовательно, В
записывается под буквой N.
Буквы С
также нет, значит, она записывается под
О.
Буква D
уже есть, буквы Е
нет, значит под Р
записывается Е,
и так до конца строки. Не
поместившиеся
буквы записываются сначала этой же
строки (см.)

В
итоге получим следующее:

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

Букве Sисходного текста соответствует
букваН, стоящая под ней во второй
строке алфавита подстановок, буквеЕисходного текста – букваZшифртекста,
и т. д. Таким образом

исходное
сообщение SEND
MORE MONEY

шифруется
как HZBY
TCGZ TCBZS.

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

Задача8.Сформировать
таблицу подстановок в системе с ключевой
фразой

КАК ДЫМ ОТЕЧЕСТВА НАМ СЛАДОК И
ПРИЯТЕН

Решение. Выберем некоторое число k,
0k< 25. Пусть
k=3. Исключим повторяющиеся буквы в
ключевой фразе:

КАДЫМОТЕЧСВНЛИПРЯ.

Как и в предыдущей задаче, запишем
полученную ключевую фразу во второй
строке алфавита подстановок, начиная
с буквы, числовой код которой совпадает
с выбранным числом k=3:

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

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

Квантовая криптография

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

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

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

Попытка подслушивания квантовой коммуникации обречена на провал заранее, потому что любое вмешательство в квановую связь воздействует на частицы и нарушает сообщение. Это особенность нашей реальности и физическое свойство нашей вселенной.

Шифр Вернама

Еще до эпохи компьютеров и машин, таких как «Enigma», американский инженер разработал одноразовый код. Это был единственный шифр, который математически доказал свою полную эффективность. Проще говоря, если все правила протокола шифрования с одноразовым кодом использовались правильно, зашифрованное сообщение, даже сегодня с помощью самых мощных компьютеров, не могло быть взломано без знания ключа шифрования/дешифрования!

Если это так, то зачем нам нужны другие шифры? Здесь стоит обратить внимание «при правильном использовании». То, что данный шифр полностью эффективен и устойчив к любым атакам, не означает, что его легко внедрить

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

Но вернемся к идее Вернама

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

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

Но недостатком такого решения является необходимость согласования между сторонами о наборе ключей, что очень непрактично. Этот шифр, благодаря своей 100%-ной эффективности, используется в узких, редко используемых и сверхсекретных каналах связи, например, для «горячей линии» между президентами Соединенных Штатов и Российской Федерации.

История и применение

Шифр Цезаря назван в честь Гая Юлия Цезаря, который использовал его с левым сдвигом на 3

Шифр Цезаря называют в честь Юлия Цезаря, который согласно «Жизни двенадцати цезарей» Светония использовал его со сдвигом 3, чтобы защищать военные сообщения. Хотя Цезарь был первым зафиксированным человеком, использующим эту схему, другие шифры подстановки, как известно, использовались и ранее.

Его племянник, Август, также использовал этот шифр, но со сдвигом вправо на один, и он не повторялся к началу алфавита:

Есть доказательства, что Юлий Цезарь использовал также и более сложные схемы.

Неизвестно, насколько эффективным шифр Цезаря был в то время, но, вероятно, он был разумно безопасен, не в последнюю очередь благодаря тому, что большинство врагов Цезаря были неграмотными, и многие предполагали, что сообщения были написаны на неизвестном иностранном языке. Нет никаких свидетельств того времени касательно методов взлома простых шифров подстановки. Самые ранние сохранившиеся записи о частотном анализе — это работы Ал-Кинди 9-го века об открытии частотного анализа.

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

В XIX веке личная секция рекламных объявлений в газетах иногда использовалась, чтобы обмениваться сообщениями, зашифрованными с использованием простых шифров. Кан (1967) описывает случаи когда любители участвовали в секретных коммуникациях, зашифрованных с использованием шифра Цезаря в «Таймс». Даже позднее, в 1915, шифр Цезаря находил применение: российская армия использовала его как замену для более сложных шифров, которые оказались слишком сложными для войск; у немецких и австрийских криптоаналитиков были лишь небольшие трудности в расшифровке этих сообщений.

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

Ключевые слова короче чем сообщение (например, «Complete Victory», используемое Конфедерацией во время гражданской войны в США), вводят циклический образец, который мог бы быть обнаружен с помощью улучшенной версии частотного анализа.

В апреле 2006 беглый босс Мафии Бернардо Провенцано был пойман в Сицилии частично из-за криптоанализа его сообщений, написанных с использованием вариации шифра Цезаря. В шифре Провенцано буквы сначала заменялись на числа — порядковые номера букв в алфавите, а уже к полученной последовательности чисел применялся шифр Цезаря — так, чтобы при сдвиге на 3 «A» была написана как «4», «B» как «5», и так далее.

Часто для удобства использования шифра Цезаря используют два насаженных на общую ось диска разного диаметра с нарисованными по краям дисков алфавитами. Изначально диски поворачиваются так, чтобы напротив каждой буквы алфавита внешнего диска находилась та же буква алфавита малого диска. Если теперь повернуть внутренний диск на несколько символов, то мы получим соответствие между символами внешнего диска и внутреннего — шифр Цезаря. Получившийся диск можно использовать как для шифрования, так и для расшифровки.

Например, если внутреннее колесо повернуть так, чтобы символу A внешнего диска соответствовал символ D внутреннего диска, то мы получим шифр со сдвигом 3 влево.

Шифр Вернама — это сложно

Теперь попро­бу­ем объ­яс­нить подробнее. 

1. Сооб­ще­ние хра­нит­ся в виде битов дан­ных. Допу­стим, мы шиф­ру­ем текст. Ком­пью­тер не уме­ет рабо­тать с тек­стом как тако­вым, он этот текст хра­нит как набор чис­ло­вых кодов (про­ще гово­ря, у ком­пью­те­ра все бук­вы про­ну­ме­ро­ва­ны и он пом­нит толь­ко эти номера).

Чис­ла, в свою оче­редь, ком­пью­тер хра­нит в виде дво­ич­но­го кода, то есть битов дан­ных. Это пока что не отно­сит­ся к шиф­ро­ва­нию, это про­сто то, как хра­нит­ся любая тек­сто­вая инфор­ма­ция в компьютере.

Если мы напи­шем KOD в коди­ров­ке ASCII, то для ком­пью­те­ра это будет после­до­ва­тель­ность из трёх чисел, а каж­дое чис­ло — это набор битов: 

01001011 01001111 01000100

2. Берём слу­чай­ные биты в каче­стве клю­ча шиф­ро­ва­ния. На вхо­де у нас три чис­ла по 8 бит. Что­бы их зашиф­ро­вать, нам нуж­ны 24 слу­чай­ных бита. Возь­мём их с потол­ка, они ниче­го не значат: 

10101101 01111010 10101011

3. Накла­ды­ва­ем коды друг на дру­га и при­ме­ня­ем алго­ритм шиф­ро­ва­ния. Шифр Вер­на­ма постро­ен на прин­ци­пе «исклю­ча­ю­ще­го ИЛИ», он же XOR. Он смот­рит на каж­дую пару битов и пыта­ет­ся понять, они оди­на­ко­вые или раз­ные. Если биты оди­на­ко­вые, резуль­тат про­вер­ки будет 0, если раз­ные — 1.

Мож­но про­ве­рить себя так: XOR зада­ёт вопрос «Эти биты раз­ные»? Если да — то 1, если нет — то 0.

Если мы таким обра­зом зако­ди­ру­ем три бук­вы, мы полу­чим три новых набо­ра битов: 

Полу­ча­ет­ся, что на вхо­де у нас было 24 бита дан­ных и на выхо­де 24 бита дан­ных. Но эти дан­ные теперь совсем дру­гие. Если пере­ве­сти эти чис­ла обрат­но в текст, мы получим: 

KOD → æ5ï

Исторические шифры и первые шифраторы

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

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

Помимо шифров, нельзя не упомянуть о приборах для шифрования, которые разрабатывали древние математики. Например, скитала — первый шифратор, разработанный в Спарте. Представлял собой палку, на которую по всей длине наматывалась лента пергамента. Текст наносился вдоль оси палки, после чего пергамент снимался, и получалось шифрованное сообщение. Ключом служил диаметр палки. Однако такой способ шифрования был абсолютно нестойким — автором взлома стал Аристотель. Он наматывал ленту пергамента на конусообразную палку до тех пор, пока не появлялись отрывки читаемого текста.

Также ярким примером из мира древних шифраторов может стать диск Энея — диск с отверстиями по количеству букв в алфавите. Нитка протягивалась последовательно в те отверстия, которые соответствовали буквам сообщения. Получатель вытаскивал нитку, записывал последовательность букв и читал секретное послание. Однако этот шифратор обладал существенным недостатком — достать нитку и разгадать послание мог кто угодно.

Шифр сдвига

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

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

Выводы

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

ссылки:

Это первый урок из цикла «Погружение в крипту». Все уроки цикла в хронологическом порядке:

• Уроки криптографии. Основные шифры. часть 1. Основы, исторические шифраторы, как работают (и анализируются) шифры сдвига, замены, Рихарда Зорге, шифр Вернама и шифровальные машины (ты здесь)
• Распределение ключей. часть 2. Что это такое, как выполняется распределение ключей и как выбрать криптостойкий ключ
• Урок 3. Современные отечественные шифры. Что тaкое сеть Фейстеля, какими бывают отечественные блочные шифры, используемые в современных протоколах, — ГОСТ 28147—89, «Кузнечик»
• Урок 4. Современные зарубежные шифры. Что такое, как работают и в чем разница между 3DES, AES, Blowfish, IDEA, Threefish от Брюса Шнайдера
• Урок 5. Электронная подпись. Виды ЭП, как они работают и как их использовать
• Урок 6. Квантовая криптография. Что это такое, где используется и как помогает в распределении секретных ключей, генерации случайных чисел и электронной подписи