Справочник автора/Криптография

«	Кто возьмёт в плен русского шифровальщика, либо захватит русскую шифровальную технику, будет награжден Железным крестом, отпуском на родину и обеспечен работой в Берлине, а после окончания войны — поместьем в Крыму	»
— Приказ 1942 года

Здесь информация о криптографии и шифрах.

Что читать

Неспециалисту этих трёх книг должно хватить:

• Дэвид Кан. Взломщики кодов.
• Владимир Жельников. Криптография от папируса до компьютера.
• Книга шифров. Тайная история шифров и их расшифровки. Саймона Сингха

Плюс одна по-английски:

• Julian Assange, Jacob Appelbaum etc — Cypherpunks Freedom & the Future of the Internet

Если хочется художественной литературы о буднях шифроаналитиков, высокофункциональных аутистах, интернете, войне и дзета-функции — есть «Криптономикон» Стивенсона. Это не учебник, но атмосферу и пару понятий в области он передаст.

Терминология

В криптографию не входят, но близки к ней…

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

Криптография занимается такими вещами.

• Шифр — способ защитить от врага информацию, даже если факт её передачи раскроется.
• Хэш-функция — функция, принимающая на входе послание произвольной длины и возвращающая число от 0 до N.
• Криптостойкий генератор псевдослучайных чисел — генератор псевдослучайных чисел, для которого по имеющейся истории сложно предсказать дальнейшие числа. Может применяться, например, в азартных играх.
• Имитовставка — «криптографически стойкая контрольная сумма», защищающая сообщение от намеренной подмены. Частным случаем имитовставки является электронная подпись.
• Криптографический протокол — процедура обмена ключами и шифрованной информацией.
• Ключ — секретная информация, позволяющая шифровать/расшифровывать сообщения, накладывать/проверять имитовставку.

Какие бывают шифры

• Поточные и блочные.
  • Поточный — работает по одному символу.
  • Блочный — всего лишь шифр простой замены. Однако замену эту делает не по одному символу, а блоками, например, по 8 или 16 штук.
• С обратной связью и без. Обратная связь — это когда внутреннее состояние шифратора зависит от того, какие символы вы на него подали. Обратная связь мешает находить в шифротексте закономерности, однако сложнее для ручной работы: любая ошибка приведёт к тому, что остаток текста будет нечитаемым.
  • Блочные шифры обратной связи по определению не имеют. Значит, её приделывают искусственно (например, суммируют получившийся блок с предыдущим).
    • Существуют также «самокорректирующиеся» режимы шифрования, когда ошибка распространяется, например, на ошибочный блок и следующий за ним.
• С перестановкой символов и без. Перестановка мало повышает криптостойкость и хороша лишь тем, что несложное устройство — картонка с вырезами — позволяет быстро переставлять символы при ручной шифровке. Естественно, с переходом на компьютер от перестановки отказались.
• С элементами случайности (избыточностью) и без. Случайность затрудняет анализ: сходные сообщения зашифруются совершенно по-разному. Если у шифра есть обратная связь, самый простой способ добавить случайности — начать послание с нескольких случайных символов.
• Симметричные (одноключевые) и асимметричные (двухключевые). Двухключевой шифр имеет два разных ключа для зашифровки и расшифровки, это позволяет довольно интересные криптопротоколы (см. раздел о компьютерной криптографии). Ни один из существующих двухключевых шифров не пригоден для ручного исполнения, только компьютер.

Взлом шифров

Атаки делятся на:

• Атаки на основе шифротекста. У взломщика нет ничего, кроме шифровки.
• Атаки с открытым текстом. Взламывая шифр Виженера, мы предполагаем, что где-то в шифровке есть «ХАЙЛЬ ГИТЛЕР». Если так оно и оказалось, а длина ключа не более 11, шифр взламывается. Несложная компьютерная программа за долю секунды приложит открытый текст ко всем позициям шифровки — человеку остаётся только увидеть (или не увидеть) осмысленный текст.
• Атаки с подобранным открытым текстом. Интересно получается: шпион добирается до машины, вводит в неё «ААААААА» и прикарманивает выходную перфоленту.
• Атаки с адаптивно подобранным открытым текстом. Это когда шифромашину «мучают» в лаборатории.
• Атаки с подобранными ключами. Это если лаборатория позволяет менять ключи.
• Атаки с анализом неполадок. Электронную шифромашину «истязают» помехами, и от помех она начинает портить шифровку. Сравнивая порченую шифровку с эталонной, можно выяснить ключ.
• Подслушивание по сторонним каналам. Ультразвук от катушек на материнской плате (долго!), пульсации тока в цепях питания, время реакции машины…
• Социальная инженерия. Использование человеческого фактора, очень часто слабым местом любой криптосистемы является именно человек. Он может выбрать простой пароль, использовать его везде и всюду, неправильно удалить ключ шифрования, его можно напоить, в конце концов! А ещё ему свойственно шаблонное поведение и это обязательно отразится на сообщениях, которые он будет посылать, что сильно облегчит атаку с открытым текстом. В настоящее время, пожалуй, является основным методом атаки на криптосистемы, ну за исключением, конечно, физического воздействия.
• Ну и нельзя сбрасывать со счетов банальные подслушивание, пытки («терморектальный криптоанализ») и подкуп.

Чем так важен криптопротокол?

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

