Система шифрования Вижинера

σ: s_i → s_{σ (i)}, 0 ≤ i < n. Будем говорить, что в этом смысле σ является перестановкой элементов S.

Криптографическим преобразованием T для алфавита Z_m называется последовательность автоморфизмов: T = {T⁽ⁿ⁾: 1 ≤ n < ∞ } T⁽ⁿ⁾: Z_m→ Z_m,

1 ≤ n < ∞. Каждое T⁽ⁿ⁾ является, таким образом, перестановкой n -грамм из Z_m. Поскольку T⁽ⁱ⁾ и T^(j) могут быть определены независимо при i ≠ j, число криптографических преобразований исходного текста размерности n равно (mⁿ)²!. Оно возрастает непропорционально при увеличении m и n: так, при m = 33 и n = 2 число различных криптографических преобразований равно 1089!. Отсюда следует, что потенциально существует большое число отображений исходного текста в зашифрованный.

Практическая реализация криптографических систем требует, чтобы преобразования {T_k: k Î K}, где K – множество ключей, были определены алгоритмами, зависящими от относительно небольшого числа параметров (ключей). При ручном способе шифрования часто применяют шифрующие таблицы. В качестве ключа в шифрующих таблицах используются:

· размер таблицы;

· слово или фраза, задающая перестановку;

· особенности структуры таблицы.

Пример 43. Используем шифрование методом перестановки, для которой ключом служит размер таблицы 5*7:

Шифруемое сообщение: " ШЕФ НАЗНАЧИЛ ВСТРЕЧУ В ПОЛНОЧЬ НА ПЛОЩАДИ" записываем в таблицу поочередно по столбцам.

После заполнения таблицы текстом сообщения по столбцам для формирования шифротекста считывают содержимое таблицы по строкам. В итоге получится сообщение: ШЗЛЕОЬОЕНВЧЛНЩФАСУНААНЧТВОПДАИРПЧЛИ

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

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

В качестве ключа возьмем слово ВЕЛИКАН, буквы которого пронумерованы по алфавиту. Шифруемое сообщение возьмем из предыдущего примера.

До перестановки После перестановки

В правой таблице столбцы переставлены в соответствии с упорядоченными номерами букв ключа. При считывании содержимого правой таблицы по строкам и записи шифротекста группами по пять букв получим зашифрованное сообщение: ЬШЗЕОЛОНЕНЧЛВЩАФАУНСФПНЧВОТДЛАИПЧРИ▲

5.2.3. Гаммирование.

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

Процесс расшифрования данных сводится к повторной генерации гаммы шифра при известном ключе и наложении такой гаммы на зашифрованные данные.

Гаммирование является широко применяемым криптографическим преобразованием. Шифром гаммирования называется шифр с алфавитом открытых сообщений Z_m, совпадающим с алфавитом шифрованных сообщений и ключевым множеством K. При этом для любого открытого текста

A={a₁, a₂,...a_s, …}Î Z_m и " kÎ K F(A, k) = b₁, b₂,..., b_s, …

b₁ = a₁ + Ψ ₁(k) mod (m)

b_i = a_i + Ψ _i(a₁, a₂,..., a_i-1, k) mod (m), i = 2, 3,...

Таким образом, шифр гаммирования, заключается в сложении по модулю m (мощность алфавита открытых сообщений) открытого текста с некой последовательностью знаков из Z_m – гаммой, полученной из исходного ключа.

В идеальном случае гамма должна быть случайной последовательностью, то есть в ней отсутствует зависимость знаков друг от друга. Истинно случайную последовательность можно получить используя датчики случайных физических величин. В компьютерных технологиях применяют генераторы псевдослучайных последовательностей с максимально возможным периодом, построенные с использованием секретной ключевой информации.

Объем ключевой информации ограничивается в данном случае тем, что для шифрования сообщений используется ключ фиксированной длины в независимости от длины сообщения. Отсюда очевидным образом следует, что гамма не может быть произвольной последовательностью чисел из Z_m, а следовательно речи о «совершенной стойкости» идти не может.

Задача создания качественного шифра гаммирования заключается

в обеспечении следующих свойств.

1. Максимальную близость гаммы по статистическим свойствам к случайной равновероятной последовательности независимых величин.

