This has to be the simplest and most straightforward description of the Math behind RSA - a form of public key cryptography that I have come across.
Adam wants to send Eve a message.
1: Adam picks two giant prime numbers,p and q. The primes should be enormous. The larger the prime the greater the security .Adam must keep the numbers secret.
2: Adam multiplies them to get another number, N.
Adam picks another number,e.
( e and (p-1) x (q-1) should be relatively prime,but this is a technicality.)
3. Adam can now publish e and N in something like a telephone directory.
Since these two numbers are necessary for encryption, they must be available to anybody who might want to encrypt a message to Adam.
Together these two numbers are called the public key. (As well as being part of Alice's public key ,
e could also be part of everybody else's public-key. However, everybody must have a different value of N, which depends on their choice of prime numbers ,p and q.)
4. To encrypt a message , the message must first be converted into a number, M.
For example, a
word is changed into ASCII binary digits, and the binary digits can be considered as a decimal number. M is encrypted to give the ciphertext, C, according to the formula
5. Imagine that Adam wants to send Eve a simple kiss; the letter X. In ASCII this is represented by 1011000, equivalent to 88 in decimal.
So,M=88.
And the power behind the Math:
For sufficiently large values of N all the computers in the world will need longer than the age of the Universe to break the code.
Adam no longer has to worry about securely transporting the key to Eve or that the Snake might intercept the key. The more people who see the key the merrier because it helps only with encryption, not decryption.
The only thing that needs to remain secret at all times is the private-key used for decryption, and Adam can keep this with him at all times.
It took 600 volunteers 17 years ( 1977 - 1994) to decipher the value of N ( 10 to the power 129) into p and q, using their spare time on their workstations , mainframes and supercomputers each tackling a fraction of the problem.
Banking transactions, N tends to be in the region 10 to the power 308.
Sometime in the future someone may find a quick way to factor N and therefore RSA would become useless. However for the last 2000 years mathematicians have failed to find a short-cut and factoring remains a time-consuming calculation.
Rivest, Shamir and Adleman (RSA) are credited with finding the most beautiful implementation of public key cryptography at the MIT CS Lab,
though the British Government are challenging for the title of inventor of public key cryptography.
regards
[ August 19, 2003: Message edited by: HS Thomas ]