raw
smg_comms_c_wrappers    1 /*
smg_comms_c_wrappers    2  * An implementation of TMSR RSA
smg_comms_c_wrappers    3  * S.MG, 2018
smg_comms_c_wrappers    4  */
smg_comms_c_wrappers    5 
smg_comms_c_wrappers    6 #include "smg_rsa.h"
smg_comms_c_wrappers    7 #include <assert.h>
smg_comms_c_wrappers    8 
smg_comms_c_wrappers    9 void gen_keypair( RSA_secret_key *sk ) {
smg_comms_c_wrappers   10 	/* precondition: sk is not null */
smg_comms_c_wrappers   11 	assert(sk != NULL);
smg_comms_c_wrappers   12 
smg_comms_c_wrappers   13 	/* precondition: enough memory allocated, corresponding to key size */
smg_comms_c_wrappers   14 	int noctets_pq = KEY_LENGTH_OCTETS / 2;
smg_comms_c_wrappers   15 	unsigned int nlimbs_pq = mpi_nlimb_hint_from_nbytes( noctets_pq);
smg_comms_c_wrappers   16 	unsigned int nlimbs_n = mpi_nlimb_hint_from_nbytes( KEY_LENGTH_OCTETS);
smg_comms_c_wrappers   17 	assert( mpi_get_alloced( sk->n) >= nlimbs_n);
smg_comms_c_wrappers   18 	assert( mpi_get_alloced( sk->p) >= nlimbs_pq);
smg_comms_c_wrappers   19 	assert( mpi_get_alloced( sk->q) >= nlimbs_pq);
smg_comms_c_wrappers   20 
smg_comms_c_wrappers   21 	/* helper variables for calculating Euler's totient phi=(p-1)*(q-1) */
smg_comms_c_wrappers   22 	MPI p_minus1 = mpi_alloc(nlimbs_pq);
smg_comms_c_wrappers   23 	MPI q_minus1 = mpi_alloc(nlimbs_pq);
smg_comms_c_wrappers   24 	MPI phi = mpi_alloc(nlimbs_n);
smg_comms_c_wrappers   25 
smg_comms_c_wrappers   26 	/* generate 2 random primes, p and q*/
smg_comms_c_wrappers   27 	/* gen_random_prime sets top 2 bits to 1 so p*q will have KEY_LENGTH bits */
smg_comms_c_wrappers   28 	/* in the extremely unlikely case that p = q, discard and generate again */
smg_comms_c_wrappers   29 	do {
smg_comms_c_wrappers   30 		gen_random_prime( noctets_pq, sk->p);
smg_comms_c_wrappers   31 		gen_random_prime( noctets_pq, sk->q);
smg_comms_c_wrappers   32 	} while ( mpi_cmp( sk->p, sk->q) == 0);
smg_comms_c_wrappers   33 
smg_comms_c_wrappers   34 	/* swap if needed, to ensure p < q for calculating u */
smg_comms_c_wrappers   35 	if ( mpi_cmp( sk->p, sk->q) > 0)
smg_comms_c_wrappers   36 		mpi_swap( sk->p, sk->q);
smg_comms_c_wrappers   37 
smg_comms_c_wrappers   38 	/* calculate helper for Chinese Remainder Theorem:
smg_comms_c_wrappers   39 			u = p ^ -1 ( mod q )
smg_comms_c_wrappers   40 		 this is used to speed-up decryption.
smg_comms_c_wrappers   41 	*/
smg_comms_c_wrappers   42 	mpi_invm( sk->u, sk->p, sk->q);
smg_comms_c_wrappers   43 
smg_comms_c_wrappers   44 	/* calculate modulus n = p * q */
smg_comms_c_wrappers   45 	mpi_mul( sk->n, sk->p, sk->q);
smg_comms_c_wrappers   46 
smg_comms_c_wrappers   47 	/* calculate Euler totient: phi = (p-1)*(q-1) */
smg_comms_c_wrappers   48 	mpi_sub_ui( p_minus1, sk->p, 1);
smg_comms_c_wrappers   49 	mpi_sub_ui( q_minus1, sk->q, 1);
smg_comms_c_wrappers   50 	mpi_mul( phi, p_minus1, q_minus1);
smg_comms_c_wrappers   51 
smg_comms_c_wrappers   52 	/* choose random prime e, public exponent, with 3 < e < phi */
smg_comms_c_wrappers   53 	/* because e is prime, gcd(e, phi) is always 1 so no need to check it */
smg_comms_c_wrappers   54 	do {
smg_comms_c_wrappers   55 		gen_random_prime( noctets_pq, sk->e);
smg_comms_c_wrappers   56 	} while ( (mpi_cmp_ui(sk->e, 3) < 0) || (mpi_cmp(sk->e, phi) > 0));
smg_comms_c_wrappers   57 
smg_comms_c_wrappers   58 	/* calculate private exponent d, 1 < d < phi, where e * d = 1 mod phi */
smg_comms_c_wrappers   59 	mpi_invm( sk->d, sk->e, phi);
smg_comms_c_wrappers   60 
smg_comms_c_wrappers   61 	/*	tidy up: free locally allocated memory for helper variables */
smg_comms_c_wrappers   62 	mpi_free(phi);
smg_comms_c_wrappers   63 	mpi_free(p_minus1);
smg_comms_c_wrappers   64 	mpi_free(q_minus1);
smg_comms_c_wrappers   65 }
smg_comms_c_wrappers   66 
smg_comms_c_wrappers   67 void public_rsa( MPI output, MPI input, RSA_public_key *pk ) {
smg_comms_c_wrappers   68 
smg_comms_c_wrappers   69 	/* mpi_powm can't handle output and input being same */
smg_comms_c_wrappers   70 	assert (output != input);
smg_comms_c_wrappers   71 
smg_comms_c_wrappers   72   /* the actual rsa op */
smg_comms_c_wrappers   73 	mpi_powm( output, input, pk->e, pk->n );
smg_comms_c_wrappers   74 
smg_comms_c_wrappers   75 }
smg_comms_c_wrappers   76 
smg_comms_c_wrappers   77 void secret_rsa( MPI output, MPI input, RSA_secret_key *skey ) {
smg_comms_c_wrappers   78 	/* at its simplest, this would be input ^ d (mod n), hence:
smg_comms_c_wrappers   79 	 *    mpi_powm( output, input, skey->d, skey->n );
smg_comms_c_wrappers   80 	 * for faster decryption though, we'll use CRT and Garner's algorithm, hence:
smg_comms_c_wrappers   81 	 *        u = p ^ (-1) (mod q) , already calculated and stored in skey
smg_comms_c_wrappers   82 	 *       dp = d mod (p-1)
smg_comms_c_wrappers   83 	 *       dq = d mod (q-1)
smg_comms_c_wrappers   84 	 *       m1 = input ^ dp (mod p)
smg_comms_c_wrappers   85 	 *       m2 = input ^ dq (mod q)
smg_comms_c_wrappers   86 	 *        h = u * (m2 - m1) mod q
smg_comms_c_wrappers   87 	 *   output = m1 + h * p
smg_comms_c_wrappers   88    * Note that same CRT speed up isn't available for encryption because at 
smg_comms_c_wrappers   89 encryption time not enough information is available (only e and n are known).
smg_comms_c_wrappers   90 	 */
smg_comms_c_wrappers   91 
smg_comms_c_wrappers   92 	/* allocate memory for all local, helper MPIs */
smg_comms_c_wrappers   93 	MPI p_minus1 = mpi_alloc( mpi_get_nlimbs( skey->p) );
smg_comms_c_wrappers   94 	MPI q_minus1 = mpi_alloc( mpi_get_nlimbs( skey->q) );
smg_comms_c_wrappers   95 	int nlimbs   = mpi_get_nlimbs( skey->n ) + 1;
smg_comms_c_wrappers   96 	MPI dp       = mpi_alloc( nlimbs );
smg_comms_c_wrappers   97 	MPI dq       = mpi_alloc( nlimbs );
smg_comms_c_wrappers   98 	MPI m1       = mpi_alloc( nlimbs );
smg_comms_c_wrappers   99 	MPI m2       = mpi_alloc( nlimbs );
smg_comms_c_wrappers  100 	MPI h        = mpi_alloc( nlimbs );
smg_comms_c_wrappers  101 
smg_comms_c_wrappers  102 	/* p_minus1 = p - 1 */
smg_comms_c_wrappers  103 	mpi_sub_ui( p_minus1, skey->p, 1 );
smg_comms_c_wrappers  104 
smg_comms_c_wrappers  105 	/* dp = d mod (p - 1) aka remainder of d / (p - 1) */
smg_comms_c_wrappers  106 	mpi_fdiv_r( dp, skey->d, p_minus1 );
smg_comms_c_wrappers  107 
smg_comms_c_wrappers  108 	/* m1 = input ^ dp (mod p) */
smg_comms_c_wrappers  109 	mpi_powm( m1, input, dp, skey->p );
smg_comms_c_wrappers  110 
smg_comms_c_wrappers  111 	/* q_minus1 = q - 1 */
smg_comms_c_wrappers  112 	mpi_sub_ui( q_minus1, skey->q, 1 );
smg_comms_c_wrappers  113 
smg_comms_c_wrappers  114 	/* dq = d mod (q - 1) aka remainder of d / (q - 1) */
smg_comms_c_wrappers  115 	mpi_fdiv_r( dq, skey->d, q_minus1 );
smg_comms_c_wrappers  116 
smg_comms_c_wrappers  117 	/* m2 = input ^ dq (mod q) */
smg_comms_c_wrappers  118 	mpi_powm( m2, input, dq, skey->q );
smg_comms_c_wrappers  119 
smg_comms_c_wrappers  120 	/* h = u * ( m2 - m1 ) mod q */
smg_comms_c_wrappers  121 	mpi_sub( h, m2, m1 );
smg_comms_c_wrappers  122 	if ( mpi_is_neg( h ) )
smg_comms_c_wrappers  123 		mpi_add ( h, h, skey->q );
smg_comms_c_wrappers  124 	mpi_mulm( h, skey->u, h, skey->q );
smg_comms_c_wrappers  125 
smg_comms_c_wrappers  126 	/* output = m1 + h * p */
smg_comms_c_wrappers  127 	mpi_mul ( h, h, skey->p );
smg_comms_c_wrappers  128 	mpi_add ( output, m1, h );
smg_comms_c_wrappers  129 
smg_comms_c_wrappers  130 	/* tidy up */
smg_comms_c_wrappers  131 	mpi_free ( p_minus1 );
smg_comms_c_wrappers  132 	mpi_free ( q_minus1 );
smg_comms_c_wrappers  133 	mpi_free ( dp );
smg_comms_c_wrappers  134 	mpi_free ( dq );
smg_comms_c_wrappers  135 	mpi_free ( m1 );
smg_comms_c_wrappers  136 	mpi_free ( m2 );
smg_comms_c_wrappers  137 	mpi_free ( h );
smg_comms_c_wrappers  138 
smg_comms_c_wrappers  139 }
smg_comms_c_wrappers  140