0x01-前言

参考论文

  1. 《Low-Exponent RSA with Related Messages 》by Coppersmith, Franklin, Patarin and Reiter
  2. 《Solving Systems of Modular Equations in OneVariable: How Many RSA-Encrypted MessagesDoes Eve Need to Know?》by Alexander May, Maike Ritzenhofent

介绍低指数相关攻击,主要是翻译文章并使用SageMath复现攻击。

使用工具:

  1. python2, 依赖库:gmpy2
  2. SageMath

主要讨论有相关关系的消息进行RSA加密的情况。
多次进行RSA加密时,如果使用的模数 Ni 不互质,那就可求出最大公约数作为模数的一个因子,进而分解模数完成解密。

如果消息不进行填充就重复加密,是容易被攻击的。

​ 比如G. Simmons提出的共模攻击。一段消息m被加密两次。N相同,e 互质。用拓展欧几里得算法可以得到 直接计算完成攻击。
我们只讨论带填充的加密情况。

​ 我们接下来讨论的都是认为以下条件成立的情况下进行的:

  1. 公钥已知
  2. 模数互质,且分解模数困难
  3. 明文经过填充
  4. 所有密文已知

0x02-RSA 原理

RSA原理参考自https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_theory-zh/

  1. 随机选择两个不同的大素数 p q,计算 N = p×q

  2. 由欧拉函数,得 φ(N)=φ(p)φ(q)=(p−1)(q−1)

  3. 取一小于 φ(N)的整数 e,使 eφ(N) 互质。并求得 e 关于 φ(N) 的模反元素,命名为 d,有

  4. pq 的记录销毁

此时,(N,e)是公钥,(N,d)是私钥。设加密函数为E,解密函数为D

0x03-LLL算法

功能:在多项式时间内求解一元首一多项式 f(x)所有的根

条件:

如果X 为根 x 的上限

可求出一元方程
的所有根 x0

费时

sage实现

from sage import *
PR = PolynomialRing(ZZ, 'x')
x = PR.gen()
FF = (x+1024)^10 + 23*x
m = FF.small_roots(X=2**760, beta=7./8) #一个列表,表示所有根

0x04-带填充的共模攻击

参考: 《Low-Exponent RSA with Related Messages 》by Coppersmith, Franklin, Patarin and Reiter。

讨论带线性填充和非线性填充的共模攻击思路。

攻击情景:

k个明文满足某个δ阶多项式P(即所有明文存在某种相关关系)。

使用相同RSA公钥(e, N)加密得到 k 个密文

可以在时间复杂度 内恢复所有明文。

也就是说得知 k+1 个多项式就可能解出所有明文。

推广 e

我们先讨论简单情况,再证明 e 很大的时候也是可解的。

k = 2,只涉及两组消息。

δ = 1 ,即明文可以如下表示

为了方便我们讨论如下情况

e=3

加密两次,得到如下结果:

可以转化成一元一次方程,求解明文(以下除法为乘逆元):

e=5

容易找到多项式P(x) 和 Q(x),满足以下关系求得x。

事实上, e 很大的时候我们也能求出多项式的最大公约式得到线性多项式 x - m 以求解明文。

证明

从而计算得到 x 再由明文和x的多项式f(x)即可得到所有明文。

推广 δ > 1

如果所有的明文都可以用某个 δ 阶一元多项式 f 表示,δ > 1。现在证明此时也是可解的。

如果两个明文和 x 之间的关系是非线性的,加密后有如下关系

在知道填充方式的前提下,可以求解所有明文。

证明:

  1. 令 x, y 分别代表 m1, 和 m2。
  2. 在 Z/N 环上,计算 P1(x, y) 和P2(x)的关于 x 的结式,也就得到一个在 y 上的δe 阶多项式 P4。
  3. 计算 P4 和 P3 的最大公约式,也就是线性多项式 y-m2,m2可以用该线性多项式表达。
  4. 将m2(此时仍未求解)代入P1,得到一个只关于 x 的多项式,再求解此多项式和 P2的最大公约式,就能得到x=m1。

证毕, δ > 1 也可以求解。

推广 k>2

