Математики, шпионы и хакеры. Кодирование и криптография
Шрифт:
Теперь мы применим эту процедуру к конкретным числовым значениям.
Если р = 3 и q = 11, получим n = 33. Тогда ф(33) = (3–1)•(11—1) = 20.
Джеймс выбирает е, не имеющее общего делителя с 20, например, е = 7. Открытый ключ Джеймса (33,7).
• Джеймс также вычислил закрытый ключ d, который является обратным элементом к числу 7 по модулю 20, а именно число d = 3, так как 7•3
• Питер, имея открытый ключ, хочет отправить нам сообщение «9». Чтобы зашифровать это сообщение, он использует открытый ключ Джеймса и вычисляет:
97 = 4 782969
Зашифрованное
Джеймс получает сообщение «15» и расшифровывает его следующим образом:
153 = 3375
Сообщение расшифровано правильно.
Если мы выбираем большие простые числа р, q, то вычисления в алгоритме RSA становятся такими сложными, что нам придется использовать компьютер. Например, если р = 23 и q = 17, то n = 391. Открытым ключом при выбранном е = 3 будет пара (391,3). Тогда d = 235. Для простого сообщения «34» операция расшифровки будет выглядеть так:
204235
Обратите внимание на степень числа и представьте себе гигантское количество расчетов, необходимых для нахождения этого решения.
Почему мы можем доверять алгоритму 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 и другие подобные алгоритмы обладают интересной симметрией. Закрытый ключ также можно использовать для шифрования сообщения, а открытый — для расшифровки. Этот подход не усиливает безопасность — ведь открытый ключ доступен для всех — зато получатель может убедиться, что сообщение пришло от определенного отправителя, владельца закрытого ключа. Чтобы проверить подлинность отправителя сообщения, теоретически достаточно добавить к нормальному шифрованию дополнительные шаги.