In my quest to better understand the mechanics of encryption, I've found the Elgamal method the hardest to get my head around. The problem was not that the underlying math is difficult, it was that I didn't know some of the background terminology (cyclic group, congruence class, group isomorphism), the various explanations online all used different variables, and made references to "mathy" things it was supposed the reader was already familiar with. Lastly, the articles on discrete logs and Elgamal encryption on my go-to site for techie info, Wikipedia, were a hot mess, mistaking modular multiplicative inverse for division, and leaving out crucial middle steps (how to get from "collect underpants" to "profit", as it were). The whole affair really shook my faith in using Wikipedia as a trusted source for tech info.
A relatively simple explanation is this: You and your buddy both have a secret that combines to form an encryption key. To encrypt a message, multiply the key by the message value, divide by a modulus, and the remainder is your ciphertext. To decrypt, multiply the ciphertext by the key's inverse, and, again, divide by the modulus, and the remainder is the original message. Fin.
There is, naturally, some math involved, most of it geared around how to build the secret key so only you and your buddy know it, without either of you revealing your part of the secret. Let's start with some of the basic terminology, then get into the mechanics of building the encryption key.
Background
Modular arithmetic, and modular multiplicative inverse - see my previous entry on RSA. Seriously, go read it if you don't know what (mod p) or a three-lined equals sign (≡) means.
Discrete Logarithm
The answer to the question "What power do I raise 10 to in order to get 1000?" is the logarithm of 1000, base 10. The answer, of course, is 3, because 10 cubed is 1000. Standard notation looks like this:
log10(1000) = 3
But that's just a logarithm, not a discrete logarithm. A discrete log happens when you throw a modulus into the mix.
The answer to the question "What power do I raise 3 to in order to get 2 (mod 17)" is asking for a discrete log. The answer is 14, because 314 = 4,782,969 ≡ 2 (mod 17). The notation for that is a little different than the above log(1000) equation:
14 ≡ ind3 2 (mod 17)
The "ind" refers to the "index" in the base 3/mod 17 table where we'll find 2. "Index" and discrete log mean basically the same thing in this context. Check the chart below to see that it is, indeed, index 14 where we find 2.
Multiplicative Order
If p is a prime number, and n is a number less than p, then the smallest positive exponent to raise n to and get ≡ 1 (mod p) is n's multiplicative order, mod p.
If n's multiplicative order mod p is (p-1), then you can generate all the numbers from 1 to p-1 by raising n to increasing powers mod p. For example, here is a table with p as 17, and n as 3:
k 3k 3k (mod 17) 1 3 3 2 9 9 3 27 10 4 81 13 5 243 5 6 729 15 7 2,187 11 8 6,561 16 9 19,683 14 10 59,049 8 11 177,147 7 12 531,441 4 13 1,594,323 12 14 4,782,969 2 15 14,348,907 6 16 43,046,721 1
In the right-hand column, all the numbers from 1 to 16 (p-1) have been generated, making 3 a "primitive element" of 17. If we change p to 11, though, this happens:
k 3k 3k (mod 11) 1 3 3 2 9 9 3 27 5 4 81 4 5 243 1 6 729 3 7 2,187 9 8 6,561 5 9 19,683 4 10 59,049 1
This doesn't generate all the numbers from 1 to 10, due to 3's multiplicative order mod 11 being 5, and not 10. You don't have to generate the whole table to find this out, though, you can instead take the prime roots of p-1 (in this case, p-1 is 10, whose prime roots are 5 and 2), and raise n to those powers. If any of that comes out to ≡ 1 (mod p), then the multiplicative order isn't p-1.
Why is any of that important? Because we're trying to generate a substitution pad without duplicates. If there are duplicates, the "shared key" calculations become ambiguous, breaking the system.
The generator and the group
The book "Handbook of Applied Cryptography" by Menezes, et al., has a lot to say about the difficulty of finding generators, parts of which make sense, other parts are arcane and hard to follow without a lot of background in the field. For example, this is a snippet from chapter 4.6:
Recall (Definition 2.169) that if G is a (multiplicative) finite group, the order of an element α ∈ G is the least positive integer t such that at = 1. If there are n elements in G, and if α ∈ G is an element of order n, then G is said to be cyclic and α is called a generator or a primitive element of G (Definition 2.167). Of special interest for cryptographic applications are the multiplicative group ℤ*p of the integers modulo α prime p, and the multiplicative group F*2m of the finite field F2m of characteristic two; these groups are cyclic (Fact 2.213). Also of interest is the group ℤ*n (Definition 2.124), where n is the product of two distinct odd primes. This section deals with the problem of finding generators and other elements of high order ℤ*p, F*2m, and ℤ*n. See §2.5.1 for background in group theory and §2.6 for background in finite fields.
Those bold F's are mathematical double-strike F's in the source text, but they're a high-unicode value (x1d53d) that doesn't render in all browers. Also, wow, I think this is why most people hate math and technical docs. If nothing else, this shows that before you can intelligently follow the discussion, there is a wealth of background information on group theory and finite fields that needs to be learned first. The takeaways from this without doing any background reading are:
-
"Generator" and "primitive element" are the same thing.
...and they are hard to find for a large modulus.
Generators are the bases that have multiplicative order p-1, which we just discussed, that can be raised to incrementing powers (mod p) to get all the numbers between 1 and p. In this case, our generator, α, is 3, our "p" is 17, and that produces a group G that is from the table above:
α = 3, p = 17 G(k) = 3k (mod 17) ...so: G = (3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6, 1)
The group doesn't actually get generated and stored anywhere (which would be impossible with a large enough modulus); it's enough to prove that there are no duplicate values in it.
The shared key
The shared key is where the real mojo happens, and the encryption and decryption are trivial compared to generating the key. It is a value both sides can calculate with information the other gives them, based on the following identity:
αab mod p = (αa)b mod p = (αb)a mod p
The "a" and "b" variables refer to secret values that the message sender and recipient (Alice and Bob, in geek parlance) pick. A secret value, αab (let's just call it "K", for "key" ... also, I'm going to omit the "mod p" after every term for brevity's sake), can be generated if I know "a" and αb, or if I know "b" and αa.
Through the difficult nature of discrete logarithms, you can't determine "a" from αa, nor can you find "b" from αb. And here's the kicker: you can't determine K if you know both αa and αb, you have to also know one of the secret values. This means that the αa and αb values can be transmitted in the clear.
Additionally, each block of a message Alice sends can have a different secret key. In Elgamal encryption, each cipher block has two values, αa mod p, and the message ciphertext. In each block Bob receives, he'll be calculating what K for that block is, and using it to decrypt the ciphertext.
The encryption
Alice wants to send a message "m" to Bob, so she asks for his public key. Bob sends Alice the key, which contains the generator (α), the modulus (p), and his public part of the shared key, αb mod p.
Alice then picks her own secret, "a", and calculates the shared secret K with (αb)a mod p. Once K is calculated, Alice multiplies it by "m", the message. Then she sends Bob her public part of the shared key, αa mod p (denoted as "c1" in most of the online descriptions), so he can also figure out what K is, and the ciphertext Km mod p ("c2").
Bob, then, takes c1, and raises it to b mod p, to calculate K. This will be the same K Alice multiplied m by. Bob determines the modular multiplicative inverse of K (see the RSA entry for info on what an MMI is), and multiplies that by c2 mod p, revealing the original message, m.
Working example
As we've shown above, the modulus 17 has a primitive element 3. We'll call those "p" and "α". Bob picks 11 as his secret. We'll call his secret xb, and the public (αxb mod p) transformation of it yb
p: 17 α: 3 xb: 11 yb = 311 mod 17 ≡ 177,147 mod 17 = 7
Bob's public key is therefore: (17, 3, 7)
Once Alice receives the public key, she picks 6 as her private key. We'll call her private key xa, and the public transformation of it ya:
xa = 6 ya = 36 mod 17 ≡ 729 mod 17 = 15
Alice then generates the shared secret, K, by raising yb (Bob's public part of the shared key) to 6, and taking mod 17:
K = 116 mod 17 ≡ 117,649 mod 17 = 9
The message ("m") she wants to transmit is 11. Generating the ciphertext is as easy as multiplying m by K mod p:
Km mod p = 9 * 11 mod 17 ≡ 99 mod 17 = 14
The transmitted text is a combination of ya from above (or "c1"), and the ciphertext just calculated ("c2"): (15, 14)
Bob now needs to decrypt the message. First he calculates the shared key using the information he has, ya, and xb (11 and 15):
K = 1511 mod 17 ≡ 8,649,755,859,375 mod 17 = 9
This is the same K that Alice calculated with the other elements, yb and xa. Now that Bob knows K, he needs to find its inverse mod 17:
K-1 = 2 ( because 9 * 2 = 18 ≡ 1 mod 17)
With K-1, m is easily revealed:
m = c2 * K-1 mod p ≡ 14 * 2 mod 17 ≡ 28 mod 17 = 11
And that's all there is to it. In the real world, of course, the modulus would be much larger, and a lot of effort would be expended up front looking for a primitive element.
No comments:
Post a Comment