Криптографические приключения: таинственные шифры - Страница 62

Отец взял чистый лист бумаги и начал рисовать на нём алгоритм, поясняя его словами:

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

Он записал на листке: 5 и 7. Затем он продолжил:

— Вторым шагом мы вычисляем произведение двух выбранных чисел. В нашем случае это будет 35. Но одновременно нужно дополнительно вычислить число, равное произведению двух выбранных чисел, из которых вычли по единице, то есть в нашем случае 4 и 6. Это будет 24, и оно является значением функции Эйлера для числа 35. Запомните это название. Возможно, в будущем оно вам понадобится.

Отец записал на листке: 5 Ч 7 = 35 и 4 Ч 6 = 24. Потом он продолжил:

— Третьим шагом мы должны выбрать так называемую открытую экспоненту. Это показатель степени, в которую будет возводиться сообщение при шифровании. Эта открытая экспонента должна быть взаимно простой с числом 24. Обычно выбирают какое-нибудь небольшое простое число, и есть специальные правила выбора, в которые мы углубляться не будем. Сейчас мы возьмём число 17. После выбора открытой экспоненты выполняется важный шаг — вычисление секретной экспоненты. Она вычисляется как обратная к открытой экспоненте по модулю 24. Другими словами, надо найти такое число, которое при умножении на 17 давало бы по модулю 24 значение 1. Это непростая задача. Помните ещё модульную арифметику?

Мы с Катей кивнули. Отец что-то посчитал на своём смартфоне и записал: e = 17, d = 41. Я спросил:

— Как тебе удалось так быстро найти обратное число?

— На самом деле я заранее подготовился, а сейчас просто проверил. Я же брал время для того, чтобы поразмыслить. Итак, продолжим. У нас получилось множество чисел, но использовать мы будем только три. В качестве открытого ключа используется пара (17, 35), а в качестве закрытого — пара (41, 35). Как видите, все не так, как рассказала Катерина. Но давайте посмотрим, почему этот способ тоже работает.

Нам надо выбрать сообщение, которое мы будем пересылать в шифрованном виде. Сообщения в этом методе — это целые числа от 1 до произведения двух выбранных простых чисел без единицы. Но вы же понимаете, что любой текст можно преобразовать в целое число. А если использовать очень большие простые числа, как я говорил вначале, то можно будет зашифровывать и большие тексты. Совсем большой текст можно разбивать на части и шифровать их друг за другом. Это уже дело техники. Итак, в нашем игрушечном примере нам надо выбрать сообщение в виде числа от 1 до 34. Катерина, выбери случайное число.

— Двадцать пять.

Отец продолжил писать на листке и комментировать:

— Хорошо. Для того чтобы зашифровать сообщение, мы должны возвести его в степень открытой экспоненты по модулю произведения двух простых чисел. В нашем случае мы должны взять число 25 и возвести его в степень 17 по модулю 35. Что получается? Так… Получается 30. Вот теперь это число 30 и есть наша шифровка. Как её расшифровать, кто-нибудь может предположить?

Мы с Катей только пожали плечами, а потому отец продолжил:

— Надо воспользоваться закрытым ключом. Шифровку надо возвести в степень закрытой экспоненты по тому же самому модулю. В нашем простом примере получается, что надо число 30 возвести в степень 41 по модулю 35. Получается… получается 25, как ни странно. Впрочем, почему должно быть странно? Ведь это методы шифрования и расшифровки.

Вроде бы всё было понятно. Мы с Катей некоторое время смотрели на написанные выкладки, а отец рисовал диаграмму алгоритма взаимодействия при шифровании этим методом. Теперь было ещё понятнее:

Ближе к вечеру вернулись мои дядьки. Дядя Руслан сразу же протянул нам пакет. Сердце у меня ёкнуло — мне показалось, что они нашли клад. Но, раскрыв пакет, я увидел только горсть всякого металлического добра. Дядя Руслан улыбнулся:

— Вот что удалось найти. Можете разобрать и взять себе, что найдёте интересным.

Мы с Катей накинулись на содержимое пакета. Оказалось, что дядя Руслан с дядей Игорем не только осматривали окрестности и пытались сопоставить план с местностью, но и прошлись с нашим металлоискателем по полям и тропинкам. Перед нашими глазами лежали: несколько болтов, какой-то крюк, дробинки и несколько монет. Я принёс чистую тряпочку, и мы тщательно, но осторожно оттерли с монет землю и грязь.

Насколько я мог судить, среди монет не было ни одной ценной: несколько советских монеток, а также одна дореволюционная — большая медная с надписью «1 копѣйка серебромъ». Мы с Катей не знали, как поступить, и я показал эту находку папе. Он сказал, что особой ценности эта монета не имеет, и я подарил её Кате на память.

Глава 14

На следующее утро мы всем табором отправились в гости к тёте Кате. Поскольку у семейства дяди Руслана велосипедов не было, мы все пошли пешком. Перед этим я по рации вызвал Катю, и она встретила нас на главной площади села. Что ж, через пятнадцать минут мы уже были во дворе дома тёти Кати.

Пока все новые гости знакомились с хозяйкой и рассказывали, кто они такие и кем приходятся моему отцу, тот повёл нас с Катей на задний двор, где на верёвках до сих пор сушилась рыба. Отец сказал, что уже прошло две недели, так что можно снимать и пробовать. Мы помогли ему снять всю рыбу, и её оказалось очень много. С довольным видом мы принесли таз с рыбой на скамейку перед всеми. Дядя Руслан и дядя Игорь молча в изумлении смотрели на нас. Отец воскликнул: