How to use OpenSSL to extend {D,E,N} RSA key to {D,E,N,p,q,etc.}?

Question

I have an RSA key consisting of the public & private factors and the modulus D. (I'm currently generating and using the key with a JavaScript library.) I would like to use the same key to perform encryptions & decryptions with OpenSSL. I can plug my factors into an OpenSSL RSA key and everything works, but I'd like to have OpenSSL calculate the auxiliary factors it uses (if available) to speed up operations.

I'm not sure whether it's even mathematically possible to work back from {D,E,N} to those factors, but if it is, I'd like to know how to ask libopenssl to do it.

Thanks!

Reinier Torenbeek · Accepted Answer · 2020-11-14 05:41:04Z

7

The algorithm for deriving p and q from the secret d is very easy and fast, though probabilistic. It is explained very briefly in Chapter 8 of "Handbook of applied cryptography", section 8.2.2, or in Boneh's article "Twenty Years of Attacks on the RSA Cryptosystem", page 205.

You could find first an implementation of the algorithm in a high level language (for instance in Python, check the function rsa_construct in PyCrypto). From there, you can implement it via OpenSSL using its multiprecision API.

edited Nov 14, 2020 at 5:41

Reinier Torenbeek

17.2k8 gold badges48 silver badges71 bronze badges

answered Aug 9, 2012 at 18:44

SquareRootOfTwentyThree

7,72634 silver badges43 bronze badges

Thanks for the PyCrypto link -- it appears to do exactly what I want (try to compute P & Q from D & N). I just wish there was an OpenSSL function: RSA_augment_key( rsa ). I guess I'll have to write it!
– Dave M.
Commented Aug 9, 2012 at 21:00
1

Here's code to do it, in more-or-less OpenSSL format. (Also submitted to openssl-dev.)
– Dave M.
Commented Aug 10, 2012 at 5:02

Add a comment |

Dave M. · Accepted Answer · 2012-08-11 01:28:26Z

/* crypto/rsa/rsa_aug_key.c  -*- Mode: C; c-file-style: "eay" -*- */
/* ====================================================================
 * Copyright (c) 1999 The OpenSSL Project.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer. 
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. All advertising materials mentioning features or use of this
 *    software must display the following acknowledgment:
 *    "This product includes software developed by the OpenSSL Project
 *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
 *
 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
 *    endorse or promote products derived from this software without
 *    prior written permission. For written permission, please contact
 *    [email protected].
 *
 * 5. Products derived from this software may not be called "OpenSSL"
 *    nor may "OpenSSL" appear in their names without prior written
 *    permission of the OpenSSL Project.
 *
 * 6. Redistributions of any form whatsoever must retain the following
 *    acknowledgment:
 *    "This product includes software developed by the OpenSSL Project
 *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
 *
 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 * ====================================================================
 */

#include <openssl/bn.h>
#include <openssl/err.h>
#include <openssl/rsa.h>

/*
 * If key has d, e and n, but not p, q, dmp1, dmq1 and iqmp, try
 * to calculate these extra factors.  Return 1 on success or 0
 * on failure.  (The key may still be useable even if this fails.)
 */
int RSA_augment_key(RSA *key)
{
    int      spotted;
    BN_CTX  *ctx;
    BIGNUM  *ktot;
    BIGNUM  *t;
    BIGNUM  *tmp;
    BIGNUM  *a;
    BIGNUM  *two;
    BIGNUM  *l00;
    BIGNUM  *cand;
    BIGNUM  *k;
    BIGNUM  *n_1;

    if (!key || !key->d || !key->e || !key->n) return 0;

    spotted = 0;

    ctx    = BN_CTX_new( );
    ktot   = BN_new( );
    t      = BN_new( );
    tmp    = BN_new( );
    a      = 0; BN_dec2bn( &a,   "2" );
    two    = 0; BN_dec2bn( &two, "2" );
    l00    = 0; BN_dec2bn( &l00, "100" );
    cand   = BN_new( );
    k      = BN_new( );
    n_1    = BN_new( ); if (!BN_sub( n_1, key->n, BN_value_one( ) )) goto fail;

/* Python-code comments from PyCrypto
// ------------------------------------------------------------------
//      # Compute factors p and q from the private exponent d.
//      # We assume that n has no more than two factors.
//      # See 8.2.2(i) in Handbook of Applied Cryptography.
//      ktot = d*e-1*/

    if (!BN_mul( tmp, key->d, key->e, ctx ))    goto fail;
    if (!BN_sub( ktot, tmp, BN_value_one( ) ))  goto fail;

/*      # The quantity d*e-1 is a multiple of phi(n), even,
//      # and can be represented as t*2^s.
//      t = ktot */

    if (!BN_copy( t, ktot ))                    goto fail;

/*      while t%2==0:
//          t=divmod(t,2)[0] */

    while (!BN_is_odd( t ))
        if (!BN_rshift1( t, t ))                goto fail;

/*      # Cycle through all multiplicative inverses in Zn.
//      # The algorithm is non-deterministic, but there is a 50% chance
//      # any candidate a leads to successful factoring.
//      # See "Digitalized Signatures and Public Key Functions as Intractable
//      # as Factorization", M. Rabin, 1979
//      spotted = 0
//      a = 2

//      while not spotted and a<100: */
    while (!spotted && BN_cmp( a, l00 ) < 0) {

/*          k = t */
        if (!BN_copy( k, t ))                   goto fail;

/*          # Cycle through all values a^{t*2^i}=a^k
//          while k<ktot: */
        while (BN_cmp( k, ktot ) < 0) {

/*              cand = pow(a,k,n) */
            if (!BN_mod_exp( cand, a, k, key->n, ctx ))         goto fail;

/*              # Check if a^k is a non-trivial root of unity (mod n)
//              if cand!=1 and cand!=(n-1) and pow(cand,2,n)==1: */
            if (BN_cmp( cand, BN_value_one( ) ) && BN_cmp( cand, n_1 )) {
                if (!BN_mod_exp( tmp, cand, two, key->n, ctx )) goto fail;
                if (BN_cmp( tmp, BN_value_one( )) == 0) {
/*                  # We have found a number such that (cand-1)(cand+1)=0 (mod n).
//                  # Either of the terms divides n.
//                  obj.p = GCD(cand+1,n)
//                  spotted = 1
//                  break */
                    key->p = BN_new( );
                    if (!BN_add( tmp, cand, BN_value_one( ) ))  goto fail;
                    if (!BN_gcd( key->p, tmp, key->n, ctx ))    goto fail;
                    spotted = 1;
                    break;
                }
            }

//              k = k*2
            if (!BN_lshift1( k, k ))          goto fail;
        }

/*          # This value was not any good... let's try another!
//          a = a+2 */
        if (!BN_add( a, a, two ))               goto fail;
    }

    if (!spotted) {
        /* Unable to compute factors P and Q from exponent D */
        goto fail;
    }

    key->q = BN_new( );
    if (!BN_div( key->q, tmp, key->n, key->p, ctx ))    goto fail;
    if (!BN_is_zero( tmp )) {
        /* Curses!  Tricked with a bogus P! */
        goto fail;
    }

    key->dmp1 = BN_new( );
    key->dmq1 = BN_new( );
    key->iqmp = BN_new( );

    if (!BN_sub( tmp, key->p, BN_value_one( ) ))            goto fail;
    if (!BN_mod( key->dmp1, key->d, tmp, ctx ))             goto fail;
    if (!BN_sub( tmp, key->q, BN_value_one( ) ))            goto fail;
    if (!BN_mod( key->dmq1, key->d, tmp, ctx ))             goto fail;
    if (!BN_mod_inverse( key->iqmp, key->q, key->p, ctx ))  goto fail;

    if (RSA_check_key( key ) == 1)                          goto cleanup;

  fail:
    BN_free( key->p );     key->p = 0;
    BN_free( key->q );     key->q = 0;
    BN_free( key->dmp1 );  key->dmp1 = 0;
    BN_free( key->dmq1 );  key->dmq1 = 0;
    BN_free( key->iqmp );  key->iqmp = 0;
    spotted = 0;

  cleanup:
    BN_free( k );
    BN_free( cand );

    BN_free( n_1 );
    BN_free( l00 );
    BN_free( two );

    BN_free( a );

    BN_free( tmp );
    BN_free( t );
    BN_free( ktot );

    BN_CTX_free( ctx );

    return spotted;
}

note: in Python a=b binds name a to whatever object the name b refers to. No copying is involved. Two names for the same object in memory. It seems BN_copy(a, b) is not a good approximation of that semantic. — jfs, Commented Aug 10, 2012 at 5:23
I don't speak Python, and this is my first foray into OpenSSL, so the code is probably suboptimal. However, the BNs are all manipulated via pointers, and the docs are pretty clear that only specifically identified operations can have an operand as the result. You'd think rshift and lshift would, but I don't think they're on the list. Anyway, I was using BN_copy prophylactically: I assumed that just assigning the pointers would cause a memory leak. — Dave M., Commented Aug 10, 2012 at 19:17
the man page explicitly says: "For the shift functions, r and a may be the same variable." Apart from the shift operations other BN_copy() calls seems to be justified. — jfs, Commented Aug 10, 2012 at 20:13

Chris Dodd · Accepted Answer · 2012-08-09 18:17:56Z

Hard problem. To find p and q from n, you need to factor n, which is hard. Given that you know both d and e, you could instead look for a large factor of de-1, which would be phi(n). Once you have that you can take advantage of the fact that, n - phi(n) = p + q - 1 for RSA keys, and thus find p and q

So the process is roughly:

Try to guess x in de-1 = x phi(n). Sine e = 65537 for RSA, this shouldn't be too bad -- x has to be somewhere in the range 50000..200000 or so, so it should only require 100K or so trial divisions.
Now find y = (p + q)/2 = (n + phi(n) + 1)/2 and z = sqrt(yy - n), which gives you p = y+z and q = y-z

Relatively straight-forward, but there's no built-in way of doing this with openssl or any other library I'm aware of.

Collectives™ on Stack Overflow

How to use OpenSSL to extend {D,E,N} RSA key to {D,E,N,p,q,etc.}?

3 Answers 3

Not the answer you're looking for? Browse other questions tagged
c++
c
cryptography
openssl
rsa
or ask your own question.

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

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

Related

Not the answer you're looking for? Browse other questions tagged
c++
c
cryptography
openssl
rsa
or ask your own question.