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

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

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

Содержание

[править] Что читать

Я сошлюсь на две книги. Всего на две, неспециалисту этого должно хватить.

А я добавлю:

[править] Терминология

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

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

[править] Какие бывают шифры

[править] Взлом шифров

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

Ну и нельзя сбрасывать со счетов банальные подслушивание, пытки («терморектальный криптоанализ») и подкуп.

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

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

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

[править] Ручная криптография

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

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

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

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

[править] Шифры простой замены

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

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

[править] Литорея

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

[править] Шифр Цезаря

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

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

[править] Квадрат Полибия

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

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

[править] Шифр Виженера

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

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

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

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

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

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

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

[править] Колёса Джефферсона

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

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

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

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

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

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

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

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

[править] Книжный шифр

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

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

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

Этот вопрос ещё ждёт своего исследователя. Шифровальщик Брюс Шнайер придумал для писателя Нила Стивенсона шифр «Пасьянс» («шифровальная машина» — колода карт). Однако дальнейшие исследования нашли в «Пасьянсе» несколько уязвимостей.

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

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

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

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

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

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

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

[править] «Игра в имитацию»

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

А что осталось в фильме за кадром…

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

(link)

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

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

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

[править] Симметричные и асимметричные шифры

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

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

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

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

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

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

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

Как сказано выше, хэш-функция из длинного сообщения строит свёртку фиксированной длины (число от 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 — операция «исключающее ИЛИ», c1 и c2 — константы, key — ключ, длина которого соответствует длине блока хэш-функции, message — сообщение.)

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

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

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

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

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

[править] Центр сертификации

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

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

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

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

[править] Куда идёт криптография?

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

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

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

[править] Развитие тайнописи

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

Древние времена. Обрить посланнику голову, написать сообщение, подождать, пока волосы отрастут.

Древние времена. Невидимые чернила.

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

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

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

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

Компьютерное время. Информация, встроенная в видео-, звуковые и графические контейнеры наподобие AVI и JPEG.

Компьютерное время. «Жёлтые точки», которые наносит на распечатку любой цветной принтер. Точки кодируют серийный номер устройства, дату и время печати.

Компьютерное время. Нестандартные способы форматирования дисков (например, отформатировать HD-дискету на 80 дорожек, записать информацию в дорожки с нечётными номерами и переформатировать на 40 дорожек). Хранение информации в незадействованных полях файловой системы наподобие сбойных блоков или «хвостов» кластеров.

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

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

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

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

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

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

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

[править] Распространённые ошибки

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

[править] Ссылки

[править] Примечания

  1. Розеттский камень, ставший ключом к египетским иероглифам, был на трёх языках.
  2. Первый принцип — достаточная прочность ключа. Второй принцип перед вами. Остальные четыре относятся к практичности: легко меняющийся ключ, сопрягается с телеграфом, управляется одним человеком, проста в использовании.
  3. Точнее, в RSA их три: произведение и два ключа. Одна сторона знает произведение и 1-й ключ, вторая — произведение и 2-й ключ. Оба ключа можно получить, разложив произведение на простые множители… но это адски трудно.
  4. Последний, правда, не AES (у него минимальный ключ 128 бит), а Blowfish — шифр с 64-битным ключом, широко применяемый и всё ещё не скомпрометированный.
  5. Разве что Microsoft идёт на поводу у медиамагнатов: в Windows, начиная с Vista, есть Protected Media Path, задолбавший любого электронщика, строящего нестандартные устройства, Windows 10 отсылает непонятно куда каталоги дисков… Ну и Apple сделала свой магазин контента (iTunes) — но сейчас (2014) её позиция «не быть вредными», противопоставить себя настоящим звукомагнатам.
  6. Время реакции человека намного больше, чем временнóе разрешение зрения. Потому легко увидеть, действовали напарники самостоятельно или отвечали на ваше число. С компьютерами всё наоборот: реагируют они за доли миллисекунды, а типичные сетевые пинги исчисляются десятками миллисекунд.
  7. О цензуре и способах её троллить можно прочитать: «Вы, конечно, шутите, мистер Фейнман».
Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты