Это база: Зачем нужна математика в повседневной жизни - Йэн Стюарт

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

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

Как сказал Бенджамин Франклин, «трое могут сохранить секрет, если двое из них мертвы». В симметричном шифре ключ должны знать как минимум двое, что, по мнению Франклина, слишком много. В 1944 или 1945 году кто-то (возможно, Клод Шеннон, изобретатель теории информации) в исследовательском центре Bell Labs в США предложил защищать голосовую связь от подслушивания при помощи добавления к сигналу случайного шума, а затем, после получения сигнала, его вычитания. Это тоже симметричный метод, поскольку ключ здесь – случайный шум и вычитание компенсирует его добавление. В 1970 году Джеймс Эллис, инженер Центра правительственной связи Великобритании, бывшей Правительственной школы кодирования и шифрования, заинтересовался, нельзя ли генерировать шум математически. Если да, то в принципе можно создать систему, где это будет результатом не простого добавления сигналов, а математического процесса, который очень трудно обратить, даже если знать, что он собой представляет. Конечно, получатель должен иметь возможность обратить процесс, но этого можно добиться с помощью второго ключа, известного только получателю.

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

И тут на сцену выходит Клиффорд Кокс, британский математик, также работавший в Центре правительственной связи. В сентябре 1973 года Кокса неожиданно осенила блестящая идея. Он понял, что мечту Эллиса можно реализовать, создав функцию с потайным входом при помощи простых чисел. С точки зрения математики перемножить два или более простых числа легко. Можно, например, вручную перемножить два 50-значных простых числа, получив при этом 99– или 100-значный результат. Обратная операция – взять 100-значное число и найти его простые делители – намного труднее. Стандартный школьный метод «пробовать все возможные делители по очереди» здесь бесполезен: возможностей слишком много. Кокс придумал функцию, основанную на произведении двух больших простых чисел, то есть на результате их перемножения. Получившийся шифр настолько надежен, что это произведение (но не его простые сомножители) можно не держать в секрете. Для расшифровки необходимо знать эти два простых числа по отдельности, в них и кроется секретный второй ключ. Без этих чисел вы ничего не сможете сделать, знания только их произведения недостаточно. Допустим, я говорю вам, что нашел два простых числа, произведение которых равно

1192 344277 257254 936928 421267 205031 305805 339598 743208 059530 638398 522646 841344 407246 985523 336728 666069.

Сможете ли вы найти эти простые числа?{41} По-настоящему быстрый суперкомпьютер сможет это сделать, а вот ноутбук вряд ли. А если взять побольше знаков, то и суперкомпьютер выйдет из игры.

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

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

Однако в 1977 году появился точно такой же метод, который независимо придумали и быстро опубликовали три американских математика: Рональд Ривест, Ади Шамир и Леонард Адлеман. Теперь в их честь эта система называется криптосистемой Ривеста – Шамира – Адлемана (RSA). В конце концов, в 1997 году британские службы безопасности рассекретили работу Кокса, и мы теперь знаем, что именно он первым додумался до этого.

* * *

Теория чисел появляется в криптографии сразу же, как только мы понимаем, что любое сообщение может быть представлено числом. Для шифра Цезаря это число есть положение буквы в алфавите, которое математики предпочитают обозначать числами от 0 до 25 (речь, конечно, идет о латинском алфавите), а не от 1 до 26, из соображений алгебраического удобства. Таким образом, A – это 0, B – это 1 и т. д., вплоть до Z = 25. Числа за пределами этого диапазона могут быть приведены к числам внутри него посредством прибавления или вычитания чисел, кратных 26. Это соглашение закольцовывает все 26 букв алфавита, так что после Z мы вновь возвращаемся к A.