On Tue, Jul 31, 2001 at 08:26:42PM -0700, Yongdae Kim wrote: > I think my question is basically "how much more expensive modular > exponentiation is compared to modular multiplication for the given > parameters using OpenSSL library?"... And my simulation shows that it is > around 80 times... >> The number of squarings remains about the same, but many >> general multiplications can be saved. > I think squaring should be roughly as expensive as multiplication of two > same numbers... Nearly, yes. > So we still need at least 160 1024-bit multiplication... So > I think 80 times is way smaller than I expected... Any think? As I explained, BN_mod_exp uses Montgomery representation. This makes each modular multiplication a lot faster. *Single* modular multiplications cannot profit from Montgomery representation because there's a cost in converting the input into Montgomery representation, and converting the result back in the end. Modular exponentiation uses many multiplications, but each conversion is needed just once, so (for large exponents) it pays out to use Montgomery representation. -- Bodo Möller <[EMAIL PROTECTED]> PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html * TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt * Tel. +49-6151-16-6628, Fax +49-6151-16-6036 ______________________________________________________________________ OpenSSL Project http://www.openssl.org User Support Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
