singlepost

Криптоанализ шифрования xor << На главную или назад  

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

В книге Брюса Шнайера написано?

1. Определим длину ключа с помощью процедуры, известной как подсчет совпадений. Применим операцию XOR к шифротексту, используя в качестве ключа сам шифротекст с различными смещениями, и подсчитаем совпадающие байты. Если величина смещения кратна длине ключа, то совпадет свыше 6 процентов байтов. Если нет, то будут совпадать меньше чем 0.4 процента (считая, что обычный ASCII текст кодируется случайным ключом, для других типов открытых текстов числа будут другими). Это называется показателем совпадений. Минимальное смещение от одного значения, кратного длине ключа, к другому и есть длина ключа.

вопрос: 1.что подразумевается под смещением?
2. байты чего надо проверять на совпадение?

заранее спасибо за помощь)

33 ответов в теме “Криптоанализ шифрования xor”

  1. 20
    Леонид Максимов ответил:

    > точный алгоритм взлома таков:

    > 1. с помощью теста Фридмана определяем длину ключа.
    > 2. берем каждые 1-е,2-е…N-е элементы (где N – длина ключа) и применяем для них метод частотного анализа.
    > 3. дешифруем части, собираем в текст, проверяем по словарю.

    > Всем большое спасибо за помощь:)

    ну вот, разобрался :)
    на самом деле этот алгоритм можно немного улучшить (см. подсказку 3 + проведение частотного анализа на расшифрованном тексте в качестве проверки), но это не обязательно.

  2. 19
    Игорь Игоревич ответил:

    Мужик)

  3. 18
    Сергей Гурин ответил:

    хм, вобщем если кому-то интересно обобщаю ответ на собственный вопрос:

    точный алгоритм взлома таков:

    1. с помощью теста Фридмана определяем длину ключа.
    2. берем каждые 1-е,2-е…N-е элементы (где N- длина ключа) и применяем для них методчастотного анализа.
    3. дешифруем части, собираем в текст, проверяем по словарю.

    Всем большое спасибо за помощь:)

  4. 17
    Леонид Максимов ответил:

    а и не должно быть.

  5. 16
    Максим Потанин ответил:

    да-да, статистический анализ в руки.

  6. 15
    Сергей Гурин ответил:

    у меня сама книга, про xor там больше нет не слова.

  7. 14
    Леонид Максимов ответил:

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

    думаю, вам следует осилить хотя бы это.

  8. 13
    Леонид Максимов ответил:

    > В книге Брюса Шнайера написано
    > а статья на этом заканчивается

    так вы не брали в руки саму книгу?

  9. 12
    Леонид Максимов ответил:

    > Насчет состава исходного текста можно делать некоторые предположения. Например, о частоте появления в нем какого-то слова или слога.

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

    > Но это имеет смысл только в случаях, когда длина ключа не сильно отличается от длинны слова или хотя бы в несколько раз меньше длины текста.

    цитата из отрывка, приведенного автором, "Минимальное смещение от одного значения, кратного длине ключа, к другому и есть длина ключа." автоматически предполагает, что длина ключа в несколько раз меньше длины текста.

  10. 11
    Евгений Тюкавкин ответил:

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

  11. 10
    Сергей Гурин ответил:

    char key[]="…";
    int c;
    whiile((c=getc(input))!=EOF)
    {
    if(!(*key)) //перемещаем указатель на начало массива
    c^=(*key);
    putc(c,output);
    }

  12. 9
    Сергей Гурин ответил:

    ключ сможем найти только после нахождения исходного текста сделав shifr^open…
    а статья на этом заканчивается поэтому я и спрашиваю как получить исходный текст…

  13. 8
    Denis Ch ответил:

    А можно в двух словах алгоритм шифрования который использует xor ? Че т на википедии почитал никак не дойдет… Или ссылочку)

  14. 7
    Леонид Максимов ответил:

    исключающее или

  15. 6
    Denis Ch ответил:

    че такое операция xor ?

  16. 5
    Леонид Максимов ответил:

    > а как из этого получить сам открытый текст?

    в приведенных отрывках ответа на этот вопрос не содержится. читайте дальше – там будет несколько слов о частотном подборе.

    > Проксорить по ключу зашифрованный текст ещё раз.

    заметьте, что ключ все еще не найден.

  17. 4
    Веном Кац ответил:

    Проксорить по ключу зашифрованный текст ещё раз.

  18. 3
    Сергей Гурин ответил:

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

    а как из этого получить сам открытый текст?

  19. 2
    Сергей Гурин ответил:

    1. т.е. если текст содержится в массиве то xor со смещением это
    A[i]^A[i+j]???
    2. то есть искать нули в получившемся массиве?

  20. 1
    Леонид Максимов ответил:

    ответы:
    1. смещение текста относительно себя самого перед применением в качестве ключа.
    2. при совпадении результатом будет 0.

Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.