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

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, и превратить каждый блок в число, то мы получим шифр подстановки по блокам. Если взять достаточно длинные блоки, то легко различимой закономерности в частоте их встречаемости не будет, так что расшифровать текст путем наблюдения за тем, какие числа встречаются чаще других, не удастся.

* * *

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

an = a (mod n) или, что эквивалентно, an-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 в зашифрованный текст re (mod n). (Правило шифрования также можно раскрыть.)

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

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

r → re,

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

s → sd.

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