There are introductory notes on cryptography in these pages.
Mathematicians Whitfield Diffie and Martin Hellman devised a way of calculating a key that would be private to two people from the formula Yx mod P. The basis of public-key cryptography is a mathematical function that is 'one-way', that is it is easy to calculate in one direction but very hard in the other. One example of a one-way function is to multiply two very large primes: finding the answer is a matter of arithmetic but finding the original primes from the solution is very much harder. If the prime numbers are large enough a 'brute force' attempt to find the numbers (trying every possible combination until the answer is found) would take far longer than the total life of the universe.
The mod function in Excel takes the form =mod(n, divisor) and returns the remainder after integer division. For example, =mod(5,2) will return 1 while =mod(99, 12) returns 3.
The generation of a cryptographic key for an email session proceeds as follows:
Thus a session key is generated for encrypting emails between Alice and Bob. This method relies for its effectiveness on the fact that it is easy to calculate the session key when the exponents are known but very difficult when they are not. No one else can calculate this key even though the initial values of Y and P are public and anyone can acquire them.
Using numbers of the size shown here may make it appear that it would be easy to find the secret session key but in a real system (such as PGP) the numbers involved have hundred of digits. As you will see if you experiment with different numbers in the spreadsheet, Excel soon runs out of space when trying to represent such large numbers (see Numbers in Excel and the Golden Section for details of numbers in Excel).
Real cryptographic systems based on public key cryptography are more complex than this (see RSA Public Key Cryptography) and involve much larger numbers. The RSA (Rivest-Shamir-Adelman, after its authors) algorithm is a public implementation of the Diffie-Helman technique; PGP uses this algorithm. In RSA the session key is a random number chosen by the computer of the person sending the message. This key is then encrypted with the public key of the recipient, the person the sender wants to write to. The recipient decrypts the message and the session key with his private key and he can then use the session key in more conventional (symmetric) encryption. The benefit of this approach is that symmetric encryption is around 1,000 times faster than public-key encryption of the Diffie-Helman kind so it is best to use the latter only as a way of establishing a session key and then to proceed by symmetric encryption.
Individual users are allocated a public-private key pair. The public key is held in a public place and is accessible to anyone. If someone wants to send an email to Alice or Bob he can obtain their public key from the repository. The system works because only the private key of each person can decode (decrypt) a message encrypted in their public key, no other key will do the job. As long as a private key remains private a person can receive messages encrypted with their public key and only they can decrypt them.
The private key has a further use, it can be used to authenticate a message, to guarantee that the message has been sent by the sender and not by someone 'spoofing' them. The legal principle here is non-repudiation: the sender cannot deny that he sent the message because it is encrypted with his private key; and the receiver cannot claim that the message was different because he cannot generate or change message from that person. If the matter comes to court the sender can prove that he sent a given message in the exact form in which it was received.
(What if someone spoofs a sender's email and commits, for example, a libel or a forgery? How can he prove that he didn't send the message? One line of defense might be that it is up to the receiver to insist that all emails he receives be digitally signed (authenticated) with the sender's private key, otherwise he won't open them.)
Elegant though it is the Diffie-Hellman algorithm found few real-world applications. A similar approach developed at MIT by Ron Rivest, Adi Shamir and Len Adleman proved more successful in commercial products, including PGP, Lotus Notes, Motorola secure telephones, Novell Netware, Netscape Navigator and MS Internet Explorer.
This method is based on the mathematical proposition that it is relatively easy to multiply large prime numbers but much harder to derive the factors from any given large number. This is a 'one way function', easy to do in one direction but very difficult the other way round. Try, for example, factoring 91, and then imagine doing this on numbers hundreds of digits long.
The RSA algorithm works like this:
It took many years of research and a moment of inspiration to arrive at this algorithm. It is practically impossible to implement the RSA algorithm in a spreadsheet because of the very large integer values. It is possible to write routines in a programming language that do handle large integers, the algorithms can be found in text books.
A spreadsheet can be used, however, to calculate expressions like 1123 mod 187 or 68879 mod 3337. It happens that 1123 mod 187 = ((((11 x 11) mod 187) x 1121) mod 187). We can thus use iteration to calculate the result of 1123.
If we put 11 in one cell (B2)and 187 in another (C2) we can calculate 112 mod 187 as (in B3) =mod(B2*$B$2, $C$2). The '$' symbols fixes the reference to the cells so we get the right reference when we use drag-copy. The 'B2' without a '$' means that this cell reference will change to B3, B4, etc. when we use drag-copy.
We now drag-copy the formula to row 24 and there we have it, the answer of 88 in cell B24. We can put an index in the A column to show the powers.
To calculate further results of Cd mod P*Q we only need to change cells B2 and C2 and make sure the formula is copied down to the row of the power d.
The version of RSA encryption that first appeared in 1977 was known as RSA-129 on account of the length of N, 129 digits (429 binary digits). In an article in Scientific American by Martin Gardner the authors of RSA set a challenge for cryptanalysts, a short message encrypted with a 129 digit RSA key. The key N (PxQ) was published, along with e, the encryption exponent, which was 9007. The reward for achieving this was described in a signature encrypted with the same key. The message was:
16717861150380844246015271389168398245436901032358311217835038446929062655448792237
114490509578608655662496577974840004057020373
When this number is raised to the 9007th power and reduced modulo N the decrypted number is produced:
06091819200019151222051800230914190015140500082114041805040004151212011819
This was the original message, which was built up from pairs of digits representing the letters of the alphabet, 00 for a space, 01 for 'A', 02 for 'B', etc. We can see that the first character is '06' or 'F', the second is 09 or 'I', the third is 18 or 'R', and so on. The message spelt out:
FIRST SOLVER WINS ONE HUNDRED DOLLARS
The data for the puzzle was as follows:
9686 9613 7546 2206
1477 1409 2225 4355
8829 0575 9991 1245
7431 9874 6951 2093
0816 2982 2514 5708
3569 3147 6622 8839
8962 8013 3919 9055
8962 8013 3919 9055
1829 9451 5781 5154
Rivest reckoned that the time required to factor the modulus (N), was "about 40 quadrillion years" and that his money was safe. On April 26 1994, however, a solution was announced that showed it was possible to do just what Rivest thought was impossible and discover the factors by 'brute force'. It had taken the combined efforts of 600 volunteers, 1,600 computers, new factorising techniques and 8 months of work to achieve the feat, but it had been done. The scale of this achievement can be judged from the value of N, the product of P and Q:
114,381,625,757,888,867,669,235,779,976,146,612,010,218,296,721,242,362,562,561,842,935,
706,935,245,733,897,830,597,123,563,958,705,058,989,075,147,599,290,026,879,543,541
The factors of this number are:
3,490,529,510,847,650,949,147,849,619,903,898,133,417,764,638,493,387,843,990,820,577
and
32,769,132,993,266,709,549,961,988,190,834,461,413,177,642,967,992,539,798,288,533
These are the values P and Q, from which can be calculated (P-1)(Q-1) and thence the decryption key d.
Rivest's secret message? THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE
The cracking of RSA-129 encouraged the view that public keys should be at least 512 bits long and preferably 1024 bits: these should prove, for the foreseeable future, secure.
Use the Back Button to Return to the previous page