Текст книги "Математики, шпионы и хакеры. Кодирование и криптография"

Автор книги: Жуан Гомес

сообщить о нарушении

Текущая страница: 6 (всего у книги 8 страниц)

Глава 5. Общедоступная тайна: криптография с открытым ключом

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

Первый шифр, предназначенный для того, чтобы воспользоваться потенциалом компьютеров, был разработан в 1970-х гг. Например, «Люцифер», шифр, который разделял текст на блоки по 64 бита и зашифровывал некоторые из них с помощью сложной подстановки, а затем группировал их снова в новый блок зашифрованных битов и повторял процесс. Для работы такой системы было необходимо, чтобы отправитель и получатель имели компьютеры с одной и той же программой шифрования, а также общий цифровой ключ. 56-битная версия шифра «Люцифер», названная DES, была разработана в 1976 г. DES (Data Encryption Standard – «стандарт шифрования данных») по-прежнему используется в наши дни, хотя этот шифр был взломан в 1999 г. и заменен 128-битным AES (Advanced Encryption Standard) в 2002 г.

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

Проблема распределения ключей

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

Алгоритм Диффи – Хеллмана

Сама концепция безопасного обмена ключами может показаться противоречивой: как вы можете послать ключ в виде сообщения, которое уже как-то зашифровано?

Ключом, переданным заранее обычным способом? Однако, если ключами действительно несколько раз обменивались, то решение проблемы можно себе представить – по крайней мере, на теоретическом уровне.

Предположим, что отправитель по имени Джеймс шифрует сообщение с помощью своего ключа и посылает результат получателю по имени Питер, который повторно шифрует зашифрованное послание своим ключом и возвращает его отправителю. Джеймс расшифровывает сообщение своим ключом и посылает назад результат, т. е. текст, в данный момент зашифрованный только ключом Питера, который его расшифровывает. Казалось бы, вековая проблема безопасного обмена ключами решена! Неужели это правда? К сожалению, нет. В любом сложном алгоритме шифрования порядок применения ключей имеет решающее значение, а в нашем примере мы видим, что Джеймс расшифровывает сообщение, которое уже зашифровано другим ключом. Когда порядок ключей меняется, результат будет абракадаброй. Вышеизложенный пример не объясняет теории подробно, но он дает подсказку к решению проблемы. В 1976 г. два молодых американских ученых, Уитфилд Диффи и Мартин Хеллман, нашли способ, при котором два человека могут обмениваться зашифрованными сообщениями без всякого обмена секретными ключами. Этот метод использует модульную арифметику, а также свойства простых чисел. Идея заключается в следующем.

* * *

АВТОРЫ АЛГОРИТМА

Уитфилд Диффи родился в 1944 г. в Соединенных Штатах. Получив степень бакалавра математики в Массачусетском технологическом институте (МП), он с 2002 по 2009 гг. работал главой службы безопасности и вице-президентом компании Sun Microsystems (в Калифорнии).

Инженер Мартин Хеллман родился в 1945 г. и работал в IBM и Массачусетском технологическом институте, где сотрудничал с Диффи.

Уитфилд Диффи

* * *

1. Джеймс выбирает число, которое он держит в секрете. Мы обозначим это число N_j1

2. Питер выбирает другое случайное число, которое он тоже держит в секрете. Мы обозначим это число N_p1

3. Затем и Джеймс, и Питер применяют к своим числам функцию вида f(x) = а^х (mod р) где р – простое число, известное им обоим.

∙ После этой операции Джеймс получает новое число, N_j2, которое он посылает Питеру.

∙ А Питер посылает Джеймсу свое новое число N_p2

4. Джеймс вычисляет N^Nj1_p2 (mod р) и получает новое число С_j.

5. Питер вычисляет N^Np1_j2 (mod р) и получает новое число С_р.

Хотя это кажется невозможным, но числа С_j и С_р являются одинаковыми. И теперь у нас есть ключ. Заметим, что Джеймс и Питер обменивались информацией только тогда, когда они выбрали функцию f(x) = а^х (mod р) и послали друг другу числа N_j2 и N_p2. Ни то, ни другое не является ключом, поэтому перехват этой информации не будет угрожать безопасности системы шифрования. Ключ этой системы имеет следующий вид:

a^Nj1∙Np1  (mod p).

Важно также учесть, что данная функция имеет одну особенность: она необратима, то есть зная саму функцию и результат ее применения к переменной х, невозможно (или, по крайней мере, очень сложно) найти исходное значение х.

Далее, чтобы пояснить идею, мы повторим процесс с конкретными значениями.

Возьмем следующую функцию:

f(x) = 7^х (mod 11).

1. Джеймс выбирает число, N_J1 например, 3, и подставляет в функцию f(3) = 7³   2 (mod 11).

2. Питер выбирает число, N_p1 например, 6, и подставляет в функцию f(6) = 7⁶  4 (mod 11).

3. Джеймс посылает Питеру свой результат, 2, а Питер Джеймсу – свой, 4.

4. Джеймс считает 4³  9 (mod 11).

5. Питер считает 2⁶  9 (mod 11).

Это число, 9, и будет ключом системы.

Джеймс и Питер обменялись функцией f(х) и числами 2 и 4. Будет ли эта информация полезна злоумышленнику? Допустим, злоумышленник знает и функцию, и числа. Тогда он должен найти N_j1 и N_p1 по модулю 11, где N_j1и N_p1 – такие числа, которые и Джеймс, и Питер держат в секрете даже друг от друга. Если шпиону удастся узнать эти числа, он получит ключ, лишь вычислив a^Nj1∙Np1  по модулю р. Решение уравнения вида у = а^х, кстати, в математике называется дискретным логарифмом.

Например, в случае:

f(х) = 3^х (mod 17),

зная, что 3^х = 15 (mod 17), и пробуя различные значения х, мы получим, что х = 6.

Алгоритмы этого типа и задачи с дискретным логарифмом не получали должного внимания вплоть до начала 1990 гг., и лишь в последнее время эти методы начали разрабатываться. В приведенном выше примере число 6 является дискретным логарифмом числа 15 с основанием 3 по модулю 17.

Особенностью этого типа уравнений, как мы уже говорили, является сложность обратного процесса – они асимметричны. Если р больше 300, а число а больше 100, решение – и, следовательно, взлом ключа – становится крайне сложной задачей.

* * *

ВИРУСЫ И БЭКДОРЫ

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

* * *

Этот алгоритм является основой современной криптографии. Диффи и Хеллман представили свою идею на Национальной компьютерной конференции, на семинаре, который можно назвать поворотным. В полном объеме их работу можно почитать на www.cs.berkeley.edu/~christos/classics/diffiehellman.pdf, статья с названием «Новые направления в криптографии».

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

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

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

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

Простые числа спешат на помощь: алгоритм шифрования RSA

В августе 1977 г. знаменитый американский писатель и популяризатор науки Мартин Гарднер озаглавил свою колонку по занимательной математике в журнале Scientific American так: «Новый вид шифра, на расшифровку которого потребуются миллионы лет». После объяснения принципа системы шифрования с открытым ключом он показал само зашифрованное сообщение и открытый ключ N, используемый в этом шифре:

Гарднер призвал читателей попробовать расшифровать сообщение, используя предоставленную информацию, и даже дал подсказку: для решения необходимо разложить число N на простые множители р и q. Более того, Гарднер назначил приз в размере $100 (приличная сумма на тот момент) тому, кто первым получит правильный ответ. Каждый, кто захочет побольше узнать о шифре, писал Гарднер, может обратиться к создателям шифра – Рону Ривесту, Ади Шамиру и Лену Адлеману из Лаборатории информации Массачусетского технологического института.

