CryingN

CryingN

早安, 晚安, 谢谢, 再见.

[Crypto学习笔记] DES对称加密类题目

3 分钟阅读时长

发布时间：

目录

前置概念

des原理

以后有时间再写

复数域分解

写不了一点, 以后再说

国城杯2024

ez_sign

题目

from Crypto.Util.number import *
from gmpy2 import *
from hashlib import*
import random,os

flag = b'D0g3xGA{***************}'
msg = b'e = ?'

def sign(pub, pri, k):
    (p,q,g,y) = pub
    x = pri
    r = int(powmod(g, k, p) % q)
    H = bytes_to_long(sha1(os.urandom(20)).digest())
    s = int((H + r * x) * invert(k, q) % q)
    return (H,r,s)

k1 = getPrime(64)
k2 = k1 ** 2
pri = bytes_to_long(msg)
a = 149328490045436942604988875802116489621328828898285420947715311349436861817490291824444921097051302371708542907256342876547658101870212721747647670430302669064864905380294108258544172347364992433926644937979367545128905469215614628012983692577094048505556341118385280805187867314256525730071844236934151633203
b = 829396411171540475587755762866203184101195238207
g = 87036604306839610565326489540582721363203007549199721259441400754982765368067012246281187432501490614633302696667034188357108387643921907247964850741525797183732941221335215366182266284004953589251764575162228404140768536534167491117433689878845912406615227673100755350290475167413701005196853054828541680397
y = 97644672217092534422903769459190836176879315123054001151977789291649564201120414036287557280431608390741595834467632108397663276781265601024889217654490419259208919898180195586714790127650244788782155032615116944102113736041131315531765220891253274685646444667344472175149252120261958868249193192444916098238

pub = (a, b, g, y)

H1, r1, s1 = sign(pub, pri, k1)

H2, r2, s2 = sign(pub, pri, k2)

p = getPrime(128)
q = getPrime(128)
n = p * q
c = powmod(bytes_to_long(flag), e, n)

C = p**2 + q**2

print(f'(H1, r1, s1) = {H1}, {r1}, {s1}')
print(f'(H2, r2, s2) = {H2}, {r2}, {s2}')
print(c)
print(C)

'''
(H1, r1, s1) = 659787401883545685817457221852854226644541324571, 334878452864978819061930997065061937449464345411, 282119793273156214497433603026823910474682900640
(H2, r2, s2) = 156467414524100313878421798396433081456201599833, 584114556699509111695337565541829205336940360354, 827371522240921066790477048569787834877112159142
c = 18947793008364154366082991046877977562448549186943043756326365751169362247521
C = 179093209181929149953346613617854206675976823277412565868079070299728290913658
'''

解析

很混沌的一道题, 不过过程中对我造成的震撼比较大的还是来自于DSA的其中一部分, 所以分类在了这里, 首先可以简单分解问题:

\[\begin{matrix} c \equiv flag^e \mod{n} \\ C = p^2 + q^2 \end{matrix}\]

c本质上套了一层简单的rsa加密, 其中在C有提示p,q, 故获取e后可直接求取私钥计算flag, 在前面有提示:

msg = b'e = ?'

考虑到:

\[\begin{matrix} r_1 \equiv (g^k \mod{a}) \mod{b} \\ r_1 \equiv (g^{k^2} \mod{a}) \mod{b} \end{matrix}\]

属于经典的DSA关系k攻击1, 可以直接调用脚本获取k值:

R = PolynomialRing(GF(q), 'x')
x = R.gen()
f = s2*x**2*r1 - s1*x*r2 - h2*r1 + h1*r2
hh = f.roots()
k = hh[1][0]

pri1 = (s1 * k - h1) // r1
pri2 = (s2 * k**2 - h2) // r2

assert pri1 == pri2, '计算k存在问题'

在获取k后可以直接计算出x(即bytes_to_long(msg)):

\[x_1 = \frac{ks_1 - H_1}{r_1} \mod{b} \\ x_2 = \frac{k^2s_2 - H_2}{r_2} \mod{b} \\\]

计算出msg获取e:

pri1 = (s1 * k - h1) // r1
pri2 = (s2 * k**2 - h2) // r2

assert pri1 == pri2, 'pri1 != pri2'

print(l2b(int(pri1)))
#e = 44519

获取e后可以转换到C部分求取p,q, 其实在basectf第二周的时候naby师傅曾出过类似的题目, 当时在面对这种情况时提供了一个函数two_squares()2, 但是本题中明显存在多组(x, y), 这个函数并不是那么适用, 实际上我也尝试修改过内部函数, 不过效果并不显著, 关于\(x^2+y^2=n\)的可以考虑继续阅读《x^2+y^2=n的整数解 》3, Wbuildings师傅提供了复数域分解的思路4:

C = 179093209181929149953346613617854206675976823277412565868079070299728290913658

for j in divisors(ZZ[i](C)):
    pp, qq = map(int, j)
    pp, qq = abs(pp), abs(qq)
    if pp**2+qq**2 == C and is_prime(pp) and is_prime(qq):
        p, q = pp, qq

assert C == p**2+q**2, 'p, q 不符合'

计算出p,q, 之后就是常规rsa流程了.

EXP

使用少女自用九成新EXP库:

from EXP import *

h1, r1, s1 = 659787401883545685817457221852854226644541324571, 334878452864978819061930997065061937449464345411, 282119793273156214497433603026823910474682900640
h2, r2, s2 = 156467414524100313878421798396433081456201599833, 584114556699509111695337565541829205336940360354, 827371522240921066790477048569787834877112159142
c = 18947793008364154366082991046877977562448549186943043756326365751169362247521
C = 179093209181929149953346613617854206675976823277412565868079070299728290913658

p = 149328490045436942604988875802116489621328828898285420947715311349436861817490291824444921097051302371708542907256342876547658101870212721747647670430302669064864905380294108258544172347364992433926644937979367545128905469215614628012983692577094048505556341118385280805187867314256525730071844236934151633203
q = 829396411171540475587755762866203184101195238207
g = 87036604306839610565326489540582721363203007549199721259441400754982765368067012246281187432501490614633302696667034188357108387643921907247964850741525797183732941221335215366182266284004953589251764575162228404140768536534167491117433689878845912406615227673100755350290475167413701005196853054828541680397

R = PolynomialRing(GF(q), 'x')
x = R.gen()
f = s2*x**2*r1 - s1*x*r2 - h2*r1 + h1*r2
hh = f.roots()
k = hh[1][0]

pri1 = (s1 * k - h1) // r1
pri2 = (s2 * k**2 - h2) // r2

assert pri1 == pri2, '不对'

print(l2b(int(pri1)))

e = 44519

for j in divisors(ZZ[i](C)):
    pp, qq = map(int, j)
    pp, qq = abs(pp), abs(qq)
    if pp**2+qq**2 == C and is_prime(pp) and is_prime(qq):
        p, q = pp, qq

assert C == p**2+q**2, 'p, q 不符合'

n = p*q
phin = (p-1)*(q-1)
d = pow(e,-1,phin)
m = pow(c,d,n)
print(l2b(m))

# D0g3xGC{EZ_DSA_@nd_C0mplex_QAQ}

参考文献

  1. hengxinyan.NSSCTF Crypto系列–DSA[EB/OL].个人博客.https://hengxinyan.github.io/2023/08/10/Crypto%E7%B3%BB%E5%88%97–%5BDSA%5D/.2023.08.10 ↩

  2. basectf组委会.BaseCTF 2024官方Writeup合集[EB/OL].CSDN.https://j0zr0js7k7j.feishu.cn/docx/MS06dyLGRoHBfzxGPF1cz0VhnGh.2024.11.10 ↩

  3. 暑假作业写了没.x^2+y^2=n的整数解[EB/OL].知乎.https://zhuanlan.zhihu.com/p/668845092.2023.11.26 ↩

  4. Wbuildings.国城杯2024[EB/OL].个人博客.https://wbuildings.github.io/Crypto/%E5%9B%BD%E5%9F%8E%E6%9D%AF2024/#more.2024.12.07 ↩

你可能感兴趣的