当存在多组消息后,k个消息的相关于多项式 P,但是多项式 P 可能是一个包含多个元的。下面证明k>2也是可解的。

k个消息满足多项式P,共有k个多项式如下:

接着可以求出Groebner基,称为向量B,则

求得所有明文。

复杂度

我们将在文章后面使用sage计算Groebner基,进而得到所有明文。

k=2小结

无论填充是线性的还是非线性的,如果所有明文 x 都满足多项式P,转化成方程如下

使用相同公钥加密后,只要再得到两段密文,可以在复杂度

求出Groebner基后,求解一元e次方程组得到的根即为所求。
举例:

题目如下:

import gmpy2
import random
p = gmpy2.next_prime(random.getrandbits(1024))
q = gmpy2.next_prime(random.getrandbits(1024))
assert(p != q)
n = p * q
e = 17
m = int('Flag{123123-1231-13123213-123123}'.encode('hex'), 16)
cnt = 2
A = [(i + 128)**2 for i in range(cnt)]
B = [(i + 1024) for i in range(cnt)]
C = [(i + 512) for i in range(cnt)]
Cs = [int(pow(A[i] * m**2 + B[i]*m + C[i], e, n)) for i in range(cnt)]
print 'N=', n
print 'e=', e
print 'Cs=', Cs

SageMath 解题脚本如下:

from sage import *
# 事先需要将公钥密文添加到sage脚本中
N=....
e= 17
Cs= [...,...] # len(Cs) == 2
cnt = 2

A = [(i + 128)**2 for i in range(cnt)]
B = [(i + 1024) for i in range(cnt)]
C = [(i + 512) for i in range(cnt)]

PR = PolynomialRing(Zmod(N), 'x', 1)
x = PR.gen()
Fs = [((A[i] * x**2 + B[i]*x + C[i])**e - Cs[i]) for i in range(cnt)]
I = Ideal(Fs)
G_b = I.groebner_basis()[0]
m = ZZ(-G_b(0))
m = int(m + B[0])
print hex(m)[2:].strip('L').decode('hex')

k > 2总结

和k=2的情形不同之处在于此时可以涉及多个未知数。

k个明文相关,相关多项式共有k个元,已知k+1个以上关于k个明文的多项式。

示例

已知如下条件

# 参考2019redhat ctf 的密码学题目relate
import gmpy2
import random
p = gmpy2.next_prime(random.getrandbits(1024))
q = gmpy2.next_prime(random.getrandbits(1024))
assert(p != q)
n = p * q
phin = (p-1)*(q-1)
e = 5
d = gmpy2.invert(e, phin)
assert(e*d % phin)
def pad(msg, length):
    l = len(msg)
    return msg + chr(length - l) * (length - l)
flag = 'Flag{123123-1231-13123213-123123}'
flag = pad(flag, 48)
m = [int(flag[i * 16:i * 16 + 16].encode('hex'), 16) for i in range(3)]
print 'S=', sum(m) % n
cnt = len(m)
A = [(i + 128)**2 for i in range(cnt)]
B = [(i + 1024) for i in range(cnt)]
C = [(i + 512) for i in range(cnt)]
Cs = [int(pow((A[i] * m[i]**2 + B[i] * m[i] + C[i]), e, n)) for i in range(cnt)]
# Cs = [int(pow((B[i] * m[i] + C[i]), e, n)) for i in range(cnt)]
print 'N=', n
print 'e=', e
print 'Cs=', Cs

求解Groebner 基即可

sage解法

# 事先将题目的输出填入对应参数位置
# coding:utf-8
from sage import *

S= 
N=
e= 5
Cs= []
cnt = 3
A = [(i + 128)**2 for i in range(cnt)]
B = [(i + 1024) for i in range(cnt)]
C = [(i + 512) for i in range(cnt)]

PR = PolynomialRing(Zmod(N), 'x', cnt)
x = PR.gens()  # 生成 cnt 个x,用下标区分符号
Fs = [((A[i] * x[i]**2 + B[i] * x[i] + C[i])**e - Cs[i]) for i in range(cnt)]
Fs.append(x[0] + x[1] + x[2] - S)
I = Ideal(Fs)
G_b = I.groebner_basis()
for b in G_b[:-1]:
    mi = ZZ(-b(0, 0, 0))  # 3 个元
    mi = hex(mi)[2:].strip('L')
    print (('', '0')[len(mi) %2]+mi).decode('hex')

