В журнале «Xakep» написано, что XOR эффектиный криптоалгоритм
Ответ очень прост — нужно вспомнить алгоритмы шифрования. Самым простым и одним из самых эффективных (при правильном использовании) криптоалгоритмов является так называемое XOR-шифрование.
Цитата из журнала «Xaxep». OMG! XOR назвали «эффективным криптоалгоритмом».
XOR со словарем.. берем байты начиная с (month*134+day*16753) в http://az.lib.ru/t/tolstoj_lew_nikolaewich/text_0080.shtml — и казалось бы хрен раскроешь...
Одноразовый блокнот не?
Xakep ни разу не изменился.
Комментарий для zero_sharp:
Нет, приведенный в первом комментарии алгоритм с «Анной Карениной» называется «Книжный шифр».
А алгоритм «Одноразовый блокнот» предполагает, что ключ сгенерирован случайно, а не взят из книги.
Нас, кстати, так и в универе учили. Самый простой и самый эффективный алгоритм — это накладывание псевдослучайной последовательности на исходное сообщение. Работает быстро, прост в реализации, не так легко подобрать параметры. Не так?
С помощью XOR, конечно.
Ну если не цепляться к конкретной формулировке, то вообще говоря близко к истине. Под «эффективностью» здесь вероятно понимается криптостойкость, тогда это тот самый одноразовый блокнот. Правда не понятно почему «один из», а не «самый», но мелочи же ведь.
Комментарий для heller.ru/blog/:
Ну, то есть, когда размер ключа равен размеру текста. Я не думаю, что это эффективность. Для меня эффективнее алгоритм, у которого при равной стойкости размер ключа меньше, а таких хватает и они, конечно, не на XOR основаны.
Комментарий для www.evgenysamsonov.ru:
Чуть выше есть мой ответ.
При длине ключа, превышающей длину сообщения, — невзламываемый.
Комментарий для Евгения Степанищева:
А для кого-то эффективность — это возможность повторить в условиях отсутствия вычислительной техники, в принципе. Военным важно, например.
Комментарий для www.shmidt.net:
Ну уж, вы не преувеличивайте.
Всё зависит от природы сообщения. Скажем, пришло сообщение, пять букв, мы знаем, что там — русский текст (скажем, это русские переговариваются). Мы перебираем все ключи, сколько есть 256^5 = 1099511627776. XOR крайне простая и дешёвая операция, такое количество ключей переберётся очень быстро.
Далее (или в процессе), из всего полученного выбираем словарные слова или их сочетание. Что-то подходит? Передаём человеку. Несколько таких коротких сообщений и начало ключа у нас в кармане. Дальше, расшифровывая более длинные сообщения, мы подставляем начало ключа и точно так же (по контексту) стараемся расшифровать следующее слово.
Как не посмотри — XOR полная ерунда.
Военным? У них лучшая техника сейчас. Хотя, может, не в нашей армии? Но и в этом случае есть куда более удобные алгоритмы, чем XOR. Во Вторую мировую американцы вообще использовали язык индейцев чероки ( http://ru.wikipedia.org/wiki/%D0%AF%D0%B7%D1%8B%D0%BA_%D1%87%D0%B5%D1%80%D0%BE%D0%BA%D0%B8 ), но есть методы и попроще, почитайте, литературы — навалом.
P.S. Надо какой-то флаг вводить, я уже не помню с кем я на «вы», с кем на «ты» :( Вот с вами я давно переписываюсь, а как мы обращаемся друг к другу, я не помню.
Комментарий для www.shmidt.net:
Кстати, с текстом в какой-нибудь UTF-8 ещё смешнее (то есть если мы знаем формат файла, то XOR ломается много проще). Скажем, зашифрован текст в UTF-8 и там русские буквы. Тогда каждый второй байт ключа мы уже знаем с большой вероятностью — в UTF-8 (на русском алфавите) там стоят вполне конкретные значения.
Кроме того, в UTF-8 есть простенькая система обнаружения ошибок, что нам очень поможет в атаке на XOR.
Комментарий для Евгения Степанищева:
Все правильно — невзламываемый. Правда есть еще одно «небольшое» условие — ключ может использоваться только один раз.
Всего условий абсолютной (принципиально невзламываемой) криптографической системы три:
Таким образом, зашифрованное сообщение не переедет ни бита информации о ключе и исходном сообщении. Это доказал Клод Шеннон, если я не путаю.
Но если пренебречь хотя бы одним из этих условий, то да — противник при наличие некоторого количества шифротекстов сможет легко взломать ключ и расшифровать не только текущее сообщение, но и все предыдущие (зашифрованные этим ключом).
Во время холодной войны, как раз, была такая история. Американцы накапливали на компьютере всю перехваченную зашифрованную советскую переписку и автоматичсеки ее анализировали. И когда какой-то советский агент по ошибке использовал ключ несколько раз, то переписка была взломана и произошел крупный провал резидентуры. Я не помню, какой именно, но, по-моему, эта история связана с провалом Рудольфа Абеля.
Комментарий для Евгения Степанищева:
Да, мы узнаем каждый второй байт ключа. Но, если ключ используется только один раз (т. е. этот ключ больше никогда использоваться не будет), то нам эти байты абсолютно ничего не дают.
Комментарий для www.alik.su:
При таких условиях, любой алгоритм «не взламываемый», например, простое отображение одного множества в другое (что используется довольно часто).
Это совершенно не говорит о том, что XOR «эффективный криптоалгоритм». Или хотя бы надёжный.
Комментарий для Евгения Степанищева:
Военные — хитрые черти. Они, в случае чего, хотят продолжать вести боевые действия, даже если на них кастанули электромагнитный импульс ;)
Комментарий для www.shmidt.net:
Мне кажется, что для этого должны существовать более эффективные алгоритмы, чем XOR. В данном случае, XOR ничем не лучше чем сложение, например. Только сложение проще.
Комментарий для Евгения Степанищева:
Как я понял, алгоритм «простое отображение одного множества в другое» — это алгоритм замены.
Где каждый символ из алфавита (т. е. множества допустимых символов) исходного сообщения однозначно заменяется (т. е. отображается) на символ из алфавита шифротекста.
Частным случаем шифра замены является шифр Цезаря, при котором каждый символ заменяется другим, отстоящим от него в алфавите на фиксированное число позиций (в данном случае исходный и конечный алфавиты совпадают). Например: а→в, б→г, в→д, ..., ю→а, я→б.
Так вот, шифр замены НЕ ЯВЛЯЕТСЯ надежным, даже при условии одноразового использования ключей.
Он хорошо взламывается с помощью частотного анализа. Дело в том, что в исходном сообщении вероятность появления тех или иных символов не одинаковая. Так, например, в русском языке чаще всего встречается буква «о», а втором месте «е», на третьем «а» и т. д.
Так вот, при простом отображении множеств частотность элементов сохраняется. И если, например, в получившемся шифротексте чаще всего встречается символ «ъ», на втором месте «й», а на третьем — «э», то можно сделать вывод, что использовалась следующая замена: «о» → «й», «е» → «й», «а» → «э».
А при использовании алгоритма XOR частотность НЕ сохраняется, поэтому при соблюдении перечисленных условий взломать его НЕ возможно.
Хотя, конечно, вместо XOR здесь можно использовать и какой нибудь другой алгоритм. Просто XOR является одним из самых быстрых (вычислительно эффективных алгоритмов). А потребности в более изощренных алгоритмах не возникает, т. к. XOR уже обеспечивает абсолютную стойкость (разумеется, если нас усматривают три перечисленных условия).
Комментарий для www.alik.su:
Нет, это математическое понятие. Одно множество отображается в другое.
Конечно.
Безусловно. Только я ведь не про него говорю. Не надо думать, что эксперт по безопасности не знает таких простых вещей :)
Я больше скажу, даже замены отдельных слов на другие не спасают. Если алгоритмы, выявляющие паттерны в речи и реагирующие на них, а не на слова, которые там используются.
«Отображение множества» означает, в данном случае, что одно множество текстов отображается в другое. Идея простая, но ограниченная — нужно договорить о замене множества всех текстов, хотя для какие-то ситуаций шифр вполне себя оправдывает. И взломать его крайне тяжело.
Комментарий для www.alik.su:
Это недостаток — скорость. Хорошие алгоритмы ещё и такие, перебирать которые долго (по крайней мере на текущих мощностях), а методы их взлома, часто, сводятся к тому, что увеличить скорость перебора (например, снижая количество перебираемых вариатов).
XOR же перебирается очень быстро. Условия, при которых XOR хоть сколько-нибудь надёжен, довольно сложно выполнить.
Комментарий для Евгения Степанищева:
Это-то понятно. Не понятно сразу, какие именно множества Вы имели в виду.
Я предположил, что это множество допустимых символов (алфавит) исходного сообщения и аналогичное множество для шифротекста.
Поскольку множество по-определению не может содержать дублирующиеся элементы, то отображение символов однозначно. Т. е. каждому элементу первого множества (символу алфавита исходного сообщения) всегда соответствует один и тот же элемент второго множества (символ алфавита шифротекста). А это и есть простейший алгоритм замены.
Да, теперь я понял, что под множествами имелись в виду не алфавиты сообщения и шифротекста, а множества исходных и зашифрованных текстов.
Но, предположить это, вряд ли, было возможно:-) Ведь Вы говорили, это «[отображение] используется довольно часто».
Но про отображение текстов (при котором надо договориться о замене множества всех текстов) совсем нельзя сказать, что оно используется ЧАСТО. Ведь множество текстов, даже относительно короткой длины настолько велико, что договориться о замене каждого текста каждым невообразимо сложно (Разумеется, если это случайное отображение где надо договариваться о замене каждого текста, а не построенное на каких-то правилах, учитывающих особенности текста. Ибо неслучайность делает замену боле уязвимой, т. к. преподается, что противник тоже знает используемое правило).
А вот отображение алфавитов, как раз, используется достаточно часто (особенно, когда предполагается, что противник не располагает большими ресурсами или квалификацией, например в случае любовной переписки). Поэтому, я и предположил, что под отображением Вы имели в виду именно отображение алфавитов, т. е. шифр замены.
Комментарий для www.alik.su:
Есть масса случаев, когда это и не нужно. Например, требуется узнать — прошло всё по плану или пора сматываться. Как пример. Ну, то есть вполне есть ситуации, когда нужно выбрать из 3-4 вариантов. Или из 10, скажем.
В фильмах — сплошь и рядом. В жизни я и сам, признаться, использую такие вещи, а так же вкладываю информацию для посвящённых в обычные тексты. Собственно, кроме этого я вообще мало что использую в обычной жизни :)
Комментарий для Евгения Степанищева:
Ну, это, опять же, понятно :-)
Просто в том комментарии мы обсуждали не XOR вообще, а его использование применительно к абсолютной криптографической системе (удовлетворяющей трем правилам Шеннона).
Так вот, в абсолютной криптосистеме, скорость — это не недостаток, а преимущество. Недостаток в виде скорости перебора нас не волнует, т. к. перебор в данной системе все равно невозможен. А вот преимущество высокой скорости шифрования как раз будет полезно.
Другое дело, что, да, действительно, абсолютные криптосистемы часто сложно использовать на практике.
Нам надо либо запастись тоннами шифроблокнотов, чтобы иметь возможность уничтожать каждый блокнот после его использования.
Либо каким-то образом передавать эти одноразовые ключи. Но тогда возникнет проблема передачи ключа, т. е. нам нужен будет ключ, чтобы зашифровать передаваемый ключ, чтобы зашифровать ...
Комментарий для www.alik.su:
Это если рассматривать идеальных конец в вакууме. Если мы знаем хоть что-то о природе того, что надо расшифровать (например, что перед нами текст на человеческом языке), это уже зацепка, причём хорошая.
Что такое «абсолютные криптосистемы»? На свете тонны криптоалгоритмов и есть очень хорошие. Некоторые ломать (упрощать перебор) не умеют.
Не понимаю почему это так. Или абсолютная криптосистема, это быстрая, но там где перебор такой огромный, что это медленно? Тогда ключ должен быть невообразимой длины, иначе что ещё перебирать-то?
Комментарий для www.alik.su:
Это решаемая задача, кстати. В математике есть забавные алгоритмы для этого. Кроме того, грозились создать каналы связи, работающие по квантовому признаку (попытка измерения приводит к изменению характеристик канала, а значит нельзя прослушать канал так, чтобы участники этого не знали). Но я не знаю что с ними стало, не следил.
Комментарий для Евгения Степанищева:
XOR — это и есть сложение. Побитовое сложение без переноса.
Комментарий для Евгения Степанищева:
Вот здесь я с Вами принципиально НЕ соглашусь.
Если система обладает абсолютной криптографической стойкостью, то расшифровать сообщение принципиально невозможно! Даже за бесконечное время! Даже если мы знаем о нем любую информацию! Т. е. на основе этой информации мы не сможем получить ничего сверх того, что мы знаем и эта информация не даст нам ни малейшей зацепки.
Попробую объяснить. Я думаю, Вы это и так лучше меня знаете, просто, возможно мы используем разные термины, поэтому Вы не соотнесли одно с другим.
Абсолютная криптосистема (система, обладающая абсолютной криптографической стойкостью) — это система, при использовании которой шифротекст не дает никакой информации об исходном сообщении. Т. е. вероятность того что шифротекст был получен на основе исходного сообщения равна вероятности его получения на основе любого другого возможного сообщения.
И поэтому, какой бы перебор противник не применял, сколько бы времени и вычислительных ресурсов у него ни было (хоть бесконечность), он все равно не сможет восстановить исходное сообщение. Ведь на месте реального исходного сообщения с той же самой вероятностью могло быть любое другое сообщение, и противник просто не сможет узнать какое именно было на самом деле.
Один из способов достижения абсолютной криптостойкости (другие я не знаю) состоит в том, чтобы вероятность появления любого возможного символа шифротекста в любом месте всегда одинаковая. Т. е. шифротекст представляет собой абсолютно случайную последовательность символов.
На этом способе основан алгоритм «Шифр Вернама». Его абсолютную стойкость доказал Клод Шеннон.
Шифротекст получается путем применения, как-раз, таки, операции XOR между исходным сообщением и ключом. Ключ, как я уже говорил, должен удовлетворять трем требованиям:
Перебор ключей в данном случае означает перебор всех возможных строк символов равных длине сообщения. Хоть это и неимоверно долго, но теоретически возможно. Однако, в результате расшифрования с этими перебираемыми ключами, противник на выходе получит просто уже известное ему множество всех возможных исходных сообщений. Вероятность каждого сообщения одинакова, т. к. вероятность всех ключей одинакова. И об исходном сообщении противник ничего не узнает.
Так вот, самое главное.
Противник может знать некоторую информацию о структуре сообщения. Например, что каждый второй байт заполнен нулями. Тогда он узнает и каждый второй байт ключа. Но, это НЕ ДАЕТ ему никакой информации про другие, неизвестные байты ключа и сообщения. Ведь то, что символы встречаются случайно, как раз и говорит о том, что их появление не зависит от других (возможно известных противнику) символов.
Кроме того, противник не сможет использовать ставшие ему известными байты ключа при расшифровке других сообщений, т. к. ключ используется только один раз и в других сообщениях будут использоваться другие ключи другими байтами.
Еще раз повторю, в абсолютных криптосистемах перебор не то что огромный, он просто теоретически НЕВОЗМОЖЕН. В результате перебора мы просто получаем множество всех возможных сообщений, с одинаковой вероятностью того, что каждое из них и было на самом деле исх
Комментарий для Евгения Степанищева:
Этот алгоритм называется «Алгоритм Диффи — Хеллмана» (и ему подобные).
Он основан на вычислительной сложности операции дискретного логарифмирования. Т. е. очень легко вычислить k = b^a mod p. Но очень сложно провести обратную операцию, т. е. по известным k, b и p найти a.
Он, действительно, является практические надежным, т. е. время взлома очень велико.
Но, он НЕ является теоретические надежным т. е., в принципе, за определенное время может быть взломан.
И поэтому, при его использовании, абсолютная криптосистема перестает быть абсолютной криптосистемой. Более того, на сколько я знаю, для абсолютных криптосистем проблема передачи ключей вообще не решаема (при сохранении абсолютности).
Другое дело, что на практике нам часто не нужна абсолютная криптостойкость, и достаточно, чтобы для противника расшифровка стоила дороже самой информации, или время расшифровки было дольше, чем информация будет актуальной. И тогда этот алгоритм очень даже подходит. Правда, он не может защитить сообщение от подмены противником, но эту защиту обеспечивают алгоритмы шифрования с открытым ключом типа RSA.
Я плохо знаю эту тему, тут ничего по делу сказать не могу.
Комментарий для www.alik.su:
Мне как-то даже неудобно :) Неужели я произвожу впечатление человека, который это всё не знает?
Впрочем, про шифрование я очень редко пишу (если вообще писал), так что можно подумать, что я не в теме. Это не так :)
Комментарий для Евгения Степанищева:
Я прямо сказал, что считаю что Вы это хорошо знаете: «Я думаю, Вы это и так лучше меня знаете, просто, возможно мы используем разные термины, поэтому Вы не соотнесли одно с другим».
Именно поэтому и удивился, когда Вы сказали, что МОЖНО взломать текст (т. е. получить о нем какую-то заранее неизвестную информацию), зашифрованный в абсолютной криптосистеме (например, использовав как зацепку известную о нем информацию, или с помощью перебора, имея даже бесконечные ресурсы).
Еще раз повторю, видимо мы просто используем разную терминологию (например термин «абсолютная криптографическая система и стойкость»). Так вот я и пытался показать, что я имею в виду под этим термином (хотя, он, вроде бы достаточно общеупотребительный). Т. е. систему, которую нельзя взломать, даже перебором и обладая бесконечными ресурсами.
Комментарий для www.alik.su:
Ага, ок, теперь я понял.
Я немного тороплюсь сегодня, читаю не вдумчиво, вот отсюда и недопонимание.
Комментарий для Евгения Степанищева:
Ок, хорошо, что все прояснилось, и мы поняли, что каждый имел в виду :-)
Резюмирую для тех, кто не хочет читать подряд все обсуждение целиком:
В абсолютной криптосистеме при любом ключе и любом шифротексте перебор возвращает всегда один и тот же результат — список всех возможных осмысленных сообщений длины n.
Поэтому результат шифрования абсолютной криптосистемы нельзя взломать даже при наличии неограниченных ресурсов.
По этой причине, в абсолютной криптосистеме алгоритм XOR ЭФФЕКТИВЕН: благодаря своей простоте, он позволяет заметно увеличить скорость шифрования; но при этом никак не влияет на скорость перебора злоумышленником, т. к. перебор все равно невозможен.
Но во всех остальных системах перебор возможен. Там простота XOR’а позволит злоумышленнику существенно повысить скорость этого перебора. И поэтому, в них XOR является НЕЭФФЕКТИВНЫМ алгоритмом.
Таким образом, в абсолютных криптосистемах XOR — эффективен; а во всех остальных (а именно они чаще всего используются на практике) — неэффективен.
Такие дела.
Комментарий для www.alik.su:
вам присваивается звание Капитан Очевидность
Комментарий для isk.livejournal.com:
Если бы это сразу было так очевидно, то не было бы дискуссии на десять страниц.
Но, если после «Резюме (подведения итогов дискуссии)» в моем последнем комментарии все стало просто и очевидно, то это, конечно, очень хорошо и я не зря старался :-)
Учите матчасть
http://ru.wikipedia.org/wiki/%D0%A8%D0%B8%D1%84%D1%80_%D0%92%D0%B5%D1%80%D0%BD%D0%B0%D0%BC%D0%B0
Комментарий для cyanide_burnout:
Лучше вы учите матчасть. Тут размер ключа совпадает с размером теста. Это, по-вашему, эффективный алгоритм?