Корпорация «Попс»
Шрифт:
Моя бабушка улыбается.
— Не спрашивай его. Мы тут всю ночь проторчим.
Мы дружно хохочем. Да уж, это правда.
И все же, чтобы Джасмин было понятно, он быстро объясняет, как составить шифровальный алфавит на основе слова «лапсанг» (только, разумеется, без второй буквы «а»), добавив к нему все остальные буквы алфавита в обратном порядке. Он пишет на клочке бумаге что-то вроде этого:
Если и отправитель, и адресат знают, что слово-ключ — лапсанг,любое послание будет легко расшифровать (впрочем, дедушка не объясняет, что любое послание, так зашифрованное, с легкостью расшифровывается частотным анализом).
— И вот вдруг, скажем, наш ключ попал в руки врага, — продолжает он. — Нам потребуется его изменить. Но как мне, отправителю, сообщить новый ключ тебе, адресату? Что, если, дабы не компрометировать ключ, мы решим менять его каждый день? Нам все равно придется сообщать его друг другу. Я мог бы позвонить тебе по телефону и сказать: «Теперь ключ — слово дарджилинг», но телефон могут прослушивать. Будь мы уверены, что он не прослушивается, могли бы обмениваться секретной информацией по нему, и не надо никаких шифров.
— Понимаю, — кивает Джасмин. — Чтобы отправить тайное послание, зашифрованное с помощью ключа, надо сперва передать адресату не-тайное послание, сообщающее, каков теперь ключ.
— Именно, — говорит дедушка. — И это — ахиллесова пята, точка, в которой враг может перехватить информацию.
— А что, если каждый день посылать шифровку, а потом тем же шифром сообщать новый ключ?
Дедушка переносит чайник на стол и достает из буфета лучшие кофейные чашки.
— Люди пользовались подобными методами, — объясняет он. — Но понимаешь, стоит в такой ситуации врагу расшифровать одно послание, и получается бесконечное кольцо. Взломав лишь один код, они смогут раз за разом взламывать их дальше.
— Ах, — сокрушается Джасмин. — Ну, и как же тогда быть? Я знаю, об этом ты и хочешь мне…
— Ну, есть пара способов. Первый, известный как «система обмена ключами Диффи — Хеллмана — Меркла» — его так назвали в честь изобретателей, [101] — основан на невозвратных функциях и модульной арифметике, о которых Бет знает побольше моего.
101
Бейли Уитфилд «Уит» Диффи (р. 1944), Мартин Эдвард Хеллман (р. 1945) и Ральф Меркл (р. 1952) — американские криптографы, пионеры шифрования с открытым ключом; криптографический протокол Диффи — Хеллмана (впоследствии названный протоколом Диффи — Хеллмана — Меркла) был впервые опубликован в 1976 г., хотя впоследствии выяснилось, что несколькими годами раньше его изобрел Малколм Дж. Уильямсон из британского Центра правительственной связи, однако эта работа много лет хранилась в секрете.
Бабушка улыбается:
— Поверь мне, Джасмин, тебе этого знать не надо. Но по сути, это сложный математический трюк: два человека задумывают числа, прогоняют их через функцию — гораздо сложнее, чем «возьмите число, удвойте и прибавьте пять», хотя и похожую, — а потом обмениваются результатами. Замечателен этот метод тем, что даже если оба результата будут перехвачены, враг не сможет взломать код, так как для этого нужно знать не результат, а хотя бы одно из первоначальных чисел. Объяснить это очень сложно, но трюк и впрямь жутко хитрый. Широкого применения он не получил, ибо оказался непрактичным. Отправителю приходится каждый раз загодя связываться с адресатом, если нужно отправить шифровку. Но по крайней мере с математической точки зрения это шедевр. Представь: можно обмениваться ключами не тайно, а на виду у всех; даже если враг подслушает ваши слова — все равно. Полный блеск.
Дедушка прихлебывает кофе.
— На самом деле людям был нужен асимметричный ключ вместо симметричного. Другими словами, система, в которой послание шифруется и дешифруется двумя разными способами. Если бы такая система имелась, ты могла бы послать человеку, пожелавшему связаться с тобой, не ключ, а замок.Лучшая аналогия — реальный висячий замок. Скажем, у меня есть для тебя ящик с тайным содержимым. Я мог бы купить замок и ключ, запереть ящик на замок и придумать, как передать тебе ключ, чтобы его не перехватили. Альтернатива: я мог бы сообщить тебе, что у меня есть для тебя тайный ящик, и тогда тыкупила бы ключ с замком и послала мне один лишь замок. И неважно, кто перехватил бы замок — все равно он ничего не смог бы с ним сделать. Получив замок, я просто намертво привариваю его к ящику и посылаю ящик тебе. После этого даже я не смогу открыть ящик — потому что ключ от замка только у тебя.
— Очень умно, — кивает Джасмин. — Мне нравится.
— А вдруг кто-нибудь взломает замок? — говорю я. — Если его кто-нибудь перехватит, уж конечно он сможет подобрать ключ?
— Ну, тут-то собака и зарыта. Ключ и замок — это просто аналогия для… прошу прощения, для математических трюков еще мудренее. Фактически, концепцию асимметричных шифров придумали за много лет до того, как был создан нужный математический аппарат. Очень долго никто не мог измыслить функцию, которая давала бы искомый эффект. Но потом три бравых парня из Массачусетского технологического института ее нашли. Допустим, Алиса, я скажу тебе, что ключ в этой истории — это два очень больших простых числа. Каков тогда замок?
На миг задумываюсь.
— Не знаю.
— Ну, что получится, если перемножить два очень больших простых числа?
— Очень большое составное число, — отвечаю я. — С двумя очень большими простыми делителями… О! Поняла.
Ну конечно же. Если выберешь два достаточно больших простых числа и, храня их в секрете, перемножишь, то человеку, который решит факторизовать произведение, придется начать с 2, 3, 5, 7 — по-тупому, как всегда делается. Он не будет знать даже примерно, чему равны простые делители, а мне очень даже хорошо известно, что к факторизации нужно подходить методически. Бабушка однажды доказала мне, что на факторизацию достаточно большого числа N(где N— произведение двух больших простых чисел ри q) могут уйти тысячи лет, даже если проверять один простой множитель в секунду. Разумеется, это великолепный метод шифровки. Посылаешь человеку, который хочет с тобой связаться, большое составное число, он использует его для шифровки так, что тебе для декодирования нужны простые множители, и… дело в шляпе! Только ты сможешь прочитать послание. Ты можешь сказать всем на свете, чему равно N,но только ты будешь знать, чему равны ри q.
Следующие полчаса или около того мы наперебой объясняем Джасмин простые числа и факторизацию. Я присоединяюсь к лекции наравне со взрослыми, поскольку разложила для дедушки на простые множители тьму-тьмущую чисел. Наконец до Джасмин доходит.
— Но уж компьютеры-то наверняка с этим в считаные секунды справляются? — говорит она.
Бабушка качает головой:
— Если число Nдостаточно велико, можно заставить десять миллиардов компьютеров одновременно проверять по тысяче простых чисел в секунду, и все равно у них уйдет миллиард лет на то, чтобы получить ответ. Это при том, что любой из них получил бы Nиз ри qза одно мгновение.
— Поразительно, — говорит Джасмин.
— Мартин Гарднер, славный малый, который ведет колонку математических игр в журнале «Сайентифик Америкэн»… — начинает дедушка.
— Это вроде американской версии «Мозговой Мясорубки», — поясняет бабушка.
Дедушка продолжает:
— Да, так вот, еще в 1977 году он предложил людям взломать код с открытым ключом, который был длиной аж 129 цифр. Не забывайте: хотя в основе шифра и лежит большое число N, дело не только в нем. Кроме него тут еще используется всякая модульная математика. Однако безопасность этого шифра зависит от невозможности быстро факторизовать N.Таким образом, главная закавыка была в том, чтобы найти простые делители этого большого числа.