Жуан Гомес - Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография

• Название: Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография
• Автор: Жуан Гомес
• Издательство: ООО «Де Агостини»
• Жанр: Математика
• Год: 2014
• ISBN: 978-5-9774-0682-6; 978-5-9774-0639-0 (т. 2)

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

Эволюционируя вместе с развитием высоких технологий, ремесло шифрования достигло в XXI веке самой дальней границы современной науки — квантовой механики. И хотя объектом кодирования обычно является текст, инструментом работы кодировщиков была и остается математика.

Эта книга — попытка рассказать читателю историю шифрования через призму развития математической мысли.

---

4. Получатель теперь использует свой закрытый ключ, чтобы расшифровать шифр шага 1.

Хеш-функции

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

Небольшие различия в содержании сообщения приводят к совершенно разным хеш-кодам. Таким образом, получатель может быть уверен, что текст не был изменен.

Сертификаты открытых ключей

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

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

* * *

ЦИФРОВАЯ СТЕГАНОГРАФИЯ

Хотя это может показаться парадоксальным, развитие новых технологий привело к возрождению стеганографии. Обычный аудио-файл состоит из 16-битовых значений, воспроизводимых с частотой в 44,1 кГц. Очень просто использовать некоторые из этих битов для передачи секретных данных, так что слушатель вообще не заметит никакой акустической разницы. Файлы изображений также можно использовать для передачи скрытой информации.

Безопасно ли делать покупки через интернет?

Большинство интернет-шпионов и хакеров мало интересуются сообщениями, которыми обмениваются обычные люди, за одним исключением: если сообщения содержат номера кредитных карт. Но существует криптографическая система, которая защищает передачу такой важной информации, известная как TLS (Transport Layer Security — безопасность транспортного уровня). Она была разработана в 1994 г. корпорацией Netscape, занимающейся программным обеспечением для интернета, и была принята в качестве глобального стандарта два года спустя.

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

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

Глава 6. Квантовое будущее

По словам Филиппа Циммермана (см. «Безопасность для всех» на стр. 108), в «Книге кодов» Саймона Сингха говорится: «Современная криптография дает возможность создать такой шифр, который неуязвим ни для каких существующих форм криптоанализа». Как мы уже отмечали, даже самым быстрым компьютерам не под силу взломать методом перебора всех возможных вариантов такие алгоритмы шифрования, как RSA или DES, и даже такие системы, как, например, PGP. Может, какие-то математические лазейки позволят злоумышленникам упростить криптоанализ? Хотя исключить это предположение нельзя, считается, что такое маловероятно.

Прав ли Циммерман? Разрешился ли длившийся тысячелетиями конфликт между криптографами и криптоаналитиками?

Квантовые вычисления

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

Эта новая техническая революция основана на квантовой механике — теоретической науке, построенной в начале прошлого века такими учеными, как датчанин Нильс Бор (1885–1962), англичанин Поль Дирак (1902–1984), немцы Макс Планк (1858–1947), Вернер Гейзенберг (1901–1976), Эрвин Шрёдингер (1887–1961), и многими другими. Устройство Вселенной, постулируемое квантовой механикой, настолько парадоксально, что Альберт Эйнштейн, критикуя эту теорию, как-то воскликнул: «Бог не играет в кости». Несмотря на сомнения Эйнштейна, теория квантовой механики была много раз успешно протестирована, и ее правильность в настоящее время не вызывает сомнений. Большинство ученых считает, что на макроскопическом уровне — то есть на уровне звезд, домов и молекул — Вселенная подчиняется законам классической физики. Однако в квантовом мире — на уровне элементарных частиц, таких как кварки, фотоны, электроны и т. д. — действуют совсем другие законы, приводящие к поразительным парадоксам. Без этой теории не существовало бы ни ядерных реакторов, ни лазерных считывающих устройств. Не было бы никакого способа объяснить свечение солнца или работу ДНК.

Нильс Бор (слева) и Макс Планк, основатели квантовой физики, на фотографии, сделанной в 1930 г.

Кот, ни живой ни мертвый

На семинаре по квантовой физике, состоявшемся в 1958 г., Бор так ответил одному из выступающих: «Мы все согласны с тем, что эта теория является бредовой. Вопрос, который нас разделяет, состоит в том, является ли она бредовой настолько, чтобы иметь шанс оказаться правильной». Насколько, на самом деле, бредова квантовая механика? Возьмем, например, принцип суперпозиции состояний. Частица находится в суперпозиции состояний, если в один и тот же момент она находится в двух различных положениях или когда она одновременно имеет различное количество энергии. Однако когда наблюдатель производит измерения, частица всегда выбирает одно состояние или обладает определенным количеством энергии. Шрёдингер предложил мысленный эксперимент, известный как «кот Шрёдингера», чтобы проиллюстрировать этот очевидно парадоксальный принцип. Пусть в закрытом непроницаемом ящике находится кот. Внутри ящика имеется колба с ядовитым газом, связанная специальным устройством с радиоактивной частицей, так что если частица распадается, газ выходит из колбы и кот умирает. Вероятность того, что эта частица распадется в течение определенного периода времени, составляет 50 %. Эксперимент с такими параметрами зависит от поведения частицы и подчиняется законам квантовой физики.

«Кот Шрёдингера» — мысленный эксперимент, иллюстрирующий один из принципов квантовой теории, а именно принцип суперпозиции состояний.

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