-
+ 99E516C7C6B48C92437207404D2605637575722DF4D49F11C35D9B9E90A93C26EE6EB0DD5472EEAF364ECCC49F66F48A6C966FB8DDF3CD1DAE459450D573EFA9eucrypt/smg_rsa/rsa.c(0 . 0)(1 . 138)
99 /*
100 * An implementation of TMSR RSA
101 * S.MG, 2018
102 */
103
104 #include "smg_rsa.h"
105 #include <assert.h>
106
107 void gen_keypair( RSA_secret_key *sk ) {
108 /* precondition: sk is not null */
109 assert(sk != NULL);
110
111 /* precondition: enough memory allocated, corresponding to key size */
112 int noctets_pq = KEY_LENGTH_OCTETS / 2;
113 unsigned int nlimbs_pq = mpi_nlimb_hint_from_nbytes( noctets_pq);
114 unsigned int nlimbs_n = mpi_nlimb_hint_from_nbytes( KEY_LENGTH_OCTETS);
115 assert( mpi_get_alloced( sk->n) >= nlimbs_n);
116 assert( mpi_get_alloced( sk->p) >= nlimbs_pq);
117 assert( mpi_get_alloced( sk->q) >= nlimbs_pq);
118
119 /* helper variables for calculating Euler's totient phi=(p-1)*(q-1) */
120 MPI p_minus1 = mpi_alloc(nlimbs_pq);
121 MPI q_minus1 = mpi_alloc(nlimbs_pq);
122 MPI phi = mpi_alloc(nlimbs_n);
123
124 /* generate 2 random primes, p and q*/
125 /* gen_random_prime sets top 2 bits to 1 so p*q will have KEY_LENGTH bits */
126 /* in the extremely unlikely case that p = q, discard and generate again */
127 do {
128 gen_random_prime( noctets_pq, sk->p);
129 gen_random_prime( noctets_pq, sk->q);
130 } while ( mpi_cmp( sk->p, sk->q) == 0);
131
132 /* swap if needed, to ensure p < q for calculating u */
133 if ( mpi_cmp( sk->p, sk->q) > 0)
134 mpi_swap( sk->p, sk->q);
135
136 /* calculate helper for Chinese Remainder Theorem:
137 u = p ^ -1 ( mod q )
138 this is used to speed-up decryption.
139 */
140 mpi_invm( sk->u, sk->p, sk->q);
141
142 /* calculate modulus n = p * q */
143 mpi_mul( sk->n, sk->p, sk->q);
144
145 /* calculate Euler totient: phi = (p-1)*(q-1) */
146 mpi_sub_ui( p_minus1, sk->p, 1);
147 mpi_sub_ui( q_minus1, sk->q, 1);
148 mpi_mul( phi, p_minus1, q_minus1);
149
150 /* choose random prime e, public exponent, with 3 < e < phi */
151 /* because e is prime, gcd(e, phi) is always 1 so no need to check it */
152 do {
153 gen_random_prime( noctets_pq, sk->e);
154 } while ( (mpi_cmp_ui(sk->e, 3) < 0) || (mpi_cmp(sk->e, phi) > 0));
155
156 /* calculate private exponent d, 1 < d < phi, where e * d = 1 mod phi */
157 mpi_invm( sk->d, sk->e, phi);
158
159 /* tidy up: free locally allocated memory for helper variables */
160 mpi_free(phi);
161 mpi_free(p_minus1);
162 mpi_free(q_minus1);
163 }
164
165 void public_rsa( MPI output, MPI input, RSA_public_key *pk ) {
166
167 /* mpi_powm can't handle output and input being same */
168 assert (output != input);
169
170 mpi_powm( output, input, pk->e, pk->n );
171 }
172
173 void secret_rsa( MPI output, MPI input, RSA_secret_key *skey ) {
174 /* at its simplest, this would be input ^ d (mod n), hence:
175 * mpi_powm( output, input, skey->d, skey->n );
176 * for faster decryption though, we'll use CRT and Garner's algorithm, hence:
177 * u = p ^ (-1) (mod q) , already calculated and stored in skey
178 * dp = d mod (p-1)
179 * dq = d mod (q-1)
180 * m1 = input ^ dp (mod p)
181 * m2 = input ^ dq (mod q)
182 * h = u * (m2 - m1) mod q
183 * output = m1 + h * p
184 * Note that same CRT speed up isn't available for encryption because at
185 encryption time not enough information is available (only e and n are known).
186 */
187
188 /* allocate memory for all local, helper MPIs */
189 MPI p_minus1 = mpi_alloc( mpi_get_nlimbs( skey->p) );
190 MPI q_minus1 = mpi_alloc( mpi_get_nlimbs( skey->q) );
191 int nlimbs = mpi_get_nlimbs( skey->n ) + 1;
192 MPI dp = mpi_alloc( nlimbs );
193 MPI dq = mpi_alloc( nlimbs );
194 MPI m1 = mpi_alloc( nlimbs );
195 MPI m2 = mpi_alloc( nlimbs );
196 MPI h = mpi_alloc( nlimbs );
197
198 /* p_minus1 = p - 1 */
199 mpi_sub_ui( p_minus1, skey->p, 1 );
200
201 /* dp = d mod (p - 1) aka remainder of d / (p - 1) */
202 mpi_fdiv_r( dp, skey->d, p_minus1 );
203
204 /* m1 = input ^ dp (mod p) */
205 mpi_powm( m1, input, dp, skey->p );
206
207 /* q_minus1 = q - 1 */
208 mpi_sub_ui( q_minus1, skey->q, 1 );
209
210 /* dq = d mod (q - 1) aka remainder of d / (q - 1) */
211 mpi_fdiv_r( dq, skey->d, q_minus1 );
212
213 /* m2 = input ^ dq (mod q) */
214 mpi_powm( m2, input, dq, skey->q );
215
216 /* h = u * ( m2 - m1 ) mod q */
217 mpi_sub( h, m2, m1 );
218 if ( mpi_is_neg( h ) )
219 mpi_add ( h, h, skey->q );
220 mpi_mulm( h, skey->u, h, skey->q );
221
222 /* output = m1 + h * p */
223 mpi_mul ( h, h, skey->p );
224 mpi_add ( output, m1, h );
225
226 /* tidy up */
227 mpi_free ( p_minus1 );
228 mpi_free ( q_minus1 );
229 mpi_free ( dp );
230 mpi_free ( dq );
231 mpi_free ( m1 );
232 mpi_free ( m2 );
233 mpi_free ( h );
234
235 }
236