Жуан Гомес - Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография

Настоящая математика не оказывает влияния на войну. Никому еще не удалось обнаружить ни одну военную задачу, которой бы служила теория чисел.

Годфри Харолд Харди, «Апология математика» (1940)

Для расшифровки сообщения важно, чтобы шифр был обратим. Как мы уже видели в случае аффинного шифра, это можно гарантировать, лишь используя простое число в качестве модуля. Более того, произведение простых чисел является практически необратимой функцией, то есть после выполнения умножения разложить произведение на исходные множители является очень трудоемкой задачей.

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

Простые числа и «другая» теорема Ферма

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

20 = 2 2∙5

63 = З 2 ∙7

1050 = 2∙3∙5 2∙7.

Все простые числа, кроме числа 2, нечетные. Единственные два последовательных простых числа — это 2 и 3. Нечетные последовательные простые числа — т. е. пары простых чисел, отличающихся на 2 (например, 17 и 19), — называются простыми числами-близнецами . Простые числа Мерсенна и числа Ферма также представляют особый интерес.

Простое число называется числом Мерсенна, если при добавлении единицы получается степень двойки. Например, 7 — число Мерсенна, так как 7 + 1 = 8 = 2 3.

Первые восемь простых чисел Мерсенна выглядят так:

3, 7, 31,127, 8191,131071, 524287, 2147483647.

В настоящее время известно чуть более 40 простых чисел Мерсенна. Самым большим из них является гигантское число: 2 43112609—1, найденное в 2008 г. Для сравнения, примерное число элементарных частиц во Вселенной меньше, чем 2 300.

Простые числа Ферма — это простые числа вида F n= 2 2n+ 1, где n— натуральное число.

В настоящее время известно пять простых чисел Ферма: 3 ( n= 0), 5 ( n= 1), 17 ( n= 2), 257 ( n= 3) и 65537 ( n= 4).

Простые числа Ферма носят имя прославленного французского юриста и математика Пьера де Ферма (1601–1665), который их открыл. Он сделал также другие важные открытия в теории простых чисел. Классической является малая теорема Ферма, которая утверждает: «Если р— простое число, и целое ане делится на р, то а р a (mod р).»

Этот результат имеет большое значение для современной криптографии, как мы сейчас увидим.

От Эйлера к RSA

Еще один важный результат в модульной арифметике известен как соотношение Везу. Это утверждение гласит, что если аи b— целые положительные числа, тогда уравнение НОД ( a, b) = к эквивалентно существованию двух целых чисел р, q, таких что:

pa+ qb= k.

В частности, если НОД ( a, b) = 1, это соотношение гарантирует существование целых чисел ри q, таких что

pa+ qb= 1.

Работая по модулю n, возьмем НОД ( а, n) = 1, тогда обязательно существуют целые числа ри q, такие что pa+ qn= 1. Так как n — модуль, то qn= 0, следовательно, существует такое р, что pa = 1, то есть существует число, обратное числу апо модулю n, а именно р.

Элементы, имеющие обратный элемент по модулю n, являются натуральными числами, которые меньше, чем n, и удовлетворяют условию НОД ( а, n) = 1. Количество таких чисел называется функцией Эйлера и обозначается как ф(n).

Если число n представлено в виде произведения степеней простых чисел следующим образом

Например, если n= 1600 = 2 6∙5 2, то

Более того, в случае, если n— простое число, то для любого значения а выполняется НОД ( а, n) = 1, и, следовательно, любое число абудет иметь обратное по модулю n, значит ф(n)= n— 1.

Итак, подведем итог самым важным фактам.

1. ф(n)называется функцией Эйлера и обозначает количество натуральных чисел, меньших nи взаимно простых с ним.

2. Если n= рq, где ри qпростые числа, то

a(n)= (p— 1)(q— 1).

3. Из малой теоремы Ферма мы знаем, что если а— целое число, большее нуля, и р— простое число, то а р a (mod р),что эквивалентно а р — 1 1 (mod р).

4. Если НОД ( а, n) = 1, тогда имеем а ф(n) 1 (mod n).

Почему работает RSA-алгоритм?

Математические факты, изложенные выше, лежат в основе алгоритма шифрования RSA.

RSA-алгоритм зашифровывает численное представление m некоторого сообщения с помощью двух простых чисел ри q. Возьмем n= pq.Обозначим за елюбое значение, такое что НОД ( е, ф(n)) = 1, и пусть dбудет обратный элемент числа епо модулю ф(n). [Мы знаем, что он существует, так как НОД ( е, ф(n)) = 1]. Тогда:

d∙е= 1 по модулю ф(n).

Зашифрованное послание Мшифруется следующим образом: М= m е(mod n).

Алгоритм подразумевает, что исходное сообщение m может быть получено как m= M d= (m e) d(mod n).Проверка этого уравнения как раз и демонстрирует работу алгоритма RSA. Мы воспользуемся теоремой Ферма и функцией Эйлера.

Рассмотрим два случая.

1. Если ( m, n) = 1, то с функцией Эйлера имеем: m ф(n)1 (mod n).

Начнем с того, что d∙ е= 1по модулю ф(n) эквивалентно соотношению е∙ d— 1= 0 (mod ф(n))то есть существует целое значение k, такое, что е∙ d— 1= k∙ ф(n)или е∙ d= k∙ ф(n)+ 1.Используя это и формулу Эйлера, получим: