В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 13. Алгоритм RSA Речь идет о закрытом ключе, состоящем из параметров p , q , t и d . Ока- зывается, достаточно знать любое из этих значений, чтобы вычислить три остальных. Доказательство этого факта крайне поучительно. Мы предполагаем, что злоумышленник знает открытый ключ ( n, e ) , по- скольку эта информация обычно широко известна. Если злоумышленник зна- ет p или q , вычислить остальные значения не составляет труда. Зная p , он может найти q = n/p , а затем вычислить t и d точно так же, как это дела- ли мы. Что, если злоумышленнику известны значения ( n, e, t ) ? Во-первых, t = ( p − 1)( q − 1) / НОД ( p − 1 , q − 1) , но, поскольку произведение ( p − 1)( q − 1) очень близко к n , найти НОД ( p − 1 , q − 1) нетрудно — это будет ближайшее к n/t целое число. (Значение НОД ( p − 1 , q − 1) никогда не бывает слишком большим, так как маловероятно, что два случайных числа имеют один и тот же большой делитель.) Это позволяет злоумышленнику вычислить ( p − 1)( q − 1) . Он также может вычислить n − ( p − 1)( q − 1) + 1 = pq − ( pq − p − q + 1) + 1 = p + q . Теперь у злоумышленника есть n = pq и s := p + q . Исходя из этого, он может вывести следующее: s = p + q ; s = p + n/p ; ps = p 2 + n ; 0 = p 2 − ps + n. Последнее выражение — не что иное, как квадратное уравнение относи- тельно p , которое может решить любой школьник. Разумеется, зная p , зло- умышленник сможет вычислить и остальные параметры закрытого ключа. Нечто аналогичное происходит и тогда, когда злоумышленник знает d . Во всех наших системах значение e будет очень малым. Поскольку d < t , значение ed − 1 будет лишь в несколько раз больше t . Злоумышленник может просто подобрать соответствующий множитель, вычислить t и затем попы- таться найти p и q описанным способом. В случае неудачи он просто попыта- ется перебрать остальные варианты. (Существуют и более быстрые приемы, однако этот наиболее легок для понимания.) Как видите, зная одно из значений — p , q , t или d , злоумышленник может вычислить остальные значения. Поэтому мы можем предположить, что вла- делец закрытого ключа знает все четыре значения. Программной реализации RSA достаточно хранить в памяти лишь одно из этих значений. Впрочем, большинство реализаций хранят несколько значений, которые нужны для выполнения операции дешифрования RSA. Выбор того или иного решения зависит от конкретной реализации и в контексте криптографии существен- ной роли не играет. 13.4. Определение RSA 255 Если пользователь А хочет расшифровать или подписать сообщение, ему, очевидно, должно быть известно значение d . Поскольку это эквивалентно знанию p или q , можно с полной уверенностью предположить, что пользова- тель А знает множители n , а потому может проводить вычисления с помощью CRT-представлений. Это очень удобно, так как в алгоритме RSA возведение числа в степень d является наиболее ресурсоемкой операцией, а использова- ние CRT-представления позволяет сократить объем работы в 3-4 раза. 13.4.4 Размер n Число n должно быть такого же размера, как число p , которое приме- нялось в алгоритме Диффи–Хеллмана. Более подробно это рассматривается в разделе 12.7. Напомним: чтобы обеспечить защиту данных на протяжении 20 лет, минимальный размер числа n должен составлять 2048 бит или около того. По мере увеличения мощности современных компьютеров этот мини- мум будет постепенно возрастать. Если ресурсы приложения позволяют, то используйте n длиной 4096 бит или наиболее близкой к этому. Более того, убедитесь, что ваше программное обеспечение поддерживает значения n дли- ной до 8192 бит. Никто не знает, чего можно ожидать в будущем, поэтому возможность перехода на использование ключей б´ольших размеров без за- мены программного или аппаратного обеспечения может оказаться поистине спасительной. Простые числа p и q должны быть одного и того же размера. Чтобы по- лучить k -битовое число n , можно просто сгенерировать два случайных k/ 2 - битовых простых числа и перемножить их. Иногда в результате такого умно- жения мы можем получить ( k − 1) -битовое число n , но это несущественно. 13.4.5 Генерация ключей RSA Чтобы подытожить сказанное выше, рассмотрим две функции, которые генерируют ключи RSA, обладающие необходимыми свойствами. Первая из них представляет собой модификацию функции GenerateLargePrime , опи- санной в разделе 11.4. Единственное функциональное изменение — это появ- ление условий p mod 3 6 = 1 и p mod 5 6 = 1 , которые гарантируют, что мы можем использовать открытые показатели степеней 3 и 5. Разумеется, если в качестве e будут применяться другие значения, указанные условия необхо- димо подкорректировать. функция GenerateRSAPrime вход: k Размер требующегося простого числа в битах. выход: p Случайное простое число из интервала 2 k − 1 , . . . , 2 k − 1 , удо- влетворяющее условию p mod 3 6 = 1 ∧ p mod 5 6 = 1 . |