Шифрованием xor с ключом в 1 байт.

← →
Ega23 © (2009-06-14 14:29) [40]

> то даже при шифровании xor-ом расшифровка невозможно.

Возможно всё. Вопрос в приемлимости сроков, за которые это сообщение будет расшифровано.

← →
Kerk © (2009-06-14 14:36) [41]

> Ega23 © (14.06.09 14:29) [40]

Поведай как :)
Более того, с разными ключами могут получаться разные осмысленные сообщения

← →
@!!ex © (2009-06-14 14:42) [42]

> [39] Kerk © (14.06.09 14:23)
> Ну или разве что введением паяльника ректально, чтобы узнать
> ключ.

Об этом и речь. :)

← →
Anatoly Podgoretsky © (2009-06-14 14:55) [43]

> @!!ex (14.06.2009 14:42:42) [42]

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

← →
TUser © (2009-06-14 15:25) [44]

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

Есть текст Т1 и ключ Т2 той же длины, дан результат их ксора, и известно, что оба текста - русские. Ясно, что буква "а" встречается чаще буквы "ф" и пр. Следовательно пары а-а (буква "a" в обоих текстах в некоторой позиции) а-о, р-д и т.д. попадаются чаще, чем а-ф, ц-ь и пр. Каждой паре символов соотвествует символ-результат ксора, например, для а-а -> #0. Можно рассмотреть и обратную функцию - из символа в возможные пары с их вероятностями. Например, символу #0 будет соотвествовать а-а с большой вероятностью, й-й с меньшей и пр. Имея зашифрованный текст, мы можем вычислить для каждой позиции вероятности разных символов. По умному такое распределение ероятностей называется "паттерн" или "профиль". Паттерны могут быть сопоставлены словам из словаря (язык текстов - русский) - существуют специальные алгоритмы для этого (динамическое программирование, скрытые марковские модели и пр.). Таким образом, для каждого положения в тексте получаем набор вероятностей слов, отбираем наиболее вероятные (тут задача облегчается тем, что оба текста осмысленны). Далее совсем легко найти ключ, ну и расшифровать все, что угодно.

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

← →
Kerk © (2009-06-14 15:48) [45]

> TUser © (14.06.09 15:25) [44]
> Имея зашифрованный текст, мы можем вычислить для каждой
> позиции вероятности разных символов.

Не можете. Потому что каждый байт текст проxorен разным байтом ключа.

← →
sniknik © (2009-06-14 15:55) [46]

TUser © (14.06.09 15:25) [44]
это "взлом" зашифрованного простой заменой букв, т.е. вместо "а" ставим например "т" и т.д.
ничего общего с обсуждаемым алгоритмом не имеет.

давай я тебе пример "правильного"/обсуждаемого алгоритма дам, расшифруешь?

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

← →
Ega23 © (2009-06-14 15:59) [47]

> вот зашифрованное слово - #0#0#0#0#0#0
> что это?

"А "жопс" - уже было?" (с) Comedy Club

← →
sniknik © (2009-06-14 16:04) [48]

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

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

← →
sniknik © (2009-06-14 16:04) [49]

час - часть

← →
Anatoly Podgoretsky © (2009-06-14 16:10) [50]

> sniknik (14.06.2009 15:55:46) [46]

Я расшифровал, это - Привет

← →
sniknik © (2009-06-14 16:13) [51]

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

← →
sniknik © (2009-06-14 16:14) [52]

> Я расшифровал, это - Привет
а до ключа? ;о)

← →
TUser © (2009-06-14 16:38) [53]

> Решение допускает обощение на случай случайного ключа (Т2
> есть псевдослучайная последовательность), правда в этом
> случае вероятно удастся понять тематику сообщения, но не
> точное содержание (мы будем знать с большой вероятностью
> некоторые слова из Т1).

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

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

← →
Anatoly Podgoretsky © (2009-06-14 17:00) [54]

> sniknik (14.06.2009 16:14:52) [52]

Я не расшифровал? :-(

← →
sniknik © (2009-06-14 17:06) [55]

> Так что в большинстве случаев указанный шифр эффективно ломается (при достаточной длине текста и ключа).
по тому что ты написал, гарантированно на 100% ломается частный случай - длинный текст и супер короткий ключ (1 символ), что выражается в простую замену символов.
при длинном тексте и коротком ключе, можно говорить о вероятности пар, и совпадении наиболее вероятных букв с ключем.
а вот при равенстве текста и ключа вероятность стремится к 0... даже если шифрованно другим осмысленным текстом. то что символы в текстах совпадут в вероятностные пары и покажут что то осмысленное практически невероятно.
так вот разговор то ведется про третий случай. а ты приводишь расшифровку первого и частично второго (недостаточно длинный текст или достаточно длинный ключ, и вероятность расшифровки будет ближе к 0 чем к какой либо приемлемой цифре).

← →
sniknik © (2009-06-14 17:06) [56]

выражается - вырождается

← →
тимохов © (2009-06-14 22:21) [57]

слуште, и как мне удается в последнее время завязать такой спор ))
я не специально. вот задал на РСДН вопрос о замыканиях, неделю уже спорят )))

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

← →
Кто б сомневался © (2009-06-15 15:00) [58]

