Inroduction
Qiwi-Infosec - Crypto 300_1 shared key in decimal.
Description
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
1
2
3
4
5
p:8986158661930085086019708402870402191114171745913160469454315876556947370642799226714405016920875594030192024506376929926694545081888689821796050434591251;
g: 6;
a: 230;
b: 250;
g^c:5361617800833598741530924081762225477418277010142022622731688158297759621329407070985497917078988781448889947074350694220209769840915705739528359582454617;
Solution
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: g^abc mod p.
We have Alice and Bob private key (a and b), but we have only Cameron public key g^c mod p
We can’t compute directly (((g)^a)^b)^c mod p but we can compute the shared key this way:
((g^c)^a)^b mod p
The python-sage script that get the flag
1
2
3
4
5
6
7
8
9
10
11
12
#!/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 is Captured ` » 38058349620867258480