Правильный ответ был получен лишь через 17 лет. Он стал результатом сотрудничества более чем 600 человек. Ключами оказались р = 32769132993266 709549961988190834461413177642967992942539798288533 и q = 3490529510847650949147849619903898133417764638493387843990820577, а зашифрованная фраза звучала так: «Волшебные слова – это брезгливый ягнятник».

Алгоритм, представленный Гарднером, известен как RSA – буквенная аббревиатура от фамилий Rivest (Ривест), Shamir (Шамир) и Adleman (Адлеман). Это первое практическое применение придуманной Диффи системы шифрования с открытым ключом, которая повсеместно используется и по сей день. Надежность ее практически гарантирована, потому что процесс расшифровки является невероятно сложным, почти невозможным делом. Далее мы рассмотрим основы этой системы в упрощенной форме.

Подробнее об алгоритме RSA

Алгоритм RSA основан на некоторых свойствах простых чисел, о которых заинтересованный читатель может подробнее прочитать в Приложении. Мы ограничимся здесь изложением простых фактов, лежащих в основе алгоритма.

• Количество натуральных чисел, меньших n и взаимно простых с n, называется функцией Эйлера и обозначается как ф(n).

• Если n = p∙q, где р и q – простые числа, то ф(n) = (р – 1)(q – 1).

• Из малой теоремы Ферма мы знаем, что если а – целое число, большее нуля, и р – простое число, то а^р-1

 1 (mod р).

• Согласно теореме Эйлера, если НОД (n, а) = 1, то а^ф(n)

 1 (mod n).

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

Сначала Джеймс вычисляет значение n путем умножения двух простых чисел р и q (n = pq) и выбирает значение е так, чтобы НОД (ф(n), е) = 1. Напомним, что ф(n) = (р — 1)(q — 1). Данные, которые являются открытыми, – это значение n и значение е (ни при каких обстоятельствах нельзя выдавать значения р и q). Пара (n, е) является открытым ключом системы, а значения р и q называются RSА-числами. Затем Джеймс вычисляет единственное значение d по модулю ф(n), которое удовлетворяет условию d∙е = 1, то естьd является обратным элементом к числу е по модулю ф(n). Мы знаем, что обратный элемент существует, потому что НОД (ф(n), е) = 1. Это число d является закрытым ключом системы. Со своей стороны, Питер использует открытый ключ (n, е) для шифрования сообщения М с помощью функции М = m^e (mod n). Получив сообщение, Джеймс вычисляет M^d = (m^e)^d (mod n), а это выражение эквивалентно M^d = (m^e)^d = m (mod n), что свидетельствует о возможности расшифровать сообщение.

Теперь мы применим эту процедуру к конкретным числовым значениям.

Если р = 3 и q = 11, получим n = 33. Тогда ф(33) = (3–1)∙(11—1) = 20.

Джеймс выбирает е, не имеющее общего делителя с 20, например, е = 7. Открытый ключ Джеймса (33,7).

• Джеймс также вычислил закрытый ключ d, который является обратным элементом к числу 7 по модулю 20, а именно число d = 3, так как 7∙3  1 (mod 20).

• Питер, имея открытый ключ, хочет отправить нам сообщение «9». Чтобы зашифровать это сообщение, он использует открытый ключ Джеймса и вычисляет:

9⁷  = 4 782969  15 (mod 33).

Зашифрованное сообщение имеет вид «15». Питер посылает его нам.

Джеймс получает сообщение «15» и расшифровывает его следующим образом:

15³  = 3375  9 (mod 33).

Сообщение расшифровано правильно.

Если мы выбираем большие простые числа р, q, то вычисления в алгоритме RSA становятся такими сложными, что нам придется использовать компьютер. Например, если р = 23 и q = 17, то n = 391. Открытым ключом при выбранном е = 3 будет пара (391,3). Тогда d = 235. Для простого сообщения «34» операция расшифровки будет выглядеть так:

204²³⁵  34 (mod 391).

Обратите внимание на степень числа и представьте себе гигантское количество расчетов, необходимых для нахождения этого решения.

Почему мы можем доверять алгоритму RSA

Потенциальный шпион располагает значениями n и е, потому что они являются открытыми. Чтобы расшифровать сообщение, ему нужно также значение d, т. е. закрытый ключ. Как мы показали в предыдущем примере, значение d получается из n и е. Чем же обусловлена безопасность? Напомним, что для построениям/ необходимо знать ф(n) = (р – 1)(q – 1), в частности, р и q. Для этого «достаточно» разложить n на простые множители р и q. Проблема для шпиона заключается в том, что разложение большого числа на простые множители является медленным и трудоемким процессом. Если n достаточно большое (состоящее более чем из 100 цифр), не существует известных способов нахождения р и q за разумное количество времени. В настоящее время простые числа, используемые для шифрования чрезвычайно конфиденциальных сообщений, состоят более чем из 200 цифр.

Приемлемая конфиденциальность

Алгоритм RSA требует много машинного времени и очень мощных процессоров.

До 1980-х гг. только правительства, армия и крупные предприятия имели достаточно мощные компьютеры для работы с RSA. В результате у них была фактически монополия на эффективное шифрование. Летом 1991 г. Филипп Циммерман, американский физик и борец за сохранение конфиденциальности, предложил бесплатную систему шифрования PGP (Pretty Good Privacy – «достаточно хорошая степень конфиденциальности»), алгоритм которой мог работать на домашних компьютерах.

PGP использует классическое симметричное шифрование, что и обеспечивает ей большую скорость на домашних компьютерах, но она шифрует ключи по асимметричному алгоритму RSA.

Циммерман объяснил причины этой меры в открытом письме, которое заслуживает быть процитированным здесь, по крайней мере, частично из-за пророческого описания того, как мы живем, работаем и общаемся два десятилетия спустя.

«Это личное. Это конфиденциальное. И это только ваше дело и ничье другое.

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

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

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

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

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

PGP с момента его создания становится все более популярным и представляет собой наиболее важный инструмент шифрования, доступный сегодня частным лицам.

* * *

БЕЗОПАСНОСТЬ ДЛЯ ВСЕХ

Филипп Циммерман, родившийся в 1954 г., американский физик и инженер-программист, стоявший у истоков движения, которое стремится сделать современную криптографию доступной для всех. Кроме разработки системы PGP он в 2006 г. создал Zfone – программу для безопасной голосовой связи через Интернет. Он является президентом альянса OpenPGP, выступающего за открытое программное обеспечение.

Проверка подлинности сообщений и ключей

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

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

Диффи и Хеллман сами предложили гениальный способ использования шифрования с открытым ключом для проверки подлинности сообщения. В криптографических системах такого типа отправитель шифрует сообщение с помощью открытого ключа получателя, который в свою очередь использует свой закрытый ключ для расшифровки сообщения. Диффи и Хеллман заметили, что RSA и другие подобные алгоритмы обладают интересной симметрией. Закрытый ключ также можно использовать для шифрования сообщения, а открытый – для расшифровки. Этот подход не усиливает безопасность – ведь открытый ключ доступен для всех – зато получатель может убедиться, что сообщение пришло от определенного отправителя, владельца закрытого ключа. Чтобы проверить подлинность отправителя сообщения, теоретически достаточно добавить к нормальному шифрованию дополнительные шаги.

1. Отправитель шифрует сообщение с помощью открытого ключа получателя. Этот первый шаг гарантирует конфиденциальность.

2. Отправитель снова шифрует сообщение, на этот раз с помощью своего закрытого ключа. Таким образом удостоверяется подлинность сообщения, оно «подписано».

3. Получатель использует открытый ключ отправителя, чтобы расшифровать шифр шага 2. Таким образом проверяется подлинность сообщения.

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

Хеш-функции

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

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

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

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

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

* * *

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

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

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

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

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

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