If you connected to the El Gamal service, the service asked for an simple captcha (something like this):
1
2
| Are you human? Then prove it. Give me a string of length 20 that starts with
'GmBemWqYYU3K' and whose SHA1 ends in 0xFFFFFF
|
It’s easy to solve this problem via brute force
1
2
3
4
5
6
| def gethash(string):
for i in xrange(2**32):
found = start +"0000" + struct.pack("I", i)
if hashlib.sha1(found).digest().endswith("\xff\xff\xff"):
return found
raise Exception()
|
Then it came back with some numbers for El Gamal encryption
1
2
3
4
5
6
7
8
| p = [27327395392065156535295708986786204851079528837723780510136102615658941290873291366333982291142196119880072569148310240613294525601423086385684539987530041685746722802143397156977196536022078345249162977312837555444840885304704497622243160036344118163834102383664729922544598824748665205987742128842266020644318535398158529231670365533130718559364239513376190580331938323739895791648429804489417000105677817248741446184689828512402512984453866089594767267742663452532505964888865617589849683809416805726974349474427978691740833753326962760114744967093652541808999389773346317294473742439510326811300031080582618145727]
g = [5]
h = [26696554507908936438901890298746521910116296076837428579598027758704709599232074507792938304523038408818681479609235663274765869367622544690060477308012386594561731089364385195276126756738284266122817618656603247291387364232479968970841292097873094163406337052697171975191525997649688128083237295019571966329903444521571029519491271370641053546388420010130210938290487733706950967086042285583683088358738555859146406283548232111034393814745800248093828048892635459378101842319303568943324278591350525989382410677514516718516089690682625709978787615263416298977489828494334049645261849266137322546365588236717211183423]
Say "Ready" to continue. Or whatever, I'm totally not going to pay attention
to what you actually say.
Send me two integers with a space in the middle.
|
If you send two integers it will respond with something like this:
1
2
| The ciphertext is (24316120013843276962700180651395202950736108257032524928653304472152213322627248684681542868226768620090564858722715108815726282540325601075710236921914688290813774955321404209938019074410861932713051706409072056756130488352991416214504664719577261526410074779286218342066443590605387419656132776581819167500929041426381077597201975180789389723274782463954223738214864619160062769088292349602330840335087096141891310183448844663658580827548259420922598564211285172784286721198335919386929115176903138593488045028499421610236751109934783542344730434912921871218126706632277937053231716352368640624297704057236707351887, 15824865153707099492667273654691215859992002104210105030077237155795771257577803616232011516763394796465599200356564390226148545381264875845754649566196322331702722961451780073531150036878784862329895231133943940945946294798149117406583962099756557943714211229309103635506086482631947589536244898376283050240539263185280140876223263215228455550178732227324857835654972442311149584908350587058543725980838408283002176721347517331641013837401551113766151618122908235045041069646604887012930868989438700079128006952816002619376188502712735626866884553074699609945298101750484099109957145400904206150755910544223197329364).
Choose 0 if it's the first message or 1 if it's the second.
|
If you guess the number right, it will request again for two numbers and you have to repeat the procedure 64 times.
If you guessed all 64 right, you’ll receive the flag.
To solve this, we used the Legendre symbol, we will use it as a function , which returns -1 or 1.
1
2
3
4
5
| def L(g, p):
x = pow(g,(p-1)/2,p)
if x > 1:
return x-p
return x
|
So we got , and and the ciphertext which is .
is a generator in , therefore is .
Now we choose our numbers and follow the conditions and .
will give the same result as , if was .
Using this knowledge, we ended up in the following python script.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #!/usr/bin/env python2
from sock import Sock
import re
import struct
import hashlib
def gethash(string):
for i in xrange(2**32):
found = start +"0000" + struct.pack("I", i)
if hashlib.sha1(found).digest().endswith("\xff\xff\xff"):
return found
raise Exception()
def L(g, p):
x = pow(g,(p-1)/2,p)
if x > 1:
return x-p
return x
r = re.compile("'([^']*)")
cipher = re.compile("\((\d*), (\d*)\)")
#s = Sock("localhost", 1234)
s = Sock("54.218.12.97", 31333)
print s.read_until("\n").strip()
line = s.read_until("\n").strip()
print line
start = r.findall(line)[0]
found = gethash(start)
s.send(found +"\n")
for i in range(7):
s.read_until("\n").strip()
p = int(s.read_until("\n")[7:-2])
g = int(s.read_until("\n")[7:-2])
h = int(s.read_until("\n")[7:-2])
m1 = 1
m2 = (-1)%p
for i in range(5):
print s.read_until("\n").strip()
for i in range(64):
s.send("%d %d\n"% (m1,m2))
txt = s.read_until("\n").strip()
print txt
c1,c2 = map(int, cipher.findall(txt)[0])
print s.read_until("\n").strip()
if L(c2, p) == L(c1,p):
print "!0"
s.send("0\n")#1
else:
print "!1"
s.send("1\n")#2
msg = s.read_until("\n").strip()
print msg
if "Augh" in msg:
print s.read_until("\n").strip()
|