0x05-广播攻击

讨论使用多组不同的RSA公钥进行加密的攻击手段。

​ 如果使用到的模数不全部互质数,则可以直接求出最大公约数分解模数完成解密。接下来我们讨论的都是模数全部相互互质的情况。

Håstad问题

描述:

使用不同的互质模数N、相同的参数 e,加密 e 个明文,得到 e 个密文。这 e 个明文都是关于x的线性填充结果,即

求解:

​ 可以得到e 个方程

​ 因为这 e 个模数都是互质的,那么可以由中国剩余定理得到一个多项式,此多项式必定有唯一解。

又因为此多项式满足LLL算法约束,则可以求解出所有根,得到 x ,进而恢复明文。

举例

e=5

因为5个模数相互互质,所以使用中国剩余定理得到一个5阶多项式,满足LLL算法条件,可求解。

# 题目脚本
import gmpy2
import random
m = int('Flag{123123-1231-13123213-123123}'.encode('hex'), 16)
e= 5
cnt = e
A = [(i + 128) for i in range(cnt)]
B = [(i + 1024) for i in range(cnt)]
Cs = []
Ns = []
ds = []
for i in range(cnt):
    while True:
        p = gmpy2.next_prime(random.getrandbits(1024))
        q = gmpy2.next_prime(random.getrandbits(1024))
        N = p * q
        phin = (p - 1) * (q - 1)
        try:
            d = gmpy2.invert(e, phin)
        except:
            continue
        if (e * d % phin == 1):
            break
    Ns.append(int(N))
    c = pow(A[i] * m + B[i], e, N)
    Cs.append(c)
    ds.append(d)
    del p, q,d
for i in range(cnt):
    assert(pow(Cs[i], ds[i], Ns[i]) == A[i] * m + B[i])

print 'Cs = ', [int(item) for item in Cs]
print 'Ns = ', [int(item) for item in Ns]
print 'A= ', A
print 'B=', B
print 'e=', e

sageMath 解题脚本

# coding:utf-8
from sage import *

Cs = []
Ns =  []
A=  [128, 129, 130, 131, 132]
B= [1024, 1025, 1026, 1027, 1028]
e= 5

# solve
cnt = e
PR = PolynomialRing(ZZ, 'x') #1个元
x = PR.gen()
Fs = []
for i in range(cnt):
    f =  PR( (A[i]*x + B[i])**e - Cs[i] ) # 五个式子
    ff = f.change_ring(Zmod(Ns[i]))
    ff = ff.monic()
    f = ff.change_ring(ZZ)
    Fs.append(f)

F = crt(Fs, Ns)
M = reduce( lambda x, y: x * y, Ns )
FF = F.change_ring(Zmod(M))
m = FF.small_roots()#LLL算法
if m:
    m = hex(int(m[0]))[2:].strip('L')
    print(['', '0'][len(m) % 2] + m).decode('hex')
else:
    print 'no ans'

SMUPE-问题

参考《Solving Systems of Modular Equations in OneVariable: How Many RSA-Encrypted MessagesDoes Eve Need to Know?》by Alexander May, Maike Ritzenhofent

SMUPE定义

SMUPE问题: a system of univariate polynomial equations problem = 一元多项式方程组求解问题

k 是一个整数,N为满足RSA算法的模数,δ是多项式的阶。有

多项式方程组表示如下, 目的是求解 x

求解条件

Alexander May, Maike Ritzenhofent提出一种求解方法,简单地说当多项式的阶 δ 满足以下情况时可解. δ是多项式的阶

具体描述


作为 SMUPE-问题的首一多项式组

定义

SMUPE-问题 则 the SMUPE-problem 可以在以下复杂度解决。

攻击算法

先给出一个简单的例子,在后面会给出这种情况下的攻击脚本:

将一个明文m进行填充,分别使用4组RSA公钥进行加密(模数互质),多项式(1)描述如下

