2023-DASCTFX0psu3十一月挑战赛

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

2023-DASCTFX0psu3十一月挑战赛——Crypto题解

GeneratePrime

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
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
import os

def 0psu3_The_best(sz, d):
    while True:
        p = getPrime(sz)
        pp = sum([p**i for i in range(d)])
        if isPrime(pp):
            return p, pp


p, q = 0psu3_The_best(512, 5)
r = getPrime(512 * 5)
n = p * q * r
e = 65537
flag=open("flag.txt", "rb").read().strip()
flag1=flag+os.urandom(128)
m=bytes_to_long(flag1)

c = pow(m, e, n)

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


#n=43090231453250894711427929679917165532091051269639380881822679198388872373018031295429558758883298138388596507242928145888959963579111847255588834248367032580980272245414738073179172684104908272069503607376171584936239696444309039211273376010193165083254209608051430794825261116490356392215410064858020176711199543381037420111454942356936721487016187240237683725310306748046587503625096246489043270381153251813360521583717685413070481576320194446237522118380283335294528606720928637529817170809666802598938788405154468683850385277659812316577873886708164549255359514776884765904417881419804464020855420288884972204146588152412816874161445668955639456202226751519881834234916642218078966066353317917939418964763844067220460513388433020071277477619189495465483910271310025371745344364984826481983188861624474015117761898377237745775289039922285111681410319016537270412509750339539020876501534842403407208957382830000761065368861209033791387480377889838737241326116532852335478193204425626487166234964754732945953080086117315162916374952094149599597509405176646068341218684523765974759907645226607364627690026025662221036766148813918691578120023886400197652148214238256715089883892069133754778609710846757189987335827693169644541734443763194942694587436469448973201513131503797898892822373949177030567791519349220158287318717788746060997955057747930375117780320371517616412423571775682868481089431670802944047375824503353609019686495670630728618082254293585479431369645935654024149490741245953271830453426444847467908952699660750809490650479987
#e=65537
#c=30862228874892553476569860337345503267926249096036551213683005116620750680365154103242717714230966827288361499342464202425467642950081816675486231250411347472976482409360391136808439034217688010072648722396312121758844966972323513456884732046270240934002095706243044210312663525491282667971502534420245427643076262414036655243117610886157895994101178663474990136516153062956803591842233732498519246731337518545018734984319536536205092573418457928952414660837594265802406473201400259189950484841504227372735345451459452313825309333631615286962304963039625162366186574440146535361888708570569938418676320446653266676364765870547213167058713058609788316647593834008151805692510044158607162858906528913516242904419457446211348504248317409844426309455978985314882123424453618672960876022996245213882467954521212481418830104602302179759479012618982228223244131619557639469872139485197176384683400796204681045965981417650462297978265085323342772310690638049411549216990505001950512428646871875659468885490055363436412364532718888124906227240501145227269727887236864060558999336443165765870556727793253297515155026234234422303238380776900105115890363548589834345888430695886678231459920101695996112312269637459823479947618045447071359886515163416153117176539752947700226596291435270282598638974889205601333097978743387412651687356072223691445472690647184292120882095587563356691450107194982597794937293154289560470269606300576216128045797481404606810315677962659136641943747123985144899464108823536597185386155005111274476874957827391438859327653936

可以参考：ImaginaryCTF 2023] - sus (comibear.kr)

想了解原理可以参考：2023-DASCTFX0psu3十一月挑战赛-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

涉及商环等知识，先搁置一会

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#sage
from Crypto.Util.number import *

n=
e=65537
c=

R = PolynomialRing(Zmod(n), "x")

while True:
    Q = R.quo(R.random_element(5))
    res = gcd(int(list(Q.random_element() ^ n)[1]), n)
    if res > 1:
        p = res
        q = p^4 + p^3 + p^2 + p + 1
        r = n // (p*q)
        assert p * q * r == n
        phi = (p-1)*(q-1)*(r-1)
        d = inverse(e, phi)
        m = pow(c, d, n)
        print(long_to_bytes(int(m)))
        break
        # DASCTF{just_a_very_very_easy_task_with_your_talent_is_not}

FindPrime

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
from Crypto.Util.number import *
from gmpy2 import *

P = getPrime(int(512))
p_list=[]

