# crypto-Z2kDH

*Diffie-Hellman

Challenge Description

Sick of how slow it is to take the modulus of a large prime number? Tired of performing exponentiation over some weird group like ed25519? Just use the integers mod 2^k group with the unit `g = 5`

! Efficient, reliable, doesn't require any hard math!

## Challenge Files

## Solution

The script appears to be a type of the Diffie Hellman key exchange program. You can read about the method here

First, the code generates a modulus in the following manner:

In this case 1 is being shifted to the left by 258 positions. When a number is shifted to the left, the result is equivalent to multiplying the number by 2 raised to the power of the number of positions shifted.

Two files containing Alice and Bob's private key are being read to generate their respective private exponents. Using this, two public keys are created by passing the exponents as parameters to the **Z2kDH_init **function. The function does the following operation:

The two public keys are made available in the output file.

After this operation, the key exchange happens, post which a shared secret is formed by both parties. In the source code the **Z2kDH_exchange **performs this function. The values bob_public_result and alice_private_exponent are used to generate Alice's shared secret. Similarly alice_public_result and bob_private_exponent are used to construct Bob's shared secret. The mathematical equation that builds this is as follows:

Rearranging equations 1: and 2: we have:

Substitute 5: in 4: and 6: in 3:.We have

Further to find the private keys, we can use discrete log. You can read about the discrete log here:

The ciphertext is the shared key which can be decrypted with the help of the following script:

Last updated