Компьютерные сети. 6-е изд.

8.4. Криптография

Слово криптография (cryptography) происходит от греческого «тайнопись». У криптографии долгая и яркая история, насчитывающая несколько тысяч лет. В данном разделе мы всего лишь кратко упомянем некоторые отдельные моменты в качестве введения к последующей информации. Желающим ознакомиться с полной историей криптографии рекомендуется книга Кана (Kahn, 1995). Для получения всестороннего представления о текущем положении дел см. работу Кауфмана и др. (Kaufman et al., 2002). Если вы хотите подробнее ознакомиться с математическими основами криптографии, см. книгу Крафта и Вашингтона (Kraft and Washington, 2018). Если вас, наоборот, не слишком интересуют математические основы, см. работу Эспозито (Esposito, 2018).

С профессиональной точки зрения понятия «шифр» и «код» отличаются друг от друга. Шифр (cipher) представляет собой посимвольное или побитовое преобразование, которое не зависит от лингвистической структуры сообщения. Код (code), напротив, заменяет целое слово другим словом или символом. Коды в настоящее время не используются, хотя имеют богатую историю.

Наиболее успешным в истории считается код, использованный корпусом морской пехоты США в Тихом океане во время Второй мировой войны. Для ведения секретных переговоров применялись слова языка индейцев навахо, носители которого служили в американских войсках. Например, слово чаи-да-гахи-найл-цайди (что буквально означает «убийца черепах») означало противотанковое оружие. Язык навахо тоновый (для различения смысла используется повышение или понижение тона), весьма сложный, не имеет письменной формы. Но самое большое его достоинство заключалось в том, что ни один японец не имел о нем ни малейшего представления. В сентябре 1945 года в газете San Diego Union появилась статья, в которой были раскрыты сведения о том, насколько эффективным оказался опыт использования языка индейцев навахо во время военного противостояния с японцами. Японцы так и не смогли взломать этот код, и многие носители языка индейцев навахо были удостоены высоких воинских наград за отличную службу и смелость. Тот факт, что США смогли расшифровать японский код, а японцы так и не узнали язык навахо, сыграл важную роль в американской победе в Тихом океане.

8.4.1. Основы криптографии

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

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

Илл. 8.9. Модель шифрования (для шифра с симметричным ключом)

Сообщения, подлежащие зашифровке, открытый текст (plaintext), преобразуются с помощью функции, параметром которой является ключ (key). Результат шифрования, зашифрованный текст (ciphertext), обычно передается по радио или через связного. Предполагается, что противник или злоумышленник (intruder) слышит и аккуратно копирует весь зашифрованный текст. Но в отличие от адресата, он не знает ключа дешифрования, и поэтому расшифровка сообщения представляет для него большие трудности, а порой просто невозможна. Иногда он не только прослушивает канал связи (пассивный злоумышленник), но также записывает сообщения и воспроизводит их позже, вставляет свои сообщения или модифицирует оригинал, прежде чем он достигнет получателя (активный злоумышленник). Искусство взлома шифров называется криптоанализом (cryptanalysis). Искусство изобретать шифры (криптография) и искусство взламывать их (криптоанализ) вместе называются криптологией (cryptology).

Для обозначения открытого/зашифрованного текста и ключей лучше всего применять специальную нотацию. Мы будем использовать формулу C = EK (P), обозначающую, что при зашифровке открытого текста P с помощью ключа K получается зашифрованный текст C. Аналогично формула P = DK (C) означает расшифровку зашифрованного текста C для восстановления открытого текста. Из этих формул следует, что

DK (EK (P)) = P.

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

Основное правило криптографии заключается в предположении, что криптоаналитику (взломщику шифра) известен используемый метод шифрования. Другими словами, он точно знает, как работают методы шифрования E и дешифрования D на илл. 8.9. На разработку, тестирование и внедрение нового метода тратятся огромные усилия. Поэтому каждый раз, когда старый метод оказывается скомпрометированным (или считается таковым), хранить алгоритм шифрования в секрете просто непрактично. А предположение, что метод является секретным, когда это уже не так, может принести еще больше вреда.

