Одноразовый шифроблокнот

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

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

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


Но, прежде, чем речь пойдет о самом шифре, следует вспомнить историю криптографии. На эту тему очень рекомендую книгу «Взломщики кодов» Дэвида Кана, в ней хорошо показано как на протяжении многих столетий шифр и дешифровка всегда шли ноздря к ноздре, причем пресловутые «черные кабинеты» чаще всего опережали примитивную криптографию, а последствия зачастую имели серьезнейшие масштабы: достаточно вспомнить печально известную телеграмму Циммермана. И, несмотря на то, что тот же шифр Виженера в реальной истории взломали достаточно поздно, кто знает — не попадет ли ваша шифровка в руки какого-нибудь местного Блеза Паскаля и не торкнет ли его от простой идеи переписать сообщение колонкой шириной в предполагаемую длину ключа и анализировать колонки? А если от безопасности ваших сообщений зависит ваша жизнь, не лучше ли использовать то, что не взломает ни гений из прошлого, ни АНБ из настоящего, ни пришельцы из будущего? Ну, при дОлжном соблюдении технологии шифрования? А?

Кстати, о соблюдении технологии. В ней кроется и ахиллесова пята одноразового шифроблокнота. Нарушение правил ведет к тому, что абсолютно надежный шифр превращается в достаточно легко взламываемый. Пример тому — советская переписка, небольшой процент которой американцам удалось вскрыть благодаря тому, что в результате раздолбайства НКВД в сороковые годы часть случайных последовательностей использовалась неоднократно (см. проект VENONA). Как следствие, вскрытие шпионской сети Розенбергов, укравших для СССР секрет атомной бомбы.

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

Вначале надо превратить ваш текст в цифры. Для этого используется сжимающая таблица (straddling checkerboard). В каком-то смысле это аналог алгоритмов, лежащих в основе zip, rar и т.п., только таблица сжатия у нас фиксированная. Нет, вы конечно можете и просто сопоставить буквам цифры по принципу А=1, Б=2 и т.д, но из-за избыточности языка вы будете вынуждены потом шифровать где-то на треть больше. Просидев несколько часов с карандашом за тупой арифметикой, вы быстро оцените достоинства сжимающей таблицы…

Для создания сжимающей таблицы запоминаем: А И ТЕСНО. Тут задействовано семь самых часто встречающихся букв в русском языке. Для английского берем скажем AT ONE SIR (в английском языке меньше букв и можно обойтись только двумя доп. строками) и т.п. Составляем таблицу, в первой строке которой идут часто встречающиеся символы, а в остальных остатки алфавита. Обратите внимание, что в первой строке не задействованы цифры 8, 9 и 0, и они же обозначают, что буква (реже встречающаяся) кодируется не одной цифрой, а двумя. Итак, для кодирования буквы ищем ее, если она находится в первой строке, то мы выбираем номер ее колонки (например Т=3), если она в остальных колонках, то мы вначале выбираем номер ее строки, а потом номер колонки, например Б=81, а ?=07:

    1   2   3   4   5   6   7   8   9   0
    А   И   Т   Е   С   Н   О
8   Б   В   Г   Д   Ж   З   К   Л   М   П
9   Р   У   Ф   Х   Ц   Ч   Ш   Щ   Ъ   Ы
0   Ь   Э   Ю   Я   .   ,   ?

Можно добавить еще-что-то полезное в оставшиеся три ячейки в последней строке (в реальности кроме букв часто использовались специальные коды для начала передачи цифр, начала передачи специальных кодов из кодовых таблиц и т.п.). Итак, нам надо зашифровать короткое сообщение:

ПОБЕГ ЗАВТРА

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

80781 48386 18239 11000

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

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

        80781 48386 18239 11000
+
  14358 89753 24133 40169 26799
=
  14358 69434 62419 58398 37799

Вот это уже и есть шифровка:

14358 69434 62419 58398 37799

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

