Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
1. Выбрать два случайных простых числа р и q, удовлетворяющих условию |р| к \q\.
(* Для этого можно воспользоваться методом Монте-Карло, описанным ал-, горитмом 4.7. *)
2. Вычислить А^ = pq.
3. Вычислить 4>(N) = (р - l)(q - 1).
4. Выбрать случайное целое число е < <p(N), удовлетворяющее условию gcd(e, 4>(N)) = 1, и найти целое число d, такое что
ed=l(mo&<]>(N)).
(* Поскольку gcd(e, 4>(N)) = 1, это уравнение имеет решение d, кото* рое можно найти с помощью расширенного алгоритма Евклида (алгоритм 4.2). *)
5. Использовать пару (А^, е) в качестве параметров открытого ключа, тщательно уничтожить числа p,qvi <}>(N) и запомнить число d в качестве закрытого ключа.
Шифрование
Для того чтобы переслать Алисе секретное сообщение, имеющее длину т < N,1 Боб создает зашифрованный текст с.
с ¦— me(mod N).
(* С точки зрения Боба, пространство исходных сообщений представляет собой множество всех положительных чисел, которые меньше числа А'', хотя на самом деле этим пространством является группа 7L*N. *) Расшифровка
Для того чтобы расшифровать зашифрованный текст с, Алиса вычисляет формулу
т<- cd(modAr).
где к — некоторое целое число. Следовательно, значение, вычисленное Алисой в результате выполнения процедуры расшифровки, определяется по следующей
Глава 8. Шифрование — асимметричные методы
305
формуле.
cd = med = m1+W) = т ¦ m^^modiV). (8.5.1)
Следует отметить, что неравенство т < N практически всегда означает, что т Е Щ, (т.е. почти все числа, которые меньше числа N, принадлежат мультипликативной группе целых чисел, взаимно простых с числом АГ). Условие т Е нарушается, если т = up или т = vq, где и < q п v < р. В этих ситуациях Боб может разложить число N на простые множители, вычислив значение gcd(m, N). Предполагая, что это является трудноразрешимой задачей (условия, при которых факторизация числа представляет собой трудноразрешимую задачу, будут сформулированы позднее), можно предположить, что любое сообщение т < N, созданное Бобом, удовлетворяет условию т Е Щ^.
Если т 6 Щ^, то по теореме Лагранжа (следствие 5.2)
ord^(m) | #Z*N = ф(Ы).
Это утверждение справедливо для всех т Е Щ^. В соответствии с определением порядка элемента группы (определение 5.9 в разделе 5.2.2) это означает, что для всех т Е "L*N выполняется условие
m^N) = l{modN).
Отсюда следует, что
т*«*> ее {тф^)к ее l(modiV)
для любого целого числа к. Итак, величина в формуле (8.5.1) действительно равна числу т.
Пример 8.2. Допустим, что Алиса выбрала числа N = 7 х 13 = 91 и е = 5. Тогда <^(Л^) = 6 х 12 = 72. Применяя алгоритм 4.2 к паре (а, Ь) = (72,5), Алиса получает следующее число.
72 х (-2) + 5 х 29 = 1.
Иначе говоря, 5 х 29=1 (mod 72). Следовательно, секретным показателем степени, используемым Алисой при шифровании, является число 29. Алиса устанавливает пару (N,e) = (91,5) в качестве параметров открытого ключа криптосистемы RSA.
Допустим, что Боб шифрует исходное сообщение т = 3, используя формулу
c = 35 = 243 = 61(mod91).
Зашифрованное сообщение представляет собой число 61.
Для того чтобы расшифровать сообщение 61, Алиса вычисляет значение
6129EE3(mod91).
306
Часть III. Основные методы криптографии
8.6 Взлом криптосистем с открытым ключом с помощью криптоанализа
Можно сказать, что "криптосистема X является стойкой по отношению к атаке Y, но нестойкой по отношению к атаке Z", т.е. стойкость криптосистемы зависит от разновидности атаки. Активные атаки можно разделить на три вида.
Определение 8.3 (Активные атаки на криптосистемы).
Атака на основе подобранного открытого текста (chosen-plaintext attack
CPA). Атакующий выбирает исходные сообщения и передает их шифровальщику для получения зашифрованных текстов. Задача атакующего — взломать криптосистему, используя полученные пары открытых и зашифрованных текстов.
Атака на основе подобранного зашифрованного текста (chosen-ciphertext attack — CCA). Атакующий выбирает зашифрованные сообщения и передает их на расшифровку для получения исходных сообщений. Цель атакуют щего — взломать криптосистему, используя полученные пары открытых и зашифрованных текстов. Атакующий достигает успеха, если он раскры\ вает ключ и способен в дальнейшем извлекать секретную информацию из зашифрованного текста, не прибегая к посторонней помощи.
Атака на основе адаптивно подобранного зашифрованного текста (adaptive chosen-ciphertext attack — ССА2). Это — разновидность атаки ССА, в кош торой услуги расшифровки доступны для всех зашифрованных текстов, за исключением заданного.
Эти атаки можно описать следующими сценариями.
• В атаке на основе подобранного открытого текста атакующий владеет блоком шифрования.
• В атаке на основе подобранного зашифрованного текста атакующий имеет! ограниченный доступ к блоку расшифровки: после нескольких попыток доступ к блоку закрывается, и расшифровку требуемого текста атакующий должен выполнять без его помощи.
• В атаке на основе адаптивно подобранного зашифрованного текста атакующий владеет блоком расшифровки сколь угодно долго, однако, как и в предыдущем случае, расшифровка требуемого текста должна выполнять] ся без его помощи. Это условие вполне естественно — иначе атакующему незачем взламывать криптосистему.
