y = f (x).

Возьмем тот же простой пример, когда буква заменяется следующей по алфавиту. Аналогично Алиса и Боб могут договориться о замене целого числа следующим по порядку: вместо 1 писать 2, вместо 2 – 3 и так далее. Тогда для произвольного числа х наш процесс шифрования будет выглядеть как на рис. 6.1 сверху.

Рис. 6.1. Элементарная шифровка и расшифровка. В данном случае y = f(x) = x + 1

Теперь представим, что Ева умна и хитра и в принципе в состоянии перехватить или вычислить секретный ключ (в данном случае ключ – это договоренность, что Алиса и Боб пишут x + 1 вместо х). Тогда ей ничего не стоит расшифровать сообщение, она должна всего лишь вычесть единицу!

Понятно, что столь элементарный шифр нас не устраивает. Если Алиса хочет защитить свои сообщения от Евы, то в идеале ей нужен такой шифр, который зашифровать было бы просто, а расшифровать трудно. О том, как будет расшифровывать Боб, мы расскажем ниже. Пока, в терминах математики, нам следует найти очень особенное преобразование f, удовлетворяющее вот такому довольно странному условию: если мы знаем х и знаем f, мы легко можем вычислить y = f(x), а вот если мы знаем у и знаем f, то вычислить х все равно очень сложно.

Схематически наше пожелание выглядит как на рис. 6.2. И сразу возникает закономерный вопрос: а существуют ли в природе подобные преобразования?

Рис. 6.2. Шифр y = f (x), который сложно расшифровать, даже зная преобразование f

Если задуматься, станет ясно, что придумать подходящую функцию f и главное доказать, что она обладает нужными свойствами, вовсе не легко! Почему «главное – доказать»? Совсем не потому, что математики так уж любят доказательства. А потому, что тогда мы точно будем знать, что хитроумная Ева не сможет взломать шифр. Против математических доказательств Ева бессильна.

Оказывается, такие преобразования f есть. Более того, можно сделать так, чтобы Боб и Алиса могли расшифровывать сообщения, а Ева – нет! Пока не доказано, что задача расшифровки абсолютно безнадежна. Но известно, что она относится к определенной категории трудных задач, эффективное решение которых еще не найдено. Именно эти шифры используются для обмена секретными ключами, чтобы установить безопасную связь через интернет. Для построения таких шифров требуется глубокая математика. В данном случае – теория чисел.

Как вы уже поняли, шифрование имеет дело с числами и преобразованиями чисел. Этими вопросами в математике занимается теория чисел, один из классических, даже древних разделов математики. Казалось бы, зачем изучать числа? Лучшие математические умы занимались этой наукой, движимые чистым любопытством. Просто потому, что математики любят числа и любят отыскивать их скрытые закономерности. Умственные изощрения математиков с веками усложнялись без какой-либо перспективы для серьезного применения. И вдруг…

И вдруг в XX веке весь мир перешел на цифровые технологии! Наш бизнес, наше информационное обеспечение, даже наше общение и, конечно, наши секреты – все кодируется, шифруется и пересылается в виде чисел! Любимое хобби математиков неожиданно превратилось в жизненно важный источник знаний об основе современной жизни – числе.

В теории чисел особую роль играют так называемые простые числа. Простые числа знакомы нам со школы. Это числа, которые делятся только на единицу и на само себя. Многие узнают этот знаменитый ряд:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31…

Все простые числа, кроме двойки, нечетные. И это понятно, потому что четные числа делятся на два.

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

Важно понимать, что никаких формул для поиска простых чисел не существует в принципе! Простые числа распределены очень хитро. Как мы скоро увидим, они крайне важны на практике, особенно сверхбольшие простые числа. Целая индустрия, привлекающая как математиков, так и программистов, занимается построением все новых и новых простых чисел. Так, в январе 2016 года было найдено очередное простое число, равное 274207281−1. В нем 22 338 618 знаков! Нечто запредельное…

В настоящее время особенно популярны так называемые схемы шифрования с открытым ключом. Мы расскажем о схеме Диффи – Хеллмана, которая датируется 1970-ми годами и активно используется на практике. Эта схема основана на глубокой математике, но саму идею понять совсем несложно.