GM

题目给定源码

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

分析中查找到一位大师傅的资料，有该题的类似解法。

https://ctftime.org/writeup/16120

经分析

phi = 9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990711180904598841255660443214091848674376245163953774717113246203928244509033734184913005865837620134831142880711832256634797590773413831659733615722574830257496801417760337073484838170554497953033487131634973371143357507027731899402777169516770264218656483487045393156894832885628843858316679793205572348688820(output第一个)
pkey[1] = n = 9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990905528141072864168544519279897224494849206184262202130305820187569148057247731243651084258194009459936702909655448969693589800987266378249891157940262898554047247605049549997783511107373248462587318323152524969684724690316918761387154882496367769626921299091688377118938693074486325995308403232228282839975697（output第二个）
剩下的列表为enc

利用sage计算

sage: phi = 94334516617494132259194145952433213117629020379088509547997033960838
....: 63718641136503053215995576558003171249192969972864840795298784730553210417
....: 98371459376455758292743478491517763973199831089116868599924093740787177136
....: 99717135153136341987446160746108669240948546719003348103531274467786071371
....: 57751925680243990711180904598841255660443214091848674376245163953774717113
....: 24620392824450903373418491300586583762013483114288071183225663479759077341
....: 38316597336157225748302574968014177603370734848381705544979530334871316349
....: 73371143357507027731899402777169516770264218656483487045393156894832885628
....: 843858316679793205572348688820
sage: n=943345166174941322591941459524332131176290203790885095479970339608386371
....: 86411365030532159955765580031712491929699728648407952987847305532104179837
....: 14593764557582927434784915177639731998310891168685999240937407871771369971
....: 71351531363419874461607461086692409485467190033481035312744677860713715775
....: 19256802439909055281410728641685445192798972244948492061842622021303058201
....: 87569148057247731243651084258194009459936702909655448969693589800987266378
....: 24989115794026289855404724760504954999778351110737324846258731832315252496
....: 96847246903169187613871548824963677696269212990916883771189386930744863259
....: 95308403232228282839975697
sage: p=(n-phi+1-((n-phi+1)^2-4*n).nth_root(2))//2
sage: p
94130524494940356506875940901901506872984699033610928814269310978003376307730580667234209640309443564560267414630644861712331559440658853201804556781784493376284446426393074882942957446869925558422146677774085449915333876201669456003375126689843738090285370245240893337253184644114745083294361228182569510971
sage: q=n//p
sage: q
100216711979082556377200124903474313599976321274816484378304672662900171906266478070844182716079881540999761528986068197079878654411887736955737660906283803174161740862819849415729979371880583995409044839777513091451849412985192528374337852907661670174530234397743068706607004213367391908429077794527921775907
sage: Fp=Integers(p)
sage: enc=[那一堆东西]
sage: flag=[0 if Fp(f).is_square() else 1 for f in enc]
sage: print(flag)
[1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1]

将二进制数字导出整理，编写python脚本得到flag。

>>> from libnum import *
>>> n2s(0b1100110011011000110000101100111011110110110001001100100001101000110010001100010011011100111001001100000010110101100110001101000110000100110010001011010011010000111001001100000011010000101101011000100011010001100100001100100010110100111000011001000110001000111000011000100011001000110100011001100110010000111000001101100011010001111101)
'flag{bd4f1790-f4a2-4904-b4d2-8db8b24fd864}'