• В компьютерной шифровке из-за дороговизны (а зачастую и отсутствия) надёжных каналов мы даже не уверены, что на другой стороне провода тот, за кого он себя выдаёт.
• Если шифруются одинаковые сообщения, кое-какую информацию можно извлечь просто из факта, что шифровки одинаковы.
• Можно стать «промежуточным звеном» (man in the middle — «человек посередине»), перешифровывающим сообщения.
• Можно запомнить шифровку, а потом повторить её без изменений, даже не зная, что она означает.
• Кусок открытого текста можно и угадать логически. В компьютерной шифровке технические байты, присущие форматам и протоколам более низкого уровня (например, шифруем JPEG или HTTP) — отличный открытый текст. В первом протоколе немецкой шифромашины «Энигма» один и тот же текст (разовый ключ) повторялся дважды, это упрощало взлом.
• Информацию можно выудить даже из факта, что шифровка была (или не была) послана. Или вдруг в шифроканале началась бурная деятельность.
• Как периодически менять ключи, чтобы не было большого объёма сообщений, зашифрованных одним ключом? Это важно и для немецкой «Энигмы», но самый интересный протокол, скомпрометированный таким образом,— «несолёный пароль», протокол защиты паролей от утечки базы данных. Пароль передаётся под прикрытием прочного шифра (криптопротокол TLS), на сервере делается свёртка = hash(пароль), и результат сравнивают с эталонной свёрткой, хранящейся на сервере. Перебрать пароли можно загодя и общими силами, и уязвимость тут в двух фактах: 1) результат перебора, соответствие свёртка → пароль, хранится в довольно компактном виде; 2) уязвимым станет любой сайт с данным алгоритмом, лишь бы утекли шифрованные пароли.
• Когда машинам нужно проверить согласие человека — можно ли как-то сымитировать его присутствие, например, ретранслятором? Так ухитрились угнать «Теслу» со стоянки: законы США запрещают противоугонным механизмам вмешиваться в работу машины во время движения, потому близость ключа проверяется только в момент открытия дверей.
• Удастся ли подслушать что-то по сторонним каналам — например, по времени реакции системы? Сторонние каналы обычно шумны и дают ничтожную долю бита информации, так что придётся делать много-много попыток.

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

Ручная криптография

Раз шифровка выполняется руками и дешифровка руками, вокруг ручной криптографии можно раскрутить интересные детективные сюжеты. Пожалуй, самый интересный из них — несложный шифр и «ненастоящий сварщик» (вернее, криптоаналитик). Тогда читатель сможет ухватиться за мысль сыщика, проследить, как он находит улики и прикладывает их к шифротексту. А ещё ключом или контейнером для шифроблокнота может быть ничем не примечательный предмет. Хороший пример — «Пляшущие человечки»: узнав, что героиню зовут Илси (в оригинале Elsie), Шерлок устраивает атаку с открытым текстом и разрушает шифр.

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

Скитала (античная шифровальная «машина»)

В Спарте оборачивали узкий кожаный ремешок вокруг палки по спирали и писали текст. При разматывании получался набор букв, для прочтения требовалась такая же палка. Нашли и способ анализа: наматывали ремень на коническую палку и двигали туда-сюда, пока текст не начинал читаться.

Шифры простой замены

Многие из вас с такими шифрами баловались в детстве. Умелый криптоаналитик может с одного взгляда увидеть и вскрыть шифр простой замены. А неумелый — проведёт частотный анализ. Автор этих строк участвовал в конкурсе «IT Starz 2013», одним из заданий которого было вскрыть такой шифр. Нашёл частоту каждой буквы, сопоставил их с реальными частотами букв в языке — оставалось немного подправить, и готово. Два часа программирование, десять минут дешифровка.

В числе шифров простой замены…

Литорея

Шифр простой замены, приспособленный для проговаривания: например, заменяются только согласные буквы.

Шифр Цезаря

Сдвиг алфавита на n символов. Например, на 3.

А → Г
Б → Д
В → Е
...
Ь → Я
Э → А
Ю → Б
Я → В

Частный случай шифра Цезаря под названием ROT13 был популярен в свое время в сети, использовался в интернет конференциях и некотором программном обеспечении. Он удобен тем, что для расшифровки надо «сдвинуть» снова на 13 символов, то есть просто применить алгоритм еще раз. Отсюда и шутка в англоязычной среде «зашифровано ROT26» (или 2xROT13), что, по сути, означает отсутствие шифрования, так как букв A-Z всего 26.

Квадрат Полибия

Квадрат Полибия

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

Шифры-омофоны

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

О: 064 149 903 123 010 268 479

Следующая популярная буква — «А». Ей сопоставляем уже пять чисел:

А: 012 659 111 366 095

И так далее для всех букв. Самая непопулярная кодируется одним числом. При шифровании буква подменяется случайно выбранным числом, из сопоставленных. Прямое применение частотного анализа к зашифрованному посланию не даст ничего, ведь теперь частота символов примерно одинакова. Но как всегда, нюансы, нюансы… Обманутые мужья по прежнему хотели знать кто, с кем, и каким образом, поэтому человеческая мысль, подстёгиваемая ещё не открытыми к тому времени гормонами, нашла способ взлома и этого шифра. А именно, по количеству различных чисел в сообщении делается предположение что это шифр омофонической замены и частотный анализ применяется уже для подсчёта слогов и слов. Они тоже во всех языках встречаются с разной частотностью, например в английском языке это артикли «the» и «a/an». Предположив, что за слова находятся под шифром, можно символ за символом восстановить таблицу замены и прочитать сообщение.

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

Шифр Виженера

Усовершенствованный шифр Цезаря. Буквам А…Я даём номера от 0 до 32. Положив, что 0 = 33, 1 = 34, 2 = 35 и т. д., получим…

А + А = 0 + 0 = 0 = A
А + Б = 0 + 1 = 1 = Б
А + В = В
...
А + Я = Я
Б + А = Б
Б + Б = В
...
Б + Ю = Я
Б + Я = А
...

Получается такая таблица сложения (для простоты выпишу только кусок).

АБВГДЕЁЖ...ЮЯ
БВГДЕЁЖЗ...ЯА
ВГДЕЁЖЗИ...АБ
ГДЕЁЖЗИЙ...БВ
ДЕЁЖЗИЙК...ВГ
ЕЁЖЗИЙКЛ...ГД
....

Придумаем какой-нибудь ключ (например, БЕГ). Открытый текст БАГДАД. Записываем одно под другим и воспользуемся таблицей.

   БАГДАД
  +БЕГБЕГ
   ------
   ВЕЁЕЕЖ

Получаем шифровку ВЕЁЕЕЖ. Шифр прост, но не поддавался взлому три века.

Колёса Джефферсона

Современная реплика машины Джефферсона, частично разобранная. Вот такой «лоу-тек» взломали только в XX веке!

Того самого, основателя США. Стойкость близка к шифру Виженера.

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

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

Советский шифроблокнот

Вот мы и пришли к широко известному, но переоцененному шифру. Таблица сложения как у Виженера. Однако ключ заведомо длиннее сообщения. Такой ключ уже не запомнишь; у разведчика он записан в специальный блокнот. Разведчик вырывает из блокнота лист, шифрует сообщение, лист уничтожает.

Шифроблокнот — единственный шифр, который не взламывается даже теоретически, независимо от того, сколько раскрыто пар «открытый текст — шифровка». Почему так: если у нас традиционный 32-битный шифр, то для данной шифровки существует ровно 2³² открытых текстов, и хотя бы теоретически, используя гипотетический быстрый компьютер, можно перебрать их все и отметить наиболее «осмысленные». В шифроблокноте, если вы примените к зашифрованному сообщению один ключ — получите одно сообщение, примените тысячу других — получите тысячу других осмысленных сообщений. Взломщик никак не сможет понять, какое из осмысленных сообщений верное: раскрытые тексты не дают никакой информации, на то ключи и разовые.

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

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

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

Всё вышесказанное было справедливо в те времена, когда шифроблокноты писали на бумаге. При современных технологиях несложно организовать полноценную связь через шифроблокноты на всё время миссии — носители информации со временем становятся всё меньше по размерам и цене, а по ёмкости всё больше. Карты памяти размером с ноготь и ёмкостью в сотни гигабайт уже ежедневная реальность, доступная по деньгам практически каждому, а поскольку общая длина шифроблокнота в лучшем случае равна трафику обмена данными в обе стороны, такой ёмкости хранилища ключей хватит хоть на год, если видео с котиками по такому каналу не передавать. Белый шум в таких количествах легко и непринуждённо создаётся на основании данных с микрофона, приставленного к радиоприёмнику, который настроен на атмосферные помехи. А сама технология шифрования при помощи одноразовых шифроблокнотов примитивна настолько, что с ней справится даже древний микроконтроллер без дырявых операционных систем и бэкдоров от производителей/спецслужб. Главное в этом благородном деле — организовать хранение носителя с ключами так, чтобы определять любой факт несанкционированного доступа к нему, и не использовать для работы с носителем оборудование, имеющее ЛЮБОЙ канал связи. Принесли данные на носителе, зашифровали, записали на ДРУГОЙ носитель, унесли.

Книжный шифр

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

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

Есть вариант, когда в качестве шифроблокнота используется сегодняшняя газета. Берутся не слова, а номера отдельных букв в строке; если такой буквы в строке нет, передаётся «фонетический заменитель» — например «io» вместо «y» (латиницей). Далее пропускаем условное количество строк. Поскольку каждая строка газеты используется не более одного раза, а объём значительно больше объёма сообщений, получается эффект шифроблокнота. Недостаток метода тот же, что и у книги: как только противник установит название газеты, все ранее перехваченные сообщения расшифровываются. Преимущество — полное отсутствие улик. Человек интересуется политикой, каждое утро покупает несколько газет, что такого?

Способен ли ручной шифр противостоять компьютерному взлому?

Этот вопрос ещё ждёт своего исследователя. Советский шифр ВИК, ведущий родословную от квадрата Полибия и используемый в послевоенные годы группой Абеля, удалось вскрыть только с помощью перебежчика-шифровальщика, сдавшего все четыре ключа, и он считается неломаемым до сих пор. Шифровальщик Брюс Шнайер придумал для писателя Нила Стивенсона шифр «Пасьянс» («шифровальная машина» — колода карт). Однако дальнейшие исследования нашли в «Пасьянсе» несколько уязвимостей.

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

Впрочем, существует древний и совсем не криптографический метод: неизвестный язык. Издавна язык, хоть и с русской грамматикой, но звучащий совсем не по-русски, употребляется маргинальными элементами наподобие офеней. В том числе и из-за языка сложна война с национальной преступностью: сложно даже вычленить из речи имена, а сойти за своего — задача почти неразрешимая. А если язык хоть немного зашифровать — без хорошего лингвиста не разберёшься. Во вторую мировую войну американцы наняли в шифровальщики индейцев навахо — переговоры на экзотическом языке немцы взломать так и не смогли. Русские партизаны с этой же целью использовали самый настоящий язык падонков, а в одном из рассказов о войне, написанных по воспоминаниям ветеранов, в качестве шифра для голосовых переговоров использовался казахский язык. На Тихом океане англичане посадили за радиостанции юных кадетов и приказали им общаться на том французском, которому их учили в школах. Понять их не смогли не только японские специалисты по английскому (которые и занимались радиоперехватом), но и спешно затребованные специалисты по французскому, в то время как сами они друг друга вполне понимали (на уровне «Вич воч? — Сыкс воч!»). Роберт Хайнлайн в повести «Бездна» упоминает speedtalk — искусственный язык скоростного общения. Внимание: сейчас, когда вокруг компьютеры, хоть какой-то шифр всё равно нужен, чтобы статистика букв была поломана. Кнорозов расшифровал язык майя вручную и без билингвы.

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

Электромеханические шифровальные машины

Целый период, грубо от конца Первой мировой войны до развала СССР, и для авторов не слишком благодатный: работа машины всё так же требует человеческого вмешательства, это исключает сложные криптопротоколы. А вот шифры стали намного прочнее, объём переписки увеличился. Чаще всего электромеханическая машина — макгаффин, за которым гоняется «наш» шпион. Дешифровка — дело сложное и скучное, военные шифры с переменным успехом долбают целые институты.

Неавтоматическая шифровальная машина работает так: задаём букву (поворачиваем ручку или жмём на клавиатуре) — на индикаторе шифрованная, задаём вторую — на индикаторе вторая. Автоматическая перфорирует телеграфную ленту или напрямую передаёт сообщение по телеграфному каналу.

Хотя электромеханические машины работали с начала XX века и до распада СССР, известными стали разве что немецкие «Энигма» и «Лоренц». Кстати, прото-ЭВМ были разработаны британцами именно для дешифровки этих машин.

«Игра в имитацию»

Драматично показать расшифровку такой машины крайне сложно, и это видно в фильме «Игра в имитацию» — как раз про Тьюринга, его коллег и прото-ЭВМ «Бомба». Кульминация фильма — атака с открытым текстом. Да перепробовать распространённые открытые тексты — особенно такие очевидные, как «Хайль Гитлер» — это первое, что нужно сделать!