> TUser © (14.06.09 15:25) [44]

Ты не поймешь алгоритм:
Смотри - имеется ключ: #$548#$783#$257#$61C#$48E#$766#$6E8#$016#$30B#$76C#$05B#$03A#$73F#$6C9#$597#$374 и имеется слово - "привет".

Теперь ксорим каждый символ, с ключем (цифрой):
П xor $548
Р xor $783
И xor $257

итд

При таком раскладе, не зная ключа, нереально найти искомое слово. Т.к. варинатов будет очень и очень и очень много.

← →
Кто б сомневался © (2009-06-15 15:06) [59]

Нереально в смысле невозможно. Т.к. можно набрать целый словарь слов из 5 букв (при расшифровке), но не узнаешь нужное.

← →
TUser © (2009-06-15 15:22) [60]

А в [44] не зря написано "текст из центральной российской библиотеки". То есть дана библиотекка возможных ключей, пусть и большая. А про произвольные ключи дана оговорка в [44] и в [53].

← →
Тимохов_ (2009-06-15 15:27) [61]

> TUser © (15.06.09 15:22) [60]

Лан, извиняй за мой менторский немного тон. Я просто не подумал, что ты говорил про случаи с некоторыми ограничениями :)

← →
Медвежонок Пятачок © (2009-06-15 15:51) [62]

Вы про шифр Г. Вернама?
Так он действительно абсолютно невзламываемый.

← →
Dennis I. Komarov © (2009-06-15 15:57) [63]

> При таком раскладе, не зная ключа, нереально найти искомое
> слово. Т.к. варинатов будет очень и очень и очень много.
>

Да любое слово или фраза из 6-ти символов ;)

← →
Медвежонок Пятачок © (2009-06-15 15:59) [64]

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

← →
Dennis I. Komarov © (2009-06-15 16:13) [65]

> Медвежонок Пятачок © (15.06.09 15:59) [64]

Ну, по-большому счету, да...

← →
Нат © (2009-06-15 21:00) [66]

>TUser © (15.06.09 15:22) [60]
Вы утверждаете, что при выполнении условий:
1. Имеется одно сообщение
2. Для кодирования применяется XOR
3. Длина ключа = длине сообщения
4. распределение знаков шифра и текста неравновероятно
5. Известен язык сообщения и шифра
6. Текст и ключ не равны
7... Какие еще будут ограничения?
То Вы в состоянии прочитать сообщение.
Верно я Вас понимаю?
Может Вам стоит еще подумать?

← →
TUser © (2009-06-15 21:44) [67]

> Нат © (15.06.09 21:00) [66]

4. неравновероятны и известны
7. сообщение достаточно длинное

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

Если еще и

8. Известна библиотека возможных ключей, пусть и достаточно большая,

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

← →
tesseract © (2009-06-15 22:40) [68]

> TUser © (15.06.09 21:44) [67]

> 3. Длина ключа = длине сообщения

Если ключ имеет реально случайную структуру - сложнее. Это уже не "простой XOR". Прикинем библиотеку ключей - ключ имеет равновероятностную структуру - т.е примем его длину как количество вариантов перебора - библиотека в топку - без инсайдерства инормацию не получить. Допустим сообщение имеет длину 2 килобайта - 2048 букв и символов (если ещё оно неразбавлено "мусором") Наша гипотетическая библиотека должна иметь ВСЕ 2048*256 вариантов. Какой в ней смысл ?

> Если ключ имеет реально случайную структуру

См. [53]

Откуда ж возьмутся параметры распределений?
Почему не взять там же сразу текст сообщения?

4. неравновероятны и известны
7. сообщение достаточно длинное

это ничего ровным счетом нам не дает.
даже если известен алфавит сообщения и его тематика.

> См. [53]

Библиотека там не упоминалась.

> Откуда ж возьмутся параметры распределений?

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

> Библиотека там не упоминалась.

И?

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

> [74] sniknik © (16.06.09 10:35)

Это всем. Вот интересно.

Библиотека. Начинаем с Толстого "Война и мир", когда закончился, Достоевский "Преступление и наказание", затем Шекспир "Гамлет", и далее по кругу

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

Начинаем с Толстого "Война и мир",
и продолжаем с ним же, но взяв только четные буквы.
потом только буквы с четных страниц издания 66 года.
затем нечетные буквы с нечетных страниц но издания 86 года.
и так далее.
потом тоже самое, но читая роман сначала задом наперед, затем еще как-нибудь.

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

> Медвежонок Пятачок © (16.06.09 12:15) [76]

Это как раз реализация табличного шифра с ключом равным длине сообщения. Правда это не XOR и выяснить слабости алгритма затруднено.

> [76] Медвежонок Пятачок © (16.06.09 12:15)

Это уже не суть важно последовательно или иным способом - берём то из библиотеки.

Что со вторым способом - это библиотека или как?

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

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

В этом и есть суть невскрываемости шифра Вернама.
А вовсе не в том, что вариантов ключа очень много.

> берём то из библиотеки.
какой библиотеки? посмотри в [44] там в алгоритме указана библиотека?

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

Шифрованием xor с ключом в 1 байт. Найти похожие ветки