2 ms·
In the RSA cryptosystem there are three really important numbers N (which is the product of two large primes N=pq), e (the public exponent) and d (the private e
by jgrahamc 13y ago
In the RSA cryptosystem there are three really important numbers N (which is the product of two large primes N=pq), e (the public exponent) and d (the private exponent). The public key in an RSA scheme is <N,e> and the private key is <N,d>. The only bit of the private key that's private is d.
A large part of the security of RSA relies on you not being able to figure out d from N and e. Now the key element of RSA is that
de = 1 mod (p-1)(q-1)
So what happens if e = 1? You get
d = 1 mod (p-1)(q-1)
So you know the value of d. So you know the private key. So you can decrypt everything.
But you don't actually need to do that because what is RSA encryption? It's computing the following (c is the cipher text you'll transmit, m is the message being sent which is to be encrypted with the public key <N,e>)
c = m^e (mod N)
If e = 1 then that's
c = m (mod N)
but, oh wait, m is always < N so m (mod N) is just m, i.e.
c = m
i.e. the encryption does nothing.
Looking on the bright side an exponent of 1 does make RSA quite fast :-)
PS Test code for those interested showing the same N with exponents 1 and 65537 and effect of encryption: https://gist.github.com/jgrahamc/5933984 https://gist.github.com/jgrahamc/5933984
- mykhal 13y ago.. to guarantee m < N, m in real world actually is not a message itself, but a key for symmetric encryption of the message
- StavrosK 13y agoSo the key is getting transferred in plaintext, if their implementation is what I think it is.
- raverbashing 13y agoFunny, I though the private key had p and q, but then I reread the algo description The 1 mod (p-1)(q-1) comes from Euler's theorem and (p-1)(q-1) is how you calculate the totient for numbers that are the product of 2 primes p and q