Создатели фильма драматизировали до потери исторической точности. Всё одновременно и проще, и сложнее. У «Энигмы» существовала одна проблемка: она не могла кодировать букву в саму себя: А в А, В в В — и так далее, а сами коды были симметричными: если при каком-то положении дисков A превращалось в Y, то и Y превращалось в A. У машины было три диска (у морского варианта — 4), размещавшиеся в произвольном порядке. Каждые сутки порядок дисков менялся по заранее разработанному плану (конечно, секретному). Всего в комплекте «сухопутной» армейской «Энигмы» было пять сменных дисков, что давало в общей сложности 5·4·3 = 60 комбинаций. Каждый диск мог быть установлен в любую из 26 круговых позиций, что давало 60·26³=1054560 комбинаций. Далее ещё была панель с клеммами и проводками, где любую букву меняли на любую (но не в себя саму). Немцы полагали, что если к неприятелю попадёт кодирующая машинка, перебрать миллион комбинаций вручную, плюс ещё провода, за обозримое время нереально.

Мариан Реджевский догадался, что если поставить параллельно 60 машинок, можно зафиксировать все возможные суточные перестановки дисков (параллельный компьютер, однако). Следующее изобретение — подавать буквы в машинку не вручную клавишами, а с телеграфной перфоленты, что раз в сто быстрее и без человеческих ошибок. Далее в машине Реджевского начиналась работа с известной слабостью кода: тогдашний немецкий протокол предписывал вначале дважды передавать трёхбуквенный позывной. Соответственно, если первая буква не сходилась с четвёртой, вторая с пятой или третья с шестой — эту комбинацию можно было отбросить. Наконец, если в каком-то начальном положении все буквы проскочили, подходит оператор и записывает: «Машинка номер 4, комбинация 2-24-3». Далее с комбинацией оператор бежит к математикам, и те пытаются расколоть полученную белиберду. Но эта белиберда — от фиксированного положения проводов на патч-панели, оттого — просто перестановочный шифр (смотрим выше). Колется частотным анализом, не так ли?

Однако со временем немцы про эту слабость узнали и её прикрыли. Вот здесь Тьюринг и придумал пользоваться «крибами» — подсказками. Сыграло свою роль то, что пложения патч-панелей и наборы дисков устанавливались на день для всех подлодок флота, и использовались во всех случаях, в том числе и при передаче сводок погоды, которые начинались с очень удобного для расшифровиков слова WETTER (содержавшего две пары одинаковых букв, чем это важно — расскажем позже). Кроме того, если где-то атаковали подводную лодку, в передачах из соседних квадратов искали подсказки WASSERBOMBE и ENTKOMMEN («атакован глубинными бомбами» и «уклонился от противника»). Иногда на отдельных судах (особенно малотоннажных, не представляющих для подводной лодки достойной цели) приказывали ночью нарушать светомаскировку и выискивали в сводках из окрестностей слово AMPEL — «видел огни», также следили за передачами из районов минных постановок.

Дальше составлялись графы соответствий: например, если удавалось установить, что слову WETTER соответствует шифротекст RTZWRQ, можно понять, что T соответствует E во второй позиции, Z в третьей, W в четвёртой (помним про симметричность). В таком случае нам не важно, какой из проводов — T, нам важно, чтобы во второй, третьей и четвёртой позиции они давали разные шифрованные результаты. Аналогично с R — в первой, пятой и шестой позициях результаты должны быть разными, а поскольку в пятой позиции наблюдаем E, которое соответствует T во второй — получаем цикл, который позволит отсечь уже действительно много непригодных вариантов. Если хотя бы где-то появляется запрещённое совпадение — это не наш случай, двигаемся дальше. Чем больше было подобных подсказок (а точнее, чем больше циклов было в получившемся графе), тем больше вариантов отсеивались как заведомо неверные.

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

Начальные положения дисков на всех подлодках были разные, но вот конкретная комбинация и установка патч-панелей в каждый конкретный день — одна и та же по всей Атлантике. Как только аналитик, скажем, за столом 322 кричал: «Есть осмысленное для машинки 16!» — операторы брали у парня список патчей, мчались к машинке 16, втыкали проводки — и пропускали через машинку весь дневной радиоперехват. Машинка вываливала все немецкие радиограммы открытым текстом, оставалось лишь позвать переводчика. К чести сказать, такие удачи бывали не ежедневно, но достаточно часто для того, чтобы перед Черчиллем встала моральная дилемма: говорить американцам про все подлодки — конвои пойдут кружным путём, немцы поймут, что «Энигма» поколота с концами — и заменят всю систему. Не говорить о части расшифровок — погибнут моряки, в том числе британцы, зато можно сохранить жизни в будущем.

Помогли британцам и явные ошибки германских математиков. Кто-то очень умный в штабе Кригсмарине постановил, что комбинация дисков, хотя и выбранная «случайно», не должна повторяться как минимум две недели. Когда британцы это поняли, просто прыгали от радости. Действительно, если сегодня нам удалось получить осмысленное с машинки 5, а вчера — с машинки 52, то «решениями» этих машинок можно не заморачиваться целых две недели. Это сохраняет аналитикам немного сна, а к остановленным машинкам можно послать механика с маслёнкой! А еще англичанам помогло, что им еще в 1941 сдалась поврежденная лодка U-110 с судовыми документами и исправным шифровальным оборудованием.

Для авторов, желающих писать реализм: ваша персональная «Энигма» находится тут в полной боевой готовности. GOTTSCHNELL

Компьютерная криптография

Как работает RSA.

Компьютерная криптография поставила новые задачи.

• Пересылка стала настолько «дешёвой», что личная встреча — недопустимая роскошь. Потому надо убеждаться, что противная сторона — именно друг, а не враг под прикрытием.
• Зато стал возможен «пинг-понг» сообщениями: попробовал бы ты послать что-то шифрованное с курьером и дождаться ответа… Появились сложные криптопротоколы, ставшие фактически шифровальным флеботинумом. Из распространённого: умеет шифровать, но не умеет расшифровывать? — двухключевая схема (RSA, Эль-Гамаль и другие). Прошивку можно видеть и менять, но нельзя заменять на неофициальную? — тивоизация (электронная подпись плюс вшитый в устройство ключ проверки). Как наладить секретную связь, когда стороны не знают ключей друг друга? — протокол Диффи-Хеллмана. Два компьютера, не доверяющие друг другу, сообща генерируют число, гарантированно случайное — протоколы «бросания монеты в колодец».
• Сами по себе шифры практически не взламываются (во всяком случае, до появления квантовых компьютеров с большим числом кубит), так что нужен хороший обоснуй, почему тот или иной протокол — повторяю, не шифр, а протокол! — оказался «колхозным».

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

