Skip to content

Instantly share code, notes, and snippets.

@volpino volpino/crsh.py
Created Oct 13, 2014

Embed
What would you like to do?
A familiar system - ASIS CTF Finals 2014
#!/usr/bin/python
#flag = # censored
from gmpy import next_prime, invert, is_prime, mpz
from random import randint
from hashlib import sha1
def makey():
q = next_prime(randint(1, 2**1024))
x1 = next_prime(randint(1, q-1))
x2 = next_prime(x1)
y1 = next_prime(x2)
y2 = next_prime(y1)
z = next_prime(y2)
g1 = next_prime(z)
g2 = next_prime(g1)
c = divmod(pow(g1, x1, q)*pow(g2, x2, q), q)[1]
d = divmod(pow(g1, y1, q)*pow(g2, y2, q), q)[1]
h = pow(g1, z, q)
pubkey = (q, g1, g2, c, d, h)
privkey = (x1, x2, y1, y2, z)
return (pubkey, privkey)
def encrypt(m, pubkey):
q, g1, g2, c, d, h = pubkey
k = randint(1, q-1)
u1 = pow(g1, k, q)
u2 = pow(g2, k, q)
m = int(m.encode('hex'), 16)
e = divmod(pow(h, k, q)*m, q)[1]
alpha = sha1(str(u1) + str(u2) + str(e)).hexdigest()
v = divmod(pow(c, k, q)*pow(d, int(alpha, 16)*k, q), q)[1]
return (u1, u2, e, v)
def decrypt(crypt, pubkey, z):
q, g1, g2, c, d, h = pubkey
u1, u2, e, v = crypt
s = pow(u1, z, q)
s_inv = invert(s, q)
return hex(divmod(e * s_inv, q)[1])[2:].decode('hex')
def prev_prime(p):
while True:
p -= 2
if is_prime(p):
return p
#pubkey, privkey = makey()
#print pubkey
#c = encrypt(flag, pubkey)
#print c
pubkey = (mpz(136251271151175798114432982938026229490172110401533005102755262286989049184622583417708312009201423476024122677912469680055108982880741528463299142672020834652185527641834721206398483386320729427665613285937265257500825945169037119499345376317962489316486718729170177878788547880596679146803674652102959291179L), mpz(71445390607919938548377475361074566973666877698962004381686815881759650363064790907205389724727052137547259275540047248324480810969042982358139755944485006293081693292128510719329497724780095449564775706193685016091515868306878669276650004788889866268563082218902602391430478108176895385536441463628368479691L), mpz(71445390607919938548377475361074566973666877698962004381686815881759650363064790907205389724727052137547259275540047248324480810969042982358139755944485006293081693292128510719329497724780095449564775706193685016091515868306878669276650004788889866268563082218902602391430478108176895385536441463628368480207L), mpz(108199964103615859008641230860441564013546022099141268729672372560684354711029024967645311655477601297528967214190176938354612973975648677808462780788853857235728443378937276686560734685975860104201150877752699741509893128491453639598002202233433849963771486923929948182126953422409316505411725704660574071657L), mpz(103402410846165640937714634826853699897953021060814854902226893930824546559478506490958509691172995834949498468163369749905491304339347496145685254419406709457509584848035666518698160042608561655338153398962281529505944744194818819405360595447357300235672126457982381082804720943718414140633702130115821518928L), mpz(116340711871909700306245119761735910172833445394742389374011288239236399789939214131715064909418737704146479936263956091201586261917588169097003026421666887999597157485524925727710226313542982324774527228728935095548200397393540416160234666725112551485046369907177780830026445351468830181648589841619040173447L))
crypto = (
mpz(95467029105787819790685969501366652001448206091850219200437950980373198908537653149971642327326341562268633482168133967260392708002179128551446621791484500920123876866983047200450805908685344827646021342534877486305386714673539389693570659549538563696044252832011728553065377412813197782577269476428499901380L), mpz(89595710576920408480354520361707208226997008947621263700559849048228174093448090149075663223527046593283363587635794437708287463841014370347924449040164626126884978025404190308594954049190456014671432009757978067180946291164237407302064238478012485599209052294009083110639149028553486139617037940588192592074L), mpz(57101456812661040956911779152454680172788225654576055105325326802166273530593058160592967123782888106635604456486570389449265108078292983788415457231056869140594423238818468521681863517528522462778250100010993034244098761920700791617733626499616701097597271369053126885898596529980095548583743153472666478505L), mpz(130115388527739990394206680758957845883765682145236104898391558273731695522796485926165074063891018632144470079672768643505790273888231579876368492622104212560577966249611966815224426991815509628590538262064965030005368864440395952711567523963516639208866726152754741399145669201328995650062154785975721499147L))
q, g1, g2, c, d, h = pubkey
z = prev_prime(g1)
print decrypt(crypto, pubkey, z)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.