2. Отсутствие возможности практического восстановления неизвестных отрезков гаммы и ключа по известным.

Первое свойство необходимо обеспечивать для невозможности дешифрования шифра гаммирования статистическими методами. Второе – для того чтобы по части открытого текста невозможно было восстановить весь текст или другие его отрезки.

Метод гаммирования становится бессильным, если злоумышленнику становится известен фрагмент исходного текста и соответствующая ему криптограмма. Простым вычитанием по модулю получается отрезок ПСП и по нему можно восстановить всю последовательность. Злоумышленник может сделать это на основе догадок о содержании исходного текста. Так, если большинство посылаемых сообщений начинается со слов " СОВ. СЕКРЕТНО", то криптоанализ всего текста значительно облегчается. Это следует учитывать при создании реальных систем информационной безопасности.

5.2.4. Операции, используемые при построении шифров

Ниже приведены наиболее типичные операции, применяемые в современных шифрах. Линейность или нелинейность операции рассматривается над полем F₂.

1. Перестановка битов в блоке. Операция линейна. Перестановка описывается матрицей, в которой в каждой строке и в каждом столбце содеожится единственная единица, а остальные элементы – нулевые.

2. Подстановка n – разрядного слова вместо n – разрядного входного слова (операция замены). Операция при n > 2 нелинейная.

3. Циклический сдвиг (фиксированный). Операция является частным случаем перестановки.

4. Умножение на невырожденную матрицу. Если элементы матрицы лежат в кольце R, то этот оператор является линейным над R. Операция используется в качестве рассеивающего оператора в шифрах SAFER, RIJNDEL.

5. Сложение по модулю 2. Операция является " слабо" нелинейной, используется во многих шифрах (ГОСТ 28147 – 89, RC5, FIAL). Нелинейность обусловлена наличием и длиной переноса из предыдущего разряда в последующие при выполнении сложения.

6. Умножение по модулю простого числа. Операция является нелинейной, используется в шифре IDEA для простого числа p = 2¹⁶ +1. Вычисления проводятся в группе F_p^* порядка 2¹⁶.

7. Нахождение обратного элемента в расширенном поле характеристики 2. Пусть p(t) – полином степени n, задающий расширенное конечное поле из 2ⁿ элементов. Вход n – разрядной подстановки представляется элементом x(t) этого поля. Выходом подстановки является элемент y(t) поля такой, что x(t)·y(t) ≡ 1 (mod p(t)) (такая подстановка вычисляется расширенным бинарным алгоритмом Евклида). Данная операция является нелинейной и используется в стандарте шифрования RIJNDAEL.

8. Возведение в степень по модулю простого числа Ферма p. Операция y = a^x(mod p) является нелинейной. Используется в шифре SAFER.

6. АСИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ

6.1. Односторонние функции

Одним из центральных понятий криптосистем с открытым ключом

является понятие односторонней функции.

Стойкость такой системы зависит от сложности вычисления дискретных логарифмов в мультипликативной группе конечного поля в F(p). Эта стойкость гарантирована тем, что до настоящего времени не найдено быстрых алгоритмов нахождения ключа K из а, y_A, y_B.

Описанная схема открытого распределения ключей совместно с введенным понятием односторонней функции с секретом послужили основой для создания нового направления в области построения криптографических систем. Такие системы получили название криптосистем с открытым ключом.

В общем виде криптографическая система с открытым ключом представляет собой систему, включающую следующие компоненты:

– пространство открытых текстов M;

– пространство шифротекстов C;

– пространство секретных ключей K;

– множество преобразований зашифрования Е_k, k Î K

Е_k: m ® c, m Î M, c Î C;

– множество преобразований расшифрования D_k, k Î K

D_k: c ® m, m Î M, c Î C.

При этом преобразования Е_k и D_k должны обладать следующими свойствами:

1. Для каждого k Î K преобразование D_k является обратным к преобразованию Е_k т.е. D_k(Е_k(m) = m при всех m Î M.

2. По каждому выбранному ключу k Î K легко найти пару обратимых преобразований Е_k и D_k.

3. Для всех k Î K, m Î M, c Î C величины Е_k(m) и D_k(c)

легко вычисляются за полиномиальное время.

4. Почти для всех k Î K вычислительно невозможно из Е_k вывести какое - либо легко вычисляемое преобразование, эквивалентное D_k.

Свойство 4 отличает криптосистемы с открытым ключом от традиционных криптосистем с секретным ключом, в которых преобразования Е_k и D_k также зависят от секретного ключа К, но знание преобразования D_k дает знание К и D_k или наоборот, знание D_k позволяет определить К и D_k, поэтому преобразования

E_k и D_k либо оба известны, либо оба неизвестны. Это свойство 4 позволяет не засекречивать преобразование зашифрования E_k, а делать его открытым для всех, кто хочет послать секретное сообщение.

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

Пример 45. Пусть абоненты А и В условились организовать секретную переписку между собой используя секретный ключ сгенерированный при помощи алгоритма Диффи–Хеллмана. Тогда они вместе выбирают числа p = 67 и a = 11. Затем

1. А выбирает случайное целое число k_a = 47, вычисляет y_A = a^ka mod p = 11⁴⁷ mod 67 = 2 и посылает В число 2.

2. В выбирает случайное целое число k_b = 51 вычисляет y_B = a^kb mod p = 11⁵¹ mod 67 = 3 и посылает A число 3.

3. А вычисляет K = y_B^ka mod p = 347 mod 67 = 27

4. B вычисляет K = y_A^kb mod p = 251 mod 67 = 27

В итоге А и В получили секретный ключ K = 27. ▲

Без дополнительных мер безопасности (введения сертификатов открытых ключей), рассмотренный метод ключевого обмена уязвим с точки зрения атаки, известной под названием “человек посередине” (main in the midlle attact).

Предположим, что злоумышленник C может не только подслушивать сообщения между абонентами A и B, но также изменять, удалять и создавать новые ложные сообщения. Тогда злоумышленник C может выдавать себя за абонента A, передающего (или принимающего) от его имени информацию абоненту B, и за B перед абонентом A. Атака состоит в следующем:

1. A посылает B свой открытый ключ. C перехватывает его и посылает B свой собственный открытый ключ.

2. B посылает A свой открытый ключ. C перехватывает его и посылает A свой собственный открытый ключ. Таким образом, злоумышленник подменяет открытые ключи легальных участников информационного обмена на свои.

3. Когда A посылает зашифрованное сообщение B, C перехватывает его. Так как сообщение зашифровано на открытом ключе C, он расшифровывает его, затем зашифровывает его на открытом ключе B и посылает B.

4. Когда B посылает сообщения A, C перехватывает его. Так как сообщение в зашифровано на открытом ключе C, он расшифровывает его, снова зашифровывает его на открытом ключе A и посылает A.

Атака возможна, даже если открытые ключи A и B хранятся в базе данных (БД). Злоумышленник C может перехватить запрос A к БД и подменить открытый ключ. Данная атака очень эффективна. Открытые ключи должны проходить сертификацию, чтобы предотвратить подобные атаки, связанные с подменой ключей и должны регулярно меняться.

6.3. Асимметричная криптосистема RSA

В 1978 г. Рональд Ривест, Ади Шамир и Леонард Адлеман (R.Rivest, A.Shamir, L.Adleman) предложили пример функции, обладающей рядом замечательных свойств. На ее основе была построена реально используемая система шифрования, получившая название по первым буквам фамилий авторов – система RSA. Рассмотрим ее основные положения на примере криптосистемы с открытым ключом.

Система создана на основе степенной односторонней функции с секретом f(x) = x^e mod n. Блок x открытого текста, представленный как целое число в диапазоне [0, n-1], преобразуется в блок y шифротекста с помощью криптографического преобразования:

y = E_{(e, n)}(x) = x^e mod n,

где (e, n) – открытый ключ, используемый для зашифрования. При расшифровании блок x открытого текста вычисляется также с помощью степенной функции, но с другим показателем d, являющимся закрытым ключом:

x = D_{(d, n)} (y) = y^d mod n.

В основе согласованности этих преобразований лежит теорема Эйлера, в соответствии с которой для каждого числа x, взаимно простого с модулем n, выполнено сравнение x^{φ (n)} ≡ 1 mod n,

где φ (n) – функция Эйлера, равная числу натуральных чисел, не превосходящих n и взаимно простых с n:

φ (n) = n ∙ (1 -1/ p₁) ∙ (1 – 1/ p₂) ∙...∙ (1 – 1/ p_s),

если каноническое ражложение числа n есть p₁^k1 ∙ p₂^k2 ∙... p_s^ks.

Для того чтобы воспользоваться теоремой Эйлера, в криптосистеме RSA используются числа e и d, связанные соотношением

e ∙ d ≡ 1 mod φ (n). (6.1)

Тогда при x, взаимно простом с модулем n,

(x^e mod n)^d mod n = x^ed mod n = x^{t∙ φ (n)+1} mod n = x ∙ (1)^t = x.

Таким образом, с использованием ключа d реализуется корректное расшифрование.

Как выбираются числа e, d и n? Вообще, зная φ (n), число e можно выбрать взаимно простым с φ (n), проверив свойство (e, φ (n)) = 1 с помощью алгоритма Евклида. Тогда d есть решение сравнения (6.1), и d можно найти с помощью расширенного алгоритма Евклида, определяющего числа d и t такие, что

e ∙ d + t ∙ φ (n) = 1

В системе RSA модуль n есть произведение двух секретных простых чисел p и q, поэтому φ (n) = (p – 1) ∙ (q – 1). При этом если простое число e > max(p, q), то оно взаимно простое с φ (n), то есть при выработке такого ключа e можно воспользоваться быстрыми тестами проверки чисел на простоту и не применять алгоритм Евклида.

Без знания простых сомножителей p и q трудно определить значение φ (n), следовательно, при секретном числе d определение открытого текста по зашифрованному сообщению сводится либо к трудной задаче извлечения корня степени e из числа y по модулю n, либо к трудной задаче разложения числа n на простые множители.

Условие (x, n) = 1 при больших p и q почти всегда выполняется, так как доля таких чисел x есть

φ (n)/ n = (n – p –q +1)/n > 1 – 1/q – 1/p.

Криптоанализ системы RSA показал, что для стойкого шифрования необходимо выполнение следующих условий:

1. Числа p и q должны быть достаточно большими, не слишком сильно различаться и быть не слишком близкими;

2. НОД (p –1, q -1) должен быть небольшим, в лучшем случае равен 2;

3. Числа p и q должны быть сильно простыми (простое число r называется сильно простым, если r +1 имеет большой простой делитель, а r -1 имеет большой простой делитель s такой, что s -1 также имеет большой простой делитель.

Теоретические положения построения криптографических систем с открытым ключом в основном базируются на следующих фактах:

1. Кольцо целых чисел является факториальным, то есть обладет свойством однозначности разложения на простые множители. Но задача разложения больших чисел на простые множители за полиномиальное время не разрешима.

2. Задача вычисление логарифма за полиномиальное время не разрешима.

3. Следствие малой теоремы Ферма: для любого целого числа m, не делящегося на простое число p, имеет место сравнение m^p-1 ≡ 1 (mod p).

4. Функции Эйлера, которая гласит, что если натуральное число n делится в точности на k различных простых чисел p₁, p₂,..., p_k, то количество чисел, меньших n и взаимно простых с n, равно

φ (n) = n ∙ (1 – 1/p₁) ∙ (1 – 1/p₂) ∙... ∙ (1 – 1/p_k).

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

А: р_A, q_A; n_А = р_A∙ q_A; φ (n_А); НОД(e_A, φ (n_А)) = 1; 0 < e_A < φ (n_А),

B: p_B, q_B; n_B = p_B∙ q_B; φ (n_B); НОД(e_B, φ (n_B)) = 1; 0 < e_B < φ (n_B).

Затем печатается справочная книга, доступная всем желающим, которая имеет вид:

где n_А – произведение двух простых чисел, известных только абоненту А, e_A – открытый ключ, доступный каждому, кто хочет передать секретное сообщение А;

n_B – произведение двух простых чисел, известных только B,

e_B – открытый ключ, доступный каждому, кто хочет передать секретное сообщение B.

Каждый из абонентов находит свой секретный ключ из сравнений

e_A ∙ d_A ≡ 1(mod φ (n_А)), 0 < e_A < φ (n_А),

e_B ∙ d_B ≡ 1(mod φ (n_B)), 0 < e_B < φ (n_B).

В итоге имеем

Пусть абонент А решает послать сообщение m абоненту В:

А: m → В и пусть 0 < m < n_B, иначе текст делят на блоки длины меньше n_B. Сначала А зашифровывает сообщение открытым ключом абонента В, который есть в справочной книге, вычисляет:

c_A ≡ m^eB(mod n_B), 0 < m < n_B,

и отправляет абоненту В. Абонент В, расшифровывает это сообщение своим секретным ключом:

m ≡ c_A^dB(mod n_B), 0 < m < n_B,

Пример 46. Пусть абоненты A и B решили обменяться между собой секретными сообщениями с помощью системы RSA.

Абонент A выбрал простые числа р_A = 7643 и q_A = 8753, их произведение n_А=66899179, функцию Эйлера φ (n_A) = n_A∙ (1-1/р_A)∙ (1-1/q_A) = 66882784.

Затем он выбирает случайное число e_A = 9467 (открытый ключ) и находит секретный ключ из решения сравнения: e_A∙ d_A ≡ 1(mod φ (n_А)) = 9467∙ d_A ≡ 1(mod 66882784), 0 < d_A < φ (nА), т.е. d_A = 30993427.

Абонент B выбрал простые числа p_B = 7481 и q_B = 9539, их произведение n_B = 71361259, функцию Эйлера φ (n_B) = n_B∙ (1-1/p_B)∙ (1-1/q_B) = 71344240. Затем он выбирает случайное число e_B = 74671 (открытый ключ) и определяет свой секретный ключ из решения сравнения:

e_B ∙ d_B ≡ 1(mod φ (n_B)) = 74671 ∙ d_B ≡ 1(mod71344240), 0 < d_B < φ (n_B), т.е. d_B = 33289711.

Таким образом, у абонентов имеются следующие данные:

Абонент A решает послать секретное сообщение m = 95637 абоненту B. Тогда он шифрует сообщение открытым ключом абонента B:

c₁ ≡ m^eB(mod n_B)= 95637⁷⁴⁶⁷¹(mod 71361259) = 25963634.

Абонент B, получив это сообщение, расшифровывает его своим секретным ключом: m ≡ c₁^dB(mod n_B)= 25963634^33289711(mod 71361259)= 95637. ▲

6.4 Надежность системы RSA

В рассмотренной криптосистеме с открытым ключом для расшифрования сообщения m необходимо найти секретный ключ dB. Это возможно в двух случаях:

1) если известно разложение n_B на простые множители;

2) если известен модуль φ (n_B) сравнения e_B ∙ d_B ≡ 1(mod φ (n_B)).

