[红明谷CTF 2022]easy_ya

题目

from Crypto.Util.number import *
import os

from flag import flag
def gen():
    e = 3
    while True:
        try:
            p = getPrime(512)
            q = getPrime(512)
            n = p*q
            phi = (p-1)*(q-1)
            d = inverse(e,phi)
            return p,q,d,n,e
        except:
            continue
    return
p,q,d,n,e = gen()
r = getPrime(512)
m = bytes_to_long(flag+os.urandom(32))
M = m%r
c = pow(m,e,n)
print("r = %d"%r)
print("M = %d"%M)
print("n = %d"%n)
print("e = %d"%e)
print("c = %d"%c)
'''
r = 7996728164495259362822258548434922741290100998149465194487628664864256950051236186227986990712837371289585870678059397413537714250530572338774305952904473
M = 4159518144549137412048572485195536187606187833861349516326031843059872501654790226936115271091120509781872925030241137272462161485445491493686121954785558
n = 131552964273731742744001439326470035414270864348139594004117959631286500198956302913377947920677525319260242121507196043323292374736595943942956194902814842206268870941485429339132421676367167621812260482624743821671183297023718573293452354284932348802548838847981916748951828826237112194142035380559020560287
e = 3
c = 46794664006708417132147941918719938365671485176293172014575392203162005813544444720181151046818648417346292288656741056411780813044749520725718927535262618317679844671500204720286218754536643881483749892207516758305694529993542296670281548111692443639662220578293714396224325591697834572209746048616144307282
'''

题解

由题目可得

M=m%rm=M+k∗r（1）M = m\%r\\\qquad \qquad m=M+k*r\qquad（1）

又因为

c=me(modn)(2)c=m^e\quad(mod\quad n)\qquad(2)

将(1)带入（2）中，coppersmith，构造多项式

f=(M+k∗r)3−cf = (M+k*r)^3 - c

求出m，由题目可知m是长度为 32 字节的随机数与flag拼接在一起得到的，所以m前半部分是flag

wp

#sage
from Crypto.Util.number import long_to_bytes
r = 7996728164495259362822258548434922741290100998149465194487628664864256950051236186227986990712837371289585870678059397413537714250530572338774305952904473
M = 4159518144549137412048572485195536187606187833861349516326031843059872501654790226936115271091120509781872925030241137272462161485445491493686121954785558
n = 131552964273731742744001439326470035414270864348139594004117959631286500198956302913377947920677525319260242121507196043323292374736595943942956194902814842206268870941485429339132421676367167621812260482624743821671183297023718573293452354284932348802548838847981916748951828826237112194142035380559020560287
e = 3
c = 46794664006708417132147941918719938365671485176293172014575392203162005813544444720181151046818648417346292288656741056411780813044749520725718927535262618317679844671500204720286218754536643881483749892207516758305694529993542296670281548111692443639662220578293714396224325591697834572209746048616144307282

PR.<x> = PolynomialRing(Zmod(n))
m0 = x*r + M
f = (m0^3) - c
f = f.monic()
#f.small_roots() 方法返回的是一个 SageMath 的多项式对象的列表
x0 = int(f.small_roots()[0])
print(x0)
print(long_to_bytes(m))
#b'flag{53a2e494-964d-4506-a2c4-c34b9475dedd}W\xf1X6\xacP\x9bc~9\xfd\x0f\x96\xbf\x92\xb9+\xe5\xebPJ\x17\xc4\xb2\xe8\xad\x01\n\xf2j\xae\x15'
#b'flag{53a2e494-964d-4506-a2c4-c34b9475dedd}

[蓝帽杯2022]corrupted_key

题目

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from secret import flag

key = RSA.generate(1024)
open("flag.enc",'wb').write(PKCS1_OAEP.new(key.publickey()).encrypt(flag))
open('priv.pem','wb').write(key.exportKey('PEM'))

'''
-----BEGIN RSA PRIVATE KEY-----
MIICXgIBAAKBgQDXFSUGqpzsBeUzXWtG9UkUB8MZn9UQkfH2Aw03YrngP0nJ3NwH
UFTgzBSLl0tBhUvZO07haiqHbuYgBegO+Aa3qjtksb+bH6dz41PQzbn/l4Pd1fXm
dJmtEPNh6TjQC4KmpMQqBTXF52cheY6GtFzUuNA7DX51wr6HZqHoQ73GQQIDAQAB








yQvOzxy6szWFheigQdGxAkEA4wFss2CcHWQ8FnQ5w7k4uIH0I38khg07HLhaYm1c
zUcmlk4PgnDWxN+ev+vMU45O5eGntzaO3lHsaukX9461mA==
-----END RSA PRIVATE KEY-----
'''

