2022 Strong Net Cup CTF---Strong Net Pioneer ASR wp

题目

题目代码：

from Crypto.Util.number import getPrime
from secret import falg
pad = lambda s:s + bytes([(len(s)-1)%16+1]*((len(s)-1)%16+1))

n = getPrime(128)**2 * getPrime(128)**2 * getPrime(128)**2 * getPrime(128)**2
e = 3

flag = pad(flag)
print(flag)
assert(len(flag) >= 48)
m = int.from_bytes(flag,'big')
c = pow(m,e,n)

print(f'n = {
      n}')
print(f'e = {
      e}')
print(f'c = {
      c}')

''' n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001 e = 3 c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149 '''

思路

首先对n进行分解得到4个素数,p、q、r、t,可以使用在线的factordbwebsite breakdown,也可以用yafu（It is recommended to prescribe first using this tool,Then decompose its value again）

Break down a website online
factordb分解结果

yafu分解结果

The decomposition yields four prime numbers as follows

p = 225933944608558304529179430753170813347
q = 260594583349478633632570848336184053653
r = 218566259296037866647273372633238739089
t = 223213222467584072959434495118689164399

正常情况下的RSA都要求e和phi(n)要互素,不过也有一些e和phi(n)There are problems with small common divisors,These questions can be calculatede对phi(n)的逆元d来求解.But this question ise和phi(n)的最大公约数就是e本身,也就是说e | p-1,只有对c开eThe square root will do,Here is a finite field opening3The square root problem.
PS:上述中的phi(n)也可以是,（p-1）或者（q-1）或者（r-1）或者（t-1）

will be the congruence equation
$m^e\equiv c(\text{mod}n)$
简化为
$m^e\equiv c(\text{mod}p)$
$m^e\equiv c(\text{mod}q)$
$m^e\equiv c(\text{mod}r)$
$m^e\equiv c(\text{mod}t)$
然后分别在GF（p）、GF(q)、GF（r）、GF(t)上对c开e=3次方根,再用CRTCombine it to get itmod n下的解

解题脚本

sage脚本如下

import libnum
n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
e = 3
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149
p = 225933944608558304529179430753170813347
q = 260594583349478633632570848336184053653
r = 218566259296037866647273372633238739089
t = 223213222467584072959434495118689164399

R.<x> = Zmod(p)[]
f = x^e-c
f = f.monic()
results1 = f.roots()

R.<x> = Zmod(q)[]
f = x^e-c
f = f.monic()
results2 = f.roots()

R.<x> = Zmod(r)[]
f = x^e-c
f = f.monic()
results3 = f.roots()

R.<x> = Zmod(t)[]
f = x^e-c
f = f.monic()
results4 = f.roots()
for i in results1:
    for j in results2:
        for l in results3:
            for k in results4:
                param1 = [int(i[0]),int(j[0]),int(l[0]),int(k[0])]
                param2 = [p,q,r,t]
                m = CRT_list(param1,param2)
                flag = libnum.n2s(int(m))
                if b'flag' or b'gwb' or b'FLAG' or b'GWB' in flag:
                    print(flag)

flag:

flag{
    Fear_can_hold_you_prisoner_Hope_can_set_you_free}

【There are some grievances that are reluctant to speak to others,Not getting a response from those around you,All kinds of expectations、憧憬、The voice of wish,Like a drum in my heart,resounded in his own world.Heart is dumb,Always silent,It's like a person shouting hoarse,Still no one heard,This person will become less and less fond of talking,been silent,until it becomes a mute.】