Ulli Weichert/ April 3, 2022/ IT-Security, Write-Ups/ 0Kommentare

diffie-hellman

Description

Alice and Bob wanted to exchange information secretly. The two of them agreed to use the Diffie-Hellman key exchange algorithm, using p = 13 and g = 5. They both chose numbers secretly where Alice chose 7 and Bob chose 3. Then, Alice sent Bob some encoded text (with both letters and digits) using the generated key as the shift amount for a Caesar cipher over the alphabet and the decimal digits. Can you figure out the contents of the message?
Download the message here.
Wrap your decrypted message in the picoCTF flag format like: picoCTF{decrypted_message}

Solving

1. Okay a encrypted message, but we got all we need! So we just need some math and python power!
2. First we need to calculate the secret. We are lucky, because we have everything we need for that.
   1. First we calculate the public key. Here an example for Alice Public Key: A = g^alice % p
   2. Second we can calculate the secret like that keya = Bpub^alice % p
   3. Now we can iterate through the message and decrypt it letter by letter.

I created a little script (and had some fun with it 🙂 ), that will do that for you 🙂 . Feel free to use it.

#!/usr/bin/env python

from time import sleep

## Given by task description
p = 13
g = 5
alice = 7
bob = 3

## For the caeser cipher
charset="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

print("Calculating keys with given values for decrypting...")
sleep(2)
## Calculating keys
Apub = g**alice % p
Bpub = g**bob % p
print("Oh boy - still calculating...")
sleep(2)
keya = Bpub**alice % p
keyb = Apub**bob % p
print("done...")

if keya == keyb:
    print("Keys are equal! Alice's key: " + str(keya) + " and Bobs key: " + str(keyb))
else: 
    print("Keys are different. Alice's key: " + str(keya) + " and Bobs key: " + str(keyb))

print("Let's decipher the caeser encrypted message with the keys.")

sleep(2)

with open("message.txt","r") as encfile:
    message = encfile.readline()

print("\n\nHere is the encrypted message:\n" + message)
print("Now I'll will decipher it... please wait while I process the message!\n\n")
print("Calculating forwards and backwards")
sleep(2)
print("Quite difficult...")
sleep(2)
print("Swirl letters...")
sleep(2)
print("Cuddle with bees! So sweet! They produce bee vomit!")
sleep(1)
print("Sorry - got distracted.")

def decrypt(key, message,forward):
    message = message.upper()
    result = "picoCTF{"

    for letter in message:
        if forward == True:
            if letter in charset:
                letter_index = (charset.find(letter) - key) % len(charset)
                result = result + charset[letter_index]
            else:
                result = result + letter
        else:
            if letter in charset:
                letter_index = (charset.find(letter) + key) %len(charset)
                result = result + charset[letter_index]
            else:
                result = result + letter
    result = result + "}"
    return result

sleep(1)
print("First one decrypted...\n")
print("Decoded message (forward):\n\t" + decrypt(keya,message,True))
sleep(2)
print("And backwards!!!\n")
print("Decoded message (backward):\n\t" + decrypt(keya,message,False))

print("\nYou need to decide which one the flag is... Don't ask me... I know it, but I won't tell!\nYou are welcome! Thank you for traveling with deutsche Bahn!")