题解

拿到了一个残缺的私钥文件，通过PEM文件格式，可以获得n,e,dp低位，以及u

PKCS#1形式的私钥结构

RSAPrivateKey ::= SEQUENCE {
 version Version,
 modulus INTEGER, -- n
 publicExponent INTEGER, -- e
 privateExponent INTEGER, -- d
 prime1 INTEGER, -- p
 prime2 INTEGER, -- q
 exponent1 INTEGER, -- d mod (p-1)
 exponent2 INTEGER, -- d mod (q-1)
 coefficient INTEGER -- (inverse of q) mod p 
}

先将私钥文件的内容base64解密以16进制输出

2023-05-26 (3)

2023-05-26 (4)

提取信息：

key =b'\x30\x82\x02\x5e\x02\x01\x00\x02\x81\x81\x00\xd7\x15\x25\x06\xaa\x9c\xec\x05\xe5\x33\x5d\x6b\x46\xf5\x49\x14\x07\xc3\x19\x9f\xd5\x10\x91\xf1\xf6\x03\x0d\x37\x62\xb9\xe0\x3f\x49\xc9\xdc\xdc\x07\x50\x54\xe0\xcc\x14\x8b\x97\x4b\x41\x85\x4b\xd9\x3b\x4e\xe1\x6a\x2a\x87\x6e\xe6\x20\x05\xe8\x0e\xf8\x06\xb7\xaa\x3b\x64\xb1\xbf\x9b\x1f\xa7\x73\xe3\x53\xd0\xcd\xb9\xff\x97\x83\xdd\xd5\xf5\xe6\x74\x99\xad\x10\xf3\x61\xe9\x38\xd0\x0b\x82\xa6\xa4\xc4\x2a\x05\x35\xc5\xe7\x67\x21\x79\x8e\x86\xb4\x5c\xd4\xb8\xd0\x3b\x0d\x7e\x75\xc2\xbe\x87\x66\xa1\xe8\x43\xbd\xc6\x41\x02\x03\x01\x00\x01'
key=key.hex()
n=key[22:-10]
e=key[-6:]
#print(n)
print("n=",int(str(n),16))
print("e=",int(str(e),16))

key2 =b'\xc9\x0b\xce\xcf\x1c\xba\xb3\x35\x85\x85\xe8\xa0\x41\xd1\xb1\x02\x41\x00\xe3\x01\x6c\xb3\x60\x9c\x1d\x64\x3c\x16\x74\x39\xc3\xb9\x38\xb8\x81\xf4\x23\x7f\x24\x86\x0d\x3b\x1c\xb8\x5a\x62\x6d\x5c\xcd\x47\x26\x96\x4e\x0f\x82\x70\xd6\xc4\xdf\x9e\xbf\xeb\xcc\x53\x8e\x4e\xe5\xe1\xa7\xb7\x36\x8e\xde\x51\xec\x6a\xe9\x17\xf7\x8e\xb5\x98'
key2=key2.hex()
#print(key2)
v=key2[36:]
#print(v)
print("v=",int(str(v),16))
dq_low=key2[:30]
#print(dq_low)
ql=int(str(dq_low),16)
print("dql_nkbits=",ql.bit_length())
#已知q的低位120位
print("dqlow=",ql)


#n= 151036135413139226687867011199700639084856588533884431118047808395603993635242690166659649156476428533386350427603713487259266502837260466348398817558768025404903682189934563578605367223796247470920497617904900418615352839562681665973088711089128789315193951623751145385357347144960284983398745189236464272961
#print(n.bit_length())
#e= 65537
#v= 11889246144866782519155392157369478059715977597114885585873502852127888907191116911762955888968046505980125449346852147369649024143226438553109462231463320
#dql_nkbits= 120
#dqlow= 1043891160170747082120115133012365745

已知n,e，dq的低位,和v.两种方法求解

方法一：官方解法：coppersmith先恢复dq再由dq泄露，分解n

