杂题总结1

一些题目的题解

[DASCTF 2024最后一战｜寒夜破晓，冬至终章] 数论的气氛

题目：

from sympy import isprime
from sympy.ntheory import legendre_symbol
import random
from Crypto.Util.number import bytes_to_long
 
k=79    #<-- i couldn't stress more
 
def get_p():
    global k
    while True:
        r=random.randint(2**69,2**70)
        p=2**k*r+1
        if isprime(p):
            return p
        else:
            continue
 
def get_q():
    while True:
        r=random.randint(2**147,2**148)
        q=4*r+3
        if isprime(q):
            return q
        else:
            continue
 
 
def get_y():
    global n,p,q
    while True:
        y=random.randint(0,n-1)
        if legendre_symbol(y,p)==1:
            continue
        elif legendre_symbol(y,q)==1:
            continue
        else:
            return y
 
 
flag=b'DASCTF{redacted:)}'
flag_pieces=[flag[0:10],flag[11:21],flag[22:32],flag[33:43],flag[44:]]
#assert int(bytes_to_long((flag_pieces[i] for i in range(5)))).bit_length()==k
 
p=get_p()
q=get_q()
n=p*q
print(f'{n=}')
 
y=get_y()
print(f'{y=}')
 
 
def encode(m):
    global y,n,k
    x = random.randint(1, n - 1)
    c=(pow(y,m,n)*pow(x,pow(2,k),n))%n
    return c
 
cs=[]
for i in range(len(flag_pieces)):
    ci=encode(bytes_to_long(flag_pieces[i]))
    cs.append(ci)
 
print(f'{cs=}')
 
'''
n=542799179636839492268900255776759322356188435185061417388485378278779491236741777034539347
y=304439269593920283890993394966761083993573819485737741439790516965458877720153847056020690
cs=[302425991290493703631236053387822220993687940015503176763298104925896002167283079926671604, 439984254328026142169547867847928383533091717170996198781543139431283836994276036750935235, 373508223748617252014658136131733110314734961216630099592116517373981480752966721942060039, 246328010831179104162852852153964748882971698116964204135222670606477985487691371234998588, 351248523787623958259846173184063420603640595997008994436503031978051069643436052471484545]
'''

通过get_p生成的p的形式是 $2^{79} * r + 1 = p$ ，p的位数是149位左右，那么r的位数就是149-79，然后就可以用copper来解出r，从而得到p

n=542799179636839492268900255776759322356188435185061417388485378278779491236741777034539347
# print(len(bin(n)))
k = 79
PR.<r> = PolynomialRing(Zmod(n))
f = 2^k*r + 1
f = f.monic()
res = f.small_roots(X=2^(149-79), beta=0.4, epsilon=0.01)
if res:
       p = 2^79 * int(res[0]) + 1
       print(p)
#628729403897154553626034231171921094272614401

然后就是爆破m的环节，通过二次剩余来爆，因为y不是p的二次剩余，而 $x^{2^{79}}$ 肯定是p的二次剩余，那么这个m就决定了c是不是p的二次剩余，以此来爆破m
我来举一个例子，可能就好理解了

2^{10} = 2^{(1010)_2}

那我对它求勒让德符号显然是1(是二次剩余)，那我对他开方后就得到了 $2^{(101)_2}$
我们想从 $(101)_2\rightarrow(1010)_2$ ,需要在末尾+'0'(就是向左移1位)

2^{11} = 2^{(1011)_2}

我对它求勒让德符号显然是-1(不是二次剩余)，那我需要先除2，再开方得到 $2^{(101)_2}$
我们想从 $(101)_2\rightarrow(1011)_2$ ,需要在末尾+'1'(就是向左移1位并+1)
由上面两个例子我们可以得出结论：

若c是二次剩余，我们需要在m末尾+'0'
若c不是二次剩余，我们需要在m末尾+'1'
由此一直循环就可以爆破出m,题目中的循环终止条件如下

assert int(bytes_to_long((flag_pieces[i] for i in range(5)))).bit_length()==k

长度等于k即可
代码：参考

from Crypto.Util.number import *
from gmpy2 import *
p = 628729403897154553626034231171921094272614401
n=542799179636839492268900255776759322356188435185061417388485378278779491236741777034539347
y=304439269593920283890993394966761083993573819485737741439790516965458877720153847056020690
cs=[302425991290493703631236053387822220993687940015503176763298104925896002167283079926671604, 439984254328026142169547867847928383533091717170996198781543139431283836994276036750935235, 373508223748617252014658136131733110314734961216630099592116517373981480752966721942060039, 246328010831179104162852852153964748882971698116964204135222670606477985487691371234998588, 351248523787623958259846173184063420603640595997008994436503031978051069643436052471484545]
k = 79

def getm(c, m):
    global ok

    if ok: return

    if len(m) == k:
        print(long_to_bytes(int(m, 2)))
        ok = True


    if  kronecker(c, p) == -1:
        m = '1' + m
        c = int(c * invert(y, p) % p)
    else:
        m = '0' + m

    cs = res = Zmod(p)(c).nth_root(2, all=True)
    for tc in cs:
        getm(int(tc), m)


