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
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?
Author
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.