25 этюдов о шифрах
Шрифт:
Числа p, q и d будем считать секретными и обозначим секрет K={p, q, d}. Числа n и e будем считать общедоступными. Множества открытых сообщений X и шифрованных сообщений Y будем считать равными: X = Y = {1, 2, ... , n−1}.
Функцию FK : X → Y
Свойство а) односторонней функции с секретом выполнено для FK очевидным образом. Проверим свойство в). Для этого просто укажем, как при известном K инвертировать функцию FK: решением уравнения FK(x) = y будет x = yd(modn). Подробное доказательство этого факта оставляем читателю, приведем лишь необходимые выкладки без комментариев:
d∙e = φ(n)∙m + 1
(xe)d(modn) = xφ(n)∙m+1(modn) = (xφ(n))m∙x(modn) = (1)m∙x(modn) = x.
Свойство б) для функции FK строго не доказано. Пока общепризнано, что для инвертирования FK необходимо разложить n на множители, а, как указывалось в этюде 3.4, задача факторизации целых чисел относится к трудным математическим задачам.
Таким образом, описанную функцию FK можно считать кандидатом на звание односторонней функции с секретом. Система RSA строится с помощью этой функции так, как рассказано в этюде 3.2.
В газете «Известия» за 29 апреля 1994 г. под заголовком «Сверхсекретный шифр разгадан за 17 лет» появилось следующее сообщение: «Когда в 1977 году математики Рональд Ривест, Ади Шамир и Леонард Адлеман зашифровали фразу из нескольких слов, используя комбинацию из 129 цифр, они утверждали, что на разгадку понадобятся триллионы лет. Однако ключ к самому сложному в мире шифру «РСА-129» (RSA) был найден за 17 лет... Разгадка шифра за такой относительно короткий срок имеет огромное значение для государственных организаций и предпринимателей, которые пользуются аналогичными длинными цифровыми кодами для защиты секретных сведений в своих компьютерных базах данных...» Пока это сообщение не подтверждено научными публикациями, ясно лишь, что речь идет о том, что удалось разложить на множители то 129-значное
Подумайте сами:
1. Разберите примеры работы системы RSA, приведённые на стр. 241–243 книги М. Гарднера «От мозаик Пенроуза к надёжным шрифтам».
3.6. Открытое распределение ключей
Кроме принципа построения криптосистемы с открытым ключом, Диффи и Хеллмэн в той же работе предложили еще одну новую идею — открытое распределение ключей. Они задались вопросом: можно ли организовать такую процедуру взаимодействия абонентов A и B по открытым каналам связи, чтобы решить следующие задачи:
1) вначале у A и B нет никакой общей секретной информации, но в конце процедуры такая общая секретная информация (общий ключ) у A и B появляется, т.е. вырабатывается;
2) противник, который перехватывает все передачи информации и знает, что хотят получить A и B, тем не менее не может восстановить выработанный общий ключ A и B.
Диффи и Хеллмэн предложили решать эти задачи с помощью функции F(x) = αx(modp), где p — большое простое число, x — произвольное натуральное число, α — некоторый примитивный элемент поля GF(p).
Примитивным называется такой элемент a из GF(p), что каждый элемент поля, за исключением нуля, может быть представлен в виде степени a. Можно доказать, хотя это и не просто, что примитивный элемент всегда существует.
Общепризнано, что инвертирование функции αx(modp), т.е. дискретное логарифмирование, является трудной математической задачей (см. этюд 3.4).
Сама процедура или, как принято говорить, протокол выработки общего ключа описывается следующим образом.
Числа p и α считаются общедоступными.
Абоненты A и B независимо друг от друга случайно выбирают по одному натуральному числу — скажем x(A) и x(B). Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент:
y(A)=αx(A)(modp), y(B)=αx(B)(modp).
Потом они обмениваются этими элементами по каналу связи. Теперь абонент A, получив y(B) и зная свой секретный элемент x(A), вычисляет новый элемент