Thank you, everyone for your wonderful participation in my lecture on Cryptography. I have made a couple of examples to recap the two major algorithms we covered below. You may wish to try them yourself, just for fun!
Remember, the Diffie-Helman algorithm relies on making two integers, a generator (g) and a modulus (n), public knowledge. Everybody uses these. Then, everyone generates public keys to be made public. Not only public, actually, but REALLY public, so that it would be difficult for someone with impure motives to produce the illusion that you should use his public key instead of the correct one when communicating to your intended party. Ideally, a public directory should be made easily available to everyone who needs it, much like telephone books are, so that one just looks up the numbers needed for communication.
Here are some concrete (though very small) numbers for g and n so that we can walk through the scenario together:
D-H Public-Key Directory
Modulus for everybody: 1009
Generator for everybody: 2
Now, Thomas makes up some private key in the interval
[0
thomasPublicKey = 2 338 mod 1009 = 487
Also, Loretta (and potentially a lot of other people) does the same thing. She chooses her private key eLoretta = 734. Similarly,
lorettaPublicKey = 2 734 mod 1009 = 324
These get published in the common directory so that it looks like:
D-H Public-Key Directory
Modulus for everybody: 1009
Generator for everybody: 2
Now, when Thomas needs a mutual key to communicate with Loretta, he generates it like this:
mutualKey = 324 338 mod 1009 = 135
Similarly, Loretta calculates:
mutualKey = 487 734 mod 1009 = 135
Now, they have a mutual key for use in a symmetric (secret-key) algorithm to handle all further communications.
Note! In RSA, no two people should use the same modulus -- the modulus is part of the public key for that person only.
Using RSA, Thomas can actually send Loretta an encrypted message -- not just generate a mutual key. In practice, the message usually is a random key for use in a symmetric (secret-key) algorithm, however. Just as importantly, RSA can be used to authenticate messages by reversing how (and whose) keys are used. We'll concentrate on just encrypted messages here.
Before any encrypted messages can be sent, Thomas needs to generate and publish a public key. First he chooses two prime numbers. Remember, we can tell whether a number is prime or not without having to factor it. These primes should be roughly 256 bits in length, so that their product is at least 500 bits. It is commonly accepted (in this year 2001) that nobody can factor a 500 bit number without diverting the resources of a small nation for many, many months. If better security is needed, then choose larger primes.
For concreteness, let's walk through a concrete example using some very small numbers.
Thomas chooses two primes p and q and finds their product:
p = 947
q = 1511
n= p * q = 1430917
The number n is now the modulus and will be one part of the public key.
Thomas must keep p and q for just a few more minutes before he throws them away.
phi = (p-1)(q-1) = 1428460
Now Thomas randomly picks a private key e which has no common factors (other than 1) with phi. Another way of saying this is that e is relatively prime with phi. This is an important distinction, because some numbers will not work for e. For example, the number 10 would not work for e because it has common factors 2 and 5 with phi. A little thought will reveal that e can never be an even number (since phi, being the product of two even numbers, will always be even).
Thomas chooses e=56777 to be the other part of his public key. Now he uses the Extended Euclidean Algorithm to calculate:
e*d = 1 mod 1430917
d = 1/e mod 1430917 = 1089013
Now, Thomas publishes his public key which is e, and n. Thomas throws p, q, and phi away forever.
Suppose Loretta has done these steps also, and both have published their public keys in a directory which might look something like this:
RSA Public Key Directory
Okay, when Loretta wants to send Thomas an encrypted message, say the number 634448. She looks up Thomas' public key and calculates:
encryptedMessage = 63448 56777 mod 1430917 = 538176
Some more examples are presented below, all using Thomas' key above:
RSA Authentication
But what if the important thing to Thomas is that the message really did come from Loretta? Perhaps, he worries, an imposter is sending him a message. In that case, Loretta uses her private key d = 36014 with her own modulus n on the original message 63448 like so:
authenticatedMessage = 634448 453557 mod 1358429 = 140767
Now, it is easy for Thomas (or anyone who has the public-key directory) to read the message and thereby authenticate that it really did come from Loretta. They perform an operation on the number exactly the same as if they were sending an encrypted message to Loretta using her public key:
verifiedMessage = 140767 54113 mod 1358429 = 63448
If the original message were raised to any other exponent than Loretta's private key, this message would be gibberish!
Realistic Authentication
If we wanted to authenticate a long message, we could do this by just breaking up the message into small pieces and then repeating the steps just outlined for each one. However, if we have a very large file, this could mean a lot of work -- a lot of very cumbersome work!
As it turns out, large pieces of data can actually be authenticated in one step. For this, something called a hashing algorithm is used, also known as a message digest algorithm. A message digest takes messages of all different kinds of varying lengths and produces a fixed size fingerprint of that data called a digest. The fingerprint produced is said to be very unique, so that if even one bit of the data were changed, the whole digest would be completely different.
In this way, Loretta could send an authenticated digest along with the original message, and Thomas would still be assured that the message is authentic. If the digest of a message "DOING WELL. WISH YOU WERE HERE." computes to 545377, then Loretta authenticates just the digest like so:
authenticatedDigest = 545377 453557 mod 1358429 = 855990
When Thomas receives this message, he first recalculates the digest of the message. Then he compares this value to the value:
verifiedDigest = 855990 54113 mod 1358429 = 545377
This number should equal the digest of the incoming message from Loretta. If it does, then Thomas accepts the message as really being from Loretta; if it doesn't, then Thomas rejects the message as phony.
It is good to be a walking Java compiler. It is better to be a Java developer.
Last updated 03-25-2002 by webmaster
[join us] [home] [javachina]
Copyright © 1999 - 2002 Thomas Adkins, All Rights Reserved