Симметричные и асимметричные шифры

Ещё один прорыв в криптографии произошёл в 1970-е годы: появился первый двухключевой, или асимметричный шифр RSA. Основан он на том, что перемножить два длинных числа легко, а вот разложить произведение на простые множители — сложно.

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

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

Обычные шифры с одним ключом, в противовес, называют симметричными.

Абсолютно неуязвимыми считаются 4096-битный RSA (асимметричный) и 256-битный AES (симметричный), на практике не поддаются взлому даже 256 и 64 бита — поэтому не стоит описывать шифр с ключом в десятки килобайт.

Почему ключи RSA такие длинные? А потому, что в BlowFish или AES подойдёт любой ключ (кроме горстки «слабых»), в RSA — лишь такие числа, которые будут произведением двух простых чисел.

Q: В принципе, можно обобщить RSA на числа, являющиеся произведением 3 и более простых, но зачем?
A: Усложнение себе жизни на пустом месте: чтобы не потерять в криптостойкости, приходится удлинять произведение, а значит, затягивать шифровку и криптоанализ в 1,5 раза — за счёт более длинных чисел, а не мощности перебора. Шифровка происходит прямо сейчас, на имеющемся «железе», анализ — в будущем, на гипотетическом. В первом случае 1,5 играют какую-то роль, во втором — не особенно.

Криптографическая хэш-функция

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

1. Трудно обратить: для данного числа y трудно подобрать послание s, для которого h(s)=y.
2. Трудно найти коллизию: для тел p и q трудно подобрать суффиксы r и s, чтобы h(p . r) = h(q . s). (Точка — склеивание байтовых строк.)

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

Сфабриковать коллизию — интереснее. Готовим два документа с одинаковой свёрткой и заданными осмысленными частями. В нужный момент один подменяем другим.

Наиболее известный криптографический хэш — MD5. Правда, на 2014 он частично скомпрометирован — коллизии фабрикуются даже на обычном ПК. Другими словами: если документ готовил друг, MD5 ещё держится. Если враг — нет.

Имитовставка

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

Также распространены имитовставки на основе хэш-функции (HMAC), выглядят они так:

 HMAC = hash ( (key xor c1) . hash ( (key xor c2) . message ) )

(точка — склеивание байтовых строк, xor — операция «исключающее ИЛИ», c₁ и c₂ — константы, key — ключ, длина которого соответствует длине блока хэш-функции, message — сообщение.)

Имитовставки используют, если само сообщение несекретно, однако важно подтвердить подлинность (разведчик сообщает численность войск); либо когда транспортный слой умеет прочно шифровать, но никак не может проверить абонента (в HTTPS-службах). Однако тот, кто может проверять имитовставку, может её генерировать. От этого недостатка свободна…

Электронная подпись

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

Алгоритм тот же: для подписывания берут хэш-функцию и шифруют. Для сверки — расшифровывают и сверяют с настоящей хэш-функцией.

Часто для защиты от модификации прошивок их подписывают: исследовать и переделать можно, а вот прошить в устройство — фигвам! Особо смешно получается, когда даны исходники прошивки (лицензия на Linux требует это), а устройство требует подпись — такие запреты на модификацию называются «тивоизация», в честь медиаплеера TiVo.

Центр сертификации

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

К подобной уловке (называется «человек посередине») уязвимы практически все криптопротоколы. Для защиты существует так называемый «центр сертификации»: некая сторона, которой все доверяют, а открытый ключ широко известен. Центр сертификации делает электронную подпись открытого ключа и сопроводительной информации: подпись сошлась — значит, ключ сертифицирован.

Центры сертификации могут образовывать цепочки. Например, корневой центр подписывает сертификат службы безопасности, а она — ключи сотрудников. Честными должны быть все центры, а доступный ключ нужен только корневым.

Если есть возможность связаться с центром сертификации, хотелось бы проверить, не забанен ли ключ его подчинённого? Для этого существуют CRL (Certificate revocation list) и OCSP (Online certificate status protocol). Существует продолжение этого протокола, OCSP stapling, где справкой о действительности ключа заморачивается принимающая сторона — это снижает нагрузку на центр сертификации и не передаёт лишним людям имена используемых сайтов.

Две серьёзных проблемы центров сертификации. 1) Прокол любого центра приводит к лавине поддельных сертификатов, пока это не обнаружат и не забанят ключ. И чем больше развелось центров, тем чаще случаются проколы. 2) Опыт показал, что эти центры не всегда честны и подпишут поддельный сертификат «кому надо».

Аппаратные шифромодули

Шифропанки против тотальной слежки
В Великобритании стойкая криптография является уголовным преступлением

Шифромодули бывают трёх типов.

• Шифровальный сопроцессор. Наиболее простая штука, применяется в специализированных устройствах с закрытыми ОС: основной процессор слаб, а риск вредоносной программы минимален. Даёшь шифровку, даёшь ключ, он и молотит, освобождая время центрального процессора на нечто более ценное.
• Шифромодуль с хранилищем ключей. Именно так работает обычная телефонная SIM’ка: ключ никогда не покидает шифромодуля, вредоносная программа может зашифровать-расшифровать, а вот украсть ключ — нет. А ещё так устроены электронные ключи защиты от копирования, продвинутые карты контроля доступа.
• Модуль доверенных вычислений. Не просто хранит ключи, а допускает к шифровке только те программы, у которых есть сертификат. По поводу таких модулей идут большие дебаты: с одной стороны, сильно улучшают жизнь военным и корпоративным пользователям. С другой — мегакорпорация начинает контролировать компьютер, диктовать, какие программы можно запускать, а какие — нет, налаживать непреодолимую защиту от копирования. Так уж вышло, что основные производители компьютеров далеки от медиамагнатов: Intel фильмов не снимает, ASUS музыкантов не окучивает. Так что им выгодно поддерживать «пиратство», и — по крайней мере пока — такие модули остаются на военных и корпоративных машинах. В общем, очередная идея для киберпанк-антиутопии.

Куда идёт криптография?

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

