Modular Arithmetic - RSA Encryption

[ice109]

I got curious about RSA Encryption after the software signing key for TI-83s got cracked earlier this week and so I'm reading the wiki article about it[RSA]. I'm curious about a step so I'll fill in everyone and then highlight the step I'm not sure about.

Key generation:

1. pick 2 prime numbers p and q

2. compute n = p*q

3. compute the totient t = (p - 1)(q - 1)

4. pick what will be named the exponent e such that 1 < e < t and e and t are coprime

5. pick d such that d*e = 1 ( mod t )

public key is (n,e) private key is (n,d)Encryption:

public key is pre-sent, (n,e). sender uses said public key to compute/send the number/message m like such: c=[itex]m^e[/itex] ( mod n )

Decryption:

m can be recovered as such:

m = [itex]c^d = (m^e)^d=m^{1 mod t} = m^{1 + k*t}=m(m^t)^k=m ( mod n)[/itex]

where the last part is due to euler's theorem about totients.

Fin

the question why everything after key generation is done modulo n? is it to make euler's theorem work out in the end?

 

[uart]

I'm not sure if you're asking (1) why we use modulo n as opposed to not using any modulo at all, or if you're asking (2) why we use modulo n instead of modulo t as per step 5. Anyway I'll answer both.

(1) Ice the numbers in that algorithm can be 4096 binary digits or more, that corresponds to numbers bigger than 10^1000. If you tried to do those exponentiations using the full number (non-modulo) you couldn't even fit the result on the largest hard-drive let alone transmit it before our Sun burns out and our Solar system dies.

(2) Now if perhaps you meant why not use modulo t instead of modulo n? Well this is simple, given t we can easily compute (reverse engineer) the private key from the public key! This is just the algorithm (generalized Euler GCD algorithm) that we use in step 5 for computing d such that de=1 (mod t). It's just as easy (actual identical alorithm) to do this in the other direction (that is to compute e given d and t).

In other words it's absolutely essential that we don’t divulge t or the security of the algorithm is fatally compromised. That's really the interesting part about the RSA "trapdoor". Given (p-1)(q-1) it's trivial to reverse engineer the private key, yet we freely give away pq as part of the public key! At first sight it looks tantalizingly like there might be some easy way to calculate the product (p-1)(q-1) given only the product pq, but in fact there is no known way (other than actually factorising pq to get both p and q first).

 

[ice109]

I'm not sure if you're asking (1) why we use modulo n as opposed to not using any modulo at all, or if you're asking (2) why we use modulo n instead of modulo t as per step 5. Anyway I'll answer both.

(1) Ice the numbers in that algorithm can be 4096 binary digits or more, that corresponds to numbers bigger than 10^1000. If you tried to do those exponentiations using the full number (non-modulo) you couldn't even fit the result on the largest hard-drive let alone transmit it before our Sun burns out and our Solar system dies.

(2) Now if perhaps you meant why not use modulo t instead of modulo n? Well this is simple, given t we can easily compute (reverse engineer) the private key from the public key! This is just the algorithm (generalized Euler GCD algorithm) that we use in step 5 for computing d such that de=1 (mod t). It's just as easy (actual identical alorithm) to do this in the other direction (that is to compute e given d and t).


In other words it's absolutely essential that we don’t divulge t or the security of the algorithm is fatally compromised. That's really the interesting part about the RSA "trapdoor". Given (p-1)(q-1) it's trivial to reverse engineer the private key, yet we freely give away pq as part of the public key! At first sight it looks tantalizingly like there might be some easy way to calculate the product (p-1)(q-1) given only the product pq, but in fact there is no known way (other than actually factorising pq to get both p and q first).

mathematica seems to handle the exponentiation just fine:

http://www.wolframalpha.com/input/?i=(2^4096)^(2^4096)

i wasn't asking the second question.

 

[uart]

mathematica seems to handle the exponentiation just fine:

http://www.wolframalpha.com/input/?i=(2^4096)^(2^4096)

i wasn't asking the second question.

You want to transmit 10^1237 digits - you have to be kidding right? Even at 100 Gigabit's per second that's still going to take you about 10^1220 years! Our solar system is expected to survive for less than another 10^10 years.