Здесь на помощь приходит ключ шифрования. Он состоит из относительно короткой строки, определяющей один из множества вариантов результата шифрования. В отличие от самого метода шифрования, который может меняться лишь раз в несколько лет, ключ можно менять столько, сколько нужно. Таким образом, наша базовая модель представляет собой постоянный и известный общий метод, в котором в качестве параметра используется секретный и легко изменяемый ключ. Идея, согласно которой криптоаналитику известен метод, а краеугольным камнем секретности является эксклюзивный ключ, называется принципом Керкгоффса (Kerckhoff’s principle). Его в 1883 году впервые высказал голландский военный криптограф Огюст Керкгоффс (Auguste Kerckhoff, 1883). Итак:

Принцип Керкгоффса: все алгоритмы шифрования должны быть общедоступными; секретны только ключи.

Не стоит придавать большое значение секретности алгоритма. Попытка сохранить алгоритм в тайне, называемая в отрасли безопасностью за счет неясности (security by obscurity), обречена на провал. К тому же, опубликовав свой алгоритм, разработчик получает бесплатную консультацию от большого количества ученых-криптоаналитиков, горящих желанием взломать новую систему и тем самым продемонстрировать свой ум. Если никто не смог взломать алгоритм в течение долгого времени после его публикации, видимо, алгоритм достаточно прочен. (С другой стороны, исследователи иногда находят ошибки в системах защиты с открытым кодом наподобие OpenSSL спустя десять и более лет после их появления, поэтому принцип «чем больше глаз, тем меньше неполадок» далеко не всегда действует на практике.)

Поскольку только ключ является по-настоящему секретным, главный вопрос касается его длины. Рассмотрим простой кодовый замок. Его основной принцип состоит в том, что вы последовательно вводите цифры. Все это знают, но ключ хранится в секрете. Ключ длиной в две цифры образует 100 вариантов. Ключ длиной в три цифры означает 1000 вариантов, а при длине ключа в шесть цифр число комбинаций достигает миллиона. Чем длиннее ключ, тем выше показатель трудозатрат (work factor) взломщика шифра. При увеличении длины ключа показатель трудозатрат для взлома системы путем простого перебора значений ключа растет экспоненциально. Секретность передаваемого сообщения обеспечивается мощным (но все же открытым) алгоритмом и длинным ключом. Чтобы не дать прочитать свою электронную почту младшему брату, достаточно ключа длиной в 64 бита. В коммерческих системах имеет смысл использовать ключи длиной 256 бит. Для защиты текстов от спецслужб развитых государств потребуются ключи минимум в 256 бит (и гораздо больше). При этом нужно отметить, что эти цифры относятся к симметричному шифрованию, когда для шифрования и дешифрования используются одинаковые ключи. Чуть позже мы подробно обсудим различия между симметричным и асимметричным шифрованием.

С точки зрения криптоаналитика, задача криптоанализа имеет три принципиальных варианта. В первом случае у криптоаналитика есть зашифрованный текст без соответствующего открытого текста; это задача только с зашифрованным текстом (ciphertext-only problem). Криптограммы такого рода часто публикуются в газетах в разделе головоломок. Во втором случае криптоаналитик располагает зашифрованным текстом вместе с соответствующим открытым текстом; это задача с известным открытым текстом (known plaintext problem). Наконец, в третьем случае криптоаналитик может зашифровать любой произвольно выбранный им сегмент открытого текста. Это называют задачей с выбранным открытым текстом (chosen plaintext problem). Если бы криптоаналитикам было позволено задавать вопросы типа: «Как будет выглядеть зашифрованный результат для текста ABCDEFGHJKL?», криптограммы из газет решались бы очень легко.

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

Исторически методы шифрования разделились на две категории: метод подстановки и метод перестановки. Мы кратко рассмотрим их в качестве введения в современную криптографию.

8.4.2. Два базовых принципа криптографии

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

Избыточность

Первый принцип гласит, что все зашифрованные сообщения должны содержать некую избыточность, то есть информацию, которая не требуется для понимания сообщения. Приведем пример. Представьте компанию «Домосед», торгующую по почте товарами 60 000 наименований. Радуясь, что им удастся так экономно распорядиться ресурсами, программисты компании решили, что весь бланк заказа будет состоять из 16 байт для имени клиента, за которым последует поле товара из 3 байт (1 байт для обозначения количества и 2 байта для идентификатора товара). Последние 3 байта решено закодировать с помощью очень длинного ключа, известного только клиенту и компании «Домосед».

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

