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

Однако в 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.

Преимущество модульной арифметики заключается в том, что она придает списку открытых «слов» алгебраическую структуру. Это открывает широкий спектр правил для преобразования открытого текста в зашифрованный и обратно. Кокс, а позже Ривест, Шамир и Адлеман просто выбрали очень умное правило.