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
eucrypt_ch5_rsa_keys 11 assert(sk != NULL);
eucrypt_ch5_rsa_keys 12
eucrypt_ch5_rsa_keys 13
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
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
eucrypt_ch5_rsa_keys 27
eucrypt_ch5_rsa_keys 28
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
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
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
eucrypt_ch5_rsa_keys 45 mpi_mul( sk->n, sk->p, sk->q);
eucrypt_ch5_rsa_keys 46
eucrypt_ch5_rsa_keys 47
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
eucrypt_ch5_rsa_keys 53
eucrypt_ch5_rsa_keys 54 do {
eucrypt_ch5_rsa_keys 55 gen_random_prime( noctets_pq, 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
eucrypt_ch5_rsa_keys 59 mpi_invm( sk->d, sk->e, phi);
eucrypt_ch5_rsa_keys 60
eucrypt_ch5_rsa_keys 61
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
eucrypt_ch5_rsa_keys 70 assert (output != input);
eucrypt_ch5_rsa_keys 71
eucrypt_ch5_rsa_keys 72 mpi_powm( output, input, pk->e, pk->n );
eucrypt_ch5_rsa_keys 73 }
eucrypt_ch5_rsa_keys 74
eucrypt_ch5_rsa_keys 75 void secret_rsa( MPI output, MPI input, RSA_secret_key *skey ) {
eucrypt_ch5_rsa_keys 76
eucrypt_ch5_rsa_keys 77 * mpi_powm( output, input, skey->d, skey->n );
eucrypt_ch5_rsa_keys 78 * for faster decryption though, we'll use CRT and Garner's algorithm, hence:
eucrypt_ch5_rsa_keys 79 * u = p ^ (-1) (mod q) , already calculated and stored in skey
eucrypt_ch5_rsa_keys 80 * dp = d mod (p-1)
eucrypt_ch5_rsa_keys 81 * dq = d mod (q-1)
eucrypt_ch5_rsa_keys 82 * m1 = input ^ dp (mod p)
eucrypt_ch5_rsa_keys 83 * m2 = input ^ dq (mod q)
eucrypt_ch5_rsa_keys 84 * h = u * (m2 - m1) mod q
eucrypt_ch5_rsa_keys 85 * output = m1 + h * p
eucrypt_ch5_rsa_keys 86 * Note that same CRT speed up isn't available for encryption because at
eucrypt_ch5_rsa_keys 87 encryption time not enough information is available (only e and n are known).
eucrypt_ch5_rsa_keys 88 */
eucrypt_ch5_rsa_keys 89
eucrypt_ch5_rsa_keys 90
eucrypt_ch5_rsa_keys 91 MPI p_minus1 = mpi_alloc( mpi_get_nlimbs( skey->p) );
eucrypt_ch5_rsa_keys 92 MPI q_minus1 = mpi_alloc( mpi_get_nlimbs( skey->q) );
eucrypt_ch5_rsa_keys 93 int nlimbs = mpi_get_nlimbs( skey->n ) + 1;
eucrypt_ch5_rsa_keys 94 MPI dp = mpi_alloc( nlimbs );
eucrypt_ch5_rsa_keys 95 MPI dq = mpi_alloc( nlimbs );
eucrypt_ch5_rsa_keys 96 MPI m1 = mpi_alloc( nlimbs );
eucrypt_ch5_rsa_keys 97 MPI m2 = mpi_alloc( nlimbs );
eucrypt_ch5_rsa_keys 98 MPI h = mpi_alloc( nlimbs );
eucrypt_ch5_rsa_keys 99
eucrypt_ch5_rsa_keys 100
eucrypt_ch5_rsa_keys 101 mpi_sub_ui( p_minus1, skey->p, 1 );
eucrypt_ch5_rsa_keys 102
eucrypt_ch5_rsa_keys 103
eucrypt_ch5_rsa_keys 104 mpi_fdiv_r( dp, skey->d, p_minus1 );
eucrypt_ch5_rsa_keys 105
eucrypt_ch5_rsa_keys 106
eucrypt_ch5_rsa_keys 107 mpi_powm( m1, input, dp, skey->p );
eucrypt_ch5_rsa_keys 108
eucrypt_ch5_rsa_keys 109
eucrypt_ch5_rsa_keys 110 mpi_sub_ui( q_minus1, skey->q, 1 );
eucrypt_ch5_rsa_keys 111
eucrypt_ch5_rsa_keys 112
eucrypt_ch5_rsa_keys 113 mpi_fdiv_r( dq, skey->d, q_minus1 );
eucrypt_ch5_rsa_keys 114
eucrypt_ch5_rsa_keys 115
eucrypt_ch5_rsa_keys 116 mpi_powm( m2, input, dq, skey->q );
eucrypt_ch5_rsa_keys 117
eucrypt_ch5_rsa_keys 118
eucrypt_ch5_rsa_keys 119 mpi_sub( h, m2, m1 );
eucrypt_ch5_rsa_keys 120 if ( mpi_is_neg( h ) )
eucrypt_ch5_rsa_keys 121 mpi_add ( h, h, skey->q );
eucrypt_ch5_rsa_keys 122 mpi_mulm( h, skey->u, h, skey->q );
eucrypt_ch5_rsa_keys 123
eucrypt_ch5_rsa_keys 124
eucrypt_ch5_rsa_keys 125 mpi_mul ( h, h, skey->p );
eucrypt_ch5_rsa_keys 126 mpi_add ( output, m1, h );
eucrypt_ch5_rsa_keys 127
eucrypt_ch5_rsa_keys 128
eucrypt_ch5_rsa_keys 129 mpi_free ( p_minus1 );
eucrypt_ch5_rsa_keys 130 mpi_free ( q_minus1 );
eucrypt_ch5_rsa_keys 131 mpi_free ( dp );
eucrypt_ch5_rsa_keys 132 mpi_free ( dq );
eucrypt_ch5_rsa_keys 133 mpi_free ( m1 );
eucrypt_ch5_rsa_keys 134 mpi_free ( m2 );
eucrypt_ch5_rsa_keys 135 mpi_free ( h );
eucrypt_ch5_rsa_keys 136
eucrypt_ch5_rsa_keys 137 }
eucrypt_ch5_rsa_keys 138