# Writeup for problem "GM" in 虎符CTF 2020

 1 2 3 4 5 6  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 

c 是否为 mod N 下的平方剩余可以通过勒让德符号来判断，N 不是个素数所以要分解 N ，然后通过勒让德符号来判断 $c \ mod \ p$ 是否为模 p 下的平方剩余，逐个判断就得到了明文的二进制流。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18  phi = 9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990711180904598841255660443214091848674376245163953774717113246203928244509033734184913005865837620134831142880711832256634797590773413831659733615722574830257496801417760337073484838170554497953033487131634973371143357507027731899402777169516770264218656483487045393156894832885628843858316679793205572348688820 N = 9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990905528141072864168544519279897224494849206184262202130305820187569148057247731243651084258194009459936702909655448969693589800987266378249891157940262898554047247605049549997783511107373248462587318323152524969684724690316918761387154882496367769626921299091688377118938693074486325995308403232228282839975697 K = N-phi+1 # p+q L, R = 1, K while LN: R = mid elif y
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36  from Crypto.Util.number import * N = 9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990905528141072864168544519279897224494849206184262202130305820187569148057247731243651084258194009459936702909655448969693589800987266378249891157940262898554047247605049549997783511107373248462587318323152524969684724690316918761387154882496367769626921299091688377118938693074486325995308403232228282839975697 p = 94130524494940356506875940901901506872984699033610928814269310978003376307730580667234209640309443564560267414630644861712331559440658853201804556781784493376284446426393074882942957446869925558422146677774085449915333876201669456003375126689843738090285370245240893337253184644114745083294361228182569510971 def Legrend(a, p): if a == 1: return 1 if p % a == 0: return 0 if a % 2 == 0: return Legrend(a // 2, p) * pow(-1, (pow(p, 2) - 1) // 8) return Legrend(p % a, a) * pow(-1, (a - 1)*(p - 1) // 4) def read_file(): f = open("output") fileread = f.read() cipher_list = [] Number = "0123456789" temp = '' for i in fileread: if i not in Number and len(temp) != 0: cipher_list.append(int(temp)) temp = '' elif i in Number: temp += i return cipher_list cipher_list = read_file() ans='' for cip in cipher_list: if Legrend(cip,p)==1: ans+='0' elif Legrend(cip,p)==-1: ans+='1' m=int(ans,2) print(long_to_bytes(m)) 

flag{bd4f1790-f4a2-4904-b4d2-8db8b24fd864}