RSA CRT parameters? #574

Activity

1. Ivoz commented on Feb 7, 2014

   

   Ivoz

   on Feb 7, 2014

   Contributor

   More actions

   If they're only generated when an RSA private key is instantiated, I don't think it's very slow; certainly not slower than generation of p and q themselves.

   code to generate them is just (assuming an implementation of mod_mul_inv)

       phi = (p - 1) * (q - 1)
       # d = pow(e, phi - 1, phi)
       d = mod_mul_inv(e, phi)
       dp = d % (p - 1)
       dq = d % (q - 1)
       # qinv = pow(q, p - 2, p)
       qinv = mod_mul_inv(q, p)

   def mod_mul_inv(e, m):
       """ Modular Multiplicative Inverse.
           return the value x such that (x*e) mod m == 1 """
       x1, y1, x2, y2 = 1, 0, 0, 1
       a, b = e, m
       while b > 0:
           q, r = divmod(a, b)
           xn, yn = x1 - q * x2, y1 - q * y2
           a, b, x1, y1, x2, y2 = b, r, x2, y2, xn, yn
       return x1 % m
2. public commented on Feb 7, 2014

   

   public

   on Feb 7, 2014

   MemberAuthor

   More actions

   Caching them on the private key object ourselves is indeed an option too. We need some benchmarks :)
3. reaperhulk commented on Feb 8, 2014

   

   reaperhulk

   on Feb 8, 2014

   Member

   More actions

   Per discussion in IRC I support adding these values as required parameters to the constructor. We can loosen this restriction in the future if we decide computing these values in Python is permissible/desirable.
4. reaperhulk

   added

   api design

   on Feb 9, 2014
5. reaperhulk

   added this to the Second Release milestone on Feb 9, 2014
6. alex

   closed this as completedon Feb 16, 2014
7. github-actions

   locked as resolved and limited conversation to collaborators on Aug 31, 2020