Но так как n_B = p_B∙ q_B, то

φ (n_B) = φ (p_B) ∙ φ (q_B) = (p_B -1) ∙ (q_B -1) = p_B ∙ q_B - (p_B+q_B) + 1 и

(p_B –q_B)² = p_B² + q_B² – 2p_B∙ q_B = (p_B + q_B)² – 4p_B∙ q_B.

Следовательно, мы имеем равенства:

φ (n_B) = n_B - (p_B + q_B) + 1,

(p_B – q_B)² = (p_B + q_B)² – 4p_B∙ q_B,

а значит, зная φ (n_B), можно решить эту систему и найти p_B и q_B, а зная p_B и q_B, легко вычислить φ (n_B). Таким образом, оба подхода определения ключа d_B эквивалентны, т.е. задачи одной сложности. Таким образом, встает задача разложения на простые множители натурального числа.

В теории чисел, несмотря на ее многолетнюю историю и на очень интенсивные поиски в течение последних 30 лет, эффективный алгоритм разложения натуральных чисел на множители так и не найден. Конечно, можно, перебирая все простые числа до (n_B)^1/2, и деля на них n_B, найти требуемое разложение. Но учитывая, что количество простых чисел в этом промежутке асимптотически равно 2∙ (n_B)^1/2 ∙ (ln n_B)^-1, находим, что при n_B, записываемом 1000 десятичными цифрами, найдется не менее 10⁴⁹⁷ простых чисел, на которые придется делить n_B при разложении его на множители, что при современных возможностях вычислительной техники затянется на долгие годы.

