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:

modulus = 1 << 258

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.

1 * 2^258 = 348449143727040986586495598010130648530970009369229944076287389795126555724033489969679333296619414528

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:

1:bob_public_result = (5 ** bob_private_exponent) %  modulus // 4
2:alice_public_result=(5 ** alice_private_exponent) %  modulus // 4

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:

3:bob_shared_secret = (alice_public_result *4+1  ** bob_private_exponent) %  modulus // 4
4:alice_shared_exponent = (bob_public_result *4+1  ** alice_private_exponent) %  modulus // 4

Rearranging equations 1: and 2: we have:

5:(5 ** bob_private_exponent)%modulus=bob_public_result*(4+1)
6:(5 ** alice_private_exponent) %  modulus=alice_public_result*(4+1)
#Note that we are multiplying with (4+1)even though in the original 
equation the divisior is only 4.This is becasue the "//" operator in
python peroforms a floor division.

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

bob_shared_secret=(5 ** alice_private_exponent) %  modulus**bob_private_exponent) % modulus // 4
alice_shared_secret = ( (5 ** bob_private_exponent) % modulus ** alice_private_exponent) %  modulus // 4

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