e∗d≡1  mod  (phi)e∗d=k∗phi+1    两边同时模（q−1)∵dq=d  mod  (q−1)∴  e∗dq=k∗(q−1)+1e∗dq+k−1=k∗qq是未知，已知dq的低120位设x位dq的高位e∗(dqlow+x∗2120)+k−1=k∗qe*d\equiv1\ \ mod \ \ (phi)\\ e*d=k*phi+1\ \ \ \ \\两边同时模（q-1)\\ \because dq=d\ \ mod\ \ (q-1)\\ \therefore \ \ e*dq=k*(q-1)+1\\ e*dq+k-1=k*q\\ q是未知，已知dq的低120位\\ 设x位dq的高位\\ e*(dqlow+x*2^120)+k-1=k*q\\

联系U，构造多项式，求出dp

u≡q−1  mod  (p)两边同时乘以q的逆元,得到u∗q−1≡0  (mod  p)两边同时乘以k2∗q的逆元,得到u∗(k∗q)2−k2∗q≡0  (mod  n)将k∗q=e∗(dqlow+x∗2120)+k−1带入上式设k∗q=t构造多项式f=u∗t2−k∗qu\equiv q^{-1}\ \ mod \ \ (p) \\两边同时乘以q的逆元,得到\\ u*q-1\equiv 0\ \ (mod \ \ p)\\ 两边同时乘以k^2*q的逆元,得到\\ u*(k*q)^2-k^2*q\equiv 0\ \ (mod\ \ n)\\ 将k*q=e*(dqlow+x*2^{120})+k-1带入上式\\ 设k*q=t\\ 构造多项式f=u*t^2-k*q\\

获得x之后

得到dq=int(x[0]<<120)+dqlow得到dq = int(x[0] << 120) + dqlow

接下来就是dq泄露RSA | Lazzaro (lazzzaro.github.io)

dq≡d  mod  (q−1)dq\equiv d\ \ mod\ \ (q-1)\\

两边同乘e

dq∗e≡1  mod  (q−1)dq∗e−1=k∗(q−1)(dq∗e−1)∗d∗e=k′∗(q−1)k′=k∗d∗edq∗e∗d∗e−d∗e=k′∗(q−1)d∗e=−k′∗(q−1)+dq∗e∗d∗e≡1  mod  (phi)k1∗(q−1)+dq∗e−1=k2∗(p−1)∗(q−1)dq*e \equiv 1\ \ mod\ \ (q-1)\\ dq*e-1=k*(q-1)\\ (dq*e-1)*d*e=k'*(q-1)\\ k'=k*d*e\\ dq*e*d*e-d*e=k'*(q-1)\\ d*e=-k'*(q-1)+dq*e*d*e\equiv1\ \ mod\ \ (phi )\\ k1*(q-1)+dq*e-1=k2*(p-1)*(q-1)\\

化简得到

(q−1)∗(k2∗(q−1)−k1)+1=dq∗e(q-1)*(k2*(q-1)-k1)+1=dq*e

∵dp<(p−1)∴  (k2∗(q−1)−k1)∈(0,e)\because dp<(p-1)\\ \therefore \ \ (k2*(q-1)-k1)\in (0,e)

二：由dq的低位获得q的低位，再根据u，恢复q

e∗d≡1  mod  (phi)e∗d=k∗phi+1    两边同时模（q−1)∵dq=d  mod  (q−1)∴  e∗dq=k∗(q−1)+1e∗dq+k−1=k∗qq是未知，已知dq的低120位两边同时模上2120(e∗dq+k−1)∗k−1=q  mod  (2120)e*d\equiv1\ \ mod \ \ (phi)\\ e*d=k*phi+1\ \ \ \ \\两边同时模（q-1)\\ \because dq=d\ \ mod\ \ (q-1)\\ \therefore \ \ e*dq=k*(q-1)+1\\ e*dq+k-1=k*q\\ q是未知，已知dq的低120位\\ 两边同时模上2^{120}\\ (e*dq+k-1)*k^{-1}=q\ \ mod \ \ (2^{120})\\

k遍历（1，e)，求出 q的低位，coppersmith恢复q

u∗q=  (mod  p)u∗q=k∗p+1u∗q2−q=k′pk′=k∗q模pu∗q2−q=0u*q=\ \ (mod \ \ p)\\ u*q=k*p+1\\ u*q^2-q=k'p\\ k'=k*q\\ 模p\\ u*q^2-q=0

构造出多项式

wp