Получив эти сообщения, компьютер компании «Домосед» находит ключ для дешифрования по имени клиента. К несчастью для компании, почти все 3-байтные сообщения могут восприниматься как достоверные, поэтому компьютер начинает печатать заявки на доставку товаров. Может показаться странным, что клиент заказал 837 сидений для детских качелей или 540 песочниц, но вполне возможно, что он занимается строительством детских игровых площадок. Таким образом, активный злоумышленник (уволенный сотрудник) способен доставить очень много неприятностей, даже не вникая в смысл сообщений, отсылаемых его компьютером.

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

Криптографический принцип номер 1: сообщения должны содержать избыточные данные.

С другой стороны, наличие избыточной информации облегчает работу криптоаналитика по взлому шифра. Предположим, что конкуренция в бизнесе почтовых заказов чрезвычайно высока и что главный конкурент «Домоседа», фирма «Лежебока», очень хочет узнать объем продаж песочниц «Домоседа» в месяц. Для этого «лежебоки» подключились к телефонной линии «домоседов». В исходной схеме с 3-байтными номерами криптоанализ был почти невозможен, поскольку, предположив значение ключа, криптоаналитик не мог проверить правильность догадки, ведь почти все сообщения были технически корректны. С введением новой 12-байтной схемы криптоаналитик легко сможет отличить допустимое сообщение от недопустимого.

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

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

Ограниченный срок годности

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

Криптографический принцип номер 2: нужен способ борьбы с повторной отправкой старых сообщений.

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

8.4.3. Подстановочные шифры

При использовании подстановочного шифра (substitution cipher) каждый символ или группа символов заменяются другим символом или группой символов. Один из древнейших шифров такого рода — шифр Цезаря (Caesar cipher), изобретение которого приписывают римскому императору. Этот шифр заменяет все буквы алфавита на другие с помощью циклического сдвига на три позиции. Так, буква a становится буквой D, b — E, c — F, … и z — C. К примеру, слово attack превращается в DWWDFN. Мы будем обозначать открытый текст строчными символами, а зашифрованный — прописными.

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

Следующее усовершенствование заключается в установлении соответствия между каждым символом в открытом тексте (для простоты, скажем, это 26 букв) и каким-либо другим. Например,

открытый текст:

a b c d e f g h i j k l m n o p q r s t u v w x y z

зашифрованный текст:

Q W E R T Y U I O P A S D F G H J K L Z X C V B N M

Такая система называется моноалфавитным подстановочным шифром (monoalphabetic substitution cipher), ключом к которому является 26-символьная строка, соответствующая полному алфавиту. В нашем случае открытый текст attack будет преобразован в зашифрованный текст QZZQEA.

На первый взгляд эта система может показаться надежной, ведь даже если криптоаналитику известен общий принцип шифрования (подстановка одного символа вместо другого), он все равно не знает, какой из 26! ≈ 4 × 1026 возможных вариантов ключа следует применить. В отличие от шифра Цезаря применение метода простого перебора в данном случае весьма сомнительно. Даже при затратах 1 нс на проверку одного варианта ключа миллиону параллельно работающих процессорных ядер понадобится около 10 000 лет, чтобы перепробовать их все.

Тем не менее подобный шифр легко взламывается даже при наличии довольно небольших фрагментов зашифрованного текста. Для атаки может быть использовано преимущество статистических характеристик естественных языков. Например, в английском языке буква e встречается в тексте чаще всего. Следом за ней по частоте использования идут буквы t, o, a, n, i и т.д. Самыми распространенными комбинациями из двух символов, биграммами (digrams), являются th, in, er, re и an. Наиболее часто встречающимися комбинациями из трех символов, триграммами (trigrams), являются the, ing, and и ion.

Криптоаналитик, пытающийся взломать моноалфавитный шифр, прежде всего сосчитает относительные частоты всех символов алфавита в зашифрованном тексте. Затем он попробует заменить наиболее часто встречающийся символ буквой e, а следующий по частоте — буквой t. Затем он найдет триграммы самой распространенной формы tXe, где, скорее всего, X — это h. Аналогичным образом, если последовательность thYt встречается достаточно часто, то, вероятно, Y обозначает символ a. Обладая этой информацией, криптоаналитик может поискать часто встречающуюся триграмму вида aZW, что, скорее всего, означает and. Продолжая угадывать буквы, биграммы и триграммы и зная, какие последовательности символов являются наиболее вероятными, криптоаналитик побуквенно восстанавливает исходный текст.

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

