某比赛 Crypto 方向（三题全）

发表于 2024-06-28 更新于 2024-06-28

题目质量很好，懵逼不伤脑。

1、easyLCG

题目说明

from Crypto.Util.number import *
from random import randint

FLAG = ?
ROUND = randint(200, 300)

class LCG:
    lcg_a = getPrime(498)
    lcg_b = getPrime(498)
    lcg_n = getPrime(512)

    def __init__(self, lcg_seed):
        self.state = lcg_seed

    def next(self):
        self.state = (self.state * self.lcg_a + self.lcg_b) % self.lcg_n
        return self.state

seed = bytes_to_long(FLAG)
print(seed.bit_length())
lcg = LCG(seed)
for _ in range(ROUND-6):
    lcg.next()
print([lcg.next() for _ in range(6)])

# 351
# [2485483242304449696161151168576736302336140244327446722677621064961717587947642623655706309294371876714311165214262071924932913930440142186509325733360885, 6174672247406972581092780254648964828729162316422924118545162215261641830776919624579500836375440017861960302702691972683448546062254126073514097080361044, 4584872703321313263026316988830140564935997972340636369234263637913498924218112980629201945528119162637762726584003527994733552009906632734086040880127542, 4829175497283310360340169484343201154685159906303099960915060755507745973302279262836696523131741537828200567942990339422885197644614494869008027862313162, 6669041483112643196441450289748743294802963984583343809912658359929976814854869038886397237458253328867571805574485994275429182399171275201561798677581761, 2732859498560958306654933055106793656103744294844703560692860713169132266734427400301681246251133210447387861776419850678194913478737337289544516324708390]

解题思路

很原始的LCG类型题，抄板子就行。不过这里我用了格的思路，可以看在NSSCTF上的推导。

脚本exp


X = [2485483242304449696161151168576736302336140244327446722677621064961717587947642623655706309294371876714311165214262071924932913930440142186509325733360885, 6174672247406972581092780254648964828729162316422924118545162215261641830776919624579500836375440017861960302702691972683448546062254126073514097080361044, 4584872703321313263026316988830140564935997972340636369234263637913498924218112980629201945528119162637762726584003527994733552009906632734086040880127542, 4829175497283310360340169484343201154685159906303099960915060755507745973302279262836696523131741537828200567942990339422885197644614494869008027862313162, 6669041483112643196441450289748743294802963984583343809912658359929976814854869038886397237458253328867571805574485994275429182399171275201561798677581761, 2732859498560958306654933055106793656103744294844703560692860713169132266734427400301681246251133210447387861776419850678194913478737337289544516324708390]
print(len(X))

t = list(map(lambda i: X[i] - X[i-1], range(1, len(X))))
print(len(t))

m = reduce(lambda m, i: gcd((t[i+1] * t[i-1] - t[i] * t[i]), m), range(1, len(t)-1), 0)
print(m)

B = matrix(QQ,
    [
        [X[0], X[1], 1 / m, 0, 0],
        [1, 1, 0, 1 / m, 0],
        [-X[1], -X[2], 0, 0, 1],
        [m, 0, 0, 0, 0],
        [0, m, 0, 0, 0],
    ]
)
L = B.LLL()

for i in L:
    if i[0] == 0 and i[1] == 0:
        if i[-1] == 1:
            a, b = i[2] * m % m, i[3] * m % m
        elif i[-1] == -1:
            a, b = -i[2] * m % m, -i[3] * m % m

x = int(X[0])
while 1:
    x = (x - b) * pow(a, -1, m) % m
    try:
        mm = bytes.fromhex(hex(int(x))[2:])
        if b"DASCTF" in mm:
            print(mm)
            break
    except:
        pass
        
        
# b'DASCTF{342232bd-3f4e-4a79-b38b-565e3242ef16}'

2、ez_dp

题目说明

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

m = bytes_to_long(flag)

def get_key():
    p = getPrime(1400)
    f = getRandomNBitInteger(1024)
    while True:
        q = getPrime(512)
        if gcd(f, q) != 1:
            continue
        else:
            break
    h = (invert(f, p) * q) % p
    return p, h

def encrypt1(m):
    p1 = getPrime(512)
    q = getPrime(512)
    e = 65537
    n = p1 * q
    d = invert(e, ((p1 - 1) * (q - 1)))
    dp = d % (p1 - 1)
    c1 = pow(m, e, n)
    s1 = dp
    print("n=", n)
    print("e=", e)
    print("c1=", c1)
    return s1

def encrypt2(msg, p, h):
    s = getRandomNBitInteger(512)
    c = (s * h + msg) % p
    return c

s = encrypt1(m)

p, h = get_key()
c = encrypt2(s, p, h)
print("p =", p)
print("h =", h)
print("c =", c)