方法一：官方解法：coppersmith先恢复dq再由dq泄露，分解n

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import *
from gmpy2 import *
from tqdm import tqdm

n= 151036135413139226687867011199700639084856588533884431118047808395603993635242690166659649156476428533386350427603713487259266502837260466348398817558768025404903682189934563578605367223796247470920497617904900418615352839562681665973088711089128789315193951623751145385357347144960284983398745189236464272961
#print(n.bit_length())
e= 65537
u= 11889246144866782519155392157369478059715977597114885585873502852127888907191116911762955888968046505980125449346852147369649024143226438553109462231463320
dql_nkbits= 120
dqlow= 1043891160170747082120115133012365745
c = 96458723724899437870554342796876171017896652413964521193266438981853945238446913579867464909353925601873532290626111170073532116639383463734148270579305067733147411306325252107181823453497914478588342362177625026365513002442585949837516090367171824895036711246039928723021679235071368954348296729327873680822
#思路一coppersmith恢复dp，再dp泄露攻击设x为高位
def coppersmith(k):
    F.<x> = PolynomialRing(Zmod(n))
    t = e * (x * 2 ^ 120 + dqlow) + k - 1
    f =u * t ^ 2 - k * t
    f = f.monic()
    x0 = f.small_roots(X=2^392)
    return x0

def divide_pq(e, dq, n):
    for x in range(1, e):
        if (e * dq % x == 1):
            p = (e * dq - 1) // x + 1
            if (n % p != 0):
                continue
            q = n // p
            return q,p

for k in tqdm(range(e, -1, -1)):
    x0 = coppersmith(k)
    if len(x0) != 0:
        print("x0=",x0)
        dq = int(x0[0] << 120) + dqlow
        #恢复dq,dp泄露
        p, q = divide_pq(e, dq, n)
        phi=(p-1)*(q-1)
        d = inverse(e, phi)
        print("p=",p)
        print("q=",q)
        print("d=",d)
        key = RSA.construct((int(n), int(e), int(d)))     
        print(PKCS1_OAEP.new(key).decrypt(open('flag.enc', 'rb').read()))
        break
        
#p=12112790828812363063315417237469719611888243756064158121348026938824270601623590308149025542977097905953795136774300936003505715307199422663647014200158449
#q=12469144192094336933187534132907623337514842804208163244218540727384104398951558782195384932941310035462094951428865175221316720981428462265191789302379089
#d=66980701583036734736960294391078312622827897052791813876359026247918495979594634282982071853820451331222681673373427663666376575651344098661059603483956134335089509308267535247063609325195212704938058730366660923446510585605669518343968880619319880983999690229384618652977238799179660803464509489433199564801

方法二：由dq的低位获得q的低位，再根据u，恢复q

rom Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import *
from gmpy2 import *
from tqdm import tqdm
#法二：
#先由dq低位求出q的低位
q_low=[]
#使用步长为 2 的目的是只遍历奇数。这是因为偶数除了 2 外都不可能是素数，
for i in tqdm(range(1, e, 2)):
    try:
        q0 = inverse(i, 2 ** 120) * (e * dqlow + i - 1) % 2 ^ 120
        q_low.append(q0)
    except:
        continue
#找到满足条件的q的低位，恢复q
#PR.<x> = Zmod(n)[]
roots = []
for i in tqdm(range(len(q_low))):
    tq=2^120*x + int(q_low[i])
    f = u * tq ^ 2 - tq
    root = f.monic().small_roots(X = 2^392)
    if root:
        q = 2^120*int(root[0]) + int(q_low[i])
        p = n // q
        assert p * q == n
        d = inverse(e, (p - 1) * (q - 1))
        print("p=", p)
        print("q=", q)
        print("d=", d)
        rsa = RSA.construct((int(n), int(e), int(d), int(p), int(q)))
        c = long_to_bytes(c)
        print(PKCS1_OAEP.new(rsa).decrypt(c))
        #new(key): 创建一个新的 PKCS1_OAEP 密码器，key 是一个 RSA 密钥对象。
        #PKCS1_OAEP 类是用于 RSA 的 OAEP 填充方案的密码器
        #decrypt(ciphertext): 使用 RSA 私钥解密给定的密文。
        #p= 12112790828812363063315417237469719611888243756064158121348026938824270601623590308149025542977097905953795136774300936003505715307199422663647014200158449
        #q= 12469144192094336933187534132907623337514842804208163244218540727384104398951558782195384932941310035462094951428865175221316720981428462265191789302379089
        #d= 66980701583036734736960294391078312622827897052791813876359026247918495979594634282982071853820451331222681673373427663666376575651344098661059603483956134335089509308267535247063609325195212704938058730366660923446510585605669518343968880619319880983999690229384618652977238799179660803464509489433199564801
        #b'flag{f1bf5c44-e2b4-424f-baff-b38b73a82e72}'

