Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 09.10.2006, 11:57   #1
Академик
 
TigrOm's Avatar
 
Join Date: 06 2004
Location: Yerevan
Posts: 9,326
Downloads: 3
Uploads: 0
Reputation: 680 | 5
Default Montgomery mulitply

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

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

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


п.с. Встроенная в Microsoft CryptoAPI вообще не имеет RSA-1024 для осей ниже XP.
Reply With Quote
Old 09.10.2006, 12:30   #2
...overwined...
 
noone's Avatar
 
Join Date: 03 2003
Location: ...tortuga...
Posts: 3,429
Downloads: 3
Uploads: 0
Reputation: 158 | 3
Default

из оптимизаций рса знаю только алгоритм crt... (chinese reminder theorem вроде расифровывается)...
Reply With Quote
Old 09.10.2006, 12:55   #3
Академик
 
TigrOm's Avatar
 
Join Date: 06 2004
Location: Yerevan
Posts: 9,326
Downloads: 3
Uploads: 0
Reputation: 680 | 5
Default

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

все равно спасибо
Reply With Quote
Old 09.10.2006, 12:58   #4
...overwined...
 
noone's Avatar
 
Join Date: 03 2003
Location: ...tortuga...
Posts: 3,429
Downloads: 3
Uploads: 0
Reputation: 158 | 3
Default

использование sse,sse2 и т.п...
Reply With Quote
Old 09.10.2006, 13:08   #5
Академик
 
TigrOm's Avatar
 
Join Date: 06 2004
Location: Yerevan
Posts: 9,326
Downloads: 3
Uploads: 0
Reputation: 680 | 5
Default

что такое sse?
Reply With Quote
Old 09.10.2006, 16:03   #6
The splendid
 
AvDav's Avatar
 
Join Date: 07 2004
Location: Universe
Age: 36
Posts: 3,413
Downloads: 22
Uploads: 0
Reputation: 222 | 3
Default

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.
Reply With Quote
Old 09.10.2006, 16:20   #7
The splendid
 
AvDav's Avatar
 
Join Date: 07 2004
Location: Universe
Age: 36
Posts: 3,413
Downloads: 22
Uploads: 0
Reputation: 222 | 3
Default

Есть такой алгоритм быстрого умножения Тоома-Кука, не знаю правда он лучше или хуже этого.
Reply With Quote
Old 09.10.2006, 17:05   #8
Какое небо, *, Багдад!
 
knightmare's Avatar
 
Join Date: 10 2005
Location: Ереван
Posts: 1,682
Downloads: 16
Uploads: 0
Reputation: 99 | 3
Default

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

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 14:05.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.