↓Skip to main content

一个多素数RSA && 一个debug

·917 words·5 mins
Table of Contents

今天下雨

终于有时间静下心来做看我自己想看的东西了

积累了一个板子看了两篇论文学了点攻击的场景类型

DubheCTF2024-Common Prime RSA #

这篇文章讲了一些可以被攻击的多素数 RSA的种类

但没有讲实现

所以收集板子了

原论文：https://www.iacr.org/archive/asiacrypt2015/94520198/94520198.pdf、

一位老师基于上文拓展的一文：https://eprint.iacr.org/2024/061.pdf

n = 1000
gamma = 0.42
beta = 0.25


def keyGen(n, gamma):
    g = getPrime(round(n * gamma))
    while True:
        a, b = 2, 2
        while GCD(a, b) != 1:
            a = getRandomNBitInteger(round((.5 - gamma) * n - 1))
            b = getRandomNBitInteger(round((.5 - gamma) * n - 1))
        p, q, h = 2 * g * a + 1, 2 * g * b + 1, 2 * g * a * b + a + b
        if isPrime(p) and isPrime(q) and isPrime(h):
            break
    return p, q, g, a, b


p, q, g, a, b = keyGen(n, gamma)
d = getPrime(round(n * beta))
e = inverse(d, 2 * g * a * b)
print(f'N = {hex(p * q)}')
print(f'e = {hex(e)}')
flag = 'DubheCTF{{{:x}}}'.format(d & (2**128 - 1))

Common Prime RSA

特征是

p = 2ga+1 and q = 2gb + 1

这种生成方法导致在存在

式子1

$$ \begin{align} ed & = 1\mod{2gab} \\ ed & = 1 \mod{g} \\ 当 E & = e^{-1} \mod {(N-1)}时 \\ E & = e^{-1}\mod{g} \\ 同乘上E \\ d & = E\mod{g} \\ 0 & = E-d \mod{g} \\ \end{align} $$

式子2

$$ \begin{align} y & = p+q-1时\\ N-y & = 4g^{2}ab = 0\mod{g^2} \end{align} $$

令x=d

整理一下

$$ E-x=0 \mod{g} \\ N-d=0 \mod{g^2} \ $$

https://doi.org/10.1007/978-3-662-48797-6_9

这篇文章给了这种类型问题的原型

session 5 The Third Type of Equations

Alt text

$$ E-x=0 \mod{g} \\ N-d=0 \mod{g^2} \ $$

整理一下原题目里面是

$$ \begin{align} d\simeq N^{0.25} \\ p=g\simeq N^{0.48} \end{align} $$

有

gamma = 0.42
beta = 0.25
n = 2 # 有两个式子
r = 1 
r1 = 1
r2 = 2

# xi 的大小
y1 = beta = 0.25
y2 = 1/2 # p+q=n^(0.5)
nn = Gamma = 0.42

来到Mengce Zheng老师写的

《Partial Key Exposure Attack on Common Prime RSA》

中的第8个式子

牢底！完全一模一样！

Alt text

当然后面用什么什么方法

我没怎么看懂,但看懂了需要按照a1,a2的参数构造一个多项式

这里的a1,a2是我们可以获取的参数，但需要稍微计算一下，不能直接套板子

$$ \begin{align} E & = e^{-1}\mod{N-1} \\ E-x & = 0 \mod{g} \\ N-d & = 0 \mod{g^2} \\ \end{align} $$

code


PR.<x,y>= PolynomialRing(ZZ)
E = int(inverse_mod(e, N-1))
def f(i1, i2):
    return (E-x)^i1*(N-y)^i2*(N-1)^(max(t-i1-2*i2, 0))

后面的咱也看不太懂，但以后碰到微调的场景可以调参了

prompt：

# ============================================================================================================
N = 0xbe9ccc83003bedf45421b58377b946f87dfd85be82124dc5d732070d77ef68e0231c3f34dc803a8984de0573db6d83ccea0bd53a885059a10cfa3764c658c4d42c5fa90ecad8573fff8f2c41e513278c59121e42ad83310fb22b4d20e7ada42c76f08891f38c92a1b1aac712bfa7d717a4c4802ed023f12c768972ca1b
e = 0x5dc97ed7250e57ce6fac4f57885c0538b1ea540fbaca79730470b6b990f7e861adc4c5fee3acdcd9ae9a2834b606ddfae01ade33edfa96a47a0ffc0036a4497a84c38b7cdac20c38f
beta = 0.25  # log(d, N)
Gamma = 0.42  # log(g, N)


XX = int(ceil(N^beta))  # 这两个也要按照 x1
YY = int(ceil(N^0.5))   # x2的大小调整

t = 10 # 文章给的
print(f't = {t}')
n = 2
r = 1
r1 = 1
r2 = 2
y1 = beta
y2 = 1/2
nn = Gamma
R = [r1, r2]
Y = [y1, y2]

# check 判断系数是否符合预期
# for i in range(2):
    # print(Y[i]/R[i]<nn)

PR.<x,y>= PolynomialRing(ZZ)
E = int(inverse_mod(e, N-1))
def f(i1, i2):
    return (E-x)^i1*(N-y)^i2*(N-1)^(max(t-i1-2*i2, 0))
# ============================================================================================================

ref：

exp：

# 原论文：https://www.iacr.org/archive/asiacrypt2015/94520198/94520198.pdf
# 辅助理解：https://eprint.iacr.org/2024/061.pdf

from sage.all import *
from hashlib import sha256
from subprocess import check_output
from re import findall
from time import time
from binteger import Bin
from Crypto.Util.number import *


def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
  

# ============================================================================================================
N = 0xbe9ccc83003bedf45421b58377b946f87dfd85be82124dc5d732070d77ef68e0231c3f34dc803a8984de0573db6d83ccea0bd53a885059a10cfa3764c658c4d42c5fa90ecad8573fff8f2c41e513278c59121e42ad83310fb22b4d20e7ada42c76f08891f38c92a1b1aac712bfa7d717a4c4802ed023f12c768972ca1b
e = 0x5dc97ed7250e57ce6fac4f57885c0538b1ea540fbaca79730470b6b990f7e861adc4c5fee3acdcd9ae9a2834b606ddfae01ade33edfa96a47a0ffc0036a4497a84c38b7cdac20c38f
beta = 0.25  # log(d, N)
Gamma = 0.42  # log(g, N)


XX = int(ceil(N^beta))
YY = int(ceil(N^0.5))

t = 10
print(f't = {t}')
n = 2
r = 1
r1 = 1
r2 = 2
y1 = beta
y2 = 1/2
nn = Gamma
R = [r1, r2]
Y = [y1, y2]

# check
# for i in range(2):
    # print(Y[i]/R[i]<nn)

PR.<x,y>= PolynomialRing(ZZ)
E = int(inverse_mod(e, N-1))
def f(i1, i2):
    return (E-x)^i1*(N-y)^i2*(N-1)^(max(t-i1-2*i2, 0))
# ============================================================================================================

my_polynomials = []
monomials = set()


Is = []
for i1 in range(100):
    for i2 in range(100):
        if 0<=y1*i1+y2*i2<=nn*t:
            Is.append([i1, i2, i1+i2])
# 排序
for tt1 in range(len(Is)-1):
    for tt2 in range(tt1+1, len(Is)):
        if (Is[tt1][-1]>Is[tt2][-1]):
            Is[tt1],Is[tt2] = Is[tt2],Is[tt1]
          
for tt1 in range(len(Is)-1):
    for tt2 in range(tt1+1, len(Is)):
        if (Is[tt1][-1]==Is[tt2][-1]) and Is[tt1][1]>Is[tt2][1]:
            Is[tt1],Is[tt2] = Is[tt2],Is[tt1]