CTBMN BYCTC BTJDS QXBNS GSTJC BTSWX CTQTZ CQVUJ QJSGS TJQZZ MNQJS VLNSX VSZJU JDSTS JQUUS JUBXJ DSKSU JSNTK BGAQJ ZBGYQ TLCTZ BNYBN QJSW

В сообщении бухгалтерской фирмы, скорее всего, есть слово financial. Используя тот факт, что в этом слове буква i встречается дважды, разделенная четырьмя другими буквами, мы будем искать в зашифрованном тексте повторяющиеся символы, отстоящие друг от друга на это расстояние. В результате мы найдем 12 таких мест в тексте в позициях 6, 15, 27, 31, 42, 48, 56, 66, 70, 71, 76 и 82. Однако только в двух случаях, в позициях 31 и 42, следующий символ (соответствующий букве n в открытом тексте) повторяется в соответствующем месте. Из этих двух вариантов символ a имеет правильное расположение только для позиции 31. Теперь нам известно, что слово financial начинается в позиции 30. С этого момента выяснить ключ проще, применяя лингвистическую статистику английского языка и угадывая целые слова.

8.4.4. Перестановочные шифры

Подстановочные шифры «маскируют» символы открытого текста, но не меняют порядок их следования. Перестановочные шифры (transposition ciphers), наоборот, меняют порядок следования символов, но не «маскируют» их. На илл. 8.10 показан простой перестановочный шифр с колоночной перестановкой. Ключом к такому шифру служит слово или фраза, в которых нет повторяющихся букв. В данном примере в качестве ключа используется слово MEGABUCK. Цель ключа — пронумеровать колонки. Первой колонкой становится колонка под буквой, расположенной ближе всего к началу алфавита, и т.д. Открытый текст записывается горизонтально в строках. Зашифрованный текст читается по колонкам, начиная с колонки с младшей ключевой буквой.

Илл. 8.10. Перестановочный шифр

Чтобы взломать перестановочный шифр, прежде всего криптоаналитик должен понять, что он имеет дело именно с таким способом шифрования. Если посмотреть, насколько часто здесь употребляются символы E, T, A, O, I, N и т.д., можно легко заметить, что частота их употребления такая же, как в обычном открытом тексте. Становится ясно, что мы имеем дело с перестановочным шифром, поскольку при его использовании буквы представляют сами себя, и, соответственно, распределение частот остается неизменным.

Затем нужно угадать число колонок. Во многих случаях по контексту сообщения можно угадать слово или фразу. К примеру, криптоаналитик подозревает, что где-то в сообщении должно встретиться словосочетание milliondollars. Обратите внимание, что из-за присутствия этих слов в исходном тексте в зашифрованном тексте встречаются биграммы MO, IL, LL, LA, IR и OS. Символ O следует за символом M (то есть они стоят рядом по вертикали в колонке 4), поскольку они разделены в предполагаемой фразе дистанцией, равной длине ключа. Если бы использовался ключ длиной семь, тогда вместо перечисленных выше биграмм встречались бы следующие: MD, IO, LL, LL, IA, OR и NS. Таким образом, для каждой длины ключа в зашифрованном тексте образуется новый набор биграмм. Перебрав различные варианты, криптоаналитик зачастую довольно легко может определить длину ключа.

Остается узнать только порядок колонок. Если их число k невелико, можно перебрать все k(k – 1) возможных комбинаций пар соседних колонок, сравнивая частоты образующихся биграмм со статистическими характеристиками английского языка. Пара с лучшим соответствием считается правильно позиционированной. Затем все оставшиеся колонки по очереди проверяются в сочетании с уже найденной парой. Предполагается, что колонка, в которой биграммы и триграммы дают максимальное совпадение со статистикой, является правильной. Весь процесс повторяется, пока не будет восстановлен порядок всех колонок. Есть шанс, что на данном этапе текст уже будет распознаваемым (например, если вместо слова million мы увидим milloin, то сразу станет ясно, где допущена ошибка).

Некоторые перестановочные шифры принимают блок фиксированной длины на входе и выдают блок фиксированной длины на выходе. Они полностью определяются списком, сообщающим порядок, в котором символы попадают в выходной блок. Например, шифр на илл. 8.10 можно рассматривать в виде шифра с 64-символьным блоком. Его выход описывается последовательностью чисел 4, 12, 20, 28, 36, 44, 52, 60, 5, 13, …, 62. То есть четвертая входная буква a первой появится на выходе, за ней последует двенадцатая f и т.д.