'''
n= 110260074814257848908838625078501714960458516741889369726732143430937734210697873759425002497330033320466835750445829174684997535308856662838681041846947794426431497972796103034618905050690681625345580286974329394317326231752377513909290333601657981626779958969848432585669863801355518000831123865599294226787
c1= 87410783012997497089334969426735453553497110834602573140546865362447022991078781629894253455830313940054370072857581848649396014751510236334195667629699713694613970526418637921762179732923254584016634361975803026314654688055431785462894448431844588694708213156437494671986610728148872504904151549242154736587
p = 21012869988761718338002056668434640022381086646751731449032721137037733345551758802860184993656068733215079498246765657259553828250758201376752862965670037141641108407264413512347418547149638244577961647868099781047690086047340253092665472213200209122580168177065790399345363610449214898111612290510197602660551433726293151325348011730919876875489664094858613139260007122677438946422077569668626396394096578756269392219213
h = 6770491790682953636942614852064358677927258711756829789136991143125359571318236604881493887413710952826577625598345974890598833192705608538873219275181448971593360238243436263218203203262930354812832507464385245721509296553554707977362798787013782539283042526261689534233491245951252995706501115900819405349059258311900443901042496821340275234460907395830177886146041399137964230712722194756085629793582418840916735512277
c = 6132552687547528285732276436929419970961603850889618566398215255235030332018277282050536908271855446943919146591207662267815289943461335956844983042713305437715890977506659305069814807759223451215542538520079466091582962427203571721480729032807618768679976218582641269768441380693229147722826754954050492620043730436678935654351184167023259917544557009809604068417077921029798974332993383467713648518164609614847827656355
'''

解题思路

这题也是很原始的lattice类型题，套了一个dp泄露。下面是一些公式推导

首先在encrypt2 知道有下面关系，然后造格子

c - sh + kp = m \\ \begin{pmatrix} 1 & s & k \end{pmatrix} \begin{bmatrix} 1 & 0 & c \\ 0 & 1 & -h \\ 0 & 0 & p \end{bmatrix} = \begin{pmatrix} 1 & s & m \end{pmatrix}

后续在格上补一个大数使其均匀。

转到encrypt1 可以从这里知道 $dp,n$ ，有下面的推导

ed_p \equiv 1 \pmod {p-1} \\ ed_p - 1 = k(p-1) \\ ed_p - 1 + k = kp

此时在模n 下进行对 k 的 coppersmith 求解小根，就能得到 p 的倍数。后面做个 gcd 即可。

脚本exp


n= 110260074814257848908838625078501714960458516741889369726732143430937734210697873759425002497330033320466835750445829174684997535308856662838681041846947794426431497972796103034618905050690681625345580286974329394317326231752377513909290333601657981626779958969848432585669863801355518000831123865599294226787
c1= 87410783012997497089334969426735453553497110834602573140546865362447022991078781629894253455830313940054370072857581848649396014751510236334195667629699713694613970526418637921762179732923254584016634361975803026314654688055431785462894448431844588694708213156437494671986610728148872504904151549242154736587
p = 21012869988761718338002056668434640022381086646751731449032721137037733345551758802860184993656068733215079498246765657259553828250758201376752862965670037141641108407264413512347418547149638244577961647868099781047690086047340253092665472213200209122580168177065790399345363610449214898111612290510197602660551433726293151325348011730919876875489664094858613139260007122677438946422077569668626396394096578756269392219213
h = 6770491790682953636942614852064358677927258711756829789136991143125359571318236604881493887413710952826577625598345974890598833192705608538873219275181448971593360238243436263218203203262930354812832507464385245721509296553554707977362798787013782539283042526261689534233491245951252995706501115900819405349059258311900443901042496821340275234460907395830177886146041399137964230712722194756085629793582418840916735512277
c = 6132552687547528285732276436929419970961603850889618566398215255235030332018277282050536908271855446943919146591207662267815289943461335956844983042713305437715890977506659305069814807759223451215542538520079466091582962427203571721480729032807618768679976218582641269768441380693229147722826754954050492620043730436678935654351184167023259917544557009809604068417077921029798974332993383467713648518164609614847827656355

M2 = matrix(ZZ,[[2^512,0,c],
                [0,1,-h],
                [0,0,p]])
L2 = M2.LLL()

dp = int(abs(L2[0][2]))
print(dp)

P.<x> = PolynomialRing(Zmod(n))
f = 65537*dp - 1 + x 
res = f.monic().small_roots(X=65537,beta=0.47)
print(res)

p = gcd(int(f(res[0])),n)
assert is_prime(p)
print(p)
q = n // p

d = pow(65537,-1,(p-1)*(q-1))
m = pow(c1,d,n)
print(bytes.fromhex(hex(m)[2:]))

