How to Decrypt Diffie Hellman Easy How to Decrypt Diffie Hellman With Message

By Matthew Loong

Art of Encryption

The ancient Greeks passed secret messages to one another using a tool called a Scytale. The sender would print his messages horizontally on a strip of leather wrapped around a rod. When unfurled, the vertical string of letters would be meaningless to anyone else except his intended receiver who had another rod of identical diameter.

Image above: Scytale

In more recent times, the Germans used a system known by the Allies as Enigma to encrypt and decrypt messages during World War 2. Enigma was eventually broken by Alan Turing and his team, which saved countless lives by intercepting and deciphering the German messages. This was popularized in the movie The Imitation Game.

Image above: Enigma machine

Public Key Cryptography

In traditional symmetric encryption, like the dated examples above, robustness of the method depended on the security of the key. Once the key was compromised, the entire system was comprised. In contrast, Kerckhoffs's principle states that the system should be designed with the assumption that the enemy will immediately gain familiarity, so it must be designed not based on key security, but the algorithm itself. Usher in public key cryptography (PKC), and two of the most popular paradigms - Diffie-Hellman key exchange, invented by Hellman, Diffie, and Merkle; and RSA, invented by Rivest, Shamir and Adleman also in 1977. You can watch the video below to understand more about PKC.

Implementing Diffie-Hellman

Below shows a diagrammatic representation of Diffie-Hellman key exchange. Alice and Bob are able to pass secrets "a" and "b" in the form of ciphertexts g**a.mod.p and g**b.mod.p, where g and p are publicly known large prime numbers. Due to the one way nature of modulo functions, even if Eve were to capture the transmission, she would not be able to decrypt the ciphertext easily. On the other hand, when Alice and Bob receive respective ciphertexts from each other, they are able to obtain the same key K through respective modulo functions involving the received ciphertext and their own secrets, as shown below.

Below is a python implementation of the diagram above.

from random import getrandbits  # Publicly known parameters g = 2 p = 199 bits = 32   # Alice's secret a a = getrandbits(bits) A = pow(g, a, p) # Where A is the transmission from Alice to Bob   # Bob's secret b b = getrandbits(bits) B = pow(g, b, p) # Where B is the transmission from Bob to Alice   # Generate shared key K1 = pow(A, b, p) K2 = pow(B, a, p)   if (K1 == K2):     print('match') else:     print('do not match')        

Which yields the following result, proving that the keys match.

"D:\Python\PyCharm Projects (2.7)\Scripts\python.exe"  match   Process finished with exit code 0        

Implementing RSA

Below are the conceptual steps to implement RSA.

Generate keys

• Select large random prime numbers p, q, where p≠q, but with almost equal size
• Compute modulus n = pq
• Compute Φ = (p-1).(q-1)
• Select public exponent e, 1 < e < Φ, such that gcd(e, Φ) = 1, where gcd means greatest common divisor
• Compute private exponent d = e**(-1).mod.Φ, using multiplicative inversion
• Return public key (n, e), and private key (p, q, Φ,d)

Encryption

• Return m**e.mod.n= c, where m is message and c is ciphertext

Decryption

• Return c**d.mod.n = m

Below is the python implementation of RSA.

from Crypto.Util import number import random   def gcd(a, b):     while b != 0:         a, b = b, a % b     return a   def multiplicative_inverse(e, phi):     d = 0     x1 = 0     x2 = 1     y1 = 1     temp_phi = phi       while e > 0:         temp1 = temp_phi / e         temp2 = temp_phi - temp1 * e         temp_phi = e         e = temp2           x = x2 - temp1 * x1         y = d - temp1 * y1           x2 = x1         x1 = x         d = y1         y1 = y       if temp_phi == 1:         return d + phi   def Gen(minPrime):     p = number.getPrime(minPrime)     q = number.getPrime(minPrime)     n = p * q     phi = (p - 1) * (q - 1)       #Select public exponent e     e = random.randrange(1, phi)     g = gcd(e, phi)     while g != 1:         e = random.randrange(1, phi)         g = gcd(e, phi)       #Compute private exponent d     d = multiplicative_inverse(e, phi)       #Return keys (public, private)     public = (e,n)     private = (d,n)     return public, private   def encrypt(pubKey, msg):     key, n = pubKey     cipher = int(msg**key%n)     return cipher   def decrypt(privKey, ctxt):     key, n = privKey     plain = int(ctxt**key%n)     return plain   #p and q are set to be 8-bits in size public, private = Gen(8) print('public key =', public) print('private key =', private)   message = input("Enter any number smaller than key value: ")   #Encrypt and decrypt encrypted_msg = encrypt(private, message) print('Encrypted message is:', encrypted_msg) decrypted_msg = decrypt(public, encrypted_msg) print('Decrypted message is:', decrypted_msg)        

Which yields the following result. In this case the secret message is "1111" while the ciphertext is "40393". The decrypted message is identical to the secret proving that the implementation works.

"D:\Python\PyCharm Projects (2.7)\Scripts\python.exe"  ('public key =', (12179, 42781)) ('private key =', (59471, 42781))  Enter any number smaller than key value: 1111  ('Encrypted message is:', 40393) ('Decrypted message is:', 1111)   Process finished with exit code 0        

Future Trends in Cryptography

It is unlikely that any cryptographic model will remain unbroken forever. In fact, some people predict that Diffie-Hellman and RSA will be broken within the next 5 years. Increasingly replacing them is Elliptic Curve Cryptography (ECC), which relies on a whole different concept from modulo functions. You can read more about ECC in the link below.

pannellangleatild.blogspot.com

Source: https://www.linkedin.com/pulse/implementing-diffie-hellman-rsa-public-key-matthew-loong

Share this post