Читать «Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография» онлайн - страница 63

Простые числа и их значение в криптографии

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

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

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

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

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

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

20 = 2²∙5

63 = З² ∙7

1050 = 2∙3∙5²∙7.

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

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

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

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

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

Простые числа Ферма — это простые числа вида F_n = 2²ⁿ + 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, таких что: