Contents

Writeup for problem "GM" in 虎符CTF 2020

Contents

看代码发现生成的 N 和 phi 很特殊,有了 N 和 phi 显然可以算出来 p , q。

看主要加密部分是把明文转化成二进制流,对 bi 逐个加密:

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

如果令 e = int(br + bi, 2) ,$c = x^e r^2 mod N$ ,如果 bi 为 0 ,那么 e 就是偶数,可以表示为 e = 2k ,那么 c 就是 $(x^k*r)^2 \ mod \ N$ 也就是平方剩余,反之 c 不是平方剩余也就说明了 bi 为 1 。

c 是否为 mod N 下的平方剩余可以通过勒让德符号来判断,N 不是个素数所以要分解 N ,然后通过勒让德符号来判断 $c \ mod \ p$ 是否为模 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 L<R:
    mid = (L+R)//2
    if K <= mid:
        break
    y = (K-mid)*mid
    if y>N:
        R = mid
    elif y<N:
        L = mid
    else:
        print(mid)
        break
#94130524494940356506875940901901506872984699033610928814269310978003376307730580667234209640309443564560267414630644861712331559440658853201804556781784493376284446426393074882942957446869925558422146677774085449915333876201669456003375126689843738090285370245240893337253184644114745083294361228182569510971
 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}