Приведу пример жизненного криптопротокола, который отдалённо напоминает компьютерные. Собрались трое, надо выбрать, кто пойдёт за водкой. При этом даже при сговоре двоих третий должен быть уверен: если его случайное число правильное, всё будет честно. Для этого каждый бросает от одного до трёх пальцев (например, 1, 3 и 1). Считают до 1+3+1=5, начиная с кого-нибудь; тот, на ком счёт остановится, и идёт за водкой. Впрямую этот протокол на компьютер не переносится, однако принцип поняли.

Криптовалюты

Модная на момент 10-х годов XXI века тема, прямо связанная с криптографией. Разберём мы её на примере самой популярной валюты — Биткойна.

Лирическое отступление. Название «биткойн» орфографически правильно именно через «й», по правилам практической английской транскрипции. Как и в случае с Интернетом, Биткойн пишется с большой буквы, когда речь идёт о системе, и с маленькой — когда о единице валюты (хотя чаще применяется сокращение BTC). Также русской традиции соответствует Эфириум, а не Этереум: неологизм будет переводиться по правилам нарицательных слов, а там если устоявшийся в русском корень — берётся устоявшийся вид. Ну и, конечно, это авторское название (Бутерин — канадец русского происхождения и язык знает хорошо).

Биткойн — это децентрализованная пиринговая платёжная система, созданная для перевода электронных средств с одного адреса на другой. Любой человек может создать неограниченное количество биткойн-адресов, которые шифруются алгоритмом w:ECDSA — обычным алгоритмом с открытым ключом, основанным на эллиптических кривых. Каждый адрес связан с двумя ключами (открытым и закрытым) и на момент создания имеет нулевой баланс. Владелец закрытого ключа может совершить транзакцию на любой адрес, зная собственно сам адрес или открытый ключ этого адреса. Казалось бы, обычная банковская система, при чём тут криптография? Всё дело в блокчейне.

Блокчейн — это технология выстраивания непрерывных цепочек блоков данных, играющих роль распределённой базы данных всех транзакций. Каждый блок содержит в себе информацию о транзакциях (записи типа «со счета А переведено: на счет Б — 10 ВТС, на счет В — 5 ВТС, на счет Г — 1 ВТС»), хэш самого блока, хэш предыдущего блока в цепочке, хэш транзакций для их проверки и некоторая служебная информация (вроде адреса, на который пересылается награда за создание блока, подробности ниже). Для того, чтобы блок был принят системой, его хэш должен отвечать достаточно простому условию. Проблема в том, что результат хеширования функции SHA-256 считается необратимым и по входным данным невозможно предсказать результат, поэтому хэш, удовлетворяющий заданному системой условию можно получить только банальным перебором результатов работы алгоритма.

Зачем же нужны такие сложности? Для замедления получения новых блоков. Биткойн — децентрализированная система, и любой человек в системе способен создать блок, отобрав туда любые понравившиеся ему транзакции, находящиеся в очереди. Поэтому, чтобы блоки с транзакциями не создавались мгновенно, условие появление нового блока подбирается системой так, чтобы новые блоки появлялись примерно каждые 10 минут. Раз в 2016 блоков (это примерно две недели) система «смотрит» на скорость появления блоков: если благодаря увеличению вычислительной мощности новые блоки появляются чаще, то условие для принятия хэша усложняется, и наоборот. Собственно, этот процесс и называют «майнингом», причём прибыль от «майнинга» идёт двумя способами: эмиссия новых биткойнов — автору каждого нового блока переводится фиксированное количество монет; и комиссия за транзакции.

Однако что делать, если в разных участках сразу два новых блока объявили предыдущим один и тот же блок (например, если одни вычисления шли в достаточно крупной локальной сети)? На некоторое время в системе появляются две разных цепочки до тех пор, пока не настанет время репликации, и тут самая короткая цепочка вместе со всеми прошедшими в ней транзакциями будет попросту выброшена. Если же цепочки равны, то идёт сравнение сложности хэша. Если же и тут всё одинаково, то берётся с более ранним временем создания.

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

Что значит криптовалюта для криптографии? Крайне высокую надежность к внешнему вмешательству. Взламывать центральный сервер банка и менять количество ноликов на своём счету бесполезно за неимением центра — изменение блока в блокчейне приведёт к нарушению хэша и твоя цепочка не пройдёт репликацию у остальной сети. Единственная уязвимость системы — это «атака 51 %»: контролируя более 51 % вычислительной мощности, можно «втёмную» создать свою цепочку с нужными транзакциями и в нужный момент выкатить её на свет, после чего система признает эту цепочку истинной и отбросит все остальные. К счастью, такого еще не происходило (крупнейший пул контролирует 40 % вычислительной мощности, а самые длинные отброшенные цепочки не превышали пяти блоков).

Впрочем, подобная система имеет врождённые недостатки:

1. Потеря закрытого ключа означает потерю адреса. Нет кодовых слов, подтверждений личности и прочих степеней защит. Решается регистрацией адресов на сторонних сайтах, которые имеют подобные услуги, правда в таком случае безопасность счетов равна безопасности сайта.
2. Транзакции необратимы. Ошиблись в написании адреса? Переслали денег мошеннику? Нельзя куда-то позвонить или написать письмо и отменить транзакцию. С мошенничеством помогает справиться система смарт-контрактов, мультиподписи и арбитража (отсутствующая в Биткойне, зато присутствующая в более современных криптовалютах типа Эфириума), с ошибками — только внимательность при переводах.
3. Пересылка монет на несуществующий адрес фактически означает их потерю. Прямо пересекается с первым пунктом. Даже зная открытый ключ или сам адрес, сгенерировать закрытый ключ вычислительно неосуществимо. Если кто-нибудь когда-нибудь случайно сгенерирует этот адрес, то монеты туда придут, но до этого времени их можно считать потерянными.
4. Несмотря на то, что сама транзакция осуществляется мгновенно, ей требуется подтверждение, то есть сеть должна достичь консенсуса, что твоя транзакция попала в блок и этот блок оказался в истинной цепочке, а не отброшенной. Самые длинные отброшенные цепочки не превышали пяти блоков, шесть подтверждений (то есть один час) на практике вполне достаточно для уверенности. Но нет никакой разницы между «транзакция подтверждена» и «транзакция никогда не отменится» — потому платили бы вы в кафе системой, которая подтверждается за час? Зато по параметру «транзакция больше не отменится» Биткойн даже быстрее банков, где в разных странах любой перевод можно отменить в пределах от месяца до полугода.
5. Биткойн не масштабируем: если больше пользуются, будет больше транзакций, но если больше майнят — будет всё тот же 1 блок в 10 минут. Пиковая пропускная способность — около 7 транзакций в секунду. Потому, когда усиливается трафик, транзакции начинают подтверждаться с большим запозданием. Ещё один повод не платить биткойнами за обед в кафе. В одном из ответвлений Биткойна блок расширен с 1 мегабайта до 4, с возможностью расширять до бесконечности. С падением биткойна перестало быть проблемой.
6. Блокчейн Биткойна не защищён от вставки посторонней информации. В 2018 году моралофаги из Германии обнаружили в блокчейне порнографические картинки, и по германским законам, всех, кто имеет биткойн в Германии, полагается посадить за хранение. Вымарать эти картинки из блокчейна невозможно.
7. Биткойн стал серьёзным потребителем электроэнергии, порядка 0,15 % от всего потребления человечества. С немасштабируемостью биткойна выходит, что одна транзакция требует столько энергии, сколько расходует квартира в месяц. (Общее потребление Биткойна зависит от того, сколько майнят, а потребление в пересчёте на транзакцию — от соотношения «майнеры/транзакции»).
8. Биткойн псевдоанонимен: вы защищены только тем, что другие не знают вашего адреса. Прямая передача биткойна за какую-то услугу приводит к тому, что адресат начинает видеть вашу историю, прошлую и будущую. Адреса, разумеется, также псевдоанонимны, но их тоже можно деанонимизировать. Если злоумышленник выложил свой адрес, все будут знать: это плохой адрес. Для «отмывания» биткойнов существуют так называемые «миксеры», перемешивающие транзакции из разных источников — но они уничтожают всю идею децентрализованной валюты.

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

Можно ли делать криптовалюту, которая решает полезные задачи?

Возникает вопрос: а можно ли объединить, например, криптовалюту и Folding@Home, решать какую-то сложную задачу (например, свёртывание белков) и получать за это гешефт? К сожалению, нет, и вот почему.

1. Кто будет поставщиком задач? Если один институт — то, разумеется, нежелание этого института раздавать задачи полностью закроет криптовалюту. Транзакции проходят, если кто-то непрерывно занимается майнингом.
2. Как регулировать частоту появления блоков в блокчейне? В Биткойне вероятность выкопать монету (а значит, создать блок) делается изменением количества нулей в блоке: чем больше майнят, тем более круглое число должен найти майнер. А как менять сложность научных расчётов?
3. Как проверить решение? Задачи криптографии дискретные, задача или решена, или нет. Задачи науки непрерывные, и решение может быть точным и неточным. Если решение на границе допуска, тонкие особенности того или иного сопроцессора, того или иного метода решения приводят к тому, что одни клиенты объявляют задачу решённой, другие — нет.

• Допустим, поставщиком задач будет множество институтов и предприятий по всему миру — столько, что бы ситуация «нежелания» всех разом была практически невозможна. Хотя частоту появления блоков в блокчейне изменить не получится, можно менять размер вознаграждения, выдаваемого за блок (то есть, если блоков всплывает вдвое больше, то обычная криптовалюта делала бы нахождение блоков вдвое сложнее, а «научная» выдавала бы вдвое меньше монет — результат для майнера один и тот же; да, число находимых блоков будет непрерывно расти, но можно сделать криптовалюту без ограничения на эмиссию и общий запас монет). Что значит «точным и неточным», автор правки не понял. Распределенные вычисления, если они не были подвержены помехам при передачи данных, дают такой же результат, как и обычные. В общем-то, точность и неточность таких вычислений будет как раз хорошо эмулировать прямой перебор в обычных криптовалютах: и там и там понадобится много попыток для нужного результата. Помимо этого, третью проблему считаю не критичной, с ней можно ужиться (у обычной криптовалюты проблем тоже не мало, но как-то пользуются).

Квантовая криптография

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

Развитие тайнописи

Тайнопись, она же стеганография — способ скрыть, что секретное сообщение вообще есть. Тайнопись может быть зашифрована, а может и нет.

Древние времена

• Обрить посланнику голову, написать сообщение, подождать, пока волосы отрастут.
• Невидимые чернила.
• Маскировка сообщений под безобидное. «Пляшущие человечки» Конан Дойля. Дэвид Кан во «Взломщиках кодов» упоминает сообщение кукольника: «Сломанная кукла в юбке из гавайской травы будет полностью починена к первой неделе февраля» (имеется в виду срок ввода в строй крейсера «Гонолулу»). Учтите, авторы: в военное время запрещено посылать почтой всё, что может стать маскировкой: ноты, схемы вышивки и вязания, шахматные партии, списки чего-нибудь… Цензура бдит, и бдит не за пристойностью, а за шпионажем.

Средние века, арабский мир

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

• Наколы и прочие пометки в книгах.

Эпоха Просвещения

• Двоичное кодирование букв особенностями почерка (соединены ли буквы, беглое или нет написание, и т. д.) Каждая буква алфавита кодируется пятью битами.

XX век

• Микроточки — фотоснимки размером с типографскую точку, приклеенные к безобидному документу.

Компьютерное время

• Информация, встроенная в видео-, звуковые и графические контейнеры наподобие AVI и JPEG. Да чего там, в обычном TXT-шнике можно в конце каждой строки ставить или не ставить пробел. В результате в сборнике Маяковского можно (условно) беспалевно передать пару килобайт текста. В графических файлах можно заменять цвета на максимально похожие, задавая в каждый пиксель чётный или нечётный код цвета (как вариант, варьировать на плюс-минус один каждый из параметров цвета, невооружённым глазом такое не заметишь, а три бита на пиксель не лишние).
• «Жёлтые точки», которые наносит на распечатку любой цветной принтер. Точки кодируют серийный номер устройства, дату и время печати.
• Нестандартные способы форматирования дисков (например, отформатировать HD-дискету на 80 дорожек, записать информацию в дорожки с нечётными номерами и переформатировать на 40 дорожек). Хранение информации в незадействованных полях файловой системы наподобие сбойных блоков или «хвостов» кластеров.
• Антипиратские коды, начиная с несуществующей улицы в заштатной деревне и заканчивая точками на киноэкране. Для открытой информации такие коды раскрывают факт «пиратства», для закрытой — кто именно допустил утечку.