公钥分别是 (3, N0) ,(3, N1),(5, N2), (5, N3)

进行如下转化,使得每个方程左边都是6阶

移项,令方程左边为0

4个模数互质,且有四个同余式,则可以用中国剩余定理求解,得到关于m的一元6阶多项式

如果m满足LLL算法,

可以求解得到多项式的根 m

证明

设 $x_0$ 作为多项式(1)的一个解。则$x_0$为以下方程组的解

所以方程都是 首一δ 阶多项式。

使用中国剩余定理求解方程组得到一个首一 δ 阶多项式 f(x) ,且x0 是下式的根。

因为 f(x) 每一项 x^δ 的系数a_δ 存在如下关系


所以有

​ 中国剩余定理可以在时间复杂度

完成。

​ 当 f(x) 的根 x0 满足

可以使用LLL算法求解 x0 , LLL算法时间复杂度为

所以整个攻击的时间复杂度为

例题

参考 2019 redhat CTF 密码学题目《精明的Alice》

是文章在上面给出的SMUPE简单例子

import gmpy2
import random

def RSA(e):
    while True:
        p = gmpy2.next_prime(random.getrandbits(1024))
        q = gmpy2.next_prime(random.getrandbits(1024))
        N = p * q
        phin = (p - 1) * (q - 1)
        try:
            d = gmpy2.invert(e, phin)
        except:
            continue
        if (e * d % phin == 1):
            break
    return e, int(N)
PKs = [RSA(3), RSA(3), RSA(5), RSA(5)]
m = int('Flag{123123-1231-13123213-123123}'.encode('hex'), 16)
cnt = 4
A = [(i + 128) for i in range(cnt)]
B = [(i + 1024) for i in range(cnt)]
Cs = [pow(A[i] * m + B[i], PKs[i][0], PKs[i][1]) for i in range(cnt)]
print 'Cs = ', [int(item) for item in Cs]
print 'PKs = ', PKs
print '[+] enc complited.'

SageMath 脚本

# 将题目输出填入对应变量
from sage import *
Cs = [...]
PKs =  [(3,..), (3,..), (5,..), (5,..)]
cnt = 4
A = [(i + 128) for i in range(cnt)]
B = [(i + 1024) for i in range(cnt)]
PR = PolynomialRing(ZZ, 'x')
x = PR.gen()

Fs = []
for i in range(cnt):
    f =  PR( ( A[i]*x + B[i] )**PKs[i][0] - Cs[i] )
    ff = f.change_ring( Zmod(PKs[i][1]) )
    ff = ff.monic()
    f = ff.change_ring(ZZ)
    Fs.append(f)
F = crt( [ Fs[0]**2, Fs[1]**2, x*Fs[2], x*Fs[3] ], [ PKs[i][1] for i in range(cnt) ] )

M = reduce( lambda x, y: x * y, [ PKs[i][1] for i in range(cnt) ] )
FF = F.change_ring( Zmod(M) )
m = FF.small_roots(X=2**760, beta=7./8)[0]
m = hex(int(m))[2:].strip('L')
print (('', '0')[len(m) % 2]+m).decode('hex')

0x06-后记

为了方便复现,使用的工具已经尽可能地少(其实sage和python已经足够了)

SageMath安装教程:http://doc.sagemath.org/html/en/tutorial/introduction.html#installation

笔者的理论水平有限,纰漏之处还请读者海涵。

Reference:

  1. 《Low-Exponent RSA with Related Messages 》by Coppersmith, Franklin, Patarin and Reiter
  2. 《Solving Systems of Modular Equations in OneVariable: How Many RSA-Encrypted MessagesDoes Eve Need to Know?》by Alexander May, Maike Ritzenhofent
  3. RedHat CTF 官方writeup :https://mp.weixin.qq.com/s/MKaMMihP8gPSYKswAxjNqQ
  4. CTFWiki:https://ctf-wiki.github.io/ctf-wiki/crypto/
  5. SageMath文档:http://doc.sagemath.org/html/en/tutorial/introduction.html

点击收藏 | 1 关注 | 1
  • 动动手指,沙发就是你的了!
登录 后跟帖