I come back with some more questions regarding modular exponentation as it is implemented in OpenSSL.
- about BN_MONT_CTX_set in bn_mont.c:
The idea here is basically to fill in the montgomery context with the right initial values, specially we need to compute Ni such that R.R^-1 - N.Ni = 1.
Actually, it's implemented quite 'directly' requiring calculation of a modular inverse and a modular division.
Wouldn't it be better to use the "Binary Extended GCD Algorithm" to retrieve Ni (and R^-1) ? [1, paragraph 14.4.3]
- about BN_mod_exp_mont in bn_exp.c:
* Am I right that what is being implemented here exactly in modular exponentiation using a sliding window technique over
Montgomery modular multiplication ? [2, paragraph 2.5.2]
* I understand basically the beginning of the algorithm (up until lign 414), but then honestly I'm quite lost. What are we trying to store in the various val[i] ? various powers of a ?
* would somebody have the reference of the exact algorithm that is being used here ? For instance, in [2,paragraph 3.8.1] I have the algorithm of Montgomery exponentiation using the binary method, but not using sliding windows (which is what is being used here -- to my understanding).
* what's the use for a BN_mod_exp_mont and a BN_mod_exp_mont_word function ?
Many thanks Axelle.
[1] "Handbook of Applied Cryptography" - Menezes, van Oorschot, Vanstone
[2] "High Speed RSA Implementation", Koc - (http://islab.oregonstate.edu/publications.html)
______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