print(Is)

# 生成shift多项式
for each in Is:          
    i1, i2 = each[0], each[1]
    # print(i1, i2)
    tmp = f(i1, i2)
    my_polynomials.append(tmp)
          
# 构造下三角矩阵：利用偏序
known_set = set()
new_polynomials = []
my_monomials = []
 
# construct partial order
while len(my_polynomials) > 0:
    for i in range(len(my_polynomials)):
        f = my_polynomials[i]
        current_monomial_set = set(x^tx * y^ty for tx, ty in f.exponents(as_ETuples=False))
        delta_set = current_monomial_set - known_set
        if len(delta_set) == 1:
            new_monomial = list(delta_set)[0]
            my_monomials.append(new_monomial)
            known_set |= current_monomial_set
            new_polynomials.append(f)          
            my_polynomials.pop(i)
            break
    else:
        raise Exception('GG')
      
my_polynomials = deepcopy(new_polynomials)
 
# 构造矩阵：置入多项式系数
nrows = len(my_polynomials)
ncols = len(my_monomials)
L = [[0 for j in range(ncols)] for i in range(nrows)]
print(f'矩阵规模：{nrows} x {ncols}')
print('my_monomials', my_monomials)

for i in range(nrows):
    g_scale = my_polynomials[i](XX*x, YY*y)  # f(XX*x, YY*y)
    for j in range(ncols):
        L[i][j] = g_scale.monomial_coefficient(my_monomials[j])

      
# LLL得到规约系数，联立解方程            好吧这一步实在不知道在干嘛
L = Matrix(ZZ, L)
nrows = L.nrows()
L = flatter(L)
print('LLL done!') # 感觉其实导这里就能手动把d回复出来了。。。。

# Recover poly
reduced_polynomials = []
for i in range(nrows):
    g_l = 0
    for j in range(ncols):
        g_l += L[i][j] // my_monomials[j](XX, YY) * my_monomials[j]  # 消常系数，代入未知量
    reduced_polynomials.append(g_l)
print('done, next solve d')

# 结式
h1 = reduced_polynomials[0]
h2 = reduced_polynomials[1]
# 结式消y
g1 = h1.resultant(h2, y)
x = g1.univariate_polynomial().roots()
if x:
    d = x[0][0]
    flag = 'DubheCTF{{{:x}}}'.format(d & (2**128 - 1))
    print(flag)  # DubheCTF{b896a5fef7abec06cd2e6256be4ba40b}

debug #

去年使用blowfish主题以来

饱受公式渲染不正确的困扰，今天误打误撞解决了这个小问题

如果你发现你的blowfish主题的公式在本地http server和gitpage中渲染的样式不同

并出现了 “failed to find a valid digest"报错

是因为

https://github.com/golang/go/issues/59234

而hugo为修补这一问题加入JS模板验证的属性

具体方法为把文件的sha512指写在文件名里面

public\lib\katex\katex.min.6a864286ffbc8a663f5353bb2881d7bcef3b10ecc2b8a3b41a116da43e86d82ca3a3fc4f79381d7f7fdb721075d2207e0288cc4c390c1c33cb28dc4f255a8373.js:

然后开发写bug了

哈哈

解决办法要么生成静态网页的时候使用development模式

要么在 \config_default\config.toml 加入以下内容

_default位置

/m/d/M/g/Blog ❯❯❯ tree -L 2
.
├── archetypes
│   └── default.md
├── assets
│   ├── css
│   ├── img
│   └── static
├── config
│   └── _default

[security]
[security.gotemplates]
  allowActionJSTmpl = true

然后重新build再push就ok了

Alt text

笑死 因为可以允许js脚本了，之前一直不能用的搜索功能也能用了

没渲染出来的字体也正常了

https://discourse.gohugo.io/t/incorrect-sha256-value-for-integrity-attribute-with-fingerprint-function-failed-to-find-a-valid-digest/44462

原回答开发还和用户吵起来了