Montgomery mulitply

TigrOm · Oct 9, 2006, 10:57

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

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

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

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

noone · Oct 9, 2006, 11:30

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

TigrOm · Oct 9, 2006, 11:55

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

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

noone · Oct 9, 2006, 11:58

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

TigrOm · Oct 9, 2006, 12:08

что такое sse?

AvDav · Oct 9, 2006, 15:03

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 · Oct 9, 2006, 15:20

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

knightmare · Oct 9, 2006, 16:05

Может это.

Quote:

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

Oct 9, 2006, 10:57	#1
TigrOm --- Join Date: Jun 2004 Location: Yerevan Posts: 8,846 Blog Entries: 1 Rep Power: 5 Reputation: 319	Montgomery mulitply Широко применяется при RSA encryption/decryption. Есть ли методы еще большего ускорения работы алгоритма чем те что широко применяются в реализациях? (например http://bouncycastle.org) При размере ключа RSA - 1024, блок размером 500 кб дешифруется около 7 минут. Профилирование показывает расход 80% времени на Montgomery mulitply. Как побороть проблему? Кто в курсе помогите. п.с. Встроенная в Microsoft CryptoAPI вообще не имеет RSA-1024 для осей ниже XP.

Oct 9, 2006, 11:30	#2
noone ...overwined... Join Date: Mar 2003 Location: ...tortuga... Posts: 3,372 Rep Power: 6 Reputation: 134	из оптимизаций рса знаю только алгоритм crt... (chinese reminder theorem вроде расифровывается)... __________________ ...let's be gods... let's by ugly...

Oct 9, 2006, 11:58	#4
noone ...overwined... Join Date: Mar 2003 Location: ...tortuga... Posts: 3,372 Rep Power: 6 Reputation: 134	использование sse,sse2 и т.п... __________________ ...let's be gods... let's by ugly...

Oct 9, 2006, 15:03	#6
AvDav Дикообраз-безобраз Join Date: Jul 2004 Location: У самого синего моря Posts: 2,508 Rep Power: 4 Reputation: 44	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. __________________ Forza Alb-Violeţii.

Oct 9, 2006, 15:20	#7
AvDav Дикообраз-безобраз Join Date: Jul 2004 Location: У самого синего моря Posts: 2,508 Rep Power: 4 Reputation: 44	Есть такой алгоритм быстрого умножения Тоома-Кука, не знаю правда он лучше или хуже этого. __________________ Forza Alb-Violeţii.

Oct 9, 2006, 11:55	#3
TigrOm --- Join Date: Jun 2004 Location: Yerevan Posts: 8,846 Blog Entries: 1 Rep Power: 5 Reputation: 319	Она лежит в основе многих крипто алг. в том числе и Montgomery mulitply. Насколько понимаю. все равно спасибо

Oct 9, 2006, 12:08	#5
TigrOm --- Join Date: Jun 2004 Location: Yerevan Posts: 8,846 Blog Entries: 1 Rep Power: 5 Reputation: 319	что такое sse?

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode