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…
Все простые числа, кроме двойки, нечетные. И это понятно, потому что четные числа делятся на два.
Еще со времен древнегреческого математика Евклида известно, что простых чисел бесконечное множество. Однако устроены они крайне сложно, и в теории чисел было брошено немало усилий на изучение их свойств. Ниже во врезке для интересующегося читателя мы приводим несколько любопытных фактов, касающихся простых чисел. Этот материал не требует математической подготовки, но и не влияет на наш дальнейший рассказ, поэтому при желании можете его пропустить.
Несколько интересных свойств простых чисел
Простых чисел, которые не превосходят п, примерно
где ln(n) это натуральный логарифм. Заметим, что ln(n) растет гораздо медленнее, чем п. Получается, что простые числа попадаются довольно часто. По этой оценке, их количество от одного до миллиарда равно примерно 48 254 942. На самом деле таких чисел 50 847 534
[15]
, то есть оценка вполне точная. Первым, кто добился серьезных продвижений в получении подобных оценок, был наш замечательный математик Пафнутий Львович Чебышев (1821–1894).
Есть и такой забавный результат: между х и 2х всегда находится простое число. Это так называемый постулат Бертрана. Однако проблема его уточнения очень сложна, а именно: верно ли, что между х и 1,1х есть простые числа (хотя бы при больших x)? Верно ли, что они есть между х и x + √x? Первое верно, а о втором никто не знает.
Все верят в бесконечность числа «простых близнецов»: 11 и 13, 17 и 19, 29 и 31 и так далее. Но пока никто не может это доказать.
Важно понимать, что никаких формул для поиска простых чисел не существует в принципе! Простые числа распределены очень хитро. Как мы скоро увидим, они крайне важны на практике, особенно сверхбольшие простые числа. Целая индустрия, привлекающая как математиков, так и программистов, занимается построением все новых и новых простых чисел. Так, в январе 2016 года было найдено очередное простое число, равное 274207281−1. В нем 22 338 618 знаков! Нечто запредельное…
Открытый обмен ключами
В настоящее время особенно популярны так называемые схемы шифрования с открытым ключом. Мы расскажем о схеме Диффи – Хеллмана, которая датируется 1970-ми годами и активно используется на практике. Эта схема основана на глубокой математике, но саму идею понять совсем несложно.
