How can you securely agree on a shared secret key for symmetric cryptography, when you don't have a secure channel? Diffie-Hellman key exchange saves the day! Well, really it's key agreement or key negotiation rather than key exchange.
We have two players, Alice and Bob. They agree on a base, b, and a modulus, m. They can agree on the base and modulus in public. In fact, since there are better and worse forms for those values, they probably should do this in public, or simply choose a base and modulus in common use. For example, the modulus must be a prime number, and it is taken into account when choosing the base, see a detailed description for more on these choices. The modulus m should be a large prime, at least 300 digits, but b can (and usually is) a small number, 2 and 5 being the usual choices.
Alice and Bob each pick a secret number, Sa and Sb, respectively. Either of them can decide it's time to switch to a new key for their communication channel, making this a session key system. For security, these should also be large — at least 100 digits.
Each then calculates a public value from their secret value, by calculating Public = bSecret modulo m as follows:
Alice says: Pa = ( bSa ) modulo m Bob says: Pb = ( bSb ) modulo m
Now, because modulus of discrete logarithms is a one-way function — easy to calculate in one direction, but impractical or impossible to calculate in reverse — they can safely publish the base, modulus, and their public values and be confident that even highly motivated mathematicians could not discover their secret values. This includes Alice and Bob themselves — they cannot discover each other's secret values.
However, they can calculate a shared secret using the base, the modulus, the other party's public value, and their secret value. See above regarding X.509v3 digital certificates for issues of making certain that they really have the public key of the other player, and not some "man in the middle" pretending to be the other end.
Alice calculates the shared secret this way:
| Kalice,bob | = | [ PbSa ] modulo m |
| = | [ ( [ bSb ] modulo m)Sa ] modulo m | |
| = | [ ( bSb )Sa ] modulo m | |
| = | [ b(SbSa) ] modulo m |
Bob calculates the shared secret this way:
| Kbob,alice | = | [ PaSb ] modulo m |
| = | [ ( [ bSa ] modulo m)Sb ] modulo m | |
| = | [ ( bSa )Sb ] modulo m | |
| = | [ b(SaSb) ] modulo m |
Since bSaSb = bSbSa, the two keys are equal. Since either of the two players must use their secret key in the calculation, it is a shared secret.
Note that each player must use the first form of the equation from each pair, as that form uses their secret and the other player's public value. The remaining lines are there for us to work through the equivalence. Note that any calculation of the shared secret requires some secret information, and thus an outsider cannot calculate it. Also, while an outsider might happen to guess the shared secret (although good choices of base and modulus make that extremely unlikely), the involvement of modulo arithmetic means that they would have no way of verifying that they had guessed correctly.
Security relies on:
For a trivial example, not secure because of the small modulus and secrets:
Their shared secret key is 25.
The Cathedral of San Lorenzo in Perugia, Umbria, Italy, housing what purports to be the Virgin Mary's engagement ring, and in front of it, the Fontana Maggiore.
The secure sharing of secrets or access is an old problem! Here is a classic example:
Perugia is today the capital city of the Italian region of Umbria. But the modern country of Italy is a fairly new thing, with the peninsula organized under one government only in 1870. From the time the Roman Empire fell apart starting in the late 300s until then, the peninsula of Italy was a collection of many Papal regions, colonies of other empires, and powerful city-states, including that of Perugia.
In the 1400s, the city of Chiusi had many visitors who came to see that city's prized relic — what purported to be the Virgin Mary's engagement ring. This was a jade disc about 6-7 cm in diameter and a little over 1 cm thick. (and before complaining about the discomfort of wearing such a thing as a ring, or the lack of jade trading routes between China and Palestine in the first century BC, remember that this was in Renaissance Italy and dubious relics were common)
The leaders of Perugia decided that they should go to Chiusi in force and steal Mary's engagement ring so that Perugia could get all the benefits. Not just the income from pilgrimage tourism, but also the sacred bonus points for owning such a relic (and how that favor might be offset by their having stolen the ring through military force didn't seem to enter into the equation). So, they attacked Chiusi in 1473 and stole the ring.
Their immediate worry was that a bigger city, maybe Florence, would then attack Perugia and steal the ring away. So they should get a local blacksmith to make a very sturdy box that would be attached into the stonework of their Cathedral of San Larenzo and locked with a strong lock.
Cesare Borgia — do not give the key to this guy!
But then who would hold the key to the lock? This was the era of the Borgias and conspiracy was common in Italy. No single person could be trusted to hold the key to the box.
So the blacksmith was directed to make a fairly large iron box with straps to be fastened around structural elements of the cathedral. The box had a very large hasp with fifteen holes, and fifteen locks were then used to lock the lid closed. Fifteen reasonably trustworthy citizens were selected, and each received the key to one of those locks.
So, a few times a year, at the pilgrimage seasons, these fifteen reasonably trustworthy citizens brought their keys to the cathedral, collectively unlocked all those locks, and the ring was displayed for the visitors.
If you are interested in more details about Perugia, Umbria, and travel in Italy, click here.
The leaders of Perugia had devised a M-of-N secret-sharing mechanism. No one person could had access. The access mechanism, a collection of keys, was distributed across a group of N (15) people, and some subset M (actually all 15 of them in this case) could combine their partial access to access the protected secret.
What if one of those supposedly upstanding Perugians had died of the plague? If the family couldn't find the key, they would have to get the blacksmith to cut into the box (and here we see that we have to trust the providers of the security technology). A better solution would have been to make it a true subset, M out of N where M < N. You can do that with combinations of chains and locks, but physical M-of-N control quickly becomes complicated.
Mathematics to the rescue! There are several ways to accomplish M-of-N secret key sharing, this is just one of the more commonly used methods:
Adi Shamir's method ["How to Share a Secret", Communications of the ACM, v.24, n.11, Nov 1979, pp 612-613] starts by choosing some prime p which is larger than the largest possible secret key. Remember, if a key is a string of k bits, it can be thought of as a number in the range 0 through 2k - 1.
Then generate an arbitrary polynomial of degree M - 1. Let's be a little less paranoid (smaller N) and more careful (M<N in case of plague loss), use a 5-of-7 scheme. So, N = 7 and M = 5. Here is our polynomial, where S is the secret number:
F(x) = (ax4 + bx3 + cx2 + dx + S) mod p
The coefficients a, b, c, d are chosen randomly, and they must be kept secret.
Now, we said we wanted to share the secret among seven people,
so we just need to generate seven "shadow" values:
ki = F(xi)
We could simply evaluate our polynomial for x = 1, ,2, ..., and give each result to one of our seven people. Our polynomial has five unknowns: a, b, c, d, S, and so you could solve for those with any five output values.
Here is an example:
Secret: S = 42
Prime: p = 101
5-of-7 sharing
Random coefficients: 4, 13, 9, 25
Polynomial:
F(x) = (4x4 + 13x3 + 9x2 + 25x + 42) mod 101
Generate six shadow values:
F(1) = (4*14 + 13*13 + 9*12 + 25*1 + 42) mod 101 = 93
F(2) = (4*24 + 13*23 + 9*22 + 25*2 + 42) mod 101 = 94
F(3) = (4*34 + 13*33 + 9*32 + 25*3 + 42) mod 101 = 25
F(4) = (4*44 + 13*43 + 9*42 + 25*4 + 42) mod 101 = 37
F(5) = (4*54 + 13*53 + 9*52 + 25*5 + 42) mod 101 = 73
F(6) = (4*64 + 13*63 + 9*62 + 25*6 + 42) mod 101 = 74
F(7) = (4*74 + 13*73 + 9*72 + 25*7 + 42) mod 101 = 76
Distribute the shadow values to the seven individuals. In the future, any five of their shadow values can be used to create and solve a set of five linear equations in five unknowns.
|
|
|
|
|||||||||
|
|||||||||
|
| © Bob Cromwell Feb 2012. Created with /bin/vi and ImageMagick, hosted on OpenBSD with Apache. Root password available here, privacy policy here. |
