В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 13. Алгоритм RSA В материале этой главы используются значения p , q и n . Значения p и q — это два разных больших простых числа, длина каждого из которых состав- ляет порядка тысячи бит или более. Значение n определяется как n := pq . (На сей раз это обычное произведение, а не взятое по модулю какого-нибудь числа.) 13.2 Китайская теорема об остатках Вместо того чтобы проводить вычисления по модулю простого числа p , как это было в схеме Диффи–Хеллмана, мы будем работать по модулю со- ставного числа n . Чтобы лучше понять изложенное, вы должны познакомить- ся еще с некоторыми аспектами теории чисел. Пожалуй, наиболее полезным из них является китайская теорема об остатках (Chinese Remainder Theo- rem — CRT) . Таким названием данная теорема обязана тому, что в своей ба- зовой форме впервые была доказана китайским математиком Сунь Цзе (Sun Tsu), жившим в первом веке до нашей эры. (Большинство математических понятий, которые нужно знать для работы с алгоритмами Диффи–Хеллмана и RSA, были сформулированы еще тысячи лет назад, поэтому не могут быть слишком сложными, не так ли?) Числа по модулю n — это 0 , 1 , . . . , n − 1 . Они не образуют конечное по- ле, как в том случае, если бы n было простым числом. Математики обозна- чают это множество чисел как Z n и называют его кольцом (ring) , но нам этот термин не понадобится. Для каждого x из Z n можно вычислить пару ( x mod p, x mod q ) . Китайская теорема об остатках утверждает, что можно выполнить и обратную операцию: зная ( x mod p, x mod q ) , восстановить ис- ходное значение x . Для упрощения записи введем обозначение ( a, b ) := ( x mod p, x mod q ) . Вначале покажем, что восстановление исходного значения x вообще воз- можно, а затем приведем алгоритм его вычисления. Чтобы вычислить x по заданным ( a, b ) , следует убедиться, что в Z n не существует второго такого числа x 0 , для которого x 0 mod p = a и x 0 mod q = b . В противном случае и x и x 0 привели бы к появлению одной и той же пары ( a, b ) , и ни один алгоритм не смог бы распознать, какое из этих значений является исходным. Пусть d := x − x 0 — это разность чисел, которым соответствует одна и та же пара ( a, b ) . Имеем ( d mod p ) = ( x − x 0 ) mod p = ( x mod p ) − ( x 0 mod p ) = a − a = 0 , а следовательно, d кратно p . Аналогичным образом получаем, что жүктеу/скачать 2,74 Mb. Достарыңызбен бөлісу:
|