2023DASCTF X 0psu3十一月挑战赛

GeneratePrime

解最多的题，但我不会做。赛后一看wp，好啊原来是原题。研究一下原理，感觉确实难度可以。

题目

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

分析

参考博客 \[n=(p^4+p^3+p^2+p+1)\cdot p\cdot r\]

\[p^5-1=(p-1)\cdot(p^4+p^3+p^2+p+1)=(p-1)\cdot q\]

构造一个阶为\(p^5-1\)的域，利用其生成元\(g\)计算\(g^n\)的阶。

\[order(g^n)=\frac{p^5-1}{gcd(n,p^5-1)}=\frac{p^5-1}{q}=p-1\]

对于阶的定义，我们可以得到阶为\(p-1\)的任意元素\(a\)满足\(a^{p-1}=1\)，\(1\)指幺元。

参考上述博客，应用群环域的性质得到\(g^n=ax^2+bx+c\)，即表示成度最大为二的多项式。

结合上述两式写成如下形式： \[(0x^2+0x+c)^{p-1}=1,c \in (0,p)\]

此时用到另一条性质，阶为\(p-1\)的元素个数为\(\phi(p-1)\)个，而\(c\)的取值个数要大于\(\phi(p-1)\)个，因此\(g^n\)只能由常数产生。

至此上述的分析都是在阶为\(p^5-1\)的环上进行的讨论，而实际当中我们并没有p，倘若构造出模\(n\)的环，那么在该环上计算得到的\(g^n\)的一次项和二次项系数应该都是\(kp\)，这样再与\(n\)求解gcd即可。

exp

k = 5
n=
e=65537
c=

R = Zmod(n)["x"]
while True:
    Q = R.quo(R.random_element(k))
    pp1 = gcd(ZZ(list(Q.random_element() ^ n)[1]), n)
    if pp1 != 1:
        print(pp1)
        qq = sum([pp1**i for i in range(k)])
        rr = n // (pp1 * qq)
        assert n == pp1 * qq * rr
        break
phi = (pp - 1) * (qq - 1) * (rr - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m))

FindPrime

没啥意思，就嗯缝，agcd+amm

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

exp

from sympy.ntheory.modular import crt
from Crypto.Util.number import *
n = 68770027076980723946939075792572969610228738501865973895618044035550466673326811210718966610231582633896160130057212343512606374318082678735227998163020559923237005947682357783487924911009663067842443440348588088325506801639924926097944176357432282915587075930988972621730524537492705984723766652062305363027

c = 46935517038224473812546067305866276864169387205589347201858550096671613860700878462369638807831295923952343159795466895818221029692119135003812788250010552362110290387383510093277209478665971066986914981717774698233220968427990066291572377851164878122374241804989577737820368814455456808941766309324614067608
p = 8475751295865335034925394592760419247986527875671629878727167186701425140981793707985425024055132199826439868047385642931090550239766413089832011638673209
q = n//p
e = [7,191,23111329]
N = n
d1 = inverse(e[2],(p-1)*(q-1))
c = pow(c,d1,N)

#p
dp1 = inverse(191,p-1)
cp = pow(c,dp1,p)
PR.<x> = Zmod(p)[]
f = x^7 - cp
resp = f.roots()

#q
PR.<x> = Zmod(q)[]
f = x^(191*7) - c
resq = f.roots()

for i in resp:
    for j in resq:
        ti = int(i[0])
        tj = int(j[0])
        n = [p,q]
        c = [ti,tj]
        m = crt(n,c)[0]
        if(b"DASCTF" in long_to_bytes(int(m))):
            print(long_to_bytes(int(m)))

MathFactor1

题目

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

思路一

给了\(p^{21}+q^{17}\)的低位，相当于给了一组剪枝条件，从低位开始爆破即可，最后得到的p_list都不算长，遍历一下通过coppersmith打一个高位就可。这是官方wp给的解法，用剪枝确实不好想，给了这样一个限制剪枝效果确实挺好。

def get_pq(n,d1):
    a = [0]
    b = [0]
    maskx = 1
    maskn = 2
    for i in range(300):
        nbit = n % maskn
        t_a = []
        t_b = []
        for j in range(len(a)):
            for aa in range(2):
                for bb in range(2):
                    d=d1% maskn
                    tmp2 = n % maskn
                    tmp_p=(aa * maskn // 2 + a[j])
                    tmp_q=(bb * maskn // 2 + b[j])
                    tmp1 =(tmp_p**21+tmp_q**17) % maskn
                    tmp3=(tmp_p*tmp_q)%maskn
                    if tmp2 == tmp3:
                        if tmp1==d:
                            t_a.append(aa * maskn // 2 + a[j])
                            t_b.append(bb * maskn // 2 + b[j])
        maskx *= 2
        maskn *= 2
        a = t_a
        b = t_b
    return a,b

n=89049581381915401856270440494182068395799559452947499744642830361236578373835725708887668528820916651578050248209041339369091828040992115394942524278397293747808840107939504743946806866214713225533666120894844131211241905215662457238793580469827973839976134854993162976454283311566973255659612267446150515233
e=65537
c=16305239798028293699632813396005973660370581911030264211210444559974188415332021689054795983319112132645051076901780239982290095820283651929773925636804434706351474493000010749679965744672518110692104573489299874390925347271040454693791271882869477780584606934066152476594086178041874762147934091597942667138
d1=1253867202722198232827428701701674148965306906567632781415318063046179456643047348348144258
p_list,q_list=get_pq(n,d1)
R.<x>=Zmod(n)[]
for p_ in p_list:
    f=p_+pow(2,299)*x
    f1=f.monic()
    r=f1.small_roots(X=2^214,beta=0.49)
    if r:
        p=f(r[0])
        p=int(p)
        print(p)
        assert isPrime(p)
        q=n//p
        phi=(p-1)*(q-1)
        d=invert(e,phi)
        m=pow(c,d,n)
        flag=long_to_bytes(int(m))
        print(flag)
        break

思路二

通过解模\(2^{300}\)的方程来得到可能的低300位p，\(d=p^{21}+q^{17}\)，再遍历求高位即可。

p = var('p')
p0 = solve_mod([p^38 - d1*p^17 + n^17  == 0], 2^300)