|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
03.05.2013, 15:02 | #1 |
Пользователь
Регистрация: 13.02.2011
Сообщений: 14
|
Взлом XOR-шифра
Здравствуйте, пишу программу для взлома XOR шифра.
Прочитал по этому поводу в "Прикладной криптографии" Брюса Шнайера. Там описан следующий алгоритм: "Предположим,что открытый текст использует английский язык.Более того,пусть длина ключа любое небольшое число байт.Ниже описано,как взломать этот шифр: 1.Определим длину ключа с помощью процедуры,известной как ПОДСЧЕТ СОВПАДЕНИЙ. Применим операцию XOR к шифротексту,используя в качестве ключа сам шифротекст с различными смещениями,и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа,то совпадет свыше 6 процентов байтов. Если нет,то будут совпадать меньше чем 0.4 процента( считая,что обычный ASCII текст кодируется случайным ключом,для других типов открытых текстов числа будут другими). Это называется показателем совпадений. Минимальное смещение от одного значения,кратного длине ключа,к другому и есть длина ключа. 2. Сместим шифротекст на эту длину и проведем операцию XOR для смещенного и оригинального шифротекстов.Результатом операции будет удаление ключа и получение открытого текста,подвергнутого операции XOR с самим собой,смещенным на длину ключа. Так как в английском языке на один байт приходится 1.3 бита действительной информации,существующая значительная избыточность позволяет определить способ шифрования." Немного не понимаю, что мы считаем совпадающими байтами? Совпадения между строкой шифротекста и полученной строкой? Или только в полученной строке? Нашел на википедии статью http://ru.wikipedia.org/wiki/%D0%98%...BD%D0%B8%D0%B9 Пробовал разные варианты реализовывать, и просто индекс совпадений и взаимный индекс, результаты получаются не те, которые нужны. Может дело в том, что шифрую только 32 буквы русского алфавита? Но ведь при смещении кратном длине ключа всплески должны быть, но их нету. Пишу на C++ |
03.05.2013, 16:48 | #2 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Если верить статье по приведенной Вами ссылке, то не 0.4%, а 4%.
А разницу между 4% и 6% на не очень длинном тексте уловить будет затруднительно. Я бы оценил минимальную длину текста в 3000-10000 знаков. |
03.05.2013, 19:22 | #3 |
Пользователь
Регистрация: 13.02.2011
Сообщений: 14
|
Ну там же написано сместить и ксорить. Вот я сместил строку, отксорил с исходной, и считаю совпадения ксоровской с исходной строкой, ведь так?
У меня строка длинной около 500 символов и после той процедуры которую я описал выше, для всех 500-та смещений получается одинаковый индекс совпадений - 5,4% вот код: Код:
Шифрую вот эту строку: "Ниже описано, как взломать этот шифр: 1. Определим длину ключа с помощью процедуры, известной как подсчет совпадений. Применим операцию XOR к шифротексту, используя в качестве ключа сам шифротекст с различными смещениями, и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа, то совпадет свыше 6 процентов байтов. Если нет, то будут совпадать меньше чем 0.4 процента (считая, что обычный ASCII текст кодируется случайным ключом, для других типов открытых текстов числа будут другими). Это называется показателем совпадений. Минимальное смещение от одного значения, кратного длине ключа, к другому и есть длина ключа." Ключ: "сложениепомодулюдва" После ксора получаю: "Ьгиг лвафпгв, ддщ йщпммсщт ычгъ эзъь: 1. Алгоъбйиэ пеоию восщм я лэзрэюю юыарайыхф, жлмбвщукл ксб бибьяаэ явмлупыйкй. Юыжкааай ббйюдега XOR о ъиеыафазщчь, жэбкшчщчэ в ылщгфяка еетщд влт ькфбеьгпьъ ф яолемджеик сэочгиечйз, ж гаавьццвеэ ъадкнмесчдл еувмя. Зсъг мгоеянво эвбкоумэ кбльле йгнвл жеъдл, мк уоудовая щзфцй 6 бфээыйроу копчгк. Аюед гбб, щр есдвщ яизвибпьр вбючжб хеэ 0.4 дюиуиечп (яыжцуф, йцм оррщлюд ASCII ъаеяю дкчгочзтаф янцъимвха дпньри, жло пюхжеэ чзбвм кббоярыд щлмфяжз шжэед тшъчр дбшнойе). Хчб гмйяслыцуя юеджвнъадла яксдюазнщв. Воиедедтбаб взыэзнщо аф лйелма лгддоумэ, кбльллож бджбл ошхйд, и дбшнийю а аюьр кпыжю ойюжл." Последний раз редактировалось Stilet; 04.05.2013 в 11:23. |
03.05.2013, 21:13 | #4 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Я не силен в С и не могу понять нескольких вещей.
1. Если Вы переводите символы к одному регистру, то почему у Вас и до и после ксора фигурируют символы в обоих регистрах? Как вообще получены те абзацы, которые содержатся в сообщении №3? 2. Почему в результате ксора кириллические символы переходят в кириллические. По идее они должны переходить в символы (включая служебные) из первой половины таблицы. 3. Вы пытаетесь все сделать в одном цикле - и привести к нужному регистру, и проксорить, но в таком подходе, минимум, два недостатка: - Вы многократно выполняете одну и ту же работу, - Вы лишаетесь возможности проконтролировать промежуточный результат. |
03.05.2013, 21:41 | #5 | |
Пользователь
Регистрация: 13.02.2011
Сообщений: 14
|
Цитата:
Функция перевода в шифрованный текст в другом месте. И работает она верно, проверял в ручную. Причем я шифрую только русские буквы, пропуская нерусские символы и служебные. Служебные символы не получаются, потому что я привожу все русские символы к коду от 0 до 31, а при ксоре таких чисел, числа большие 31 не получатся, ну а потом перевожу в обратный вид. |
|
03.05.2013, 21:56 | #6 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Я тут тоже набросал небольшую программку, которая делает некоторые подготовительные действия.
Длина Вашего абзаца 638 символов. Из них 515 - символов кириллицы. Посчитанный по этому файлу индекс = 5.12% Для проверки взял другой файл объемом 72100 символов, из которых 57761 - кириллица. Индекс по нему = 5.72%, что гораздо ближе к таблице по Вашей ссылке. Вопрос остается: как Вы получаете проксоренный код, ведь, судя по числу букв 32, в нем должны быть исключительно буквы одного регистра. А у Вас - разного. Подозреваю, что это первая ошибка. |
03.05.2013, 23:25 | #7 | ||
Пользователь
Регистрация: 13.02.2011
Сообщений: 14
|
Как вы считаете индекс?
Цитата:
Соответственно после ксора "а" и к примеру "Я" получится "я", тоже самое и если сменить регистр. Цитата:
Последний раз редактировалось Stilet; 04.05.2013 в 11:27. |
||
04.05.2013, 10:10 | #8 | ||
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Привожу символы к диапазону 0-31.
Прохожу весь текст и на каждый символ увеличиваю значение того из 32 счетчиков, который соответствует данному числу. Суммирую произведения самого счетчика на него же без 1 (32 слагаемых). Делю на N*(N-1), где N - длина текста. Цитата:
Цитата:
1. Ксорил зашифрованный текст с самим собой с разными смещениями и считал индекс: при 0-м смещении получал 100%, а при всех других - в районе 3.3%. Особенностей не обнаружил. 2. Подсчитывал индекс по проксоренному тексту с разным шагом (т.е. каждый второй, каждый третий...). В среднем индекс 5.4-5.5%, и особенностей также выявить не удалось. |
||
04.05.2013, 11:43 | #9 | ||
Пользователь
Регистрация: 13.02.2011
Сообщений: 14
|
Цитата:
Я же написал,что "а" и "А" у меня будут иметь одинаковые код, без различий из-за регистра. Цитата:
|
||
04.05.2013, 12:12 | #10 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
А я провел рефакторинг, обнаружил ошибку, - оказывается, я как для отладки ограничил перекодируемую часть буфера 20 символами, так и осталось.
Исправил. Теперь результат следующий: 1. ксор с самим собой с разными смещениями: Код:
Не слишком много, но вполне детектируемо. 2. При выборке с разным шагом - здесь результаты различаются очень отчетливо: Код:
попали - 5.47%-5.49%. Но это все при объеме файла 1.9 Мб. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Разгадка шифра | saivs | Общие вопросы Delphi | 6 | 15.04.2013 18:28 |
Реализация книжного шифра!!! | InnaSidorenko | Помощь студентам | 1 | 20.11.2012 21:23 |
Анализ блочного шифра на криптостойкость | kaarol | Фриланс | 1 | 13.02.2012 20:36 |
Реализация шифра Плейфера в Delphi | ALUKARD2011 | Помощь студентам | 3 | 14.10.2011 15:56 |
Криптоанализ шифра Виженера | kalbim | Помощь студентам | 3 | 17.05.2011 22:27 |