Рейтинг:2

Shift Cypher, абсолютно безопасный?

флаг in

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

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

forest avatar
флаг vn
Он абсолютно безопасен точно так же, как однобитовый XOR-шифр абсолютно безопасен при шифровании одного бита.
флаг in
@forest Почему? Ответ Даниэля С показывает контрпример.
Рейтинг:1
флаг ru

Не обязательно. Рассмотрим шифр сдвига Цезаря на латинском алфавите из 26 символов. Мы сопоставляем букву с одним из чисел 0-25, скажем $х$ и добавьте значение ключа $k\in [0,25]$ вычислить $у=х+к\мод {26}$ а затем сопоставьте обратно с алфавитом. Если $к$ выбирается равномерно случайным образом, то это совершенно безопасно. Однако если расширить диапазон $к$ сказать $[0,30]$ это уже не совсем безопасно, так как значения $х+0\мод {26}$, $х+1\мод{26}$, $х+2\мод{26}$, $х+3\мод{26}$ и $х+4\мод{26}$ в два раза более вероятны, чем другие шифротексты. Это дает существенную информацию о $х$ и, следовательно, открытый текст. Например, если мы видим зашифрованный текст «b», соответствующий $у=1$ у нас есть больше доказательств того, что $х=23, 24, 25, 0, 1$ чем другие значения. Таким образом, байесовская статистика увеличивает нашу уверенность в том, что буква открытого текста принадлежит множеству {'x', 'y', 'z', 'a', 'b'}, и уменьшает нашу уверенность в том, что она лежит вне этого множества. Мы не смогли бы сделать такой вывод с помощью абсолютно надежного шифра.

Как правило, для достижения единообразия, необходимого для совершенной безопасности, пространство ключей должно быть кратно размеру пространства зашифрованного текста, а ключи должны быть выбраны равномерно случайным образом. Однако полной безопасности можно добиться и другими средствами (например, в приведенной выше схеме, если мы выберем ключи $\{0,1,2,3,4,26,27,28,29,30\}$ с вероятностью 1/52 и другие ключи с вероятностью 1/26, то шифр сдвига по-прежнему совершенно надежен.

флаг in
Кажется, я понял, почему они в два раза более вероятны, чем другие шифротексты, ведь если $x=0$, то $0+1\mod\ 26 = 1 = 0 + 27\mod\ 26$. Но почему он дает больше информации о $x$ и, следовательно, об открытом тексте? Не могли бы вы уточнить подробнее?
Daniel S avatar
флаг ru
Я добавил еще несколько слов; дайте мне знать, если необходимы дальнейшие разъяснения.
флаг in
Кажется, теперь я вижу это: для произвольного сообщения, не входящего в наш «набор убеждений» $m$, $P(M=m\mid C = y = 1) = 0$, между тем $P(M=m) = 1/26$. Таким образом, по определению это не совсем безопасно, верно?
Daniel S avatar
флаг ru
Почти. Для однородного сообщения $M$ и для $m$ вне нашего набора убеждений $P(M=m|C=y=1)=1/30$ и для $m$ внутри нашего набора убеждений $P(M=m| С=у=1)=1/15$. Оба они отличаются от унифицированного предыдущего 1/26, и поэтому полная безопасность не достигается.
флаг in
Как вы получили $1/30$ и $1/15$? Если бы $y=1$, разве мы не знали бы, что возможны только значения $x=23,24,25,0,1$ и, следовательно, если сообщение находится за пределами нашего множества убеждений, $P(M=m\mid C =y=1) = 0$?
Daniel S avatar
флаг ru
Потому что для каждого $m$ вне нашего набора убеждений существует ровно 1 значение $k$ из 30, которое привело бы к $y=1$, и для каждого $m$ в нашем наборе убеждений есть 2 значения $k$ из 30, что привело бы к $y=1$.

Ответить или комментировать

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