RSA as a pairing
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 dissertations-and in BLS elliptic curves.
A pairing is a bilinear mapping from two groups to a third group
e:G1*G2GT.
Here bilinear means that if Pis an element ofG1andQis an element ofG2, andaandb 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 dissertation mentions that exponentiation is a special case of pairing if you let G1 andGT be the multiplicative group of the integers modr 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 tor =pq wherep andq are large primes. The productpq is made public but the factorization intop andq is held secret. A message [1] is encrypted by exponentiation modn where the exponent is the public key. In Lynn's notation, the message isg and the public key isa.
The security of RSA encryption depends on the fact that you can't recoverg from gamodn unless you know a trapdoor, the factorization ofn [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 ofn. It's conceivable that breaking RSA encryption is easier than factoring, but so far that does not appear to be the case.
The post RSA as a pairing first appeared on John D. Cook.