Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to make the RSA structure of Openssl manually, knowing the public key ($n$, $e$) and the CRT parameters $p$, $q$, $d_P$, $d_Q$, and $u = q^{-1} \mod p$.

That is, I want to get the $d$ value (private exponent) of the RSA structure by using Openssl API. If there are already any implemented functions, it would be great to me.

share|improve this question
    
1) Do you know e? Different es result in different ds. 2) How did you end up with knowing all those values but not knowing d? – CodesInChaos Oct 1 '14 at 9:30
    
if you use a standard $e$ it is quite easy to recover the $d$ exponent. (but at the moment I dont remember if there is a direct function in OpenSSL API) – ddddavidee Oct 1 '14 at 9:59
    
I am supposed to receive N,E,P,Q,DP1,. and etc, except for the D value. With the values (N,E,D), I should test encryption/decripton. – GT Kim Oct 1 '14 at 10:15
2  
Compute $\phi = (P-1)(Q-1)$ and then the modular multiplicative inverse of $e$ using extended euclidean. – CodesInChaos Oct 1 '14 at 10:56
    
Thanks, I will try it. – GT Kim Oct 1 '14 at 11:56

Calculate $\phi(n) = (p-1) (q-1) = n - p - q + 1$. Then $d = e^{-1} \mod \phi(n)$.

With OpenSSL, the code should look something like this (error checking omitted):

BN_CTX *ctx = BN_ctx_new();
BIGNUM *d = BN_dup(n);
BN_sub(d, d, p);
BN_sub(d, d, q);
BN_add_word(d, 1);
BN_mod_inverse(d, e, d);
BN_ctx_free(ctx);
return d;

The inverse calculation is less straightforward. There's a good description in Twenty Years of Attacks on the RSA Cryptosystem by Dan Boneh (Fact 1).

share|improve this answer
    
Thank you, Gilles. Your codes helped me greatly. :) – GT Kim Oct 2 '14 at 2:09
1  
BN_mod_inverse(d,e,n) should be BN_mod_inverse(d,e,d) because the value in d is the euler totient phi(n). – Frank Zonneveld May 19 at 12:06

For completeness, here is how to compute $d$ without resorting to the value of public exponent $e$.

  1. Compute $\delta = \gcd(p-1,q-1)$;
  2. Define $p' = p-1$ and $q' = (q-1)/\delta$;
  3. Compute $i_{q'} = (q')^{-1} \bmod p'$ and $d_{q'} = d_q \bmod q'$;
  4. Return $d = d_{q'} + q'[i_{q'} (d_{p}-d_{q'}) \bmod p']$.

Note that the so-obtained value for $d$ is defined modulo $\lambda(N)=p'q'$ (i.e., the Carmichael function of $N$). If the implementation requires a private exponent $d$ of a larger size, adding any multiple of $p'q'$ gives another valid private exponent.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.