From: Mark Wooding Date: Thu, 25 Jul 2013 17:30:45 +0000 (+0100) Subject: rsa.c: Fix incorrect commentary. X-Git-Tag: debian/0.3.0_beta2~42 X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=secnet.git;a=commitdiff_plain;h=104e8e74fd858a4efff3d8e186406adc431465fa rsa.c: Fix incorrect commentary. The Euler function phi(n) is defined to be phi(n) = #{ 1 < i < n | gcd(i, n) = 1 } the number of natural numbers less than n and prime to it; equivalently, it's the size of the multiplicative group (Z/nZ)^*. If n = p q is the product of two primes then phi(n) = (p - 1)(q - 1). But phi(n) is not (if n is composite) the exponent of (Z/nZ)^*. It's certainly true that a^{phi(n)} = 1 for all a in (Z/nZ)^*; but the exponent of a group G is the /smallest/ positive integer e such that a^e == 1 for all a in G. This quantity is denoted lambda(n); in our simple case where n = p q is the product of two primes it's true that lambda(n) = lcm(p - 1, q - 1) Since p and q are large primes, both p - 1 and q - 1 are even, so lambda(n) is at least a factor of 2 smaller than phi(n). In fact, lambda(2) = 1, lambda(2^f) = 2^{f-2} for f >= 1, and lambda(p^f) = p^{f-1} (p - 1) for prime p > 2; and, in general, if n = p_1^{f_1} ... p_m^{f_m} is the prime factorization of n then lambda(n) = lcm(lambda(p_1^{f_1}), ... lambda(p_m^{f_m})) Signed-off-by: Mark Wooding --- diff --git a/rsa.c b/rsa.c index 0bd106f..fed468d 100644 --- a/rsa.c +++ b/rsa.c @@ -430,8 +430,9 @@ static list_t *rsapriv_apply(closure_t *self, struct cloc loc, dict_t *context, /* * Verify that d*e is congruent to 1 mod (p-1), and mod * (q-1). This is equivalent to it being congruent to 1 mod - * lcm(p-1,q-1), i.e. congruent to 1 mod phi(n). Note that - * phi(n) is _not_ simply (p-1)*(q-1). + * lambda(n) = lcm(p-1,q-1). The usual `textbook' condition, + * that d e == 1 (mod (p-1)(q-1)) is sufficient, but not + * actually necessary. */ mpz_mul(&tmp, &d, &e); mpz_sub_ui(&tmp2, &st->p, 1);