for i in range(30):
    q=getPrime(1024)
    r=getPrime(450)
    l=q*P+r
    p_list.append(l)
    
path1="D:/CTF题目\密码\出题1/"
with open("output.txt",'w')as f1:
    for val in p_list:
        f1.write(str(val))
        f1.write("\n")

Q=getPrime(512)
N=P*Q
e=e1*e2
m=bytes_to_long(flag2)
c=pow(m,e,N)
assert m<N
print("N=",N)
print("e=",e)
print("c=",c)

#N=68770027076980723946939075792572969610228738501865973895618044035550466673326811210718966610231582633896160130057212343512606374318082678735227998163020559923237005947682357783487924911009663067842443440348588088325506801639924926097944176357432282915587075930988972621730524537492705984723766652062305363027
#e=30899846873
#c=46935517038224473812546067305866276864169387205589347201858550096671613860700878462369638807831295923952343159795466895818221029692119135003812788250010552362110290387383510093277209478665971066986914981717774698233220968427990066291572377851164878122374241804989577737820368814455456808941766309324614067608

$l_i = q_i\times P + r_i$

AGCD问题，参考格密码 | Lazzaro (lazzzaro.github.io)

构造格：其中$t$为$r_i$的数量级

LLL规约后，得到$q_0\times 2^t$，进而求得$q_0$

然后$l_0 // q_0 = P$，因为$r_0\approx2^{450},q_0\approx2^{1024}$，整除后剩下$P$

得到$P$之后，解RSA

$\because e = 30899846873 = 7 \times 191 \times 23111329$

发现$\frac{e}{7}$分别与$\phi(n),P-1,Q-1$存在公因数$191,1,191$

对于$\frac{e}{7}$我们可以求出$m^7 \equiv c^{d_1} \mod P$，其中$\frac{e}{7}\times d_1 \equiv 1 \mod (P-1)$

同理$\frac{e}{191}$分别与$\phi(n),P-1,Q-1$存在公因数$7,7,7$，对于这个我们没法求逆元

$\frac{e}{1337}$分别与$\phi(n),P-1,Q-1$存在公因数$1,1,1$

对于$\frac{e}{1337}$我们可以求得$m^{1337}\equiv c^{d_2}\mod (Q-1)$,其中$\frac{e}{1337}\times d_2 \equiv 1\mod (Q-1)$

上面分别选择$P,Q$作为模是为了下面用中国剩余定理，为什么不在第二处用$n$，是因为以$n$作为模数的话，不利于有限域开方

然后分别对$m^{7},m^{1337}$有限域开发求得因子，再遍历因子用中国剩余定理

exp:

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from Crypto.Util.number import *
import gmpy2

N=68770027076980723946939075792572969610228738501865973895618044035550466673326811210718966610231582633896160130057212343512606374318082678735227998163020559923237005947682357783487924911009663067842443440348588088325506801639924926097944176357432282915587075930988972621730524537492705984723766652062305363027
e=30899846873
c=46935517038224473812546067305866276864169387205589347201858550096671613860700878462369638807831295923952343159795466895818221029692119135003812788250010552362110290387383510093277209478665971066986914981717774698233220968427990066291572377851164878122374241804989577737820368814455456808941766309324614067608

l = []
for i in open("output.txt","r").readlines():
    l.append(eval(i))
    
n = 30
Ge = Matrix(ZZ,n,n)

for i in range(n):
    Ge[0,i] = l[i]
    Ge[i,i] = -l[0]

t = 2^450
Ge[0,0] = t

