Posts QIWI - Crypto 300_1
Post
Cancel

QIWI - Crypto 300_1

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

This post is licensed under CC BY 4.0 by the author.