8.4.5. Одноразовые блокноты

Разработать шифр, который невозможно взломать, на самом деле довольно легко. Метод его создания известен на протяжении уже нескольких десятилетий. В качестве ключа выбирается произвольная битовая строка, длина которой совпадает с длиной исходного текста. Открытый текст также преобразуется в последовательность двоичных разрядов, например, с помощью стандартной кодировки ASCII. Наконец, две эти строки поразрядно складываются по модулю 2 (операция XOR). Полученный в итоге зашифрованный текст невозможно взломать, поскольку в достаточно большом отрывке любая буква, биграмма или триграмма будет равновероятной. Этот метод называется одноразовым блокнотом (one-time pad) и теоретически является панацеей от любых атак (как существующих сегодня, так и будущих), независимо от вычислительных мощностей, которыми обладает взломщик. Объясняется это теорией информации: дело в том, что в зашифрованном сообщении не содержится никаких сведений для взломщика, поскольку любой открытый текст нужной длины является равновероятным кандидатом.

Пример практического использования одноразового блокнота показан на илл. 8.11. Для начала фраза «I love you» («Я люблю тебя») преобразуется в 7-битный ASCII-код. Затем составляется некий одноразовый блокнот 1, который складывается по модулю 2 с сообщением. В результате получается шифр. Чтобы его разгадать, криптоаналитику придется перебрать все возможные варианты одноразового блокнота, всякий раз проверяя, каким получается открытый текст. Например, если попробовать расшифровать послание с помощью блокнота 2 (см. илл. 8.11), получится текст «Elvis lives» («Элвис жив»). На самом деле для генерации любой последовательности из 11 символов в кодировке ASCII найдется одноразовый блокнот. Именно это мы имеем в виду, говоря, что в зашифрованном тексте не содержится никаких сведений: из него можно извлечь любое сообщение подходящей длины.

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

Сообщение 1: 1001001 0100000 1101100 1101111 1110110 1100101 0100000 1111001 1101111 1110101 0101110

Блокнот 1: 1010010 1001011 1110010 1010101 1010010 1100011 0001011 0101010 1010111 1100110 0101011

Зашифрованный текст: 0011011 1101011 0011110 0111010 0100100 0000110 0101011 1010011 0111000 0010011 0000101

Блокнот 2: 1011110 0000111 1101000 1010011 1010111 0100110 1000111 0111010 1001110 1110110 1110110

Открытый текст 2: 1000101 1101100 1110110 1101001 1110011 0100000 1101100 1101001 1110110 1100101 1110011

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

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

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

Интересно, что решение проблемы передачи по сети одноразового блокнота пришло из совершенно неожиданного источника — квантовой механики. Эта область все еще является экспериментальной, но при этом многообещающей. Если получится усовершенствовать данный метод, все задачи криптографии можно будет решать с помощью одноразовых блокнотов, ведь это самый надежный способ защиты информации. Ниже мы вкратце опишем суть технологии, называемой квантовой криптографией. В частности, мы рассмотрим протокол BB84, названный так в честь его создателей и года, в котором его описание было впервые опубликовано в работе Беннета и Брассара (Bennet and Brassard, 1984).

Допустим, пользователь Алиса хочет передать одноразовый блокнот другому пользователю, Бобу. Алиса и Боб называются принципалами (principals), это главные герои в нашей истории. К примеру, Боб может быть банкиром, с которым хочет сотрудничать Алиса. Имена «Алиса» и «Боб» традиционно используются для обозначения принципалов практически во всех материалах, касающихся криптографии, с тех пор как Рон Ривест (Ron Rivest) использовал их впервые много лет назад (Ривест и др.; Rivest et al., 1978). Криптографы вообще обожают разного рода традиции. Если бы мы описали взаимоотношения Алекса и Барбары, нам бы никто не поверил (и стало бы понятно, что автор на самом деле далек от криптографии). А так, может быть, поверят. Поэтому пусть Алиса и Боб будут героями нашей книги.

