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