В журнале «Xakep» написано, что XOR эффектиный криптоалгоритм

XOR со словарем.. берем байты начиная с (month*134+day*16753) в http://az.lib.ru/t/tolstoj_lew_nikolaewich … 0080.shtml  — и казалось бы хрен раскроешь…

Одноразовый блокнот не?

Xakep ни разу не изменился.

Нас, кстати, так и в универе учили. Самый простой и самый эффективный алгоритм — это накладывание псевдослучайной последовательности на исходное сообщение. Работает быстро, прост в реализации, не так легко подобрать параметры. Не так?

С помощью XOR, конечно.

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

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

Комментарий для Евгения Степанищева:

Ну, то есть, когда размер ключа равен размеру текста. Я не думаю, что это эффективность.

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

Комментарий для Евгения Степанищева:

>При длине ключа, превышающей длину сообщения, — невзламываемый.
Ну уж, вы не преувеличивайте.

Все правильно — невзламываемый. Правда есть еще одно «небольшое» условие — ключ может использоваться только один раз.

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

Таким образом, зашифрованное сообщение не переедет ни бита информации о ключе и исходном сообщении. Это доказал Клод Шеннон, если я не путаю.

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

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

Комментарий для Евгения Степанищева:

Кстати, с текстом в какой-нибудь UTF-8 ещё смешнее (то есть если мы знаем формат файла, то XOR ломается много проще). Скажем, зашифрован текст в UTF-8 и там русские буквы. Тогда каждый второй байт ключа мы уже знаем с большой вероятностью — в UTF-8 (на русском алфавите) там стоят вполне конкретные значения.

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

Комментарий для Евгения Степанищева:

Военным? У них лучшая техника сейчас. Хотя, может, не в нашей армии?

Военные — хитрые черти. Они, в случае чего, хотят продолжать вести боевые действия, даже если на них кастанули электромагнитный импульс ;)

Комментарий для Евгения Степанищева:

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

Как я понял, алгоритм «простое отображение одного множества в другое» — это алгоритм замены.

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

Частным случаем шифра замены является шифр Цезаря, при котором каждый символ заменяется другим, отстоящим от него в алфавите на фиксированное число позиций (в данном случае исходный и конечный алфавиты совпадают). Например: а→в, б→г, в→д, …, ю→а, я→б.

Так вот, шифр замены НЕ ЯВЛЯЕТСЯ надежным, даже при условии одноразового использования ключей.

Он хорошо взламывается с помощью частотного анализа. Дело в том, что в исходном сообщении вероятность появления тех или иных символов не одинаковая. Так, например, в русском языке чаще всего встречается буква «о», а втором месте «е», на третьем «а» и т.д.

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

А при использовании алгоритма XOR частотность НЕ сохраняется, поэтому при соблюдении перечисленных условий взломать его НЕ возможно.

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

Комментарий для Евгения Степанищева:

>Как я понял, алгоритм «простое отображение одного множества в другое» — это алгоритм замены.
Нет, это математическое понятие. Одно множество отображается в другое.

Это-то понятно. Не понятно сразу, какие именно множества Вы имели в виду.

Я предположил, что это множество допустимых символов (алфавит) исходного сообщения и аналогичное множество для шифротекста.

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

«Отображение множества» означает, в данном случае, что одно множество текстов отображается в другое. Идея простая, но ограниченная — нужно договорить о замене множества всех текстов,

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

Но, предположить это, вряд ли, было возможно:-) Ведь Вы говорили, это «[отображение] используется довольно часто».

Но про отображение текстов (при котором надо договориться о замене множества всех текстов) совсем нельзя сказать, что оно используется ЧАСТО. Ведь множество текстов, даже относительно короткой длины настолько велико, что договориться о замене каждого текста каждым невообразимо сложно (Разумеется, если это случайное отображение где надо договариваться о замене каждого текста, а не построенное на каких-то правилах, учитывающих особенности текста. Ибо неслучайность делает замену боле уязвимой, т.к. преподается, что противник тоже знает используемое правило).

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

Комментарий для Евгения Степанищева:

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

Это недостаток — скорость. Хорошие алгоритмы ещё и такие, перебирать которые долго (по крайней мере на текущих мощностях), а методы их взлома, часто, сводятся к тому, что увеличить скорость перебора (например, снижая количество перебираемых вариатов).

XOR же перебирается очень быстро. Условия, при которых XOR хоть сколько-нибудь надёжен, довольно сложно выполнить.

Ну, это, опять же, понятно :-)

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

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

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

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

Либо каким-то образом передавать эти одноразовые ключи. Но тогда возникнет проблема передачи ключа, т.е. нам нужен будет ключ, чтобы зашифровать передаваемый ключ, чтобы зашифровать …

Комментарий для Евгения Степанищева:

В данном случае, XOR ничем не лучше чем сложение, например. Только сложение проще.

XOR — это и есть сложение. Побитовое сложение без переноса.

Комментарий для Евгения Степанищева:

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

Вот здесь я с Вами принципиально НЕ соглашусь.

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

Что такое «абсолютные криптосистемы»? На свете тонны криптоалгоритмов и есть очень хорошие. Некоторые ломать (упрощать перебор) не умеют.

Попробую объяснить. Я думаю, Вы это и так лучше меня знаете, просто, возможно мы используем разные термины, поэтому Вы не соотнесли одно с другим.

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

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

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

На этом способе основан алгоритм «Шифр Вернама». Его абсолютную стойкость доказал Клод Шеннон.

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

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

Так вот, самое главное.

Противник может знать некоторую информацию о структуре сообщения. Например, что каждый второй байт заполнен нулями. Тогда он узнает и каждый второй байт ключа. Но, это НЕ ДАЕТ ему никакой информации про другие, неизвестные байты ключа и сообщения. Ведь то, что символы встречаются случайно, как раз и говорит о том, что их появление не зависит от других (возможно известных противнику) символов.

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

>Так вот, в абсолютной криптосистеме, скорость — это не недостаток, а преимущество.
Не понимаю почему это так. Или абсолютная криптосистема, это быстрая, но там где перебор такой огромный, что это медленно? Тогда ключ должен быть невообразимой длины, иначе что ещё перебирать-то?

Еще раз повторю, в абсолютных криптосистемах перебор не то что огромный, он просто теоретически НЕВОЗМОЖЕН. В результате перебора мы просто получаем множество всех возможных сообщений, с одинаковой вероятностью того, что каждое из них и было на самом деле исходным.

И использование более быстрого алгоритма на ускорение или замедление этого невозможного перебора никак не повлияет. Ноль умножить на любое число всегда ноль.

А вот на скорость шифрования повлияет положительно, что нам выгодно.

Комментарий для Евгения Степанищева:

> Либо каким-то образом передавать эти одноразовые ключи. Но тогда возникнет проблема передачи ключа, т.е. нам нужен будет ключ, чтобы зашифровать передаваемый ключ, чтобы зашифровать …
Это решаемая задача, кстати. В математике есть забавные алгоритмы для этого.

Этот алгоритм называется «Алгоритм Диффи — Хеллмана» (и ему подобные).

Он основан на вычислительной сложности операции дискретного логарифмирования. Т.е. очень легко вычислить k = b^a mod p. Но очень сложно провести обратную операцию, т.е. по известным k, b и p найти a.

Он, действительно, является практические надежным, т.е. время взлома очень велико.

Но, он НЕ является теоретические надежным т.е., в принципе, за определенное время может быть взломан.

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

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

Кроме того, грозились создать каналы связи, работающие по квантовому признаку

Я плохо знаю эту тему, тут ничего по делу сказать не могу.

Комментарий для Евгения Степанищева:

Я прямо сказал, что считаю что Вы это хорошо знаете: «Я думаю, Вы это и так лучше меня знаете, просто, возможно мы используем разные термины, поэтому Вы не соотнесли одно с другим».

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

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

Комментарий для Евгения Степанищева:

Ага, ок, теперь я понял.
Я немного тороплюсь сегодня, читаю не вдумчиво, вот отсюда и недопонимание.

Ок, хорошо, что все прояснилось, и мы поняли, что каждый имел в виду :-)

Резюмирую для тех, кто не хочет читать подряд все обсуждение целиком:

В абсолютной криптосистеме при любом ключе и любом шифротексте перебор возвращает всегда один и тот же результат — список всех возможных осмысленных сообщений длины n.

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

По этой причине, в абсолютной криптосистеме алгоритм XOR ЭФФЕКТИВЕН: благодаря своей простоте, он позволяет заметно увеличить скорость шифрования; но при этом никак не влияет на скорость перебора злоумышленником, т.к. перебор все равно невозможен.

Но во всех остальных системах перебор возможен. Там простота XOR'а позволит злоумышленнику существенно повысить скорость этого перебора. И поэтому, в них XOR является НЕЭФФЕКТИВНЫМ алгоритмом.

Таким образом, в абсолютных криптосистемах XOR — эффективен; а во всех остальных (а именно они чаще всего используются на практике) — неэффективен.

Такие дела.

Комментарий для www.alik.su:

вам присваивается звание Капитан Очевидность

Учите матчасть
http://ru.wikipedia.org/wiki/%D0%A8%D0%B8% … 0%BC%D0%B0

Евгений Степанищев (bolknote.ru), это эффективный алгоритм. сгенерировать ключ на основе первоначального ключа не сложно, и применить его к полезным данным очень быстро и очень эффективно, учите матчасть