[HZNUCTF2023]easy_dsa

题目

from hash import *
from sage import *
from secrets import flag
from Crypto.Util.number import *
from gmpy2 import invert


def dsa(hmac, _pk, _sk, k):
    _p, _q, _g, _y = _pk
    x = _sk
    r = pow(_g, k, _p) % _q
    s = ((hmac + x * r) * invert(k, _q)) % _q
    return int(r), int(s)


m = int(flag.hex(), 16)
p = getPrime(2048)
q = getPrime(256)
g = getRandomNBitInteger(2048)
y = pow(g, m, p)
pk = (p, q, g, y)
sk = m
hm1 = int(SM3(default_hm1), 16)
hm2 = int(SM3(default_hm2), 16)
nonce = getPrime(64)
xxxx = getPrime(20)
print(f"(r1, s1) = {dsa(hm1, pk, sk, nonce)}")
print(f"(r2, s2) = {dsa(hm1, pk, sk, nonce ** 2 + xxxx)}")
print(f"p = {p}\nq = {q}\ng = {g}\ny = {y}")
# (r1, s1) = (43665657147136977892760835332544097729763754398125679419859037123212964274095, 11372107439153704547599978617809027960018057676066118055075660375442954789009)
# (r2, s2) = (29184887007213204285288676779168140587575609668559831035949650649308618592275, 5011738292572181542092375902756977363590922060964162373234404450451520414798)
# p = 31961141251107494919420190534228520246958409864267239760354623819192809291490262139213317490432416411403367763443527530375117617196123131270496004125231254335150221348901335274505489844222882171272650010562960614279185073793274638651086760235178963210965828168433516820007716846876686795459738332444629111764967204355463398049697867061034126529189537688874999118692225915790053920062142349951686250122300061810240375783724631961234942175580462986265098353263395579346466921241016500821787793395554444982717141449909744838267161237273856377774256250949274635575801148994817767751541256849860886577256992383324866941911
# q = 69375998045163628324086568160767337544901252262545889505892695427466730978301
# g = 23095306638137759877487469277470910487928442296144598697677211337473146684728707820084075779044942034329888686699655576145455963231144004571165817481066424910959951439014314776050521403558035997997820617824839889597136772108383034876458141163933312284054415480674388788905935457149956424898637134087874179010376667509489926236214865373552518669840236207944772752416668193786003948717604980584661094548997197117467440864460714843246250800575997370964173558788145639802963655916833143883799542309432910222224223561677245110195809587171802538978009246887077924173034608600837785506594525481696000424121705524449481831586
# y = 30195133393879069638917191223585579396119430591488890396938821804398771785068454607425044458865556053274470709839502680269466948174813926392729790863065933078609827279352860810689776644132512095691760326095517755483748554008211568781998662554432781285208646921699265866446498342049913829592480268053599307065979016922204438675164034767731708343084371572648019835171087671868322447023378942812010740490724160077164191297435291229504616686997442254543493394641023587237077429236872101951650325361004443988267286616139798736713430746804524113024341440435623834197278500144543476528466395780355874841379098027115073850819

题解

nss上小师傅的题解![文章 - HZNUCTF 2023 preliminary]easyDSA rookie的WriteUp | NSSCTFimage-20230526100659378-1685066826813-7

获得h1

default_hm2 = b'HZNUCTFRound#1'
SM3解密
default_hm1 = b'2c01fd6136d3f0fd465f23314b50e78bb9d59924b4fe64707b440417583b16de'
h1 = int(default_hm1, 16)
print(h1)

image-20230526101555277

wp

from Crypto.Util.number import *
import itertools
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

