July 22nd, 2011

2017

История шифрования, часть 2: Энигма

Давно хотел прочитать о немецком шифре второй мировой войны — до сих пор встречались только отдельные кусочки информации.

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

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

Второе слабое место нашли англичане — если правильно угадать хотя бы одно зашифрованное слово (например, каждое утро, ровно в 06:05 немцы передавали прогноз погоды, в начале которого разумно было предположить слово «Wetter»), то по нему можно поднять код дня, а за ним и все сообщения этого дня.
Для того, чтобы увереннее предполагать слова в зашифрованных сообщениях, англичане ставили мины на видном месте, а потом искали их координаты в сообщениях немецких подводных лодок другим немецким подводным лодкам.

Если не учитывать эти две дырки — только полный перебор всех вариантов. В переборе парадоксальным образом помогало стремление криптологов ручками усилить случайность — о невозможности и вредности таких мер полезно помнить. Например, в машине Энигма было несколько дисков, и каждый день диски переставлялись случайным образом. Но протокол требовал переставлять их так, чтобы ни один диск не оставался на том же месте, что он был вчера — что вдвое сокращает количество переборов, если мы уже знаем вчерашний код. И таких «дополнительных мер безопасности» было множество.


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

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

Disclaimer n°1: да, к гомосексуализму тогда отношение было не такое, как в Англии сейчас. Но при этом и не такое, как сегодня в России. Если я правильно понял, Тьюринг пришёл в полицию заявить о квартирной краже и сам рассказал о своей сексуальной ориентации полицейским. После чего долго не мог поверить, что они не шутят, пытаясь задержать его в участке.
Disclaimer n°2: Я, естественно, не к тому, что ненужных стране людей вполне можно чморить, но гениям обычно и не такие вещи прощали.


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

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


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

По этому поводу прекрасная история — англичане расшифровали радиограмму с координатами 9-ти немецких танкеров. Если их потопить тут же все 9, немцы могут понять, что их код расшифровали. Так что приняли решение потопить только 7, а 2 пускай плывут дальше. Проблема в том, что оставшиеся 2 танкера случайно попались не бывшим в курсе английским лётчикам, которые успешно их тоже потопили.


А после войны Англия не стала рассекречивать работы по взлому Энигмы, а раздала трофейные аппараты правительствам стран Commonwealth под видом совершенно надёжной технологии :-)
2017

История шифрования, часть 3: после Энигмы

Глава про RSA. Парни, которые придумали алгоритм, увлекались математикой с самого детства. До такой степени, что даже ездили на математические олимпиады в СССР! На следующей странице — фотография британской делегации на олимпиаде :-)

Ещё одна поразившая фраза — «беседа текла рекой, темы менялись от общих вопросов археологии до крыс, чьё присутствие в бочке с сидром улучшает вкус последнего...»
Я (пока что) не нашёл в интернете ни одного упоминания эффекта крыс на вкус сидра!


Упомянули книгу «The spycatcher» by Peter Wright. По описанию она мне понравилась, залез в Википедию, и нашёл там упоминание проекта RAFTER — поиск пассивных приёмников советских шпионов. Утверждается, эта технология используется сейчас для детектирования телевизоров, чтобы заставить людей платили налог на телевизор.
Мне казалось, я когда-то читал про эту технологию, и я был уверен, что именно таким образом меряют телевизионную аудиторию. А оказалось, её меряют каким-то совершенно кустарными способами...


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


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

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

Очень интересная тема — распространение существующего «материального» законодательства на появляющийся нематериальный мир. Куда вести вора, укравшего в виртуальном мире мешок с алмазами? А если эти алмазы вполне конвертируемы в привычную валюту? А если воровство — предусмотренная часть игры? А если для него вор хакнул игру? Прекрасная тема!
2017

История шифрования, про языки

Когда книга вместо основной темы вдруг начинает рассказывать про разные языки и письменности, становится понятно, что это — хорошая книга!

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

Очевидная проблема — в языке навахо нет нужных армии технических терминов (классическое «муруки-буруки трансформатор салаки-бараки аккумулятор»). Проблема обходится составлением отдельного словаря: истребитель — ястреб, бомбардировщик — сова и т.д. Для имён собственных и непредусмотренных в словаре терминов сделали возможность передачи по буквам: «Дрозд-Журавль-Олень» даёт «Джо».

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

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


Небольшое ответвление в книге — рассказ о расшифровке древних письменностей.

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

Ещё при иероглифы — росту интереса в Европе способствовала перестройка Рима папой Сикстом VI, который, как утверждает книга, «построил кучу дорог и поставил по египетскому обелиску на каждом перекрёстке».
Меня, чью душу единственный Парижский обелиск регулярно греет, заинтересовал этот факт. Оказывается, в Риме действительно множество египетских обелисков, большинство из них было привезено ещё в античность, но долгое время, грубо говоря, провалялись без дела. Из них папа Сикст VI установил «всего» три.


В контексте же иероглифов упомянули Юнга, которого мы все проходили в школе на уроке про волновую теория света.
Оказывается, этот же человек придумал термин «индо-европейские языки», он же первым прочёл имена фараонов в египетских документах. Удивительный человек был!

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