Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | |
Про методы стат. анализа шифротекста — читаем «Пляшущие человечки» Конан Дойля до просветления ;-) 14.10.06 11:29 Число просмотров: 4608
Автор: HandleX <Александр М.> Статус: The Elderman
Отредактировано 14.10.06 11:31 Количество правок: 1
|
|
|
|
<theory>
|
Криптоанализ алгоритма xor 12.10.06 09:34
Автор: andrew_ Статус: Незарегистрированный пользователь
|
Есть сообщение зашифрованое по такому алгоритму x<- x Xor y. Где x - исходное сообщение, y -ключ.
Ключ неизвестен. Необходимо расшифровать это сообщение.
|
|
Ну, ладно, в связи с тем, что не многие удосужаться... 12.10.06 12:02
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
Ну, ладно, в связи с тем, что не многие удосужаться расжевывать прописные истины, буду краток.
> Есть сообщение зашифрованое по такому алгоритму x<- x
> Xor y. Где x - исходное сообщение, y -ключ.
> Ключ неизвестен. Необходимо расшифровать это сообщение.
Будем отталкиваться, от метода гаммирования. Он является невзламываемым, если используется, так называетмый, "одноразовый блокнот". Если же ключ достаточно короткий и применяется многократно, то можно поломать статистическими методами.
Это очень простой, быстрый и легкий шифр, но с взаимоисключающими понятиями "стойкость" и "практичность". Либо стойкость не велика, но удобно, либо если стойкость высока, то очень неудобно пользоваться.
В принципе этого будет достаточно. Я так понимаю, что интересует теория, поскольку если б интересовал конкретный взлом, то были бы выложены числа. Так что примеры криптоанализа приводить не буду.
|
| |
Да ламерство же галимое!!! 13.10.06 09:34 [kstati, Zef]
Автор: Zef <Alloo Zef> Статус: Elderman
|
|
Если чел не выкладывает чисел, то ясно же, что он че такое XOR не сечет ни разу! Это же ежу ясно, что гамма в общем случае абсолютно стойка. Можно че-то пытаться подобрать имея тока фрагменты открытых и криптованных данных.
|
| | |
Гм 14.10.06 09:41
Автор: Heller <Heller> Статус: Elderman
Отредактировано 14.10.06 09:43 Количество правок: 1
|
> Если чел не выкладывает чисел, то ясно же, что он че такое
> XOR не сечет ни разу!
Очень странная связь между причиной и следствием.
> Это же ежу ясно, что гамма в общем
> случае абсолютно стойка.
Ну это спорно. Гамма будет абсолютно стойкой только в том случае, если:
а). Длина ключа больше или равна длине текста
б). Либо ключ, либо открытый текст не имеет статистических зависимостей внутри себя.
Перечисленные условия далеко не являются "общим случаем".
> Можно че-то пытаться подобрать
> имея тока фрагменты открытых и криптованных данных.
Допустим, мы имеет весь шифротекст. Допустим, мы имеем даже фрагмент ключа/открытого текста (вообще без разницы). Пускай длина ключа равна длине текста. Если ключ не имеет статистических зависимостей внитри себя (что как раз таки скорее всего), то не понятно как тогда его ломать. Если же мы знаем только фрагменты открытых и криптованных данных, то ломать что-либо вообще бесполезно.
"Одноразовый блокнот" при сформулированных мной выше условиях является абсолютно стойким шифром, какими бы данными мы ни обладали. Это доказано Шеноном еще аж в бородатом году.
|
| | | |
Все таки надо считать что это доказано теми, кто ввел термин... 10.12.06 23:11
Автор: MadBinom Статус: Незарегистрированный пользователь
|
> "Одноразовый блокнот" при сформулированных мной выше
> условиях является абсолютно стойким шифром, какими бы
> данными мы ни обладали. Это доказано Шеноном еще аж в
> бородатом году.
Все таки надо считать что это доказано теми, кто ввел термин "Стойкий в ситуации номер такой-то", и даже не бало доказано, так как очевидно вытекало из определений стойкости номер такой-то и шифра гаммирования. И, кстати, в определенных ситуациях он не абсолютно стойкий, так как при описанных тобой пунктах и при наличии зашифрованного сообщения количество информации о ключе не равно нулю(см. определения в Шеноне), так как известна минимальная (либо точная) длинна гаммы. Идеален во всех ситуациях лишь шифр нумерации(нумеруем все возможные сообщения :) ).
|
| | | | |
Бред от и до. 13.12.06 00:00
Автор: Heller <Heller> Статус: Elderman
|
Бред от и до.
> Все таки надо считать что это доказано теми, кто ввел
> термин "Стойкий в ситуации номер такой-то", и даже не бало
> доказано, так как очевидно вытекало из определений
> стойкости номер такой-то и шифра гаммирования. И, кстати, в
Абсюлютно стойкий шифр, это шифр, для которого
H(M)=H(M|C)
Здесь H - неопределенность, M - исходный текст, C - шифротрекст.
Другими словами, знание шифротекста не дает нам НИКАКИХ данных об исходном тексте. Именно в этой ситуации Шенон все и доказывал, а не "в ситуации номер такой-то". Если говорить про "ситуации", то для них для всех (известна часть ключа, известна часть шифра и пр.) есть куча неравенств для стойкости/сложности взлома/неопределнености и пр. Щеннон описал предельный случай. Так что в независимости от "ситуации" одноразовый блокнот при сформулированных мной условиях будет абсолютно стойким шифром (опять же в соответствии с определением абсолютной стойкости, с которым вряд ли кто поспорит).
> определенных ситуациях он не абсолютно стойкий, так как при
> описанных тобой пунктах и при наличии зашифрованного
> сообщения количество информации о ключе не равно нулю(см.
> определения в Шеноне), так как известна минимальная (либо
> точная) длинна гаммы. Идеален во всех ситуациях лишь шифр
> нумерации(нумеруем все возможные сообщения :) ).
1. Опять же, определение абсолютной стойкости вводится из определения неопределенности. Там НИГДЕ не фигурирует длина гаммы (и вообще этот термин больше применим к поточным шифрам - в этой ветке ему не место). Вы читали Шенона или для красного словца сослались на его "определения"?
2. Про "шифр нумерации" бред.
3. Прежде чем писать в форум, попробуйте почитать книжки. Это совет, типа добрый.
|
| | | | | |
Знаю, что шифртекст длины 100 байт. Исходный текст может... 13.12.06 00:22
Автор: MadBinom Статус: Незарегистрированный пользователь
|
> Другими словами, знание шифротекста не дает нам НИКАКИХ
> данных об исходном тексте.
Знаю, что шифртекст длины 100 байт. Исходный текст может быть длины 120?150?
А это уже информация.
Именно поэтому знание длины шифртекста определяет ограничения на длину гаммы. Отсюда и поправка про абсолютную стойкость. Неужели не ясно?
> 1. Опять же, определение абсолютной стойкости вводится из
> определения неопределенности. Там НИГДЕ не фигурирует длина
> гаммы (и вообще этот термин больше применим к поточным
> шифрам - в этой ветке ему не место). Вы читали Шенона или
> для красного словца сослались на его "определения"?
Я его даже сдавал :).
> 2. Про "шифр нумерации" бред.
Классический пример.
> 3. Прежде чем писать в форум, попробуйте почитать книжки.
В хотел было, но посмотрев FAQ форума, не увидел требования по чтению криптоталмудов. Читаю Донцову и еще какую-то... забыл.
> Это совет, типа добрый.
|
| | | |
Дык, это и есть "общий случай" 16.10.06 14:00
Автор: Zef <Alloo Zef> Статус: Elderman
|
> Гамма будет абсолютно стойкой только в том
> случае, если:
> а). Длина ключа больше или равна длине текста
> б). Либо ключ, либо открытый текст не имеет статистических
> зависимостей внутри себя.
Ключ ограниченной длинны и корреляция, это уже "частные случаи"
|
| | |
да знаю что такое XOR, мне нужен общий алгоритм а не... 13.10.06 10:50
Автор: andrew_ Статус: Незарегистрированный пользователь
|
> Если чел не выкладывает чисел, то ясно же, что он че такое
> XOR не сечет ни разу!
да знаю что такое XOR, мне нужен общий алгоритм а не конкретный пример взлома.
|
| | | |
Про методы стат. анализа шифротекста — читаем «Пляшущие человечки» Конан Дойля до просветления ;-) 14.10.06 11:29
Автор: HandleX <Александр М.> Статус: The Elderman
Отредактировано 14.10.06 11:31 Количество правок: 1
|
|
|
| | | | |
Оба-на! У нас с тобой потрясающее совпадение мыслей! 24.10.06 04:20
Автор: Zef <Alloo Zef> Статус: Elderman
|
|
Еще в пятницу мне это в голову пришло, да руки не дошли отпостить.
|
| | | | | |
Среда обитания мыслеформ ещё слабо изучена... Но там и не такое бывает :) 24.10.06 15:22
Автор: HandleX <Александр М.> Статус: The Elderman
|
|
|
| | | |
Имея только шифровку и зная алгоритм взломать "замену"... 13.10.06 12:15
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 13.10.06 12:24 Количество правок: 3
|
> да знаю что такое XOR, мне нужен общий алгоритм а не
> конкретный пример взлома.
Имея только шифровку и зная алгоритм взломать "замену" невозможно. Дело вовсе не в XORе, он просто зеркальный, его можно заменить парой ADD и SUB, например. Побайтовые операции как XOR, так и другие можно рассматривать, как замену того, что было до, на то, что получили после. Изменим операцию с XOR на ADD получим другую таблицу соответствия байт исходного текста и зашифрованного. Будем XORить с другим значением - будет другая таблица.
Один байт при подобном методе не используется, так как он очень легко ломается. Просили пример - вот вам: допустим шпион поксорил текст одним значением. Тогда контрразведчик определит, какое число в шифровке встречается чаще всего, которое чуть пореже, которое еще реже и так до самого редкого. Самое частовстречающееся число заменит буквой "О", следующее "Е", следующее более редкое "И", затем "А", и так до "Ч" или "Ф" - самых редких букв. Потом читаем текст, и может быть обнаружим ошибки, такие как вместо буквы "В" стоит буква "П" и наоборот. Может будут тройные циклические замены. Внесем коррективы и воаля!
Если используется циклическое использование ключа, когда ключ короче текста, то после того, как очередную букву проксорили с последним байтом ключа опять начинаем использовать первый, затем второй байт ключа и так далее по кругу. В этом случае взлом чуть сложнее, но аналогичен.
Если же ключ больше текста и при шифровке очередных данных берется новый ключ, то взломать почти невозможно.
Итак, если вам даны числа и сказано, что они с чем-то проксорены, то получить оригинал невозможно, даже если использовалось ксоренье всего с одним байтом! Нужно обязательно иметь что-то еще. Например свойство исходных данных. Как в случае с русским текстом мы знаем чатоту, с которой встречаются буквы в тексте. И вообще, что это читабельный текст, в нем есть словарные слова. Таким образом, при подборе ключа, например, мы сможем определить успешность угадывания ключа и, может быть, внесение корректив.
Очень сложно предложить метод криптоанализа, не зная что еще известно об исходных данных и о ключе. Может он достаточно короток и подобрать его можно простым перебором. Может мы имеем доступ к програмке-генерилке ключей и исследование ее покажет, что она всего-то может сгенерить сотню разных, хотя и длинных ключей. Тогда будем перебирать их все. Расшифровка одинм из них будет то, что нам надо, но только мы должны понять, глядя на результаты взлома, получилось или нет. Для этого надо знать или свойства исходных данных или их фрагмент достаточной длины.
В вашей задаче, как в начале, так и во втором посте нет ничего для криптоанализа. Одного алгоритма мало даже для никем неприменимого ксора. Если хотите ознакомится с большинством методов, поищите на соответствующих сайтах и выбирете наиболее подходящий в зависимости от условий. Один умный дядька сказал, что алгоритм должен быть стоек, даже если злоумыщленнику известно ВСЕ, кроме самого ключа. Стойкость - это невозможность взлома и получения ключа, кроме как перебора всех возможных ключей.
Наиболее удобным способом взлома XORа будет один из:
1. Имеем какой-либо текст и его шифровку. Тогда подсунув в шифровалку шифровку и исходный текст в качестве ключа получим ключ, которым уже сможем расшифровать требуемую шифровку.
2. Имеем возможность подсунуть текст шифровальшику и получить шифровку. Тогда подсовываем длинную последовательность нулей и получаем ключ (он же зашифрованная последовательность нулей), которым может расшифровать заданную шифровку.
Остальные методы я предлагаю найти самостоятельно в книжках или в интернете в электронном виде.
Уф, ну и написал опус, в надежде, что больше вопросов не будет, а то меня несколько дней не будет на форуме.
|
| | | | | |
Ну, да. Это для короткого ключа. Но ты же не сказал, что ключ - корокий. (см. "общий случай") 24.10.06 04:53
Автор: Zef <Alloo Zef> Статус: Elderman
|
|
|
| | | | | | |
Но то что там написано не получается 24.10.06 08:13
Автор: andrew_ Статус: Незарегистрированный пользователь
|
Не совсем понятно как считать совпадения, я считал так
int calc_equal(const char* str,int length)
{
int e_num=0;
for(int i=0;i<length;i++)
for(int j=i+1;j<length;j++){
if(str[i]==str[j]){
e_num++;
break;
}
}
return e_num;
}
str - строка, int length - длина строки
Тока получается все время слишком много совпадений.
|
| | | | | | | |
В той статье описывается как решить твой проблему в ситуации... 10.12.06 23:23
Автор: MadBinom Статус: Незарегистрированный пользователь
|
|
В той статье описывается как решить твой проблему в ситуации когда длина ключа короче, чем текст, а потом статистические свойства текста и соотношение длины текста к длине ключа МОГУТ позволить нам найти открытый текст(а могут и не позволить :) ). Так что рассказывай подробнее свою задачу.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
