Это база: Зачем нужна математика в повседневной жизни

Шифровать сообщение по одной букве, используя для каждой буквы всегда одинаковое численное обозначение, не слишком надежно: каким бы ни было правило, шифр все равно остается шифром подстановки. Но если поделить сообщение на блоки длиной, скажем, букв по 10, а сегодня скорее по 100, и превратить каждый блок в число, то мы получим шифр подстановки по блокам. Если взять достаточно длинные блоки, то легко различимой закономерности в частоте их встречаемости не будет, так что расшифровать текст путем наблюдения за тем, какие числа встречаются чаще других, не удастся.

* * *

Кокс и Ривест – Шамир – Адлеман выводили свои правила из красивой теоремы, открытой Ферма в 1640 году, которая показывает, как ведут себя степени чисел в модулярной арифметике. Говоря современным языком, Ферма рассказал своему другу де Бесси, что если n – простое число, то

aⁿ = a (mod n) или, что эквивалентно, a^n-1 = 1 (mod n)

для любого числа a. «Я продемонстрировал бы тебе это, если бы не боялся, что получится слишком длинно», – писал Ферма. Эйлер получил недостающее доказательство в 1736 году, а в 1763 году он опубликовал более общую теорему, которая применима, если модуль не является простым числом. Теперь a и n не должны иметь общий делитель, а степень n – 1 во втором варианте формулы заменена на функцию Эйлера φ(n). Нам нет нужды знать, что это такое{42}, но необходимо понимать, что если n = pq есть произведение двух простых чисел p и q, то φ(n) = (p – 1)(q – 1).

Криптосистема RSA действует следующим образом:

• Найдите два больших простых числа p и q.

• Вычислите произведение n = pq.

• Вычислите φ(n) = (p – 1)(q – 1). Держите это в секрете.

• Выберите число e, не имеющее общих простых делителей с φ(n).

• Вычислите d так, чтобы de = 1 (mod φ(n)).

• Число e можно раскрыть. (Кстати говоря, это дает очень мало полезной информации о φ(n).)

• Сохраните d в секрете. (Это принципиально важно.)

• Пусть r – текстовое сообщение, зашифрованное как число по модулю n.

• Конвертируйте r в зашифрованный текст r^e (mod n). (Правило шифрования также можно раскрыть.)

• Чтобы расшифровать r^e, следует возвести его в степень d (mod n). (Не забываем, что d секретно.) Это дает (r^e)^d, что равно r^ed, что равно r по теореме Эйлера.

Здесь правило шифрования звучит как «возвести в e-ю степень»:

r → r^e,

а правило расшифровки как «возвести в d-ю степень»:

s → s^d.

Кое-какие математические фокусы, в которые я не буду вдаваться, дают возможность производить все эти действия быстро (на современных компьютерах) при условии, что вам известны p и q по отдельности. Самое неприятное – то, что если они вам неизвестны, то знание n и e не сильно помогает в вычислении d, необходимого для расшифровки сообщения. По существу, вам нужно найти простые делители p и q числа n, что, как мы видели (судя по всему), намного труднее, чем перемножить p и q и найти таким образом n.

Иными словами, «возведение в степень e» и есть требуемая функция с потайным входом.

В настоящее время все вышеописанное может быть проделано за минуту или около того на обычном ноутбуке для, скажем, 100-значных простых чисел p и q. Одна из приятных особенностей системы RSA состоит в том, что по мере того, как компьютеры становятся более мощными, достаточно всего лишь увеличивать p и q. Метод по-прежнему будет работать.

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

Начальник Кокса Ральф Бенджамин, научный руководитель, главный инженер и директор Центра правительственной связи, прекрасно знал свое дело и сразу обратил внимание на эту возможность. Он написал в рапорте: «Я считаю ее очень важной для военного применения. В быстро меняющейся военной ситуации можно встретить непредвиденные угрозы или возможности. Тот, кто может раздавать свой ключ быстро при помощи электронных средств связи, получает серьезное преимущество перед противником». Но компьютеры тех времен не могли выполнить эту задачу, и британское правительство упустило, как позже оказалось, громадные возможности.

* * *