Added Details and Links
Note: I am not a cryptographer, I just like playing with large numbers.
There are no secret information provided in this blog post, it is all available online, this is just my added two cents, take it for what it is worth.
The Diffie-Hellman Key Exchange method is used to share a "Secret Key" between two users, without sending the shared Secret Key across the network.
See: Google Diffie Hellman.
The idea is simple, and the maths can be simple:
k=<my secret number>
g=<a publicly shared number>
p=<a publicly shared large prime number>
A new Shared or Secret Key: G = (g ^ k) mod p
What can make it difficult and secure is that VERY large numbers can be used, and therefore making it very difficult for an observer (villain) to use brute force to discover the Shared Secret Key.
If you read the available documentation about Diffie Hellman Key Exchange, you will no doubt learn all about; Alice, Bob (the good guys), and Eve (the villain). I suggest it for some bed time reading.
Note: the online documentation suggest that Alice and Bob must first each know some public numbers for "g" and "p".
But, there is nothing preventing a proper and secure Key Exchange when Alice initiates the process by sending Bob three numbers; "g", "p" and "g2B" (g to Bob) values.
Bob would need to use these three values to compute the "Shared Secret Key". Bob also returns to Alice a computed "g2A" (g to Alice), now Bob is finished, he now knows the Shared Secret Key. Alice will also know the Shared Secret Key when she completes her next calculation.
Alice uses the returned "g2A" value to compute the same "Shared Secret Key".
It looks like magic, but it is simple when you look at the maths with small numbers, and knowing:
g^(ab) mod p == g^(ba) mod p
where: "a" is Alice's secret key ("kA"), and "b" is Bob's secret key ("kB").
See the online documentation.
You will also learn from online documents, that "p" should be a Large Prime Number, and "g" should be greater than "0", but less than "p", and "k" is a Secret Key that should NOT be shared.
Which is all good advice, if you are implementing a banking system, or saving the world via encrypted text messages. But the Diffie Hellman function works regardless of the numbers used, so in the examples below, some small and maybe inappropriate values are used.
What started my interested in Diffie Hellman Key exchange is the UNIX provided, and neat little and powerful, utility called "bc". The "bc" command can deal with VERY large numbers without difficulty.
An Example:
A Diffie Hallman Example, with small numbers.
Assume that Alice, Bob and Eve will know and/or use the following:
gP =16
pP = 101
As stated above, these numbers could be suggested by Alice or Bob, or both. Or, the numbers could be hard coded into a application that they both use. If large enough, the knowledge of these numbers does NOT detract from security.
Note: For this example, I will use the upper case "P" to denote a number is "Public", "pP" is normally prime. I will use "kA" for Alice secret key, and "kB" for Bob's secret key. Also, "g2B" and "g2A" are the computed exchanged values. Then finally, "gS" becomes the value of the "Shared Secret Key".
Note: "g2B" and "g2A" are just like other "g" values that can be used in the same Diffie Hellman formula.
Eve can eavesdrop on all of the network data exchanges between Alice and Bob, but will NOT be able to compute the Shared Secret Key, because Eve is not privy to Alice's or Bob's Secret Keys.
-----------------------
Alice's Secret Key, known only by her, is: kA = 7
Alice wants to Share a Secret Key with Bob.
Alice computes a: g2B = (gP ^ kA) mod pP with her key.
Alice will do this on UNIX system with the values above using the following command:
$ g2B=`echo "(16^7)%101" | bc`
g2B becomes 80
Alice can now send "qP", "pP" and "g2B" to Bob as clear text within an email (or whatever). Note: Eve may or can eavesdrop on the Internet traffic.
-----------------------
Bob's Secret Key, known only by him, is: kB = 11
Because Bob also uses a UNIX system, he computes from the values sent from Alice a value to be returned to Alice: g2A = (gP ^ kB) mod pP
$ g2A=`echo "(16^11)%101" | bc`
g2A becomes 71
Bob can now sends Alice "g2A", so she can complete her side of the key exchange.
Bob also can compute the "Shared Secret Key" as: gS = (g2B ^ kB) mod pP
$ gS=`echo "(80^11)%101" | bc`
gS becomes 54
Bob is now finished, he knows the Shared Secret Key as "54".
-----------------------
With the value of "g2A" sent by Bob, Alice can complete her side of the exchange, by computing: gS = (g2A ^ kA) mod pP
$ gS=`echo "(71^7)%101" | bc`
gS becomes 54
Alice now finished, she knows the Shared Secret Key as "54".
-----------------------
Both Alice and Bob both know the same value of "gS", the Share Secret Key as "54". Alice or Bob, could now use the Shared Secret Key to encrypt messages that hopefully only the opposite could decrypt.
Eve is left clueless.
-----------------------
But there is a flaw !
With small numbers, as used in this example, Eve could Brute Force a decryption solution, by trying all numbers starting with "0". In this case it will only take 54 iterations to find the correct Shared Secret Key that would successfully decrypt Alice's message. Eve could easily know (via eavesdropping) the value of "pP" is small, and therefore, can assume the Secret Key is some number between 0 and 101, which implies a brute force attack is warranted.
But Normally
Normally, the values of "gP", "pP", and the resulting "g2B" and "g2A" are VERY much larger numbers, maybe hundreds or thousands of digits.
Imagine what Eve prospects of having enough CPU horse power to attempt a sequential attack if "pP" is extremely large number - prospects = none.
If "pP" is large enough, a brute force attack could take forever even with multiple very fast computers.
Some Experiments
Remember I said "bc" can deal with large numbers, well, to avoid "typing" a large number I will use exponentiation to generate some numbers for "qP" and "pP", for Alice try this:
$ gP="(3^456)"
$ pP="(2^4253-1)" # A Large Prime Number
$ kA="12345"
$ time echo "${gP}^${kA} % ${pP}" | bc
On my 3.2GHz Workstation, this took about 6 minutes to compute, if necessary try shorten the lapse time, by changing Alice's key to "123".
$ gP="(3^456)"
$ pP="(2^4253-1)"
$ kA="12345"
$ time echo "${gP}^${kA} % ${pP}" | bc
80926261610442626577264521832490790161484618732554432140432039188058\
63206215275578738866144144831890725477013508191723348004478728927721\
95788786903156432412894232199564275068253627223471477034284902245829\
91421266442623706953457344345029183351048403313211524973218664085545\
87664348342026922029976056154815423683953094807171496683969416932115\
99132155230551185025739817346443301752666222054850477088018492513173\
91624760224393336362809726321106680382250456588357956381388166323729\
38771361918677860624224646340387910263769022858722611291936528412356\
03100668125135517222317410124988021081469568935461035793383680680665\
55390092789716566511778596204161424690071853937453863897083377508927\
67048039381017256779118656382146384480277810498377460548282809326731\
69234441684180112706844382298511472521071812891762065337050899792993\
70060526297317940169650082051030560624756658527561344770507458651702\
43716790444907248809569095106287466645236990947552803718232042574873\
11042448383261839081283910961519762548619655187688322601121778057413\
25524176872795543285574829694591574831681802471828336907766795593351\
38229222971475049624002124059810014875496597620324310354937668694220\
99070653730452586152318927155511512700751348007603716449001964877066\
01906432412801407287885578931224463376104843439581857726
real 5m48.432s
user 5m44.929s
sys 0m0.400s
The results is about 1200 digits for "g2B".
Stay tuned, more interesting "bc" observations to follow.
Me?, I just like very BIG numbers :-)
-- Home Page: https://WA0UWH.blogspot.com
No comments:
Post a Comment