mike
October 29th, 2001, 13:23
Quote:
Originally posted by DakienDX
...
I think no one can explain why RSA works or why SHA was converted to SHA-1.
...
|
I can do both.
First is Fermat's Little Theorem:
a^(p-1) mod p = 1, where p is prime, ^ is exponentiation, and a is any number less than p. So
a^b mod p = a^(b mod p-1) mod p.
That implies that for n=p1 * p2 * ... * pk, the product of kdistinct primes, that a^(p1-1)(p2-1)...(pk-1) = 1. This product in the exponent is usually called phi(n).
So a^b mod n = a^(b mod phi(n)) mod n.
So pick two large primes p and q, and multiply them to get n. Then phi(n) = (p-1)(q-1).
Now, you want a two step process, encrypt then decrypt, so that you get the same number back. Well, a^1=a, obviously, so you need two exponents whose product equals 1 mod phi(n).
Pick e at random, and since you know phi(n), you can calculate
d = e^-1 mod n
Publish n and e as your public key. In order to break the code, you need to find d. You could calculate it if you knew (p-1)(q-1), but the only way anyone knows how to get that from n is to factor it. This is very hard.
Then to encrypt your message M, you have
C=M^e mod n
and to decrypt you have
C^d mod n = M^ed mod n = M^(ed mod phi(n)) mod n
= M^1 mod n = M.
Voila!
SHA was probably changed to SHA-1 to avoid an attack that works somewhat like differential cryptanalysis. I say probably because a guy later found an attack that works on SHA-0 but not on SHA-1. If anyone is interested, I can post the reference.