Hack.lu 2010 CTF Challenge #7 Writeup

Breiers Deathmatch (150)
Schnuce Breier has challenged you to a cryptographer’s deathmatch.
Connect to pirates.fluxfingers.net 8007/tcp and get the secret number.

$ nc pirates.fluxfingers.net 8007
Hi. This is your friendly 'Decryption Oracle'
We have implemented a well-known public-key cryptosystem. Guess which ;)

Modulo: 5628290459057877291809182450381238927697314822133923421169378
062922140081498734424133112032854812341
Generator: 99
Public Key: 135744434201778324839308712462911647727754874814096844915
5264250239122362719894347099351280643528244
Ciphertext: (44750535504622985677351849167148532593337860047243938284
03819968944371696234280482660523326406427034, 40867215175893797288404
946257736816173818197916450869030897144967500283290022490653051180592
71096141)
Insert your Ciphertext-Tuple for me to decrypt - comma seperated (e.g.
5,6)
>>> 44750535504622985677351849167148532593337860047243938284038199689
44371696234280482660523326406427034, 40867215175893797288404946257736
81617381819791645086903089714496750028329002249065305118059271096141
Duh! This would be too easy, right?

Ciphertext consists from 2 numbers, it should be an El Gamal cryptosystem.
In El Gamal, the public key is (p,g,y=g^x). We know them:
p is Modulo
g is Generator
y is Public Key

Encryption algorithm:
k – random (ephemeral key)
c1 = g^k (mod p)
c2 = M * y^k (mod p)

(c1, c2) is ciphertext

Decryption:
M = c2/(c1^x) (mod p)

We are to make the service to decrypt the message, without giving ciphertext to him in it’s initial form. It’s pretty easy, we can multiply c2 by 2 and then divide the result by two:
So, we send (c1, c2*2), receive M2 = c2*2/(c1^x) (mod p) and calculate M = M2/2 (mod p):

$ nc pirates.fluxfingers.net 8007
Hi. This is your friendly 'Decryption Oracle'
We have implemented a well-known public-key cryptosystem. Guess which ;)

Modulo: 5628290459057877291809182450381238927697314822133923421169378062
922140081498734424133112032854812341
Generator: 99
Public Key: 135744434201778324839308712462911647727754874814096844915526
4250239122362719894347099351280643528244
Ciphertext: (41825515265437061640942636436479629462349412223362537818815
60365619622829030601031151502516559081608, 15384270178209934586156113242
39137557460949040901187143519958777947772936657937341638294059899245093)
Insert your Ciphertext-Tuple for me to decrypt - comma seperated (e.g. 
5,6)
>>> ^Z                                                                                                   
[1]+  Stopped                 nc pirates.fluxfingers.net 8007

$ py
Python 2.6.5 (r265:79063, Apr 16 2010, 13:09:56) 
[GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 15384270178209934586156113242391375574609490409011871435199587779477
72936657937341638294059899245093*2
307685403564198691723122264847827511492189808180237428703991755589554587
3315874683276588119798490186L
>>> 
[2]+  Stopped                 python

hellman@hellpc ~/Temp/hacklu/7 $ fg 1
nc pirates.fluxfingers.net 8007
418255152654370616409426364364796294623494122233625378188156036561962282
9030601031151502516559081608,3076854035641986917231222648478275114921898
081802374287039917555895545873315874683276588119798490186 
Decrypted:
1772769743432258561317602
^C

hellman@hellpc ~/Temp/hacklu/7 $ fg 2
python
>>> 1772769743432258561317602/2
886384871716129280658801L

It’s not obvious, but the flag is 886384871716129280658801.

2 comments

    • adithya on October 21, 2013 at 10:53
    • Reply

    hi,
    i have p,g,y,c1,c2 given.. i have a problem calculating x..is ther any other way to calculate the secret key(x) other than bruteforcing?

    1. It’s discrete logarithm problem – to calculate x. There are better methods than bruteforce, but they all are (sub)exponential and finding x for large primes is very hard. In this challenge you don’t need to figure out x, you are just deceiving the decryption oracle.

Leave a Reply

Your email address will not be published.