[虎符网络安全赛道]Crypto-GM1 min read

题目如下：

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}