Вобщем требуется создать программу, которая бы дешифровала сообщения зашифрованные простым xor-ом с длиной ключа меньшим сообщения.
В книге Брюса Шнайера написано?
1. Определим длину ключа с помощью процедуры, известной как подсчет совпадений. Применим операцию XOR к шифротексту, используя в качестве ключа сам шифротекст с различными смещениями, и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа, то совпадет свыше 6 процентов байтов. Если нет, то будут совпадать меньше чем 0.4 процента (считая, что обычный ASCII текст кодируется случайным ключом, для других типов открытых текстов числа будут другими). Это называется показателем совпадений. Минимальное смещение от одного значения, кратного длине ключа, к другому и есть длина ключа.
вопрос: 1.что подразумевается под смещением?
2. байты чего надо проверять на совпадение?
заранее спасибо за помощь)
2 июня 2009 в 21:03
> точный алгоритм взлома таков:
> 1. с помощью теста Фридмана определяем длину ключа.
> 2. берем каждые 1-е,2-е…N-е элементы (где N – длина ключа) и применяем для них метод частотного анализа.
> 3. дешифруем части, собираем в текст, проверяем по словарю.
> Всем большое спасибо за помощь:)
ну вот, разобрался
на самом деле этот алгоритм можно немного улучшить (см. подсказку 3 + проведение частотного анализа на расшифрованном тексте в качестве проверки), но это не обязательно.
2 июня 2009 в 0:00
Мужик)
1 июня 2009 в 23:02
хм, вобщем если кому-то интересно обобщаю ответ на собственный вопрос:
точный алгоритм взлома таков:
1. с помощью теста Фридмана определяем длину ключа.
2. берем каждые 1-е,2-е…N-е элементы (где N- длина ключа) и применяем для них методчастотного анализа.
3. дешифруем части, собираем в текст, проверяем по словарю.
Всем большое спасибо за помощь:)
1 июня 2009 в 22:02
а и не должно быть.
1 июня 2009 в 19:03
да-да, статистический анализ в руки.
1 июня 2009 в 19:03
у меня сама книга, про xor там больше нет не слова.
1 июня 2009 в 7:01
дополнительные подсказки:
1. частота появления символов в языке достаточно хорошо сохраняется.
2. ключ (скорее всего из целого числа байт, но это не важно) разбивает текст на несколько полосатых частей.
3. (дополнительно) вам известны позиции нулей в результате xor со смещением и зашифрованные символы в этих позициях.
думаю, вам следует осилить хотя бы это.
1 июня 2009 в 7:00
> В книге Брюса Шнайера написано
> а статья на этом заканчивается
так вы не брали в руки саму книгу?
1 июня 2009 в 6:05
> Насчет состава исходного текста можно делать некоторые предположения. Например, о частоте появления в нем какого-то слова или слога.
может оказаться неочевидным, что попадания частовстречающегося слога или слова в разные позиции ключа будут кодироваться так, что их можно будет найти частотным анализом.
> Но это имеет смысл только в случаях, когда длина ключа не сильно отличается от длинны слова или хотя бы в несколько раз меньше длины текста.
цитата из отрывка, приведенного автором, "Минимальное смещение от одного значения, кратного длине ключа, к другому и есть длина ключа." автоматически предполагает, что длина ключа в несколько раз меньше длины текста.
1 июня 2009 в 0:03
Можно гадать на кофейной гуще. Насчет состава исходного текста можно делать некоторые предположения. Например, о частоте появления в нем какого-то слова или слога. Но это имеет смысл только в случаях, когда длина ключа не сильно отличается от длинны слова или хотя бы в несколько раз меньше длины текста. Тогда текст можно ксорить с каким-либо частым словом и искать совпадения в получаемых последовательностях с учетом длины ключа и смещения.
1 июня 2009 в 0:00
char key[]="…";
int c;
whiile((c=getc(input))!=EOF)
{
if(!(*key)) //перемещаем указатель на начало массива
c^=(*key);
putc(c,output);
}
1 июня 2009 в 0:00
ключ сможем найти только после нахождения исходного текста сделав shifr^open…
а статья на этом заканчивается поэтому я и спрашиваю как получить исходный текст…
31 мая 2009 в 23:04
А можно в двух словах алгоритм шифрования который использует xor ? Че т на википедии почитал никак не дойдет… Или ссылочку)
31 мая 2009 в 22:05
исключающее или
31 мая 2009 в 22:03
че такое операция xor ?
31 мая 2009 в 21:03
> а как из этого получить сам открытый текст?
в приведенных отрывках ответа на этот вопрос не содержится. читайте дальше – там будет несколько слов о частотном подборе.
> Проксорить по ключу зашифрованный текст ещё раз.
заметьте, что ключ все еще не найден.
31 мая 2009 в 19:02
Проксорить по ключу зашифрованный текст ещё раз.
31 мая 2009 в 15:03
2. Сместим шифротекст на эту длину и проведем операцию XOR для смещенного и оригинального шифротекстов. Результатом операции будет удаления ключа и получение открытого текста, подвергнутого операции XOR с самим собой, смещенным на длину ключа.
а как из этого получить сам открытый текст?
31 мая 2009 в 15:01
1. т.е. если текст содержится в массиве то xor со смещением это
A[i]^A[i+j]???
2. то есть искать нули в получившемся массиве?
31 мая 2009 в 14:05
ответы:
1. смещение текста относительно себя самого перед применением в качестве ключа.
2. при совпадении результатом будет 0.