Group theory and RSA encryption

RSA encryption a map from numbers mod n to numbers mod n where n is a public key. A message is represented as an integer m and is encrypted by computing

c = m^e mod n

where e is part of the public key. In practice, e is usually 65537 though it does not have to be.

Multiplicative group

As we discussed in the previous post, not all messages m can be decrypted unless we require m to be relatively prime to n. In practice this is almost certainly the case: discovering a message m not relatively prime to n is equivalent to finding a factor of n and breaking the encryption.

If we limit ourselves to messages which can be encrypted and decrypted, our messages come not from the integers mod n but from the multiplicative group of integers mod n: the integers less than and relatively prime to n form a group G under multiplication.

The encryption function that maps m to m^e is an invertible function on G. Its inverse is the function that maps c to c^d where d is the private key. Encryption is an automorphism of G because

(m₁ m₂) ^e = m₁^e m₂^e mod n.

Totient functions

Euler's theorem tells us that

m⁽ⁿ⁾ = 1 mod n

for all m in G. Here is Euler's totient function. There are (n) elements in G, and so we could see this as a consequence of Lagrange's theorem: the order of an element divides the order of a group.

Now the order of a particular m might be less than (n). That is, we know that if we raise m to the exponent (n) we will get 1, but maybe a smaller exponent would do. In fact, maybe a smaller exponent would do for all m.

Carmichael's totient function (n) is the smallest exponent k such that

m^k = 1 mod n

for all m. For some values of n the two totient functions are the same, i.e. (n) = (n). But sometimes (n) is strictly less than (n). And going back to Lagrange's theorem, (n) always divides (n).

For example, there are 4 positive integers less than and relatively prime to 8: 1, 3, 5, and 7. Since (8) = 4, Euler's theorem says that the 4th power of any of these numbers will be congruent to 1 mod 8. That is true, but its also true that the square of any of these numbers is congruent to 1 mod 8. That is, (8) = 2.

Back to RSA

Now for RSA encryption, n = pq where p and q are large primes and p q. It follows that

(pq) = (p) (q) = (p - 1)(q - 1).

On the other hand,

(pq) = lcm( (p), (q) ) = lcm(p - 1, q - 1).

Since p - 1 and q - 1 at least share a factor of 2,

(n) (n)/2.

Example

It's possible that (n) is smaller than (n) by more than a factor of 2. For example,

(7 * 13) = 6 * 12 = 72

but

(7 * 13) = lcm(6, 12) = 12.

You could verify this last calculation with the following Python code:

>>> from sympy import gcd>>> G = set(n for n in range(1, 91) if gcd(n, 91) == 1)>>> set(n**12 % 91 for n in s)

This returns {1}.

Implementation

The significance of Carmichael's totient to RSA is that (n) can be replaced with (n) when finding private keys. Given a public exponent e, we can find d by solving

ed = 1 mod (n)

rather than

ed = 1 mod (n).

This gives us a smaller private key d which might lead to faster decryption.

OpenSSL example

I generated an RSA key with openssl as in this post

 openssl genpkey -out fd.key -algorithm RSA \ -pkeyopt rsa_keygen_bits:2048 -aes-128-cbc

and read it using

 openssl pkey -in fd.key -text -noout

The public exponent was 65537 as noted above. I then brought the numbers in the key over to Python.

 from sympy import lcm modulus = xf227d5...a9 prime1 = 0xf33514...d9 prime2 = 0xfee496...51 assert(prime1*prime2 == modulus) publicExponent = 65537 privateExponent = 0x03896d...91 phi = (prime1 - 1)*(prime2 - 1) lamb = lcm(prime1 - 1, prime2 - 1) assert(publicExponent*privateExponent % lamb == 1) assert(publicExponent*privateExponent % phi != 1)

This confirms that the private key d is the inverse of e = 65537 using modulo (pq) and not modulo (pq).

Related posts

• Groups of semiprime order
• Selected cryptography posts

The post Group theory and RSA encryption first appeared on John D. Cook.