Известны и более эффективные алгоритмы разложения целых чисел на множители, чем простой перебор простых делителей, но и они работают очень медленно.

Необходимо также отметить, что система RSA обладает мультипликативным свойством. Поясним сказанное. Пусть m₁ и m₂ – 2 различных открытых текста, а c₁ и с₂ – соответствующие им шифртексты. Заметим, что (m₁ ∙ m₂)^e = m₁^e ∙ m₂^e = c₁ ∙ c₂ (mod n).

Другими словами, шифртекст открытого текста m = m₁ ∙ m₂ есть c = c₁ ∙ c₂(mod n). Это свойство, называемое также гомоморфным свойством RSA, позволяет осуществить атаку по выбранному шифртексту. Его нужно учитывать при совмещении схем шифрования на основе RSA и цифровой подписи RSA.

Кроме того, известно еще несколько атак на RSA. Рассмотрим из них две.

Первая из них называется ”Метод безключевого чтения RSA”. Суть заключается в следующем.

Криптоаналитику известны открытый ключ (e, n) и шифротекст c.

Тогда он подбирает такое число k, для которого выполняется следующее

соотношение: c^ek(mod n) = c. Т.е. криптоаналитик просто проводит k раз

зашифрование на открытом ключе перехваченного шифротекста. Это выглядит следующим образом: (((c^e)^e)^e…)^e = c^ek = c^{φ (n)-1} = c(mod n). Найдя такое k, криптоаналитик вычисляет c^k = m^ek = m^{φ (n)-1} = m (mod n), т.е. получает открытый текст m.

