Как сказал Бенджамин Франклин, «трое могут сохранить секрет, если двое из них мертвы». В симметричном шифре ключ должны знать как минимум двое, что, по мнению Франклина, слишком много. В 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. Тогда шифр Цезаря может быть сведен к простому математическому правилу, более того, к формуле
n → n + 3.
Обратный процесс выглядит очень похоже:
n ← n + 3 или n → n – 3.
Именно это делает данный шифр симметричным.
Мы можем изобретать новые шифры, меняя правила, или формулу. Нам нужен лишь простой способ превращения сообщения в число и две формулы: одна для превращения открытого текста в зашифрованный и вторая для его расшифровки. Каждая из формул должна быть обратной по отношению к другой.
Существует множество способов превращать открытый текст в числа. Простой способ состоит в том, чтобы использовать для каждой буквы числа 0–25 и выстраивать эти числа в ряд, добавляя к числам 0–9 нулик, чтобы получилось 00–09. Тогда JULIUS превратится в 092011082018 (не забывайте, A = 00). Возможно, потребуются дополнительные числа для пробела, знаков пунктуации, ну и т. д. Правило, которое превращает одно число в другое, называется теоретико-числовой функцией.
Замыкание чисел в кольцо – стандартный фокус теории чисел, известный как модулярная арифметика. Выберем число – здесь это 26. Теперь представим, что 26 – это все равно что 0, так что из всех чисел вам потребуются только числа от 0 до 25. В 1801 году Карл Фридрих Гаусс в своей знаменитой книге «Арифметические исследования» (Disquisitiones Arithmeticae) указал, что в такой системе можно складывать, вычитать и умножать числа, руководствуясь обычными законами алгебры и не выходя за пределы выбранного диапазона 0–25. Просто производите обычные вычисления с обычными числами, а затем возьмите остаток от деления результата на 26. Так, 23 × 17 = 391, что равно 15 × 26 + 1. Остаток равен 1, поэтому в этом необычном варианте арифметики 23 × 17 = 1.
Эта идея работает и при замене 26 любым другим числом; число это называют модулем, и мы можем подписать (mod 26), чтобы подчеркнуть происходящее. Таким образом, если быть точными, мы вычислили, что 23 × 17 = 1 (mod 26).
Но как насчет деления? Если мы разделим это равенство на 17 и не будем слишком заморачиваться тем, что все это означает, то получим
23 = 1/17 (mod 26).
Таким образом, разделить на 17 – все равно что умножить на 23. Мы теперь можем придумать новое правило шифрования:
n → 23n (mod 26);
обратной формулой к этому будет
n ← 17n (mod 26).
Это правило сильно перемешивает алфавит и расставляет буквы в следующем порядке:
AXUROLIFCZWTQNKHEBYVSPMJGD.
Это по-прежнему шифр подстановки на уровне отдельных букв, так что его несложно взломать, но он наглядно показывает, что мы можем менять формулу. Кроме того, он иллюстрирует использование модулярной арифметики – а это ключ к обширным областям теории чисел.
Однако деление может оказаться более хитрым делом. Поскольку 2 × 13 = 26 = 0 (mod 26), мы не можем делить на 13, в противном случае мы бы получили, что 2 = 0/13 = 0 (mod 26), что неверно. То же относится и к делению на 2. Общее правило таково, что мы можем делить на любое число, не имеющее общих простых делителей с модулем. Поэтому 0 исключается, но это не удивительно: на 0 нельзя делить и обычные целые числа. Если модулем является простое число, мы можем делить на любое число меньше модуля, за исключением 0.
Преимущество модульной арифметики заключается в том, что она придает списку открытых «слов» алгебраическую структуру. Это открывает широкий спектр правил для преобразования открытого текста в зашифрованный и обратно. Кокс, а позже Ривест, Шамир и Адлеман просто выбрали очень умное правило.
Шифровать сообщение по одной букве, используя для каждой буквы всегда одинаковое численное обозначение, не слишком надежно: каким бы ни было правило, шифр все равно остается шифром подстановки. Но если поделить сообщение на блоки длиной, скажем, букв по 10, а сегодня скорее по 100, и превратить каждый блок в число, то мы получим шифр подстановки по блокам. Если взять достаточно длинные блоки, то легко различимой закономерности в частоте их встречаемости не будет, так что расшифровать текст путем наблюдения за тем, какие числа встречаются чаще других, не удастся.