Ну, а теперь самое главное (и самое трудоемкое): как сгенерировать достаточное количество случайных чисел. Ведь одноразовый шифроблокнот предполагает уничтожение каждой страницы после расшифровки, и для передачи определенного объема текста надо такое же количество случайных данных! Это и является вторым недостатком одноразового шифроблокнота: создание шифроблокнотов занятие длительное и трудоемкое, причем надо суметь создать реально случайную последовательность. Первое, что приходит в голову, это взять кости и накидать набор чисел, вот только на обычных игральных костях всего лишь цифры от 1 до шести, а кидать пару костей и складывать цифры нельзя, т.к. распределение суммы уже подчиняется вполне понятной закономерности и у вас выйдет не совсем случайная последовательность цифр. Можно конечно попробовать сделать кость на d10, как на иллюстрации справа, но попробуйте ее выточить напильником с достаточной точностью!

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

 11 = 0    21 = 6    31 = 2   41 = 8   51 = 4
 12 = 1    22 = 7    32 = 3   42 = 9   52 = 5
 13 = 2    23 = 8    33 = 4   43 = 0   53 = 6
 14 = 3    24 = 9    34 = 5   44 = 1   54 = 7
 15 = 4    25 = 0    35 = 6   45 = 2   55 = 8
 16 = 5    26 = 1    36 = 7   46 = 3   56 = 9

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

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

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

