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