(r1, s1) = (43665657147136977892760835332544097729763754398125679419859037123212964274095, 11372107439153704547599978617809027960018057676066118055075660375442954789009)
(r2, s2) = (29184887007213204285288676779168140587575609668559831035949650649308618592275, 5011738292572181542092375902756977363590922060964162373234404450451520414798)
p = 31961141251107494919420190534228520246958409864267239760354623819192809291490262139213317490432416411403367763443527530375117617196123131270496004125231254335150221348901335274505489844222882171272650010562960614279185073793274638651086760235178963210965828168433516820007716846876686795459738332444629111764967204355463398049697867061034126529189537688874999118692225915790053920062142349951686250122300061810240375783724631961234942175580462986265098353263395579346466921241016500821787793395554444982717141449909744838267161237273856377774256250949274635575801148994817767751541256849860886577256992383324866941911
q = 69375998045163628324086568160767337544901252262545889505892695427466730978301
g = 23095306638137759877487469277470910487928442296144598697677211337473146684728707820084075779044942034329888686699655576145455963231144004571165817481066424910959951439014314776050521403558035997997820617824839889597136772108383034876458141163933312284054415480674388788905935457149956424898637134087874179010376667509489926236214865373552518669840236207944772752416668193786003948717604980584661094548997197117467440864460714843246250800575997370964173558788145639802963655916833143883799542309432910222224223561677245110195809587171802538978009246887077924173034608600837785506594525481696000424121705524449481831586
y = 30195133393879069638917191223585579396119430591488890396938821804398771785068454607425044458865556053274470709839502680269466948174813926392729790863065933078609827279352860810689776644132512095691760326095517755483748554008211568781998662554432781285208646921699265866446498342049913829592480268053599307065979016922204438675164034767731708343084371572648019835171087671868322447023378942812010740490724160077164191297435291229504616686997442254543493394641023587237077429236872101951650325361004443988267286616139798736713430746804524113024341440435623834197278500144543476528466395780355874841379098027115073850819

h1=19905280947443115569469777697852124038269468456842113763109865796452965095134
#设两个参数
p.<k1,x0>=PolynomialRing(Zmod(q))
f=(s1*k1-h1)*inverse(r1,q)-(s2*k1**2+s2*x0-h1)*inverse(r2,q)
roots = small_roots(f, (2^64, 2^20), m=1, d=2)
k1,x0=roots[0]
x=(s1*k1-h1)*inverse(r1,q)%q
flag=hex(x)[2:]
print(bytes.fromhex(flag))


#b'JU57_@N_e@SY_5QU4RE_K!'

[DASCTF省赛2022]rssssssaaaa

题目

from Crypto.Util.number import *
from secret import flag
p = getPrime(1024)
q = getPrime(1024)
n = p*q
m = bytes_to_long(flag)
e = 65537
c = pow(m, e, n)

print("n =", n)
print("c =", c)
print("p =", p&((1<<560) - 1))#得到了560位全为1的二进制数，保留 p 的二进制表示的低 560 位


#n = 21595945409392994055049935446570173194131443801801845658035469673666023560594683551197545038999238700810747167248724184844583697034436158042499504967916978621608536213230969406811902366916932032050583747070735750876593573387957847683066895725722366706359818941065483471589153682177234707645138490589285500875222568286916243861325846262164331536570517513524474322519145470883352586121892275861245291051589531534179640139953079522307426687782419075644619898733819937782418589025945603603989100805716550707637938272890461563518245458692411433603442554397633470070254229240718705126327921819662662201896576503865953330533
#c = 1500765718465847687738186396037558689777598727005427859690647229619648539776087318379834790898189767401195002186003548094137654979353798325221367220839665289140547664641612525534203652911807047718681392766077895625388064095459224402032253429115181543725938853591119977152518616563668740574496233135226296439754690903570240135657268737729815911404733486976376064060345507410815912670147466261149162470191619474107592103882894806322239740349433710606063058160148571050855845964674224651003832579701204330216602742005466066589981707592861990283864753628591214636813639371477417319679603330973431803849304579330791040664
# p = 1426723861968216959675536598409491243380171101180592446441649834738166786277745723654950385796320682900434611832789544257790278878742420696344225394624591657752431494779

题解

本来想写

f=p+x∗2560f=p+x*2^{560}

结果result为空，因为低位太少了，要求的x太大 了

已知了p的一部分(低位部分)，但是缺少了另一部分(高位部分)。为了尝试恢复正确的p，我们需要尝试不同的偏移量。
偏移量可以看作是一个参数，它确定了在尝试恢复p时我们将考虑的可能取值范围。通过尝试不同的偏移量，我们可以生成多个可能的高位部分的取值，并将其与已知的低位部分组合起来。