Итак, если Алисе и Бобу удастся принять некоторый единый одноразовый блокнот, их переговоры будут полностью конфиденциальными. При этом возникает очевидный вопрос: как им обменяться секретным ключом, не используя физические носители (DVD-диск или USB-накопитель)? Мы можем предположить, что пользователи находятся на разных концах одного оптоволоконного кабеля, по которому они могут передавать и принимать световые импульсы. Бесстрашная шпионка Труди установила на пути этого кабеля активное подслушивающее устройство. Она может считывать сигналы, идущие в обоих направлениях. К тому же она может передавать в обе стороны фальшивые сообщения. Ситуация для Алисы и Боба, казалось бы, безнадежная, но на помощь приходит квантовая криптография.

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

Чтобы сгенерировать одноразовый блокнот, Алисе понадобятся два набора поляризационных фильтров. Первый набор состоит из вертикального и горизонтального фильтров и называется прямолинейным базисом (rectilinear basis). Базис — это просто система координат. Второй набор отличается от первого только тем, что он повернут на 45 градусов; то есть один фильтр можно представить в виде линии, идущей из нижнего левого угла в верхний правый, а другой — в виде линии из верхнего левого в нижний правый угол. Это диагональный базис (diagonal basis). Итак, у Алисы есть два набора фильтров, и она может поставить любой из них на пути светового луча. На самом деле у нее не четыре отдельных фильтра, а кристалл, поляризация которого может на огромной скорости переключаться в одну из четырех позиций с помощью электричества. У Боба имеется такое же устройство. Тот факт, что у Алисы и Боба есть по два базиса, играет важную роль в квантовой криптографии.

В каждом базисе Алиса обозначает одно из направлений нулем, а другое единицей. В нашем примере вертикальному направлению она присвоила значение 0, а горизонтальному — 1. Затем, независимо от этого, для направления «нижний левый — верхний правый» Алиса выбрала значение 0, а для направления «верхний левый — нижний правый» — 1. Она отправляет эти варианты Бобу в виде открытого текста, прекрасно понимая, что ее сообщение может прочитать злоумышленник.

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

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

Илл. 8.12. Пример квантовой криптографии

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

Но погодите, мы же забыли про Труди! Предположим, что ей очень хочется узнать, о чем говорит Алиса, поэтому она внедряет в линию связи свой детектор и передатчик. К несчастью для Труди, она тоже не знает, через какой базис пропускать каждый фотон. Лучшее, что она может сделать, — это выбрать базисы случайным образом, как Боб (илл. 8.12 (е)). Когда Боб открытым текстом сообщает Алисе, какие базисы он использовал, а та отвечает ему, какие из них верны, Труди, как и Боб, узнает, какие биты она угадала, а какие — нет. Как видно из рисунка, базисы Труди совпали с базисами Алисы в позициях 0, 1, 2, 3, 4, 6, 8, 12 и 13. Однако из ответа Алисы (илл. 8.12(г)) ей становится известно, что в одноразовый блокнот входят только биты 1, 3, 7, 8, 10, 11, 12 и 14. Четыре из них (1, 3, 8 и 12) были угаданы правильно, Труди их запоминает. Остальные биты (7, 10, 11 и 14) не были угаданы, и их значения остаются для Труди неизвестными. Таким образом, Бобу известен одноразовый блокнот, начинающийся с последовательности 01011001 (илл. 8.12 (д)), а все, что досталось Труди, — это обрывок 01?1??0? (илл. 8.12 (ж)).

Конечно, Алиса и Боб осознают, что Труди пытается захватить часть их одноразового блокнота, поэтому они стараются уменьшить количество информации, которая может ей достаться. Для этого они могут внести дополнительные изменения. Например, одноразовый блокнот можно поделить на блоки по 1024 бита и возвести каждый из блоков в квадрат, получая, таким образом, числа длиной 2048 бит. Затем можно использовать конкатенацию 2048-битных чисел в качестве одноразового блокнота. Имея лишь часть битовой строки, Труди никогда не сможет проделать эти преобразования. Действия над исходным одноразовым блокнотом, уменьшающие долю информации, получаемой Труди, называются усилением секретности (privacy amplification). На практике вместо поблочного возведения в квадрат применяются сложные преобразования, в которых каждый выходной бит зависит от каждого входного.

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

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

Хотя применение квантовой криптографии было продемонстрировано на примере 60-километрового оптоволокна, для этого требуется сложное и дорогое оборудование. В то же время сама идея выглядит многообещающе, особенно если решить проблемы с масштабированием и уровнем необходимых затрат. Чтобы узнать больше о квантовой криптографии, см. работу Клэнси и др. (Clancy et al., 2019).