Crypto 300_1

Crypto - 300 Points

Alice, Bob, and Cameron want to get shared key by Diffie-Hellman method. Their public keys respectively are g^a mod p, g^b mod p, g^c mod p. Will Alice and Bob be able to get shared key without Cameron’s private key? The flag is the first 20 digits of the shared key in decimal form.

p: 8986158661930085086019708402870402191114171745913160469454315876556947370642799226714405016920875594030192024506376929926694545081888689821796050434591251;
g: 6;
a: 230;
b: 250;
g^c: 5361617800833598741530924081762225477418277010142022622731688158297759621329407070985497917078988781448889947074350694220209769840915705739528359582454617;

Writeup

This is a simple crypto challenge on the Diffie-Hellman key exchange protocol.

In this scenario we have 3 user that need to agree on a shared key and we need to calculate it.

The formula for the shared key is: gabc mod p.

We have Alice and Bob private key (a and b), but we have only Cameron public key gc mod p

We can’t compute directly (((g)a)b)c mod p but we can compute the shared key this way:
((gc)a)b mod p

The python-sage script that get the flag

#!/usr/bin/env sage -python

p=8986158661930085086019708402870402191114171745913160469454315876556947370642799226714405016920875594030192024506376929926694545081888689821796050434591251
g=6
a=230
b=250
gc=5361617800833598741530924081762225477418277010142022622731688158297759621329407070985497917078988781448889947074350694220209769840915705739528359582454617

gca = (gc**a) % p
gcab = (gca**b) % p

print "flag: ", str(gcab)[:20]
# flag: 38058349620867258480