已知p的低低（560位），用i 控制偏移量，构造多项式,coppersmith,求出p

f=p+i∗2∗∗(560)+x∗2∗∗(560+i.nbits())f=p + i*2**(560) + x*2**(560+i.nbits())

wp

from Crypto.Util.number import *
import tqdm
n = 21595945409392994055049935446570173194131443801801845658035469673666023560594683551197545038999238700810747167248724184844583697034436158042499504967916978621608536213230969406811902366916932032050583747070735750876593573387957847683066895725722366706359818941065483471589153682177234707645138490589285500875222568286916243861325846262164331536570517513524474322519145470883352586121892275861245291051589531534179640139953079522307426687782419075644619898733819937782418589025945603603989100805716550707637938272890461563518245458692411433603442554397633470070254229240718705126327921819662662201896576503865953330533
c = 1500765718465847687738186396037558689777598727005427859690647229619648539776087318379834790898189767401195002186003548094137654979353798325221367220839665289140547664641612525534203652911807047718681392766077895625388064095459224402032253429115181543725938853591119977152518616563668740574496233135226296439754690903570240135657268737729815911404733486976376064060345507410815912670147466261149162470191619474107592103882894806322239740349433710606063058160148571050855845964674224651003832579701204330216602742005466066589981707592861990283864753628591214636813639371477417319679603330973431803849304579330791040664
p = 1426723861968216959675536598409491243380171101180592446441649834738166786277745723654950385796320682900434611832789544257790278878742420696344225394624591657752431494779


#设高位为x
PR.< x > = Zmod(n)[]
for i in tqdm.tqdm(range(2**10)):
    i = Integer(i)
    p = 1426723861968216959675536598409491243380171101180592446441649834738166786277745723654950385796320682900434611832789544257790278878742420696344225394624591657752431494779
    f = p + i*2**(560) + x*2**(560+i.nbits())
    res = f.monic().small_roots(X=2^(1024-560-i.nbits()), beta=0.4)
    if res:
        print(res)
        p = p + i*2**(560) + int(res[0])*2**(560+i.nbits())
        q = n // p
        if  p * q==n:
            d = inverse(65537,(p-1)*(q-1))
            print(long_to_bytes(int(pow(c,d,n))))

#DASCTF{ce73935b2e83a78aa5079a9e59ae4980}

[LitCTF 2023]Where is P?

题目

from Crypto.Util.number import *
m=bytes_to_long(b'XXXX')
e=65537
p=getPrime(1024)
q=getPrime(1024)
n=p*q
print(p)
c=pow(m,e,n)
P=p>>340
print(P)
a=pow(P,3,n)
print("n=",n)
print("c=",c)
print("a=",a)
#n= 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
#c= 6566517934961780069851397787369134601399136324586682773286046135297104713708615112015588908759927424841719937322574766875308296258325687730658550956691921018605724308665345526807393669538103819281108643141723589363068859617542807984954436567078438099854340705208503317269397632214274507740533638883597409138972287275965697689862321166613821995226000320597560745749780942467497435742492468670016480112957715214640939272457886646483560443432985954141177463448896521810457886108311082101521263110578485768091003174683555938678346359150123350656418123918738868598042533211541966786594006129134087145798672161268647536724
#a= 22184346235325197613876257964606959796734210361241668065837491428527234174610482874427139453643569493268653377061231169173874401139203757698022691973395609028489121048788465356158531144787135876251872262389742175830840373281181905217510352227396545981674450409488394636498629147806808635157820030290630290808150235068140864601098322473572121965126109735529553247807211711005936042322910065304489093415276688746634951081501428768318098925390576594162098506572668709475140964400043947851427774550253257759990959997691631511262768785787474750441024242552456956598974533625095249106992723798354594261566983135394923063605

题解

爆破P，开三次，求出P

P=p>>340P=p>>340

可知p的高位泄露（1024-340= 684 位），Coppersmith恢复p

WP

import gmpy2
from Crypto.Util.number import *

