Montgomery mulitply

[TigrOm]

Широко применяется при RSA encryption/decryption.
Есть ли методы еще большего ускорения работы алгоритма чем те что широко применяются в реализациях? (например http://bouncycastle.org)

При размере ключа RSA - 1024, блок размером 500 кб дешифруется около 7 минут. Профилирование показывает расход 80% времени на Montgomery mulitply. Как побороть проблему?

Кто в курсе помогите.


п.с. Встроенная в Microsoft CryptoAPI вообще не имеет RSA-1024 для осей ниже XP.

[noone]

из оптимизаций рса знаю только алгоритм crt... (chinese reminder theorem вроде расифровывается)...

[TigrOm]

Она лежит в основе многих крипто алг. в том числе и Montgomery mulitply. Насколько понимаю.

все равно спасибо

[noone]

использование sse,sse2 и т.п...

[TigrOm]

что такое sse?

[AvDav]

Streaming SIMD Extensions, nabor kommand dlia operaciy s plavayushei tochkoi dlia processorov Intel & AMD. Toka oni ne vo vsex processorax est, skajem v Pentium 2 po moemu net, da i v nekotorix P 3.

[AvDav]

Есть такой алгоритм быстрого умножения Тоома-Кука, не знаю правда он лучше или хуже этого.

[knightmare]

Может это.

Методы «быстрого умножения» – например, методы основанные на Быстром Преобразовании Фурье (FFT – Fast Fourier Transform) – выполняются меньшим количеством шагов; тем не менее они не получили широкого распространения из-за сложности программного обеспечения, а также потому, что с типичными размерами ключей они фактически работают медленнее. Однако производительность и эффективность приложений и оборудования реализующих алгоритм RSA быстро увеличиваются.