Код не обязательно да Винчи

[бобыль]

Сегодня в связи с модой на Код да Винчи вот какой у меня возник вопрос.

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

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

[lofar]

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

Пример.

1) Открытое сообщение:      "Большинство криптосистем работает с блоками".

2) Блоки (по 8 знаков/байт): "Большинс","тво крип","тосистем"," работае","т с блок","ами     ".

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

Отмечу, что Ваш вопрос вовсе не лишен смысла. Особенности структуры руского (или любого другого) языка накладывает определенные ограничения на вид блоков. Скажем, блок вида "ййЭЭцц11" вряд ли появится в реальном сообщении. Эти принципы используются при статистическом анализе криптосистем.

[Yuri Gendelman]

lofar писал(а):

Большинство криптосистем работает с блоками...

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

[бобыль]

У меня еще два вопроса, посложнее и попроще:

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

2. Почему говорят Код да Винчи, но не говорят Шифр да Винчи?

[photon]

бобыль писал(а):

2. Почему говорят Код да Винчи, но не говорят Шифр да Винчи?

Осмелюсь предположить: Хотя слова и синонимичны, но выбор именно слова "код" можно объяснить происхождением слов: во французском языке слово "chiffre" буквально переводится как "цифра", очевидно, что в данном случае имеется в виду другое, и более удачным является все-таки выбор слова "код".

[ИСН]

1. Это вопрос сильно философский...
2. А это просто неграмотный перевод.
Upd. Да нет, какой там французский. Замороченный жизнью переводчик смотрит на обложку, там написано "The Da Vinci Code". Что он напишет по-русски? Будет ли лезть в высокие материи?

[Yuri Gendelman]

бобыль писал(а):

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

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

[lofar]

В математике код и шифр (криптосистема) четко разделены. Код это произвольное подмножество в $\Omega^n$, где $\Omega$ --- конечный алфавит (если код двоичный, то $\Omega=\{0,1\}$). Коды используются для передачи сигнала по зашумленным каналам. Классическим примером кода является код проверки на четность (Parity Check).

Криптосистема это четверка $(X,Y,K,f)$, где $X$ --- множество открытых сообщений, $Y$ --- множество зашифрованных сообщений, $K$ --- множество ключей, и $f\colon X\times K\to Y$ --- функция шифрования. При данном ключе $k\in K$, открытое сообщение $x\in X$преобразуется в зашифрованное сообщение $f(k,x)$.

[Yuri Gendelman]

lofar писал(а):

В математике код и шифр (криптосистема) четко разделены. Код это произвольное подмножество в $\Omega^n$, где $\Omega$ --- конечный алфавит
...
Криптосистема это четверка $(X,Y,K,f)$

Мне кажется, приведенное Вами определение кода - это определение произвольного языка над конечным алфавитом. Кодирование - это отображение языка на язык: тройка $(X,Y,f)$, т.е. нечто подобное тому, что Вы определили как шифр. Это конечно вопрос терминологии, но по-моему шифр - это частный случай кода, для которого функция кодирования - односторонняя (обращение ее требует очень много времени и/или выч. ресурсов).

[незваный гость]

бобыль писал(а):

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

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

[lofar]

Yuri Gendelman писал(а):

Кодирование - это отображение языка на язык...

Да, Вы правы, есть и такое кодирование. Термин кодирование перегружен. Я говорил о кодах исправляющих ошибки. Это не совсем язык, поскольку рассматриваются слова исключительно длины $n$, и это существенно. Так, пресловутый код проверки на четность есть подмножество в $\mathbb Z_2^n$ вида $\{(x_1,\ldots,x_{n-1},x_n)|x_n = x_1+\ldots+x_{n-1}\}$.

незванный гость писал(а):

Классический пример -- одноразовый блокнот, последовательность случайных цифр.

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

[Yuri Gendelman]

lofar писал(а):

Я говорил о кодах исправляющих ошибки. Это не совсем язык, поскольку рассматриваются слова исключительно длины $n$, и это существенно. Так, пресловутый код проверки на четность есть подмножество в $\mathbb Z_2^n$ вида $\{(x_1,\ldots,x_{n-1},x_n)|x_n = x_1+\ldots+x_{n-1}\}$.

Говорим мы, разумеется, об одном и том же. Я просто больше привык к представлению, например, Вашего примера как отображения $\mathbb Z_2^{n-1} \Rightarrow \mathbb Z_2^n$ вида $(x_1,\ldots,x_{n-1}) \Rightarrow (x_1,\ldots,x_{n-1}, \bigoplus_{i=1}^{n-1}{x_i})$. Но это лишь различия в терминологии.

[бобыль]

Yuri Gendelman писал(а):

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

Вообще-то про коды/шифры я спросил потому, что восхищен ажиотажем вокруг Кода да Винчи. Сходите в книжный магазин и посмотрите, сколько продается книг а-ля Код да Винчи - названий 30, не меньше! Что это такое - очередное поветрие или нечто большее? Быть может, массовое сознание дойдет однажды до понимания окружающего нас мира как некой вселенской шифровки?

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

Или вот: предположим, что мир вокруг нас - это кинофильм с вмонтированным в него "25-м кадром" (постоянно внушающим нам, что мир этот настоящий, натуральный, подлинный, настоящий, натуральный, подлинный...). Как бы мы могли об этом догадаться?

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

Наконец, кому, если не нам, адресованы эти шифровки?

[незваный гость]

бобыль писал(а):

Быть может, массовое сознание дойдет однажды до понимания окружающего нас мира как некой вселенской шифровки?

Почему бы миру действительно не быть шифровкой?

Потому, что миру нечего скрывать. Хотя есть, что кодировать.

Да и от кого скрывать-то? От этой обезьяны, всего 4-6 миллионов лет назад слезшей с дерева, и невесть что о себе возомнившей? Еще от инфузорий прятать начнем!... да от камней.

[Yuri Gendelman]

бобыль писал(а):

Что это такое - очередное поветрие или нечто большее?

По-моему это просто мода. Слишком книгу разрекламировали.

бобыль писал(а):

Почему бы миру действительно не быть шифровкой?

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