Montgomery modular exponentiation in OpenSSL.
Hi all, 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]
Re: Doc. relative to BN functions ?
Hi, I'll be answering both answers to my mail in this mail. First, thanks guys for your answers. simple google.com search on sliding window montgomergy shows at least two pointers: http://citeseer.nj.nec.com/kaya96analyzing.html http://users.belgacom.net/dhem/these/ Ok, thanks for the pointers. Actually, I do not really lack the theoretical approach of Montgomery or sliding windows, as I've downloaded many papers on the subject, but there's really a difference between the algorithm.. and the actual implementation in OpenSSL... If you install OpenSSL 0.9.7 then you install several manual pages too. They are placed in sections 3. You can also go to openssl-0.9.7a/doc/crypto/ and use perldoc -F BN_*. Thanks, this will be quite helpful, I hadn't seen those... Cheers, Axelle. __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Doc. relative to BN functions ?
Hi, I'm trying to understand the code that is written in openssl/crypto/bn. I have found some old documentation at http://www.columbia.edu/~ariel/ssleay/cryptosupp_index.html, but this is incomplete. I'd like to find some developer level documentation explaining how to use the BN_xxx functions, and basically how they are implemented. For instance: - what's the use of the BN_CTX structure ? Is it to maintain sort of a pool of BIGNUMs instead of always allocating new BIGNUMs ? what do the tos,pos, depth and too_many fields mean ? what's the correct way of using the BN_CTX_ functions (declare a BN_CTX * pointer, do a BN_CTX_start on it, retrieve an available buffer with BN_CTX_get...) - is there some explanation step by step of the bn_mod_exp_mont function (in bn_exp.c) ? I've got the reference algorithms of Montgomery just next to me (in chap 14 of Handbook of Applied Cryptography), but I'm quite lost at matching the steps with the actual coding. - the bn_mod_exp_mont() function uses a window. Is there a link to the sliding window technique the Handbook of Applied Crypto talks about ? Thanks Axelle. __ OpenSSL Project http://www.openssl.org Development Mailing List [EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
