The Problem
Let’s examine how it’s possible for your web browser to establish an encrypted communication channel with your bank’s website. Obviously you don’t want a malicious party to intercept your personal information (such as your password, account number, social security number, etc) as it’s transmitted to and from your web browser and the bank’s web server. When you opened an account the bank did not provide you with a secret decoder ring. So how does your web browser know how to decrypt data transmitted by the bank’s web server? And how does the bank’s web server know how to decrypt data transmitted by your web browser? Did they send each other a secret key to use for decryption? But if they did then couldn’t a malicious party intercept the secret key and monitor the entire communication? The answer is no, they did not exchange secret keys. They exchanged public keys while retaining their own private (secret) keys. They then used mathematics to derive the shared key used for encryption and decryption.
Previous Solution
Prior to asymmetric key cryptography, two parties wishing to communicate securely would first have to exchange private keys. Imagine a general commanding an army in war. Prior to a battle the general would provide his officers with a code (or key) that was identical (or symmetric) to his own key. This would be done in person or perhaps by courier. The general and his officers would then use the key to encrypt and decrypt messages sent over telephone lines and radio broadcasts, enabling them to securely strategize during the battle over wires and frequencies known to be monitored by the enemy.
Symmetric key cryptography’s requirement that two parties exchange private keys prior to establishing a secure communication channel imposes a severe burden on the parties. What if they’ve never met in person? What if one or both parties are in a physically dangerous position and unable to rely on couriers? What if the enemy captures the courier? All of these conditions prevent secure communication, or worse, compromise secure communication- that is, the parties believe they’re communicating securely, however, the enemy is listening.
Let’s put it in modern day terms: What if you want to join the hot new website but are worried a hacker could intercept your personal information as you build out your profile and library of documents? It is impossible for you to meet with employees of the website to exchange private keys. The website was launched only yesterday, the servers running the website are located in Europe, and you’re in the States.
Modern Solution
Web surfers have never had to worry about this situation because the problem was solved in the 1970s by Whitfield Diffie and Martin Hellman. Actually it was solved publicly in the 1970s. It was solved privately (and classified as a state secret) in the late 1960s by mathematicians and engineers at the British signals intelligence agency.
I’ll show you the solution of how to establish an encrypted communication channel among two parties that have never met in person- and how to do this in such a way that a malicious party that intercepts the handshake (all the data exchanged prior to establishing the encrypted channel) cannot recreate the shared key and eavesdrop on the communication. I’ll show you the solution then I’ll write code to prove the solution works. I will focus on how each party obtains the shared key. I will not get into the mechanics of how this shared key is used to encrypt and decrypt messages or how the HTTPS, SSL, and TLS protocols work.
The Math
I found a succinct explanation of the math that enables asymmetric key cryptography on a web page of the Computer Science department of Cornell University. I’ll restate it here:
1976: Diffie-Hellman Key Exchange
This operation allows two principals to set up a shared key given a public-key system. It uses a computational assumption called, unsurprisingly, the Computational Diffie-Hellman (CDH) assumption. CDH states that, given g, a generator for a finite field of size n and randomly chosen values a and b in this field, it is hard for an adversary to construct g pow (a * b) given only g, g pow a, and g pow b. If this assumption is true, then it can be used to exchange shared keys between two principals A and B as follows:
- A chooses random a, sets M1 = g pow a mod n, and sends M1 to B
- B chooses random b, sets M2 = g pow b mod n, and send M2 to A
- A computes K = M2 pow a mod n = g pow (a*b) mod n
- B computes K = M1 pow b mod n = g pow (a*b) mod n
- Now A and B share a key K, but CDH implies that no eavesdropper can construct K given only the information that was transmitted between A and B.
“Pow” means “to the power of.” For example, 2 pow 3 = 2 * 2 * 2 = 8. “Mod” means “modular division” or remainder. For example, 23 mod 5 = 3 because 23 divided by 5 = 4 with 3 remaining. “G” is the cipher suite (a publicly known algorithm) used to encrypt and decrypt messages, such as AES. “N” is the block size. Messages are encrypted or decrypted in chunks (blocks). This allows large files to be uploaded or downloaded as a stream and the encryption / decryption occurs on each chunk, so the web browser and server are not required to load the entire file into memory.
That’s a lot to unravel, so let me attempt to clarify it in my own words: Diffie and Hellman realized communications can be protected by the computational difficulty of finding discrete logarithms. They proposed a technique where each party computes a math operation; shares some (but not all) of their values with the other party; the other party computes another math operation using the received values and their own private values. Both parties are guaranteed to arrive at the same result because:
- (g pow b mod n) pow a mod n = g pow (a*b) mod n. And…
- (g pow a mod n) pow b mod n = g pow (a*b) mod n.
The handshake does not disclose the shared key (the secret key used by both parties to encrypt and decrypt messages) because it’s extremely difficult to determine the shared key given only the partial information transmitted. It would require enormous computing power and time.
The above math is the foundation of all Internet security. So the next time you see a lock icon in your web browser you can thank the ingenuity of Whitfield Diffie and Martin Hellman for keeping your personal information safe.
Proof of Concept Code
We can do better than merely give thanks. We can demystify the technique and confirm our understanding of it. Alright, let’s write code that performs these calculations to see if Principal A and Principal B (borrowing the terminology of the Cornell University professor) arrive at the same shared key. I’ll write the code in C# and use “long”, one of its integer primitive data types.
Let’s run the program.
Testing using small, positive integers. g = 0005. This is the encryption generator. n = 0009. This is the block size of the generator. Large messages are encrypted in multiple blocks. a = 0003. This is a random integer chosen by Principal A. m1 = 0008. This is a public key transmitted from Principal A to Principal B. b = 0007. This is a random integer chosen by Principal B. m2 = 0005. This is a public key transmitted from Principal B to Principal A. ak = 0008. This is the shared key Principal A uses to encrypt and decrypt messages sent to / received from Principal B. bk = 0008. This is the shared key Principal B uses to encrypt and decrypt messages sent to / received from Principal A. Shared keys (for use by Principals A and B using generator g) match.
Success! Principal A and B arrived at the same shared key. However, this code has a major flaw: integer overflow. See what happens when the integers are larger than in the previous example.
Testing using small, positive integers. g = 0097. This is the encryption generator. n = 0051. This is the block size of the generator. Large messages are encrypted in multiple blocks. a = 0004. This is a random integer chosen by Principal A. m1 = 0013. This is a public key transmitted from Principal A to Principal B. b = 0067. This is a random integer chosen by Principal B. m2 = -0026. This is a public key transmitted from Principal B to Principal A. ak = 0016. This is the shared key Principal A uses to encrypt and decrypt messages sent to / received from Principal B. bk = -0026. This is the shared key Principal B uses to encrypt and decrypt messages sent to / received from Principal A. Shared keys (for generator g) do not match.
The mathematical “pow” operation produces a number that is too large for a long data type to hold. In C#, a signed long (meaning it may hold a positive or negative value) has a range of -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. That’s quintillions- a large number but not large enough. In the example above, g pow b = 97 pow 67 = 1.2992902989583128285857113849691e+133. Clearly this is out of range of a C# long. Among other problems, the “pow” operation overruns the bit (1 or 0) that indicates whether the long represents a positive or negative value. The output value is an incorrect result in both magnitude and sign.
We can force C# to throw an exception and halt program execution rather than return an incorrect result. Wrap the code in a “checked” block.
Testing using small, positive integers.
g = 0035. This is the encryption generator.
n = 0064. This is the block size of the generator. Large messages are encrypted in multiple blocks.
a = 0078. This is a random integer chosen by Principal A.
Unhandled Exception: System.OverflowException: Arithmetic operation resulted in an overflow.
at ErikTheCoder.Sandbox.AsymmetricCryptography.Program.TestWithSmallIntegers(Int32 MaxValue) in C:\Users\Erik\Documents\
Visual Studio 2017\Projects\Sandbox\Asymmetric Cryptography\Program.cs:line 81
at ErikTheCoder.Sandbox.AsymmetricCryptography.Program.Main(String[] Args) in C:\Users\Erik\Documents\Visual Studio 2017\
Projects\Sandbox\Asymmetric Cryptography\Program.cs:line 63
That’s better. We’ve eliminated the integer overflow bug. However, the program is incapable of dealing with all but the smallest integers. Let’s use the BigInteger struct, which implements an arbitrarily large integer with no upper or lower bounds. Note that BigInteger provides a ModPow method optimized to perform modulus division on a number raised to the power of another number. We’ll use some really, really large integers.
Testing using big, positive integers. g = 4623264641941000503532012476318116435609358341347462119686823465010882045736216217976984068989383057034808479032198740168870 99541776821228086174856265912210482182011542926704597590143432464481998528138410480838102894800337254985287180758275174234278544 99170794292272841839648759185733978075946126990110515065574563691638170159350483175571057495110046843590549127240783273436616643 41201353412648487960953728420021917895784074419993432526101324001044450392200974189349695764586486839935173636064439527438138148 413836549041468482501504312198102693140395135987631575531613754037817704537785497780296049181649308951634026. This is the encryption generator. n = 3247679056049659934252997113216211614893703505717797219816822261555493391676788355312770340777744269811664652319415138419778 27130560460415572450225075034703808109580880751759862765636509977818701133788361553820522087282999641502774045459204230253353412 46023930292752144043924152155358217602164940668615237277199654666171485482988574666015234197293990353967027855207419510635964795 50608216058321914535357116652057542513515232968340637905763967891981367289433148746837150418896401032210225346940229049682753069 713015189122530192462573772949516856948167567467531833364514227776544058101361846837193577224483647562201660. This is the block size of the generator. Large messages are encrypted in multiple blocks. a = 8539412049136636075248488786400002467570622701371512356829505791114046214131633730944354349180950489313174885683617483265058 13747987599972806416102839051266099733662662972616899705450816192563887849505335989904499411790492130379920425799131682655409789 01074936132381798029286128203664259720163020478509814986140933938251375686702355818174170791259753231429050345002886893441982458 75955928425171158054973063710716648442926209003589668512189495026851219452290120688527203262115073805104836246296447380135611240 292254455651957337380079645638412406645000256828143549158058301135139223766809324677154549755973142195121595. This is a random integer chosen by Principal A. m1 = 818577041310940535601593464701080174852611246909933947677182069322223192435316197716081346221528683445082415108811528400059 15646312291571494352757177638172619601582645848007988567761168183778312333675036854717127994920002147906741940783992889269754920 83215009111985616218830107243368906364389460351839013958748683015758690428259260784004633648034568353598633151220776166053968585 04552417445342095294552514507871745126723589172795454444807858404942742805191574062110289602305019461655279132745725874485025128 874351426039030054413383770248499634581001565373812852961886378522688639200987025701701070061482480653920056. This is a public key transmitted from Principal A to Principal B. b = 1001581363662651635780131150689022233508449230567262117601461864548052559833442142647876560976556216694824256532629526119936 90635743499197166913240138585369731276810237727727914104799706369881402969098723168804953004730923288891914716238365366059804635 59768108173588004573776815842311535278408300813987472135059265981957928190767610865462857659605703588649370957419112553284991622 12106907294690100498177067576855961792340260572011207448645110717956105491090185443883736953697213147684768208862780735194042156 7706761070991409037597238095721695340451289393077542185685538936401765303675414521868269567859502644600971848. This is a random integer chosen by Principal B. m2 = 312402013774781670843159610838952187097890068297916578748739492551746501460738792401299722693247683244026702067556824083169 22445020376595154232688137100292681851344553131107346353880501520456153156632343429479947526008552540684710007000290551648529920 84085348601507155506732343571017279608605902132234495154498379745327144605959059279022424605000143341439038897599087607308358249 45216605393943474045015313907868402684974975694092425981856082164686303180508936351143786393010000619617816070154898896996764507 2676422006230436318158302584326459730975065165313798922593355126483889135406466529955122799924740726694855336. This is a public key transmitted from Principal B to Principal A. ak = 232335492768787810773145611812504194775584663176790406491075541939106739562603392565422150070737043883251858060659851631237 67655615098918642594934979357067929078167442595749146946336121123790429599826758060381386573209267882506244115619913735129687601 78548338790500252673427968818503868099072200638029136542112411647944151437859369326764053020414433855022441556653987848596497408 04735072846330709612627733759745945039515379153585156603927993293651374394236536996710229712049957142701102091814632736400887535 9087908337215313274959391026373597139117388806950235976690540705579198662509649368618680233395635566083471956. This is the shared key Principal A uses to encrypt and decrypt messages sent to / received from Principal B. bk = 232335492768787810773145611812504194775584663176790406491075541939106739562603392565422150070737043883251858060659851631237 67655615098918642594934979357067929078167442595749146946336121123790429599826758060381386573209267882506244115619913735129687601 78548338790500252673427968818503868099072200638029136542112411647944151437859369326764053020414433855022441556653987848596497408 04735072846330709612627733759745945039515379153585156603927993293651374394236536996710229712049957142701102091814632736400887535 9087908337215313274959391026373597139117388806950235976690540705579198662509649368618680233395635566083471956. This is the shared key Principal B uses to encrypt and decrypt messages sent to / received from Principal A. Shared keys (for use by Principals A and B using generator g) match.
Success!
You may review the full source code in the Asymmetric Cryptography folder of my Sandbox project in GitHub.
See the next post in this series, Encrypting and Decrypting Text.
Do I understand that in order for the “intruder..bad guy” to determine K, he would have to generate a practically infinite array of numbers and then test each one which is in this day of computers, impossible?
That depends on the size of the keys. Let’s assume the bad guy intercepts the handshake between party A and B. He observes g, n, ((g pow a) mod n) and ((g pow b) mod n). He wants to determine K. He knows K = (g pow (a * b)) mod n, so he needs to determine a and b.
If the key size is small, say 3 bits, then all integers are in the range 0..7 because 2 pow 3 = 8. Let’s say the bad guy observes the following:
g = 2
n = 5
((g pow a) mod n) = 3
((g pow b) mod n) = 4
He can easily crack this by brute force- that is, try all integers from 0 to 7 for both a and b until he finds a pair that satisfies the equations above. That’s easy, there’s only 64 combinations to try. The answer is…
Reveal Answer
But as key size grows this become less and less feasible. Typical key sizes are 1024 or 2048 bits. I should write a program that “observes” the data transmitted during a Diffie-Hellman key exchange then attempts to crack the shared key by brute force. Time how long it takes. Then plot this against key size to predict brute force cracking times. That’s an idea for a follow up post.
Of course someone with a deep understanding of number theory can construct a program that’s more efficient than brute force. And a weak cipher (the algorithm that encrypts and decrypts messages using the shared key) can leak information. The Allies cracked Nazi Enigma ciphers because they knew sycophantic German generals always ended their messages with “Heil Hitler” and, as it turned out, the German cipher was vulnerable to this exploit.
But even with a deep understanding of number theory, it’s extremely unlikely the bad guy can crack communications protected by Diffie-Hellman key exchange and a modern cipher within a reasonable time period to be useful.