qwb-2020-baby crt-solve.py

from Crypto.Util.number import GCD, long_to_bytes
from hashlib import sha1
from tqdm import *

n = 26318358382258215770827770763384603359524444566146134039272065206657135513496897321983920652242182112479484135343436206815722605756557098241887233837248519031879444740922789351356138322947108346833956405647578838873425658405513192437479359531790697924285889505666769580176431360506227506064132034621123828090480606055877425480739950809109048177976884825589023444901953529913585288143291544181183810227553891973915960951526154469344587083295640034876874318610991153058462811369615555470571469517472865469502025030548451296909857667669963720366290084062470583318590585472209798523021029182199921435625983186101089395997
m = 26275493320706026144196966398886196833815170413807705805287763413013100962831703774640332765503838087434904835657988276064660304427802961609185997964665440867416900711128517859267504657627160598700248689738045243142111489179673375819308779535247214660694211698799461044354352200950309392321861021920968200334344131893259850468214901266208090469265809729514249143938043521579678234754670097056281556861805568096657415974805578299196440362791907408888958917063668867208257370099324084840742435785960681801625180611324948953657666742195051492610613830629731633827861546693629268844700581558851830936504144170791124745540
s = 20152941369122888414130075002845764046912727471716839854671280255845798928738103824595339885345405419943354215456598381228519131902698373225795339649300359363119754605698321052334731477127433796964107633109608706030111197156701607379086766944096066649323367976786383015106681896479446835419143225832320978530554399851074180762308322092339721839566642144908864530466017614731679525392259796511789624080228587080621454084957169193343724515867468178242402356741884890739873250658960438450287159439457730127074563991513030091456771906853781028159857466498315359846665211412644316716082898396009119848634426989676119219246
e = 65537

y = pow(s, e, n)

for i in tqdm(range(0, 65536)):
    q = GCD(y - pow(m, i, n), n)
    if q.bit_length() >= 1020:
        p = n//q
        flag = "flag{" + sha1(long_to_bytes(p)).hexdigest() + "}"
        print flag
        break
# i = 27145
# flag{601cb6f6d990ed5b89cf0de60508a95c07543793}

qwb-2020-baby crt-task.py

from Crypto.Util.number import getPrime, GCD, long_to_bytes, getStrongPrime
from gmpy2 import gcd
from hashlib import sha1
from random import randint
# from secret import flag, p, q
import libnum

def gen_t(d):
    while True:
        t = getPrime(16)
        if t % 4 == 3 and libnum.gcd(d, t - 1) == 1:
            break
    return t

def sign(m, params):
    d, p, q, n, t1, t2, e1, e2 = params
    dp = d % ((p - 1) * (t1 - 1))
    dq = d % ((q - 1) * (t2 - 1))
    k = getPrime(16)
    Sp = pow(m + k, dp, p * t1)
    Sq = pow(m, dq, q * t2)
    Cp = q * t2 * libnum.invmod(q * t2, p * t1)
    Cq = p * t1 * libnum.invmod(p * t1, q * t2)
    S = (Cp * Sp + Cq * Sq) % (n * t1 * t2)
    c1 = (m - pow(S, e1, t1) + 1) % t1
    c2 = (m - pow(S, e2, t2) + 1) % t2
    # return pow(S, c1 * c2, n)
    print c1 == (-k+1)%t1
    print p
    print pow(S, c1 * c2, n) 
    print pow((Cp*Sp % n) + (Cq*Sq % n), c1, n)
    print pow(S, c1 * c2, n) % p == pow(Sp % p, c1, p)
    print pow(pow(S, c1 * c2, n), e, p) == pow(m+k, c1, p)
    print pow(pow(S, c1 * c2, n), e, n) - pow(m, c1, n)
    print q
    print gcd((pow(pow(S, c1 * c2, n), e, n) - pow(m, c1, n)), n)
    print (pow(pow(S, c1 * c2, n), e, n) - pow(m, c1, n)) % q

e = 65537
p = getPrime(1024)
q = getPrime(1024)

n = p*q
d = libnum.invmod(e, (p - 1) * (q - 1))
t1 = gen_t(d)
et1 = libnum.invmod(d, t1 - 1)
t2 = gen_t(d)
et2 = libnum.invmod(d, t2 - 1)
params = (d, p, q, n, t1, t2, et1, et2)
m = randint(1, n-1)
sig = sign(m, params)