# b'DASCTF{th1s_1s_NTRU_And_Dp}'

3、p-1高位攻击

题目说明

import uuid
from Crypto.Util.number import *
from sage.all import *

flag = ("DASCTF{" + str(uuid.uuid4()) + "}").encode()
m = bytes_to_long(flag)
p, q = getPrime(256), getPrime(256)
phi = (q - 1) * (p - 1)
e = getPrime(256)
while True:
    e = next_prime(e)
    d = inverse_mod(e, phi)
    print(int((e * d - 1) // phi).bit_length())
    if (e * d - 1) // phi.bit_length() >= 120:
        ed1 = e * d - 1
        phi = (p - 1) * (q - 1)
        break

q_high = q >> 120 << 120
print(f"{p = }")
print(f"{q_high = }")
print(f"{e = }")
print(f"{d = }")
c = pow(m, d, p * q)
print(f"{c = }")
"""
p = 104972055463933479200574678219895894194023752029484798658224692242190851628301
q_high = 72503520013659319553438202098095419026840442742112803280959116977958759170048
e = 76798736050861087860251573138624328801131026809587391139129370361257176660643
d = 4516628399629928927666639239260422748934760909253970963332110111403362750325520573822831057720436368752480789235094323353455057451415359187266585002061707
c = 6270136250823720520545290554363376477855894636577767047522294947358559798810833186509641487748745519863674705966550753544189154739420020332172828310262938
"""

解题思路

跟前面那题很像，卡了一个界。

已知 $p , q_h ,c ,e ,d$ ，这里是泄露了 $q$ 的高位，但是 $n$ 未知，也就是模数未知。

不过给了 $e,d$ 那么就很容易想到 $ed - 1 = k(p-1)(q-1)$

进一步地，为了求得 $q$ ，易知 $(q - 1) | k(q-1)$ ,可以构造式子

ed_q - 1 = (ed - 1) \div (p-1) = k(q-1) \\ q_h - 1 + x \equiv 0 \pmod {q-1} \\ q_h - 1 + x = k (q-1)

此时只需要在 $k(q-1)$ 下求得 $x$ ，然后做个 gcd 就能得到 $p$

但是卡界了，稍微讨论一下。回到题目可以知道：

$p$ 低 120 bit 未知，
$k(q-1)$ 为 510 bit，
$k = (ed - 1) // phi$ 的 bits 实测应该在 256 bit（当然这里的 phi 不知道，但是可以用 $(p-1)^2$ 做近似），相当于上式的 $k$ 约为 256 bit。

再来讨论 CopperSmith ，

所求的 $q-1$ 约占 $k(q-1)$ 的 $\frac{256}{510} \approx 0.5$ ，那么令 $\beta = 0.5$ 。
在 sagemath 默认实现的 small_roots 中，epsilon 默认为 $\beta \div 8$ 。这时候， $\epsilon = 0.0625$ ，所以小根的上界大约为 $|x_0| < X = (k(p-1))^{\frac{\beta^2}{1} - \epsilon}$ ，也就是 $\beta^2 - \epsilon = 0.25 - 0.0625 = 0.1875$ 。这显然无法达到目标 $\frac{120}{510} \approx 0.2352$ 。
所以调节 epsilon 的大小为 0.03，此时 $\beta^2 - \epsilon = 0.25 - 0.03 \approx 0.22$ 。(ps：由于用了一堆近似，所以这里也是近似的结果。（pss：sagemath 实现的时候用 ceil 向上取整。

经过一通乱调，就能得出结果了。

脚本exp


p = 104972055463933479200574678219895894194023752029484798658224692242190851628301
q_high = 72503520013659319553438202098095419026840442742112803280959116977958759170048
d = 76798736050861087860251573138624328801131026809587391139129370361257176660643
e = 4516628399629928927666639239260422748934760909253970963332110111403362750325520573822831057720436368752480789235094323353455057451415359187266585002061707
c = 6270136250823720520545290554363376477855894636577767047522294947358559798810833186509641487748745519863674705966550753544189154739420020332172828310262938

assert gcd(e*d - 1,p - 1) == p - 1

kq_1 = (e*d - 1) // (p - 1)

P.<x> = PolynomialRing(Zmod(kq_1))

f = q_high - 1 + x
res = f.monic().small_roots(X=2^120,beta=0.5,epsilon=0.03)
print(res)
q = int(f(res[0])) + 1
assert is_prime(q) 
d = pow(e,-1,(p-1)*(q-1))
m = pow(c,d,p*q)
print(bytes.fromhex(hex(m)[2:]))

# b'DASCTF{81e5cb8c-d836-4372-b2aa-133f67a44e25}'