# 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.