q0 = int(abs(Ge.LLL()[0][0]) // t)
P = int(abs(l[0] // q0))

Q = N // P
phi = (P-1)*(Q-1)

d1 = gmpy2.invert(e//7,P-1)
m_7 = pow(c,d1,P)

d2 = gmpy2.invert(e//1337,Q-1)
m_1337 = pow(c,d2,Q)

R.<x> = PolynomialRing(Zmod(P))
f = x^7 - m_7
f = f.monic()
res1 = f.roots()

R.<x> = PolynomialRing(Zmod(Q))
f = x^1337 - m_1337
f = f.monic()
res2 = f.roots()

for i in res1:
    for j in res2:
        m = CRT_list([int(i[0]),int(j[0])],[P,Q])
        flag = long_to_bytes(int(m))
        if b"DASCTF" in flag:
            print(flag)
            break
# DASCTF{VERY_VERY_EASY_AND_TAKE_THE_NEXT_TIME}

MathFactor——不会

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 random import randint
from Crypto.Util.number import *
from secret import flag
def encrypt(key, message, mask):
    return pow(64901, message^^mask, key)
def get_Prime_leak(bits,t1):
    x,y=0,1
    while True:

        u=randint(1,200)
        v=randint(1,200)
        x,y=u*x+t1*v*y,v*x-u*y
        if int(x).bit_length()<=bits//2:
            p=x^2+t1*y^2|1
            if isPrime(int(p)) and int(p).bit_length()>=bits:
                return p
        else:
            x,y=0,1
t1=getPrime(16)
print(f"t1={t1}")
p=get_Prime_leak(512,t1)
q=get_Prime_leak(512,t1)
assert p>q
n=p*q
print(f"n={n}")
flag=bytes_to_long(flag)
messages = [getRandomNBitInteger(flag.bit_length()) for i in range(200)]
enc = [encrypt(p, message, flag) for message in messages]

with open("output.txt",'w')as f2:
    f2.write(f'message = {messages}\n')
    f2.write(f'enc = {enc}')

#t1=39041
#n=31757681951092898377241647622353350811555571588021442714393002561722357855033517882719102833176105251763057313366942759802483366389547670310504898517419619177075155149247837212852121269080431969095421646338619498652624131319645919876504536274428562199882910834700167991957991646691071345200388502034841600000001

MathFactor1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
p=getPrime(512)
q=getPrime(512)
n=p*q
d=(p**21+q**17)
d1=d&(2**300-1)

flag=open("flag.txt").read().strip()
import os

flag=flag+os.urandom(60)

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

#n=89049581381915401856270440494182068395799559452947499744642830361236578373835725708887668528820916651578050248209041339369091828040992115394942524278397293747808840107939504743946806866214713225533666120894844131211241905215662457238793580469827973839976134854993162976454283311566973255659612267446150515233
#e=65537
#c=16305239798028293699632813396005973660370581911030264211210444559974188415332021689054795983319112132645051076901780239982290095820283651929773925636804434706351474493000010749679965744672518110692104573489299874390925347271040454693791271882869477780584606934066152476594086178041874762147934091597942667138
#d1=1253867202722198232827428701701674148965306906567632781415318063046179456643047348348144258

参考这篇博客中Crack p部分，WriteUp(Aurora) - Mission Impossible | 0xDktb’s Blog (dunkirkturbo.github.io)

$\because d = p^{21} + q^{17}$

$\therefore d\times p^{17} = p^{38} + n^{17}$

题目给出d1 = d & (2**300 - 1)

则有$d_1\times p^{17} \equiv p^{38} + n^{17} \mod 2^{300}$

因为$p$是512bit的数，解上面这个方程能得到低300位，便可以用coppersmith恢复$p$

exp:

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
# sage
from Crypto.Util.number import *
import gmpy2

n=89049581381915401856270440494182068395799559452947499744642830361236578373835725708887668528820916651578050248209041339369091828040992115394942524278397293747808840107939504743946806866214713225533666120894844131211241905215662457238793580469827973839976134854993162976454283311566973255659612267446150515233
e=65537
c=16305239798028293699632813396005973660370581911030264211210444559974188415332021689054795983319112132645051076901780239982290095820283651929773925636804434706351474493000010749679965744672518110692104573489299874390925347271040454693791271882869477780584606934066152476594086178041874762147934091597942667138
d1=1253867202722198232827428701701674148965306906567632781415318063046179456643047348348144258

var("p")
f = p^38 + n^17 - d1*p^17 == 0

roots = solve_mod([f],2^300)

for i in roots:
    plow = int(i[0])
    R.<x> = PolynomialRing(Zmod(n))
    f = x * 2^300 + plow
    f = f.monic()
    res = f.small_roots(2^212,beta=0.4)
    if res:
        p = int(res[0])*2^300 + plow
        q = n // p
        d = gmpy2.invert(e,(p-1)*(q-1))
        m = pow(c,d,n)
        print(long_to_bytes(int(m)))			#DASCTF{0psu3_is_the_most_Greatest_army}
        break
-------------已经到底啦！-------------