flag = b''
for tc in cs:
    ok = False
    getm(tc, '')

#DASCTF{go0_j06!let1sm0v31n_t0_th3r_chanlenges~>_<}

[2024-蜀道山高校联合公益赛] Something like coppersmith

from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import hashlib
from secret import flag

p = 6302810904265501037924401786295397288170843149817176985522767895582968290551414928308932200691953758726228011793524154509586354502691822110981490737900239
g = 37
x = getRandomRange(1, p)
key = hashlib.md5(str(x).encode()).digest()
aes = AES.new(key=key, mode=AES.MODE_ECB)
print(f"y = {pow(g, x, p)}")
print(f"xl = {x & (2**404 - 1)}")
print(f"enc = {aes.encrypt(pad(flag, 16))}")
"""
y = 1293150376161556844462084321627758417728307246932113125521569554783424543983527961886280946944216834324374477189528743754550041489359187752209421536046860
xl = 17986330879434951085449288256517884655391850545705434564933459034981508996937405053663301303792832616366656593647019909376   
enc = b'\x08[\x94\xc1\xc2\xc3\xb9"C^\xd6P\xf9\x0c\xbb\r\r\xaf&\x94\x8cm\x02s\x87\x8b\x1c\xb3\x92\x81H\xe7\xc6\x190a\xca\x91j\xc0@(\xc5Fw\x95\r\xee'
"""

一看到这种题就头大，参考糖醋小鸡块的博客
p-1的因子：

2 · 385057 · 727646221919<12> · 193893885660581<15> · 193166780451443059<18> · 3881671740574461385603964379125531<34> · 77364837756797328321829387679372821139010103152781295726133301368685957<71>

题目给了x的低位404，我在找p的第2-4个因子相乘得到106bit的数，这个数量级的数dlp比较好求，并且可以和x的低位做crt，得到(404+106)bit的数，很接近x(p是512bit且x<(p-1))，最后再爆破几位

x \equiv xl \mod 2^{404}

x \equiv xr \mod (p-1)//r

其实重点就是如何找到这个xr,鸡块的代码：

p = 6302810904265501037924401786295397288170843149817176985522767895582968290551414928308932200691953758726228011793524154509586354502691822110981490737900239
r1 = 193166780451443059
r2 = 3881671740574461385603964379125531
r3 = 77364837756797328321829387679372821139010103152781295726133301368685957

r = r1*r2*r3
Fp = GF(p)
xr = discrete_log(Fp(pow(y,r,p)), Fp(pow(g,r,p)), operation="*", ord=(p-1)//r)

其实就是写成 $y^{r} \equiv g^{r} \mod p$ 那这个式子的阶就变成了(p-1)//r(p的第5-7个因子相乘),那就是第2-4个因子相乘的数量级，就可以求出xr了
可能还有人疑惑为什么写成 $y^{r} \equiv g^{r} \mod p$ 这个式子的阶就变成了(p-1)//r
其实很好理解，例如：

y^{x} \equiv 1\mod p

(y^{r})^{x_1} \equiv 1 \mod p

那么下式的x_1(也是下式的阶)显然等于 $\frac{x}{r}$
这都是一些我个人的理解，有问题希望指正
代码：

from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib

y = 1293150376161556844462084321627758417728307246932113125521569554783424543983527961886280946944216834324374477189528743754550041489359187752209421536046860
xl = 17986330879434951085449288256517884655391850545705434564933459034981508996937405053663301303792832616366656593647019909376   
enc = b'\x08[\x94\xc1\xc2\xc3\xb9"C^\xd6P\xf9\x0c\xbb\r\r\xaf&\x94\x8cm\x02s\x87\x8b\x1c\xb3\x92\x81H\xe7\xc6\x190a\xca\x91j\xc0@(\xc5Fw\x95\r\xee'
g = 37
p = 6302810904265501037924401786295397288170843149817176985522767895582968290551414928308932200691953758726228011793524154509586354502691822110981490737900239
r1 = 193166780451443059
r2 = 3881671740574461385603964379125531
r3 = 77364837756797328321829387679372821139010103152781295726133301368685957

r = r1*r2*r3
Fp = GF(p)
xr = discrete_log(Fp(pow(y,r,p)), Fp(pow(g,r,p)), operation="*", ord=(p-1)//r)

x = crt([xl, xr], [2^404, (p-1)//r])

for i in range(2^10):
    temp = x + i*lcm([2^404, (p-1)//r])
    if(temp > p-1):
        break
    key = hashlib.md5(str(temp).encode()).digest()
    aes = AES.new(key=key, mode=AES.MODE_ECB)
    print(aes.decrypt(enc))


#LZSDS{m@N_Wh@t_c@n_I_5@y_____dfa015cdc546}

[DASCTF 2024最后一战｜寒夜破晓，冬至终章] 数论的气氛

[2024-蜀道山高校联合公益赛] Something like coppersmith

感谢您的支持，我会继续努力的!