1 /* CRT work by Simon Tatham */
8 #define AUTHFILE_ID_STRING "SSH PRIVATE KEY FILE FORMAT 1.1\n"
10 #define mpp(s,n) do { char *p = mpz_get_str(NULL,16,n); printf("%s 0x%sL\n", s, p); free(p); } while (0)
14 struct rsaprivkey_if ops
;
23 struct rsapubkey_if ops
;
28 /* Sign data. NB data must be smaller than modulus */
30 static const char *hexchars
="0123456789abcdef";
32 static string_t
rsa_sign(void *sst
, uint8_t *data
, uint32_t datalen
)
34 struct rsapriv
*st
=sst
;
35 MP_INT a
, b
, u
, v
, tmp
, tmp2
;
43 msize
=mpz_sizeinbase(&st
->n
, 16);
45 if (datalen
*2+4>=msize
) {
46 fatal("rsa_sign: message too big");
51 for (i
=0; i
<datalen
; i
++) {
52 buff
[4+i
*2]=hexchars
[(data
[i
]&0xf0)>>4];
53 buff
[5+i
*2]=hexchars
[data
[i
]&0xf];
57 for (i
=datalen
*2+4; i
<msize
; i
++)
62 mpz_set_str(&a
, buff
, 16);
65 * Produce an RSA signature (a^d mod n) using the Chinese
66 * Remainder Theorem. We compute:
68 * u = a^dp mod p (== a^d mod p, since dp == d mod (p-1))
69 * v = a^dq mod q (== a^d mod q, similarly)
71 * We also know w == iqmp * q, which has the property that w ==
72 * 0 mod q and w == 1 mod p. So (1-w) has the reverse property
73 * (congruent to 0 mod p and to 1 mod q). Hence we now compute
75 * b = w * u + (1-w) * v
78 * so that b is congruent to a^d both mod p and mod q. Hence b,
79 * reduced mod n, is the required signature.
86 mpz_powm(&u
, &a
, &st
->dp
, &st
->p
);
87 mpz_powm(&v
, &a
, &st
->dq
, &st
->q
);
88 mpz_sub(&tmp
, &u
, &v
);
89 mpz_mul(&tmp2
, &tmp
, &st
->w
);
90 mpz_add(&tmp
, &tmp2
, &v
);
91 mpz_mod(&b
, &tmp
, &st
->n
);
98 signature
=write_mpstring(&b
);
105 static rsa_checksig_fn rsa_sig_check
;
106 static bool_t
rsa_sig_check(void *sst
, uint8_t *data
, uint32_t datalen
,
109 struct rsapub
*st
=sst
;
119 msize
=mpz_sizeinbase(&st
->n
, 16);
123 for (i
=0; i
<datalen
; i
++) {
124 buff
[4+i
*2]=hexchars
[(data
[i
]&0xf0)>>4];
125 buff
[5+i
*2]=hexchars
[data
[i
]&0xf];
129 for (i
=datalen
*2+4; i
<msize
; i
++)
134 mpz_set_str(&a
, buff
, 16);
136 mpz_set_str(&b
, signature
, 16);
138 mpz_powm(&c
, &b
, &st
->e
, &st
->n
);
140 ok
=(mpz_cmp(&a
, &c
)==0);
149 static list_t
*rsapub_apply(closure_t
*self
, struct cloc loc
, dict_t
*context
,
156 st
=safe_malloc(sizeof(*st
),"rsapub_apply");
157 st
->cl
.description
="rsapub";
158 st
->cl
.type
=CL_RSAPUBKEY
;
160 st
->cl
.interface
=&st
->ops
;
162 st
->ops
.check
=rsa_sig_check
;
167 if (i
->type
!=t_string
) {
168 cfgfatal(i
->loc
,"rsa-public","first argument must be a string");
171 if (mpz_init_set_str(&st
->e
,e
,10)!=0) {
172 cfgfatal(i
->loc
,"rsa-public","encryption key \"%s\" is not a "
173 "decimal number string\n",e
);
176 cfgfatal(loc
,"rsa-public","you must provide an encryption key\n");
181 if (i
->type
!=t_string
) {
182 cfgfatal(i
->loc
,"rsa-public","second argument must be a string");
185 if (mpz_init_set_str(&st
->n
,n
,10)!=0) {
186 cfgfatal(i
->loc
,"rsa-public","modulus \"%s\" is not a decimal "
187 "number string\n",n
);
190 cfgfatal(loc
,"rsa-public","you must provide a modulus\n");
192 return new_closure(&st
->cl
);
195 static uint32_t keyfile_get_int(struct cloc loc
, FILE *f
)
202 cfgfile_postreadcheck(loc
,f
);
206 static uint16_t keyfile_get_short(struct cloc loc
, FILE *f
)
211 cfgfile_postreadcheck(loc
,f
);
215 static list_t
*rsapriv_apply(closure_t
*self
, struct cloc loc
, dict_t
*context
,
225 MP_INT e
,d
,iqmp
,tmp
,tmp2
,tmp3
;
227 st
=safe_malloc(sizeof(*st
),"rsapriv_apply");
228 st
->cl
.description
="rsapriv";
229 st
->cl
.type
=CL_RSAPRIVKEY
;
231 st
->cl
.interface
=&st
->ops
;
233 st
->ops
.sign
=rsa_sign
;
236 /* Argument is filename pointing to SSH1 private key file */
239 if (i
->type
!=t_string
) {
240 cfgfatal(i
->loc
,"rsa-public","first argument must be a string");
242 filename
=i
->data
.string
;
244 filename
=NULL
; /* Make compiler happy */
245 cfgfatal(loc
,"rsa-private","you must provide a filename\n");
248 f
=fopen(filename
,"rb");
250 if (just_check_config
) {
251 Message(M_WARNING
,"rsa-private (%s:%d): cannot open keyfile "
252 "\"%s\"; assuming it's valid while we check the "
253 "rest of the configuration\n",loc
.file
,loc
.line
,filename
);
256 fatal_perror("rsa-private (%s:%d): cannot open file \"%s\"",
257 loc
.file
,loc
.line
,filename
);
261 /* Check that the ID string is correct */
262 length
=strlen(AUTHFILE_ID_STRING
)+1;
263 b
=safe_malloc(length
,"rsapriv_apply");
264 if (fread(b
,length
,1,f
)!=1 || memcmp(b
,AUTHFILE_ID_STRING
,length
)!=0) {
265 cfgfatal_maybefile(f
,loc
,"rsa-private","failed to read magic ID"
266 " string from SSH1 private keyfile \"%s\"\n",
271 cipher_type
=fgetc(f
);
272 keyfile_get_int(loc
,f
); /* "Reserved data" */
273 if (cipher_type
!= 0) {
274 cfgfatal(loc
,"rsa-private","we don't support encrypted keyfiles\n");
277 /* Read the public key */
278 keyfile_get_int(loc
,f
); /* Not sure what this is */
279 length
=(keyfile_get_short(loc
,f
)+7)/8;
281 cfgfatal(loc
,"rsa-private","implausible length %ld for modulus\n",
284 b
=safe_malloc(length
,"rsapriv_apply");
285 if (fread(b
,length
,1,f
) != 1) {
286 cfgfatal_maybefile(f
,loc
,"rsa-private","error reading modulus");
289 read_mpbin(&st
->n
,b
,length
);
291 length
=(keyfile_get_short(loc
,f
)+7)/8;
293 cfgfatal(loc
,"rsa-private","implausible length %ld for e\n",length
);
295 b
=safe_malloc(length
,"rsapriv_apply");
296 if (fread(b
,length
,1,f
)!=1) {
297 cfgfatal_maybefile(f
,loc
,"rsa-private","error reading e\n");
300 read_mpbin(&e
,b
,length
);
303 length
=keyfile_get_int(loc
,f
);
305 cfgfatal(loc
,"rsa-private","implausibly long (%ld) key comment\n",
308 c
=safe_malloc(length
+1,"rsapriv_apply");
309 if (fread(c
,length
,1,f
)!=1) {
310 cfgfatal_maybefile(f
,loc
,"rsa-private","error reading key comment\n");
314 /* Check that the next two pairs of characters are identical - the
315 keyfile is not encrypted, so they should be */
317 if (keyfile_get_short(loc
,f
) != keyfile_get_short(loc
,f
)) {
318 cfgfatal(loc
,"rsa-private","corrupt keyfile\n");
322 length
=(keyfile_get_short(loc
,f
)+7)/8;
324 cfgfatal(loc
,"rsa-private","implausibly long (%ld) decryption key\n",
327 b
=safe_malloc(length
,"rsapriv_apply");
328 if (fread(b
,length
,1,f
)!=1) {
329 cfgfatal_maybefile(f
,loc
,"rsa-private",
330 "error reading decryption key\n");
333 read_mpbin(&d
,b
,length
);
335 /* Read iqmp (inverse of q mod p) */
336 length
=(keyfile_get_short(loc
,f
)+7)/8;
338 cfgfatal(loc
,"rsa-private","implausibly long (%ld)"
339 " iqmp auxiliary value\n", length
);
341 b
=safe_malloc(length
,"rsapriv_apply");
342 if (fread(b
,length
,1,f
)!=1) {
343 cfgfatal_maybefile(f
,loc
,"rsa-private",
344 "error reading decryption key\n");
347 read_mpbin(&iqmp
,b
,length
);
349 /* Read q (the smaller of the two primes) */
350 length
=(keyfile_get_short(loc
,f
)+7)/8;
352 cfgfatal(loc
,"rsa-private","implausibly long (%ld) q value\n",
355 b
=safe_malloc(length
,"rsapriv_apply");
356 if (fread(b
,length
,1,f
)!=1) {
357 cfgfatal_maybefile(f
,loc
,"rsa-private",
358 "error reading q value\n");
361 read_mpbin(&st
->q
,b
,length
);
363 /* Read p (the larger of the two primes) */
364 length
=(keyfile_get_short(loc
,f
)+7)/8;
366 cfgfatal(loc
,"rsa-private","implausibly long (%ld) p value\n",
369 b
=safe_malloc(length
,"rsapriv_apply");
370 if (fread(b
,length
,1,f
)!=1) {
371 cfgfatal_maybefile(f
,loc
,"rsa-private",
372 "error reading p value\n");
375 read_mpbin(&st
->p
,b
,length
);
379 fatal_perror("rsa-private (%s:%d): fclose",loc
.file
,loc
.line
);
383 * Now verify the validity of the key, and set up the auxiliary
384 * values for fast CRT signing.
387 if (i
&& i
->type
==t_bool
&& i
->data
.bool==False
) {
388 Message(M_INFO
,"rsa-private (%s:%d): skipping RSA key validity "
389 "check\n",loc
.file
,loc
.line
);
396 /* Verify that p*q is equal to n. */
397 mpz_mul(&tmp
, &st
->p
, &st
->q
);
398 if (mpz_cmp(&tmp
, &st
->n
) != 0)
402 * Verify that d*e is congruent to 1 mod (p-1), and mod
403 * (q-1). This is equivalent to it being congruent to 1 mod
404 * lcm(p-1,q-1), i.e. congruent to 1 mod phi(n). Note that
405 * phi(n) is _not_ simply (p-1)*(q-1).
407 mpz_mul(&tmp
, &d
, &e
);
408 mpz_sub_ui(&tmp2
, &st
->p
, 1);
409 mpz_mod(&tmp3
, &tmp
, &tmp2
);
410 if (mpz_cmp_si(&tmp3
, 1) != 0)
412 mpz_sub_ui(&tmp2
, &st
->q
, 1);
413 mpz_mod(&tmp3
, &tmp
, &tmp2
);
414 if (mpz_cmp_si(&tmp3
, 1) != 0)
417 /* Verify that q*iqmp is congruent to 1 mod p. */
418 mpz_mul(&tmp
, &st
->q
, &iqmp
);
419 mpz_mod(&tmp2
, &tmp
, &st
->p
);
420 if (mpz_cmp_si(&tmp2
, 1) != 0)
423 /* Now we know the key is valid. */
427 * Now we compute auxiliary values dp, dq and w to allow us
428 * to use the CRT optimisation when signing.
430 * dp == d mod (p-1) so that a^dp == a^d mod p, for all a
431 * dq == d mod (q-1) similarly mod q
432 * w == iqmp * q so that w == 0 mod q, and w == 1 mod p
434 mpz_sub_ui(&tmp
, &st
->p
, 1);
435 mpz_mod(&st
->dp
, &d
, &tmp
);
436 mpz_sub_ui(&tmp
, &st
->q
, 1);
437 mpz_mod(&st
->dq
, &d
, &tmp
);
438 mpz_mul(&st
->w
, &iqmp
, &st
->q
);
442 cfgfatal(loc
,"rsa-private","file \"%s\" does not contain a "
443 "valid RSA key!\n",filename
);
456 return new_closure(&st
->cl
);
459 init_module rsa_module
;
460 void rsa_module(dict_t
*dict
)
462 add_closure(dict
,"rsa-private",rsapriv_apply
);
463 add_closure(dict
,"rsa-public",rsapub_apply
);