Следующая атака осуществляется на базе общего модуля. Основные предпосылки для ее осуществления заключаются в следующем.

При реализации RSA можно раздать всем абонентам криптосети одинаковый модуль n, но каждому свои значения e_i (открытый ключ) и d_i (секретный ключ). При этом наиболее очевидная проблема заключается в том, что если одно и то же сообщение когда-нибудь шифровалось разными e_i и e_k, причем НОД(e_i, e_k) = 1 (как обычно и бывает), то открытый текст может быть расшифрован даже при неизвестных d_i и d_k.

Таким образом, пусть заданы: m – сообщение, а и b – два открытых ключа шифрования, n – модуль. Тогда щифротекстами являются c₁ = m^а (mod n) и c₂ = m^b (mod n). Криптоаналитику известны: n, а, b, c₁ и c₂. Так как а и b взаимно простые числа, то можно найти такие целые числа x и y, что аx + by =1. Тогда, возведя c₁ в степень x, а c₂ – в степень y, получим:

c₁^x c₂^y = (m^а)^x (m^b)^y = m^аx+by = m¹ = m.

Пример 43. Пусть абонент А хочет послать сообщение m = 237135 абоненту В. Абоненту А даны n = 399799 и открытый ключ a = 4397. Он зашифровывает сообщение открытым ключом c₁= 237135⁴³⁹⁷ ≡ 268100(mod 399799) и посылает это число в открытый канал связи. Абонент В хочет также послать сообщение m = 237135 другому абоненту. Для В даны n = 399799 и открытый ключ b = 7517. Он зашифровывает сообщение открытым ключом, т.е. c₂=237135⁷⁵¹⁷ ≡ 263851(mod 399799) и также посылает это число в открытый канал связи. Таким образом, криптоаналитику известно: зашифрованные сообщения c₁ и c₂, модуль n, открытые ключи a и b. Далее криптоаналитик решает уравнение аx + by = 1 = 4397x +7517y и получает x=− 1607 и y=940. Затем он возводит c₁ в степень |x|, т.е.

c₁^|x| = d₁ = 268100¹⁶⁰⁷ ≡ 12105(mod 399799), а c₂ в степень |y|, т.е.

c₂^|y| = d₂ = 263851⁹⁴⁰ ≡ 362154(mod 399799).

Так как x < 0, то находится (d₁)^-1 = 12105^-1 ≡ 39501(mod 399799). (При y < 0 искали бы (d₂)^-1). Далее, перемножая

(d₁)^-1*d₂ ≡ 39501*362154(mod 399799) = 237135 = m, т.е. получили открытый текст. ▲

6.5. Проблемы практической реализации RSA

В настоящее время алгорит