Меры против компьютерной тайнописи

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

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

Поиск «неладного» в контейнере. Чем больше процент полезного сигнала, тем больше следов оставляет тайнопись. Например, если картинки — фотографии с минимальной обработкой, исследование шумов может показать: матрица и дебайеризатор так не шумят.

И просто сопоставлением нескольких сообщений.

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

Распространённые ошибки

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

• Основная стратегия шифрования — в том, чтобы при известном алгоритме нельзя было расшифровать сообщение, не зная секретного ключа, или поставить чужую электронную подпись под своими данными. Вопреки этому, встречается представление, будто секрет представляет именно способ шифрования. Это было бы неразумно по ряду причин: широко известный алгоритм может быть неоднократно и многими людьми проверен, в то время как тайный по ясной причине доступен только узкому кругу лиц и может содержать неизвестные уязвимости, которые в любой момент могут быть эксплуатированы; создать новый и хороший алгоритм шифрования — нетривиальная задача для специалистов, и даже когда он создан, должно пройти немало времени, прежде чем можно будет убедиться в его надежности.
  • Тем, кто всё ещё хочет придумать свой шифр: есть несколько удачных взломов самодельных шифров, на слуху DVD и HDCP (оба, что интересно, защита медиаконтента от копирования). Каждый свободный DVD-плеер ломает защиту: это делается за долю секунды, а хранить ключи запрещает DMCA, американский закон о цифровом копирайте.
  • Маятник регулярно качается из стороны в сторону: когда какой-то алгоритм шифрования считается невзламываемым, приобретают особую важность ключи, когда же в нём находят уязвимость, расцветают буйным цветом наколенные протоколы, основная защищённость которых — в их секретности. Из известных подобных качаний — окончательный взлом шифра Цезаря и всевозможных перестановочных шифров методом частотного анализа (аль-Кинди, IX век), вызвавший многовековую лавину доморощенных шифров, вылившуюся в появление шифра Виженера (который до конца XIX века ломали только за счёт невежливого обращения с ключами: каждая вторая пара совершающих адюльтер искренне полагала, что «любовь навеки» — достаточно надёжный ключ для секретной переписки, на чём их и ловили мужья-рогоносцы, а конфедераты всю американскую Гражданскую войну использовали ровно три ключа: «Manchester Bluff», «Complete victory» и, ближе к концу войны, «Come retribution», так что северяне их переписку читали, как открытую книгу, при правильном обращении с ключами вручную он практически не кололся), ещё одна чехарда с кодовыми книгами и секретными сигналами, появление «Энигмы», взломы «Энигмы», и снова суета с кодовыми книгами и одноразовыми шифроблокнотами вплоть до появления RSA.
• В фильмах, где показывают хакеров, нередко эксплуатируется следующая картина мира: каждая организация или человек использует свой шифр, который хакер за определенное время может взломать, при этом чем серьезнее организация, тем больше уйдет время. На самом деле используется крохотная горстка различных общеизвестных алгоритмов, которые, как правило, никто еще не взломал и, вероятнее всего, не сможет это сделать (а если и сможет, то потратит на это годы сложнейших математических исследований). Нахождение уязвимостей в отдельных алгоритмах быстро становится известно, а, взломай кто-нибудь что-то из фундаментальных принципов шифрования, мир бы сильно изменился. В реальности хакеры существуют, но взламывают они не шифры, а дыры в системах безопасности, уводят пароли из записных книжек секретарш и данные cookies из браузеров на незащищенных машинах, перехватывают и анализуют поток между узлами сети и занимаются кучей разных вещей, совершенно не похожей на то, что показывают обычно в кино.
  • Что интересно, лучшие помощники хакера в стане противника — программисты и сотрудники службы безопасности. Программисты, разрабатывающие системы безопасности, по большей части совершенно не думают, как сделать работу с шифрованием удобной для пользователя, из-за чего пользователи, например, предпочитают пользоваться не корпоративной защищённой почтой, а личной на публичном сервисе. А безопасники сильно осложняют пользователям жизнь всевозможными трудновыполнимыми требованиями, наподобие паролей не короче 16 символов, обязательно содержащих буквы в разном регистре, цифры и знаки препинания. Да, ещё чтобы на каждом сервисе был свой пароль, и чтобы раз в месяц он менялся. Поэтому такие пароли обычно записываются на бумажке, спрятанной рядом с рабочем местом (чтоб безопасник не увидел), а часто и вообще приклеиваются с обратной стороны клавиатуры.
• Еще один кинематографический штамп — подбор пароля по символам. Он тоже не имеет ничего общего с реальностью: хэш-функции устроены так, что самое небольшое изменение в аргументе сильно меняет результат, так что есть только один способ подобрать пароль: нужно угадать его целиком (а для этого в случае более-менее длинного пароля потребуется невообразимо большое время). Понять, близок ли введенный пароль реальному, нельзя.
• Приплетать шифроблокноты без нужды. Применяешь шифроблокнот — значит, есть надёжный канал связи такой же пропускной способности. И шифроблокнот годится, если канал только в одну сторону, либо доступен только два часа в неделю, а сообщения передавать нужно постоянно. Основу сообщения часто шифруют более простыми шифрами, а блокнот оставляют на имена и даты.
• Ключи невообразимой длины. Вовсю работают симметричные шифры в 64 бита и асимметричные в 1024 бита, 256 и 4096 — достаточный запас, чтобы будущие слабости не бросили тень на шифр. Таких ключей может быть много (например, в сложных протоколах), но удлинять их до килобайт бессмысленно. Не забывайте: один бит — это вдвое!
• Никто не скрывает полезную нагрузку (если, конечно, её длина может превысить один блок) под асимметричными шифрами — это расточительство по процессорной мощи. Под асимметричными шифрами хранят обычный симметричный ключ, которым и закрыто сообщение.

Ссылки

• Мужчина сидит в американской тюрьме, потому что не смог расшифровать содержимое HDD
• В Англии ты можешь попасть за решётку за хранение шума