题目如下:
from secret import flag import random from Crypto.Util.number import * from fractions import gcd def make_key( nbit): while True: p, q = getPrime(nbit), getPrime(nbit) N, phi = p * q, (p-1)*(q-1) x = random.randint(1, N) if (N % 8 == 1) and (phi % 8 == 4) and (p != q): if pow(q ** 2 * x, (p-1)/2, p) + pow(p ** 2 * x, (q-1)/2, q) == N - phi - 1: break return (x, N), phi def encrypt(msg, pkey): msg, cipher = bin(bytes_to_long(msg))[2:], [] x, N = pkey for bi in msg: while True: r = random.randint(1, N) if gcd(r, N) == 1: br = bin(r)[2:] c = (pow(x, int(br + bi, 2), N) * r ** 2) % N cipher.append(c) break return cipher nbit = 1024 pkey,phi = make_key( nbit) enc = encrypt(flag, pkey) print phi print pkey[1] print enc
先观察程序的主要部分,直接输出了phi,又因为:
x, N = pkey
所以输出的pkey[1]就是N,最后输出了密文。
参考了Crypto CTF 2019的这道题:https://ctftime.org/writeup/16120
用SAGE直接可以解,SAGE的安装方法如下:
⚪sudo wget https://mirrors.tuna.tsinghua.edu.cn/sagemath/linux/64bit/sage-9.0-Ubuntu_18.04-x86_64.tar.bz2
⚪tar xvf sage-9.0-Ubuntu_18.04-x86_64.tar.bz2
⚪./sage
sage: phi = 9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990711180904598841255660443214091848674376245163953774717113246203928244509033734184913005865837620134831142880711832256634797590773413831659733615722574830257496801417760337073484838170554497953033487131634973371143357507027731899402777169516770264218656483487045393156894832885628843858316679793205572348688820 sage: n = 9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990905528141072864168544519279897224494849206184262202130305820187569148057247731243651084258194009459936702909655448969693589800987266378249891157940262898554047247605049549997783511107373248462587318323152524969684724690316918761387154882496367769626921299091688377118938693074486325995308403232228282839975697 sage: p=(n-phi+1-((n-phi+1)^2-4*n).nth_root(2))//2 sage: q=n//p sage: Fp=Integers(p) sage: flag=[...] # encrypted flag sage: f2=[0 if Fp(f).is_square() else 1 for f in flag]
运行后得到:
把这一串二进制转为字符串即可:
flag{bd4f1790-f4a2-4904-b4d2-8db8b24fd864}