A familiar system - ASIS CTF Finals 2014

crsh.py

#!/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)