The last couple posts have been about group pairings, specifically Tate pairings as they’re used in cryptography. This post will show that RSA encryption can be seen as a special case of pairing-based cryptography.
The idea comes from Ben Lynn’s 2007 dissertation. Lynn is the “L” in BLS signatures—one of the topics in his disserations—and in BLS elliptic curves.
A pairing is a bilinear mapping from two groups to a third group
e: G1 × G2 → GT.
Here bilinear means that if P is an element of G1 and Q is an element of G2, and a and b are nonnegative integers, then
e(aP, bQ) = e(P, Q)ab.
There are more criteria for a pairing to be useful in cryptography, but we won’t need those for this post.
Ben Lynn’s disseration mentions that exponentiation is a special case of pairing if you let G1 and GT be the multiplicative group of the integers mod r and let G2 be the additive group of integers mod (r − 1). Then you can define a pairing by
e(g, a) = ga.
Typically you can’t just write down a simple expression for a pairing, but in this case you can.
RSA encryption corresponds to r = pq where p and q are large primes. The product pq is made public but the factorization into p and q is held secret. A message [1] is encrypted by exponentiation mod n where the exponent is the public key. In Lynn’s notation, the message is g and the public key is a.
The security of RSA encryption depends on the fact that you can’t recover g from ga mod n unless you know a trapdoor, the factorization of n [2]. This is true of pairings more generally: it is not practical to recover the inputs to a pairing from the output unless you know a trapdoor.
Related posts
[1] In practice, RSA isn’t used to encrypt entire messages. Instead, it is used to encrypt a key for a symmetric encryption algorithm such as AES, and that key is used to encrypt the message. This is done for efficiency.
[2] Or, more specifically, a private key that can easily be computed if you know the factorization of n. It’s conceivable that breaking RSA encryption is easier than factoring, but so far that does not appear to be the case.