73 комментария Одноразовый шифроблокнот

  • vashu1

    Неплохо — особенно таблица для генерации случайных кубиками порадовала, все продумано.

    Добавить ссылки на предыдущие статьи по криптографии?

  • elsergv

    отбрасывая возникающий перенос: тут не понял когда всегда или чтоб не шестизнак? и ещё поправьте 8+3=1 и 8+5=3. не знаю откуда скопировали, но там соврали, а Вы не просмотрели

    • Grue

      отбрасывая возникающий перенос: тут не понял когда всегда или чтоб не шестизнак?

      Всегда отбрасывается перенос при сложении, всегда отбрасывается знак при вычитании. Операция должна быть обратимой: 4+7 получаем 1 и потом 1-7 получаем изначальную 4.

      и ещё поправьте 8+3=1

      Исправил.

      8+5=3

      Где? Там так и было.

      не знаю откуда скопировали, но там соврали, а Вы не просмотрели

      Я этот пример от фонаря сам выдумал, т.к. подробных русских статей на эту тему нет. Кстати, получилась хорошая демонстрация того, насколько ручной процесс шифровки трудоемок — глюк случился даже на очень коротком сообщении. Где-то читал в описании операции VENONA, что большинство советских шифровок содержали что-то вроде «ваше сообщение не удалось расшифровать, зашифруйте и передайте еще раз».

  • hludens

    Стоит добавить почему нельзя использовать один лист дважды.
    В этом случае банально вычев одно сообщение из другого получим частный случай шифрование одного текста другим. Это вполне вскрываемо.
    т.е. Т1+Ш -(Т2+Ш)= Т1-Т2

  • SerjZ

    Очень стойкий и простой шифр https://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%81%D1%8C%D1%8F%D0%BD%D1%81_(%D1%88%D0%B8%D1%84%D1%80)
    http://habrahabr.ru/post/138986/
    Аналитически не расшифровывается, только перебором (54!), т.е до начала производства мощных ЭВМ это железобетонный шифр.

    • Grue

      Он еще более трудоемок.

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

      А вот в Пасьянсе один единственный сбой и все, приплыли.

    • Grue

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

      • Йож

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

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

        • vashu1

          >> практически невзламываемый … основанный на дереве Хаффмана.

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

    • Grue

      Ну и третье. Самое главное. Пасьянс, в том виде, в котором его описывает Шнаер, является всего лишь способом получить гамму — и каждый раз ОДНУ И ТУ ЖЕ! То есть в исходном виде это тупо тот же самый случай, про который писал hludens — Т1+Ш -(Т2+Ш)= Т1-Т2!

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

      • hludens

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

    • Йож

      Обычный XOR с псевдослучайной последовательностью. За такое бьют канделябрами. И за дело. 🙂

    • Taras

      >Очень стойкий и простой шифр https://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%81%D1%8C%D1%8F%D0%BD%D1%81_(%D1%88%D0%B8%D1%84%D1%80)
      http://habrahabr.ru/post/138986/
      Аналитически не расшифровывается, только перебором (54!), т.е до начала производства мощных ЭВМ это железобетонный шифр.

      Отдельная колода карт для каждой шифровки уже не удобнее, чем всего лишь одна отдельная страница для той же цели. При этом играть этой колодой нельзя, так как нарушится порядок. Целый склад карт, которыми агент не играет, подозрителен. И ещё порядок шифровок жёстко привязан к порядку ключей. А если одна шифровка не была принята? Тогда следующую будут пытаться расшифровать её ключом, прочитается бред. То есть одна не принятая шифровка и связь утрачена. Через помехи не пробился и даже не узнал об этом и всё. Несколько надёжней привязывать ключ ко дню передачи. Но тогда есть, что передавать, нет, а ключ уже использован.

  • Grue

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

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

    Причем при серии сообщений колода не восстанавливается в исходный вид а продолжает применяться для всей переписки.

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

    В общем способ годный но с ограничениями

    Случайный вектор инициализации как-то лучше — по крайней мере ошибка локализуется в одном сообщении и не влияет на последующие, но…

    • Camrad

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

  • dan14444

    С практически-шпионской точки зрения — стойкое шифрование не самое важное, куда полезнее вообще не дать повода считать, что «это» — шифровка. А сам наличие «вероятной шифровки» или тем более шифроблокнота — шпиёна пАлит, после чего используется терморектальный криптоанализатор…

    Ну и следствие… Например, берём какую-то книгу и цифруем группы символов, длину каждой группы задаём по второй книге. Дёшево и сердито, без очень хорошего компа или знания об этом алгоритме — хрен взломаешь. Частотный анализ не поможет. Запомнить данные издания нескольких книг — куда безопаснее, чем переть с собой шифроблокнот(ы), при вполне пристойной стойкости. При этом единичные ошибки легко компенсируются, в отличие от «шифра-колоды» и подобных.

    • Grue

      С практически-шпионской точки зрения — стойкое шифрование не самое важное

      Розенберги голосуют против такой точки зрения, прямо с электрического стула.

      куда полезнее вообще не дать повода считать, что «это» — шифровка

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

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

      Это очень плохая идея. Она нарушает принцип Керкгоффса — «враг знает систему». Если вы приехали в другую страну и побежали покупать книги, ваши покупки в докомпьютерную эпоху легко отследит любой приличный детектив. Ну а раньше начала 20 века и выбор книг очень ограничен, вдобавок ко всему, т.е. сильно уменьшается и объем поиска.

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

      • Alex Besogonov

        Есть мнение, что на принцип Керкгоффа в докомпьютерную эру можно немного положить. Просто из-за совсем другой модели угроз.

      • dimav

        не надо покупать. есть самая распространенная книга — бибилия. а еще есть псалмы. (и прочие песнопения) которые можно просто запомнить.

        • Grue

          Пц.

          Который не заяц.

          А ничего, что зная систему, библию и псалмы будут в первую очередь шерстить — ровно по причине распространенности?

          Еще раз, шифры изобретают либо новички-дилетанты, либо специалисты по криптографии. Глупо городить слабый шифр, памятуя о том, что даже в 17 веке можно нарваться на гения-математика. Я в следующей статье напишу про удобный в применении и при том реально надежный (прошедший суровую проверку реальностью) докомпьютерный шифр, когда осилю ее доделать. Stay tuned.

          • dimav

            а что вы собираетесь шерстить? сопоставление номера стиха букве? или число букв А (или там гласных) во второй строчке стиха? или еще чтото подобное?

            • Hludens

              А что там шерстить? по группам цифр можно определить что имеется в виду: слово/буква, Станица/строка/буква, или еще какая комбинация. Если речь идет о конкретном тексте из писания то все элементарно, просто берете и перебираете стихи пытаясь расшифровать первые 5-10 букв способом слово/буква, строка/буква т.д.
              Если складывается во что то связное читаем дальше.
              Выглядит крайне затратно, но на самом деле десяток просто умеющих читать людей за пару часов вскроют ваш шифр из библии какой бы стих вы не выбрали.
              На проверку одного стиха уходит 5-10 минут…

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

  • Lalartu

    А какую роль играют числа кроме первого в первой колонке?

  • dimav

    вопрос а насколько важны именно полностью случайные числа? особенно если речь идет о докомпьютерных временах?

  • dimav

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

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

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

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

    расшифровывающий знает кто ему послал послание — шпион или контрразведка

    • Hludens

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

      • Grue

        Так что при попадании шифроблокнота в руки противника (и наличии у него ранее отправленных сообщений) он быстро раскрутит этот секрет как нефиг делать.

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

        • Hludens

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

          • dimav

            как? получатель(центр) может расшифровать как просто закодированное сообщение так и сообщение закодированное с «добавками».

          • Grue

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

            Для этого есть код «работаю без принуждения». Нет подтверждения от получателя с этим кодом? Значит центр перестает отправлять шифровки и выясняет через другого агента что же на самом деле случилось.

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

            Понятно, что агент может сдать код. Но это уже лежит совсем в другой плоскости.

            • hludens

              //Для этого есть код «работаю без принуждения».
              Разумеется, но это уже вопрос организации шпионской сети, а не вопрос криптографии.

              • Grue

                А там все работает в комплексе, нельзя рассматривать что-то одно отдельно.

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

    • Grue

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

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

      Это поможет примерно так же, как если броню танка прикрыть салфеткой.

      • dimav

        «. И так только получатель и отправитель» а это как говориться не факт. владельца шифроблокнота можно арестовать (с блокнотом)
        можно скопировать его используя снотворное или таможенный досмотр или агента в стане противника или как статье «силу».

        • Hludens

          А после такого провала защищай-не защищай разницы нет. Подобные защиты СЛИШКОМ слабы.

  • dimav

    статья замечательна (за содержательные комменты отдельное спасибо участникам) но насколько тема «попадаческая» ?
    как я подозреваю до появления радио (или точнее до появления портативных передатчиков) столь надежная (но и громоздская) схема особого смысла не имеет.
    поскольку результат разительно отличается от обычного текста то передать его по открытым (или просматриваемым) каналам нельзя. лучше идти сразу сдаваться в контразведку. да и владение блокнотом 100% улика.
    еще остается официальная защищенная проводная телеграфная связь (государственная и коммерческая). значит 50-70 лет «опережения» есть.

    • Grue

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

      Вообще-то посылка шифровок по почте, а в 19 веке и телеграфом — норма начиная с 15-16 века, и примерно тогда же была поставлена на поток государственная перлюстрация почты и взлом шифров в «черных кабинетах», причем как правило лидировали взломщики. А по телеграфу шифровки шпарили все, кому не лень. В 19 веке в штатах был большой скандал с Демократической партией, скупавшей голоса, вскрыто было именно путем дешифровки сообщений, зашифрованных хреновым шифром. Джефферсон вон свой шифр изобрел (и неплохой!), потому что позарез надо было. Без всякого радио, 18 век. История переписки русских анархистов и ко — тоже отдельная песня, без всякого радио.

      Короче, читайте Codebreakers Кана до полного просветления.

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

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

      • dimav

        вы абсолютно правы. если про телеграф (открытый канал) я вспомнил то восприятие почтово-бумажной корреспонденции как «закрытой» это привычка жителя 20 века от которой надо избавляться..
        и помнить школьную программу 🙂
        у Гоголя в Ревизоре
        губернатор просит почтмейстера вскрывать и читать переписку правительственного чиновника и вообще всякую подзрительную почту
        а почтмейстер не только не возмущается но и наоброт говорит что я дескать давно для собственного удовольствия всю ее читает.

  • drol

    А можно использовать 11-ричную систему? Понадобится всего одна дополнительная буква, которая может шифроваться любой случайной. Складывать и вычитать несложно. Зато можно высыпать на стол мешок обычных костей и складывать близлежащие пары, приняв сдвиг: 0=1, 1=2 и т.д.

    • Grue

      А смысл? Ради подстройки под обычные кости менять систему счисления? Оно и так трудоемко…

      • drol

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

        • Grue

          Складывать и вычитать несложно. Зато можно высыпать на стол мешок обычных костей и складывать близлежащие пары, приняв сдвиг: 0=1, 1=2 и т.д.

          Хм, не заметил поначалу, но вы тут простите глупость написали. Распределение суммы двух бросков костей подчиняется жесткому закону: https://www.math.nmsu.edu/~breakingaway/Statistics/Lessons/TTD/P4CCWD/P4CCWD.html

          Полюбуйтесь на график, в результате сложения у вас 2 будет встречаться с вероятностью 2.78%, а 7 с вероятностью 16.67%. Поздравляю, вы только что внесли охеренную закономерность в гамму и, тем самым, дали возможность его взломать.

          Таблица перевода бросков костей в десятичные цифры не просто так сделана, а для того, чтобы выровнять распределение. Вобщем в очередной раз вышла наглядная иллюстрация того, что если вы не профессиональный криптограф, НЕХРЕН ИЗОБРЕТАТЬ.

          • drol

            Да, действительно глупость. Но я потому и спросил: «Можно ли?». Вы аргументировано ответели (и вообще, побольше бы ссылок, когда упомянаются законы или правила). Всего делов то. И не надо тут эмоции выражать. Как раз-таки, потому что я не профессиональный криптограф, я читаю эту вашу статейку. И мне интерессно, почему нельзя. Теперь я узнал про кумулятивное распределение. Спасибо.

            • Grue

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

              Надо.

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

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

              • drol

                Но у нас здесь не инструкция, а познавательная статья. Поэтому, отговорка «ТАК НАДО» совсем не к месту. Как раз вашей задачей стоит рассказать про все эти сопутствующие «совершенно неожиданные и контринтуитивные вещи, о которых вы можете не знать и где здравый смысл и интуиция не катят», а не сетовать на присловутый русский металитет.
                Это вполне нормально — предложить решение проблемы, если она есть, и тебе кажется, что есть простое решение. Другое дело, что мало кто готов углубиться в изучение дебрь математики только ради того, чтобы проверить свою пятиминутную идею, предложенную на «попаденцев»
                Поэтому, если вы не готовы отвечать на дурацкие вопросы и предложения, то оформляйте статью как следует, с кучей ссылок на статьи и другую использованную литературу.

  • Taras

    А почему сжимающая таблица и сам блокнот именно десятичные? Если их сделать двенадцатеричными, то можно не отбрасывать комбинации. И дополнительных символов можно закодировать 35, не выбрасывая ё. Без ё даже 36. И даже можно непосредственно всунуть туда цифры и все знаки препинания и ещё знаки арифметических операций.

  • Taras

    Любая генерация чего либо по ключу страдает тем, что как только противнику станет известен алгоритм генерации, сложность шифра будет определяться разнообразием ключей. А до простых алгоритмов додумаются даже аборигены. С другой стороны, зачем нужен именно блокнот? Да за тем, чтоб иметь сразу большой запас того, чем шифруешь. Если генерить по ключу, то почему бы по ключу не сгенерить решётку/шифротаблицу/заменяющий алфавит или что угодно ещё для одной конкретной шифровки? Когда позарез нужен именно большой запас? Да когда агент берет его при инфильтрации, или у связного. Ну так готовьте шифроблокноты методом монте-карло каждый в двух экземплярах.

  • fear

    Получить десятичное число с помощью кубика можно и без таблиц. Нужно так же бросить кубик два раза. Если в первый раз выпала шестерка, то бросаем заново.
    Пусть a будет первым броском (a ≠ 6), b будет вторым броском (любое значение). Тогда:

    Rand = a × 2 + (b mod 2) — 2 (для справки, b mod 2 означает остаток от деления b на 2).

    Немного по-другому, но с тем же смыслом и результатом:

    Rand = (a — 1) × 2 + b — ⌊b / 2⌋ (для справки, скобки ⌊⌋ возвращают целую часть дроби)

    Результатом будет число от 0 до 9, вероятность выпадения которого одинакова для всех чисел из этого диапазона.

    • fear

      Например, если в первый раз выпала пятерка, а во второй раз — тройка, то результатом будет 5×2+(3 mod 2)-2=9, если, соответственно, 3 и 6, то 3×2+(6 mod 2)-2=4.

      Все просто! =)

    • fear

      Посоны, вот это я намудрил! Вот супер симпл ризалт! a — первый бросок (a ≠ 6), b — второй бросок.

      Rand = a * 6 + b Нужно взять последнюю цифру. Ну или если уж нужно прям по-умному, то так:
      Rand = (a * 6 + b) mod 10 Равновероятность результатов гарантирована и проверена)

  • fear

    Опечатка во второй формуле. Не смотрите на нее =)

  • Taras

    Ну а зачем шестигранным то десятичные кидать? Делайте сразу кость d10 и никаких гвоздёв.

  • Taras

    Или рулетку на манер казиношной, но на 100 ячеек, в которых может остановиться шарик. За один раз получите две цифры, а когда нужна одна последняя при нечётном количестве, то вторую отбрасываете. Распределение равномерное.

  • Taras

    > но попробуйте ее выточить напильником с достаточной точностью!

    Зачем? На своей территории на станке, или отлить. А чтоб оправдать странный цех, зафигачить игру с костями d10. В нашей же реальности такие есть. Так почему бы и нет? Отличное прикрытие и некоторый доход от продажи костей. И хорошо, сумма бросков не равномерна. А если перед сложением умножить первый бросок на 6? Из двух реальных костей d6 получится вполне равномерная виртуальная d36, надо только покрасить их в разные цвета. Или бросать одну и ту же два раза. d36 позволяет поднять ичность таблицы и самого блокнота и кодировать больше символов. А ещё можно два тетраэдра бросать. Тетраэдр — это кость d4. Если каждая грань имеет собственный номер, то из двух реальных получим виртуальную d16. Если на одной обозначена только чётность/нечётность граней, то получается только d8, но она нам не нужна, так как восьмеричной таблицы тупо не хватает на алфавит. Но d16 вполне годна. И так как буквы нам передавать не надо, то выбрасываем ещё и код Морзе и вместо него сочиняем код для одних цифр. Не шифр, поэтому правило о не придумывании своих шифров на него не распространяется. Шифр у нас до этого кода. Можно даже равномерный.
    0 ….
    1 …-
    2 ..-.
    3 ..—
    4 .-..
    5 .-.-
    6 .—.
    7 .—
    8 -…
    9 -..-
    A -.-.
    B -.—
    C —..
    D —.-
    E —.
    F —-

  • Taras

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

    • Hludens

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

  • Igord

    Кубик вообще то условность, генератор (псевдо) случайных чисел, от карт до букв в книге.

    Вероятность этих рядов при одном бросании кубика одинаковая.
    12345
    45321

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

  • Sergey

    А можете объяснить на пальцах, чем опасно использование в шифре Вермана не случайной последовательности, а псевдо случайной.
    Везде написано, что должно быть истинно случайная, но не написано почему.
    Допустим буква А выпадает не 1/33 а 1/10 как это ослабит шифр.
    Я так понимаю есть какие то методы анализа?
    Если не сложно можете пояснить на пальцах?
    Ну или хотя бы ссылку на статью дать?

    • Hludens

      Псевдослучайная это последовательность получаемая из некой формулы по аргументу-seed.
      т.е. зная формулу мы можем банально подбирать это число вместо того чтобы ломать шифр. Число вариантов данного числа на многие порядки меньше чем число вариантов случайной последовательности :))
      кроме того шифр Вермана подразумевает зацикливание этой последовательности причем длинна данного отрезка ограничена. Опять таки, мы можем предположить длину цикла и отксорить начало сообщения его концом. при этом повторяющийся шифр взаимоуничтожится и мы получим обычное гаммирование одного осмысленного текста другим. А это уже расшифровывается.
      Разумеется точно предсказать длинну цикла трудно но можно предположить что она от Х до Х2. Что дает ограниченное число вариантов которые нужно проверить.

      • Sergey

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

  • Hludens

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

    Собственно гаммирование ксором работает по такому принципу.
    Код XOR текст = шифровка
    шифровка XOR код= текст

    Если мы используем тот же код для второго текста (или из-за повтора на другую часть текста снова приходится тот же код) то получается вот что:
    Код XOR текст = шифровка
    Код XOR текст2 = шифровка2
    шифровка XOR шифровка2= Код XOR текст XOR Код XOR текст2 = текст2 XOR текст

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

    Вот как то так…

  • Sergey

    Спасибо за разьеснение!
    Стало намного более понятно. Даже немного поиграл в криптогрофа 🙂

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

    Но а если серьезно, в чем соабосиь такого шифра?

    • Hludens

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

    • Grue

      Чтобы поиграть в криптографа, возьмите книгу, карандаш и бумагу и зашифруйте 200 знаков текста с помощью какой-нибудь книги, а через день расшифруйте. И оцените трудоемкость всего процесса. Вы на каждую букву текста будете вынуждены писать десяток цифр шифровки (и быстро это оцените по уровню скуки — я уж не говорю про кошелек, если придется передавать телеграммой и платить за каждый знак). И сравните это с таблицей Rasterschlüssel 44, где текст пишется горизонтально, а шифровка считывается вертикально, раз уж мы ушли в область pen & paper.

      Ну, и вдобавок к тому, что уже сказал Hludens, есть еще куча нюансов:

      Первый — указывая номер буквы в слове вы реально указываете «здесь есть дополнительная закономерность!». Например, английские слова реже всего начинаются с ‘x’. Частота появления букв сильно зависят от их места в слове. Если, скажем, буква кодируется как страница:строка:слово:буква в слове, то, посчитав частоты всех *:*:*:1 и найдя самые редкие это скорее всего буквы ‘x’. Или наоборот, чаще всего английское слово начинается с ‘e’. Опаньки, пару букв мы уже в тексте видим.

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

      Третий — если вы будете выбирать буквы часто, то по соседним буквам тоже можно поймать много закономерностей (см выше — первая ‘e’, рядом с ней еще меньше выбор, а вторая буква в слове тоже имеет свои закономерности), и так далее. Будете использовать все буквы на странице, то вскроется даже длина слов в книге-ключе, еще одна закономерность.

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

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

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

      И т.д. Лень думать дальше, если честно.

      Вобщем см. начало статьи — не надо изобретать велосипед. Он тут описан, причем он будет гарантированно кататься везде, даже в мире Звездных войн или Mass effect — если нужна 100% надежность. А если нужно надежность и малую трудоемкость в докомпьютерную эпоху, см. статью про RS44.

      • Igord

        Первый — указывая номер буквы в слове вы реально указываете «здесь есть дополнительная закономерность!».
        ———-
        В общем не помню где оригинал правил шифрования, эти проблемы были известны и решены.

  • Sergey

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

    >Чтобы поиграть в криптографа, возьмите книгу, карандаш и бумагу и зашифруйте 200 знаков текста с помощью какой-нибудь книги, а через день расшифруйте.
    Я взял не 200, а 600. Абзац из книги. Шифровать оказалось достаточно быстро, хотя и муторно, дело пошло проще когда сделал линейку с отверстием под букву. А вот с дешифровкой, это очень скурпулезно и скучно. Много раз ошибался.

    RS44 прочитал, эксперимент повторил 🙂 в разы быстрее.

    Спасибо что все толково разъяснили.
    PS. Отдельное спасибо за наводку dieharder, очень полезная вещь для тестирования.

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>