e=65537
n= 24479907029118467064460793139240403258697681144532146836881997837526487637306591893357774423547391867013441147680031968367449693796015901951120514250935018725570026327610524687128709707340727799633444550317834481416507364804274266363478822257132586592232042108076935945436358397787891169163821061005102693505011197453089873909085170776511350713452580692963748763166981047023704528272230392479728897831538235554137129584665886878574314566549330671483636900134584707867654841021494106881794644469229030140144595938886437242375435914268001721437309283611088568191856208951867342004280893021653793820874747638264412653721
c= 6566517934961780069851397787369134601399136324586682773286046135297104713708615112015588908759927424841719937322574766875308296258325687730658550956691921018605724308665345526807393669538103819281108643141723589363068859617542807984954436567078438099854340705208503317269397632214274507740533638883597409138972287275965697689862321166613821995226000320597560745749780942467497435742492468670016480112957715214640939272457886646483560443432985954141177463448896521810457886108311082101521263110578485768091003174683555938678346359150123350656418123918738868598042533211541966786594006129134087145798672161268647536724
a= 22184346235325197613876257964606959796734210361241668065837491428527234174610482874427139453643569493268653377061231169173874401139203757698022691973395609028489121048788465356158531144787135876251872262389742175830840373281181905217510352227396545981674450409488394636498629147806808635157820030290630290808150235068140864601098322473572121965126109735529553247807211711005936042322910065304489093415276688746634951081501428768318098925390576594162098506572668709475140964400043947851427774550253257759990959997691631511262768785787474750441024242552456956598974533625095249106992723798354594261566983135394923063605
for i in range(100000):
    if gmpy2.iroot(i * n + a, 3)[1]==True:
        P = gmpy2.iroot(i * n + a, 3)[0]
        print(f'P={P}')
        break
p4=66302204855869216148926460265779698576660998574555407124043768605865908069722142097621926304390549253688814246272903647124801382742681337653915017783954290069842646020090511605930590064443141710086879668946

'''pbits = 1024
kbits = 340
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
#经过以上一些函数处理后，n和p已经被转化为10进制
if roots:
   p = p4+int(roots[0])
   print("p: "+str(p))'''

p=148500014720728755901835170447203030242113125689825190413979909224639701026120883281188694701625473553602289432755479244507504340127322979884849883842306663453018960250560834067472479033116264539127330613635903666209920113813160301513820286874124210921593865507657148933555053341577090100101684021531775022459
q=n//p
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))
#LitCTF{Y0U_hAV3_g0T_Th3_r1ghT_AnsW3r}

[LitCTF 2023]baby_xor

题目

from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)
assert len(flag)==32
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
c1 = p^m
c2 = pow(m,e,n)
print(f'n = {n}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
"""
n = 139167681803392690594490403105432649693546256181767408269202101512534988406137879788255103631885736461742577594980136624933914700779445704490217419248411578290305101891222576080645870988658334799437317221565839991979543660824098367011942169305111105129234902517835649895908656770416774539906212596072334423407
c1 = 11201139662236758800406931253538295757259990870588609533820056210585752522925690049252488581929717556881067021381940083808024384402885422258545946243513996
c2 = 112016152270171196606652761990170033221036025260883289104273504703557624964071464062375228351458191745141525003775876044271210498526920529385038130932141551598616579917681815276713386113932345056134302042399379895915706991873687943357627747262597883603999621939794450743982662393955266685255577026078256473601
"""

题解

p为512bit，p的高位至少泄露264bit时候，环多项式方程在模n情况下有解,还有8bit，想到头为"LitCTF{"

kbits=512-256-56=200

wp

from tqdm import tqdm
e = 65537
n = 139167681803392690594490403105432649693546256181767408269202101512534988406137879788255103631885736461742577594980136624933914700779445704490217419248411578290305101891222576080645870988658334799437317221565839991979543660824098367011942169305111105129234902517835649895908656770416774539906212596072334423407
c1 = 11201139662236758800406931253538295757259990870588609533820056210585752522925690049252488581929717556881067021381940083808024384402885422258545946243513996
c2 = 112016152270171196606652761990170033221036025260883289104273504703557624964071464062375228351458191745141525003775876044271210498526920529385038130932141551598616579917681815276713386113932345056134302042399379895915706991873687943357627747262597883603999621939794450743982662393955266685255577026078256473601

m = bytes_to_long(b'LitCTF{' + b'\x00'*25)
p_high = (c1^^m)>>200

PR.<x> =Zmod(n)[]
f = (p_high << 200) + x
res = f.small_roots(X = 2^200 ,beta =0.4, epsilon=0.01)
c = res[0] + (p_high<<200)
m = int(c1) ^^ int(c)
print(long_to_bytes(m))
#LitCTF{oh!!!!coppersmith_is_fun}