raw
eucrypt_ch5_rsa_keys    1 /*
eucrypt_ch5_rsa_keys    2  * An implementation of TMSR RSA
eucrypt_ch5_rsa_keys    3  * S.MG, 2018
eucrypt_ch5_rsa_keys    4  */
eucrypt_ch5_rsa_keys    5 
eucrypt_ch5_rsa_keys    6 #include "smg_rsa.h"
eucrypt_ch5_rsa_keys    7 #include <assert.h>
eucrypt_ch5_rsa_keys    8 
eucrypt_ch5_rsa_keys    9 void gen_keypair( RSA_secret_key *sk ) {
eucrypt_ch5_rsa_keys   10 	/* precondition: sk is not null */
eucrypt_ch5_rsa_keys   11 	assert(sk != NULL);
eucrypt_ch5_rsa_keys   12 
eucrypt_ch5_rsa_keys   13 	/* precondition: enough memory allocated, corresponding to key size */
eucrypt_ch5_rsa_keys   14 	int noctets_pq = KEY_LENGTH_OCTETS / 2;
eucrypt_ch5_rsa_keys   15 	unsigned int nlimbs_pq = mpi_nlimb_hint_from_nbytes( noctets_pq);
eucrypt_ch5_rsa_keys   16 	unsigned int nlimbs_n = mpi_nlimb_hint_from_nbytes( KEY_LENGTH_OCTETS);
eucrypt_ch5_rsa_keys   17 	assert( mpi_get_alloced( sk->n) >= nlimbs_n);
eucrypt_ch5_rsa_keys   18 	assert( mpi_get_alloced( sk->p) >= nlimbs_pq);
eucrypt_ch5_rsa_keys   19 	assert( mpi_get_alloced( sk->q) >= nlimbs_pq);
eucrypt_ch5_rsa_keys   20 
eucrypt_ch5_rsa_keys   21 	/* helper variables for calculating Euler's totient phi=(p-1)*(q-1) */
eucrypt_ch5_rsa_keys   22 	MPI p_minus1 = mpi_alloc(nlimbs_pq);
eucrypt_ch5_rsa_keys   23 	MPI q_minus1 = mpi_alloc(nlimbs_pq);
eucrypt_ch5_rsa_keys   24 	MPI phi = mpi_alloc(nlimbs_n);
eucrypt_ch5_rsa_keys   25 
eucrypt_ch5_rsa_keys   26 	/* generate 2 random primes, p and q*/
eucrypt_ch5_rsa_keys   27 	/* gen_random_prime sets top 2 bits to 1 so p*q will have KEY_LENGTH bits */
eucrypt_ch5_rsa_keys   28 	/* in the extremely unlikely case that p = q, discard and generate again */
eucrypt_ch5_rsa_keys   29 	do {
eucrypt_ch5_rsa_keys   30 		gen_random_prime( noctets_pq, sk->p);
eucrypt_ch5_rsa_keys   31 		gen_random_prime( noctets_pq, sk->q);
eucrypt_ch5_rsa_keys   32 	} while ( mpi_cmp( sk->p, sk->q) == 0);
eucrypt_ch5_rsa_keys   33 
eucrypt_ch5_rsa_keys   34 	/* swap if needed, to ensure p < q for calculating u */
eucrypt_ch5_rsa_keys   35 	if ( mpi_cmp( sk->p, sk->q) > 0)
eucrypt_ch5_rsa_keys   36 		mpi_swap( sk->p, sk->q);
eucrypt_ch5_rsa_keys   37 
eucrypt_ch5_rsa_keys   38 	/* calculate helper for Chinese Remainder Theorem:
eucrypt_ch5_rsa_keys   39 			u = p ^ -1 ( mod q )
eucrypt_ch5_rsa_keys   40 		 this is used to speed-up decryption.
eucrypt_ch5_rsa_keys   41 	*/
eucrypt_ch5_rsa_keys   42 	mpi_invm( sk->u, sk->p, sk->q);
eucrypt_ch5_rsa_keys   43 
eucrypt_ch5_rsa_keys   44 	/* calculate modulus n = p * q */
eucrypt_ch5_rsa_keys   45 	mpi_mul( sk->n, sk->p, sk->q);
eucrypt_ch5_rsa_keys   46 
eucrypt_ch5_rsa_keys   47 	/* calculate Euler totient: phi = (p-1)*(q-1) */
eucrypt_ch5_rsa_keys   48 	mpi_sub_ui( p_minus1, sk->p, 1);
eucrypt_ch5_rsa_keys   49 	mpi_sub_ui( q_minus1, sk->q, 1);
eucrypt_ch5_rsa_keys   50 	mpi_mul( phi, p_minus1, q_minus1);
eucrypt_ch5_rsa_keys   51 
eucrypt_ch5_rsa_keys   52 	/* choose random prime e, public exponent, with 3 < e < phi */
eucrypt_ch5_rsa_keys   53 	/* because e is prime, gcd(e, phi) is always 1 so no need to check it */
eucrypt_ch5_rsa_keys   54 	do {
eucrypt_ch15_arbi...   55 		gen_random_prime( E_LENGTH_OCTETS, sk->e);
eucrypt_ch5_rsa_keys   56 	} while ( (mpi_cmp_ui(sk->e, 3) < 0) || (mpi_cmp(sk->e, phi) > 0));
eucrypt_ch5_rsa_keys   57 
eucrypt_ch5_rsa_keys   58 	/* calculate private exponent d, 1 < d < phi, where e * d = 1 mod phi */
eucrypt_ch5_rsa_keys   59 	mpi_invm( sk->d, sk->e, phi);
eucrypt_ch5_rsa_keys   60 
eucrypt_ch5_rsa_keys   61 	/*	tidy up: free locally allocated memory for helper variables */
eucrypt_ch5_rsa_keys   62 	mpi_free(phi);
eucrypt_ch5_rsa_keys   63 	mpi_free(p_minus1);
eucrypt_ch5_rsa_keys   64 	mpi_free(q_minus1);
eucrypt_ch5_rsa_keys   65 }
eucrypt_ch5_rsa_keys   66 
eucrypt_ch5_rsa_keys   67 void public_rsa( MPI output, MPI input, RSA_public_key *pk ) {
eucrypt_ch5_rsa_keys   68 
eucrypt_ch5_rsa_keys   69 	/* mpi_powm can't handle output and input being same */
eucrypt_ch5_rsa_keys   70 	assert (output != input);
eucrypt_ch5_rsa_keys   71 
eucrypt_ch12_wrap...   72   /* the actual rsa op */
eucrypt_ch5_rsa_keys   73 	mpi_powm( output, input, pk->e, pk->n );
eucrypt_ch12_wrap...   74 
eucrypt_ch5_rsa_keys   75 }
eucrypt_ch5_rsa_keys   76 
eucrypt_ch5_rsa_keys   77 void secret_rsa( MPI output, MPI input, RSA_secret_key *skey ) {
eucrypt_ch5_rsa_keys   78 	/* at its simplest, this would be input ^ d (mod n), hence:
eucrypt_ch5_rsa_keys   79 	 *    mpi_powm( output, input, skey->d, skey->n );
eucrypt_ch5_rsa_keys   80 	 * for faster decryption though, we'll use CRT and Garner's algorithm, hence:
eucrypt_ch5_rsa_keys   81 	 *        u = p ^ (-1) (mod q) , already calculated and stored in skey
eucrypt_ch5_rsa_keys   82 	 *       dp = d mod (p-1)
eucrypt_ch5_rsa_keys   83 	 *       dq = d mod (q-1)
eucrypt_ch5_rsa_keys   84 	 *       m1 = input ^ dp (mod p)
eucrypt_ch5_rsa_keys   85 	 *       m2 = input ^ dq (mod q)
eucrypt_ch5_rsa_keys   86 	 *        h = u * (m2 - m1) mod q
eucrypt_ch5_rsa_keys   87 	 *   output = m1 + h * p
eucrypt_ch5_rsa_keys   88    * Note that same CRT speed up isn't available for encryption because at 
eucrypt_ch5_rsa_keys   89 encryption time not enough information is available (only e and n are known).
eucrypt_ch5_rsa_keys   90 	 */
eucrypt_ch5_rsa_keys   91 
eucrypt_ch5_rsa_keys   92 	/* allocate memory for all local, helper MPIs */
eucrypt_ch5_rsa_keys   93 	MPI p_minus1 = mpi_alloc( mpi_get_nlimbs( skey->p) );
eucrypt_ch5_rsa_keys   94 	MPI q_minus1 = mpi_alloc( mpi_get_nlimbs( skey->q) );
eucrypt_ch5_rsa_keys   95 	int nlimbs   = mpi_get_nlimbs( skey->n ) + 1;
eucrypt_ch5_rsa_keys   96 	MPI dp       = mpi_alloc( nlimbs );
eucrypt_ch5_rsa_keys   97 	MPI dq       = mpi_alloc( nlimbs );
eucrypt_ch5_rsa_keys   98 	MPI m1       = mpi_alloc( nlimbs );
eucrypt_ch5_rsa_keys   99 	MPI m2       = mpi_alloc( nlimbs );
eucrypt_ch5_rsa_keys  100 	MPI h        = mpi_alloc( nlimbs );
eucrypt_ch5_rsa_keys  101 
eucrypt_ch5_rsa_keys  102 	/* p_minus1 = p - 1 */
eucrypt_ch5_rsa_keys  103 	mpi_sub_ui( p_minus1, skey->p, 1 );
eucrypt_ch5_rsa_keys  104 
eucrypt_ch5_rsa_keys  105 	/* dp = d mod (p - 1) aka remainder of d / (p - 1) */
eucrypt_ch5_rsa_keys  106 	mpi_fdiv_r( dp, skey->d, p_minus1 );
eucrypt_ch5_rsa_keys  107 
eucrypt_ch5_rsa_keys  108 	/* m1 = input ^ dp (mod p) */
eucrypt_ch5_rsa_keys  109 	mpi_powm( m1, input, dp, skey->p );
eucrypt_ch5_rsa_keys  110 
eucrypt_ch5_rsa_keys  111 	/* q_minus1 = q - 1 */
eucrypt_ch5_rsa_keys  112 	mpi_sub_ui( q_minus1, skey->q, 1 );
eucrypt_ch5_rsa_keys  113 
eucrypt_ch5_rsa_keys  114 	/* dq = d mod (q - 1) aka remainder of d / (q - 1) */
eucrypt_ch5_rsa_keys  115 	mpi_fdiv_r( dq, skey->d, q_minus1 );
eucrypt_ch5_rsa_keys  116 
eucrypt_ch5_rsa_keys  117 	/* m2 = input ^ dq (mod q) */
eucrypt_ch5_rsa_keys  118 	mpi_powm( m2, input, dq, skey->q );
eucrypt_ch5_rsa_keys  119 
eucrypt_ch5_rsa_keys  120 	/* h = u * ( m2 - m1 ) mod q */
eucrypt_ch5_rsa_keys  121 	mpi_sub( h, m2, m1 );
eucrypt_ch5_rsa_keys  122 	if ( mpi_is_neg( h ) )
eucrypt_ch5_rsa_keys  123 		mpi_add ( h, h, skey->q );
eucrypt_ch5_rsa_keys  124 	mpi_mulm( h, skey->u, h, skey->q );
eucrypt_ch5_rsa_keys  125 
eucrypt_ch5_rsa_keys  126 	/* output = m1 + h * p */
eucrypt_ch5_rsa_keys  127 	mpi_mul ( h, h, skey->p );
eucrypt_ch5_rsa_keys  128 	mpi_add ( output, m1, h );
eucrypt_ch5_rsa_keys  129 
eucrypt_ch5_rsa_keys  130 	/* tidy up */
eucrypt_ch5_rsa_keys  131 	mpi_free ( p_minus1 );
eucrypt_ch5_rsa_keys  132 	mpi_free ( q_minus1 );
eucrypt_ch5_rsa_keys  133 	mpi_free ( dp );
eucrypt_ch5_rsa_keys  134 	mpi_free ( dq );
eucrypt_ch5_rsa_keys  135 	mpi_free ( m1 );
eucrypt_ch5_rsa_keys  136 	mpi_free ( m2 );
eucrypt_ch5_rsa_keys  137 	mpi_free ( h );
eucrypt_ch5_rsa_keys  138 
eucrypt_ch5_rsa_keys  139 }
eucrypt_ch5_rsa_keys  140 
eucrypt_ch12_wrap...  141 void rsa_oaep_encrypt( MPI output, MPI input, RSA_public_key *pk) {
eucrypt_ch12_wrap...  142   /* precondition: output is different from input */
eucrypt_ch12_wrap...  143   assert( output != input );
eucrypt_ch12_wrap...  144 
eucrypt_ch12_wrap...  145   /* precondition: output has enough memory allocated */
eucrypt_ch12_wrap...  146 	unsigned int nlimbs_n = mpi_nlimb_hint_from_nbytes( KEY_LENGTH_OCTETS);
eucrypt_ch12_wrap...  147 	assert( mpi_get_alloced( output ) >= nlimbs_n);
eucrypt_ch12_wrap...  148 
eucrypt_ch12_wrap...  149   /* precondition: input is at most max_len_msg octets long */
eucrypt_ch12_wrap...  150   unsigned int nlimbs_msg = mpi_nlimb_hint_from_nbytes( max_len_msg );
eucrypt_ch12_wrap...  151   assert( mpi_get_nlimbs( input ) <= nlimbs_msg);
eucrypt_ch12_wrap...  152 
eucrypt_ch12_wrap...  153   /* Step 1: oaep padding */
eucrypt_ch12_wrap...  154   /* get message char array and length */
eucrypt_ch12_wrap...  155   int msglen = 0;
eucrypt_ch12_wrap...  156   int sign;
eucrypt_ch12_wrap...  157   unsigned char * msg = mpi_get_buffer( input, &msglen, &sign);
eucrypt_ch12_wrap...  158   /* allocate memory for result */
eucrypt_ch12_wrap...  159   int encrlen = KEY_LENGTH_OCTETS;
eucrypt_ch12_wrap...  160   unsigned char * encr = xmalloc( encrlen );
eucrypt_ch12_wrap...  161   int entlen = KEY_LENGTH_OCTETS;
eucrypt_ch12_wrap...  162   unsigned char * entropy = xmalloc( entlen );
eucrypt_ch12_wrap...  163   int success = -10;
eucrypt_ch12_wrap...  164   /* call oaep until result is strictly < N of the rsa key to use */
eucrypt_ch12_wrap...  165   MPI oaep = mpi_alloc( nlimbs_n ); /* result of oaep encrypt/pad */
eucrypt_ch12_wrap...  166 
eucrypt_ch12_wrap...  167   int nread;
eucrypt_ch12_wrap...  168   do {
eucrypt_ch12_wrap...  169     /* get random bits */
eucrypt_ch12_wrap...  170 		do {
eucrypt_ch12_wrap...  171       nread = get_random_octets( entlen, entropy );
eucrypt_ch12_wrap...  172 		} while (nread != entlen);
eucrypt_ch12_wrap...  173 
eucrypt_ch12_wrap...  174     oaep_encrypt_c( msg, msglen, entropy, entlen, encr, encrlen, &success);
eucrypt_ch12_wrap...  175     if (success > 0) {
eucrypt_ch12_wrap...  176       /* set the obtained oaep to output mpi and compare to N of the rsa key */
eucrypt_ch12_wrap...  177       /* NB: 0-led encr WILL GET TRUNCATED!! */
eucrypt_ch12_wrap...  178       mpi_set_buffer( oaep, encr, encrlen, 0);
eucrypt_ch12_wrap...  179     }
eucrypt_ch12_wrap...  180     printf(".");
eucrypt_ch12_wrap...  181   }
eucrypt_ch12_wrap...  182   while ( success <=0 || mpi_cmp( oaep, pk->n ) >= 0 );
eucrypt_ch12_wrap...  183 
eucrypt_ch12_wrap...  184   printf("\n");
eucrypt_ch12_wrap...  185   /* Step2 : call rsa for final result */
eucrypt_ch12_wrap...  186   public_rsa( output, oaep, pk );
eucrypt_ch12_wrap...  187 
eucrypt_ch12_wrap...  188   /* clear up */
eucrypt_ch12_wrap...  189   xfree( msg );
eucrypt_ch12_wrap...  190   xfree( encr );
eucrypt_ch12_wrap...  191   xfree( entropy );
eucrypt_ch12_wrap...  192   mpi_free( oaep );
eucrypt_ch12_wrap...  193 }
eucrypt_ch12_wrap...  194 
eucrypt_ch12_wrap...  195 void rsa_oaep_decrypt( MPI output, MPI input, RSA_secret_key *sk, int *success)
eucrypt_ch12_wrap...  196 {
eucrypt_ch12_wrap...  197   *success = -1;
eucrypt_ch12_wrap...  198 	unsigned int nlimbs_n = mpi_nlimb_hint_from_nbytes( KEY_LENGTH_OCTETS);
eucrypt_ch12_wrap...  199   unsigned int nlimbs_msg = mpi_nlimb_hint_from_nbytes( max_len_msg );
eucrypt_ch12_wrap...  200 
eucrypt_ch12_wrap...  201   /* preconditions */
eucrypt_ch12_wrap...  202   assert( output != input );
eucrypt_ch12_wrap...  203 	assert( mpi_get_alloced( output ) >= nlimbs_msg);
eucrypt_ch12_wrap...  204   assert( mpi_get_nlimbs( input )  == nlimbs_n);
eucrypt_ch12_wrap...  205 
eucrypt_ch12_wrap...  206   /* rsa */
eucrypt_ch12_wrap...  207   MPI rsa_decr = mpi_alloc( nlimbs_n );
eucrypt_ch12_wrap...  208   secret_rsa( rsa_decr, input, sk );
eucrypt_ch12_wrap...  209 
eucrypt_ch12_wrap...  210   /* oaep */
eucrypt_ch12_wrap...  211   unsigned encr_len, decr_len;
eucrypt_ch12_wrap...  212   int sign, flag;
eucrypt_ch12_wrap...  213   char *oaep_encr = mpi_get_buffer( rsa_decr, &encr_len, &sign );
eucrypt_ch12_wrap...  214   char *oaep_decr = xmalloc( encr_len );
eucrypt_ch12_wrap...  215   decr_len = encr_len;
eucrypt_ch12_wrap...  216   oaep_decrypt_c( oaep_encr, encr_len, oaep_decr, &decr_len, &flag );
eucrypt_ch12_wrap...  217 
eucrypt_ch12_wrap...  218   /* check status */
eucrypt_ch12_wrap...  219   if ( flag > 0 ) {
eucrypt_ch12_wrap...  220     *success = 1;
eucrypt_ch12_wrap...  221     mpi_set_buffer( output, oaep_decr, decr_len, 0 );
eucrypt_ch12_wrap...  222   }
eucrypt_ch12_wrap...  223   else
eucrypt_ch12_wrap...  224     *success = -1;
eucrypt_ch12_wrap...  225 
eucrypt_ch12_wrap...  226   /* cleanup */
eucrypt_ch12_wrap...  227   mpi_free( rsa_decr );
eucrypt_ch12_wrap...  228   xfree( oaep_encr );
eucrypt_ch12_wrap...  229   xfree( oaep_decr );
eucrypt_ch12_wrap...  230 }
eucrypt_ch12_wrap...  231