CTF中的RSA基本套路(4)

第四部分是相关消息的内容

依赖库：

• gmpy2
• pycrypto
• pwntools
• sage

线性相关消息#

场景#

这是相关消息攻击最简单的一种形式，已知$c_1 = m_1 ^ e \mod N,c_2 = (am_1+b)^e \mod N，m_2 = am_1+b$

解法#

可以看到两次加密的消息$m_1$和$m_2$存在线性关系，当$e=3$时，根据推导(见《Low-Exponent RSA with Related Messages》)，可以得到以下关系

$m_{1}=\frac{b}{a} \frac{c_{2}+2 a^{3} c_{1}-b 3}{c_{2}-a^{3} c_{1}+2 b^{3}}$，因此可以根据已知的$c_1、c_2、a、b$轻松得到消息$m_1$（注意，这里的除法是求逆元的意思）

# python
from gmpy2 import invert
def getmessage(a, b, c1, c2, n):
    b3 = pow(b, 3, n)
    a3 = pow(a, 3, n)
    part1 = b * (c2 + 2 * c1 * a3 - b3) % n
    part2 = a * (c2 - c1 * a3 + 2 * b3) % n
    part2 = invert(part2, n)
    return part1 * part2 % n

进阶#

下面是论文中的通用情况，即$c_1= (a_1m+b_1)^e \mod n$，$c_2 = (a_2m+b_2)^e \mod n$，不通过前面推公式的方法，只需要通过$gcd$即可求得对应的消息。由于式子$(a_1m+b_1)^e - c_1 \mod n$和$(a_2m+b_2)^e -c_2 \mod n$都必然存在公共的$x-m$的根，因此通过$gcd$求得$x-m$，即可得到对应的消息$m$，

# sage
def gcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic()
    
n = 
a1 = 
b1 = 
c1 = 
a2 = 
b2 = 
e = 3
c2 = PR.<x>= PolynomialRing(Zmod(n))
g1 = (a1*x+b1)^e-c1
g2 = (a2*x+b2)^e-c2
print(-gcd(g1, g2)[0])

多消息相关#

场景#

假设存在$k$个消息，它们有关系式$P_0(x_1,x_2,…x_k)=p(x_1,x_2,…x_k) = 0 \mod N$

并且有$P_i(x_i)=x_i^e-c_i = 0 \mod N$，需要求解这$k$个消息

解法#

根据这$k+1$个等式，我们计算$Groebner$基$Groebner([P_0,P_1,…P_k])$，可以得到结果$[x_1-m_1,…x_k-m_k]$，

也就求得了所有的$k$个消息

以下举例论文中比较特殊的线性相关消息，即$P_0(x_1,x_2…x_k) = x_1+x_2+…x_k-w = 0 $

# python
from Crypto.Util.number import getPrime, bytes_to_long
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 3
m1 = bytes_to_long(b"flag{This_is_flag1}")
m2 = bytes_to_long(b"flag{This_is_flag2}")
m3 = m1+m2+10000
print(n)
print(pow(m1,e,n))
print(pow(m2,e,n))
print(pow(m3,e,n))
'''
108684504406001730978107355065522913091470167674222436489722232508562878942265531378563853986279259519842855383477949581415300994618557266600557629814170912555530200441331549267805294484355321505430150563949802485514426432450612355535035910835277447960752175362457165729276266536456917482476441605301749223673
11916677858912595626741303803048763073265062084232819699152039070779448603839943645221450568650559197753804295090892194306963679051905125
11916677858912595626741303803048763073265066091036090039985967549263766666260772390533720397506805484501981105835442312723743004564263781
95333422871300765013930430424390104586121138764086629711853351243347558333657355599432416841199469970564180649403376333107226365096683496
'''

解的脚本如下：

# sage
e = 3
cnt = 3
N=108684504406001730978107355065522913091470167674222436489722232508562878942265531378563853986279259519842855383477949581415300994618557266600557629814170912555530200441331549267805294484355321505430150563949802485514426432450612355535035910835277447960752175362457165729276266536456917482476441605301749223673
c1=11916677858912595626741303803048763073265062084232819699152039070779448603839943645221450568650559197753804295090892194306963679051905125
c2=11916677858912595626741303803048763073265066091036090039985967549263766666260772390533720397506805484501981105835442312723743004564263781
c3=95333422871300765013930430424390104586121138764086629711853351243347558333657355599432416841199469970564180649403376333107226365096683496
c = [c1,c2,c3]
PR = PolynomialRing(Zmod(N), 'x', cnt)
x = PR.gens()
F = []
for i in range(cnt):
    F.append(pow(x[i],e)-c[i])
F.append(x[0]+x[1]-x[2]+10000)
I = Ideal(F)
G= I.groebner_basis()
for b in G[:-1]:
    mi = ZZ(-b(0, 0, 0))
    print(bytes.fromhex(hex(mi)[2:]))
'''
b'flag{This_is_flag1}'
b'flag{This_is_flag2}'
'''

Hastad 攻击#

场景#

前面的两个相关消息攻击模数都是相同的，而在Hasted广播攻击中则不同

使用不同但互质的模数$n$，相同的指数$e$、加密$e$个明文得到$e$个密文，即$c_i = (a_ix+b_i)^e \mod n_i ,i=1,2…e$

解法#

通过这$e$个式子，我们有$e$个等式：$(a_ix+b_i)^e -c_i \equiv 0 \mod n_i，i=1,2…e$

由于这$e$个式子中，模数都是互质的，那么通过中国剩余定理，我们可以得到$P(x) \equiv 0 \mod M，M=\prod_{i=1}^{e} n_i$，而$P(x)$又必然存在唯一解，并满足LLL算法约束，因此可以通过sage的small_roots函数解得，以下给出两个写法分别来自https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/hastads.sage和https://xz.aliyun.com/t/6813

# sage
def linearPaddingHastads1(cArray, nArray, aArray, bArray, e=3, eps=1/8):
    """
    Performs Hastads attack on raw RSA with no padding.
    This is for RSA encryptions of the form: cArray[i] = pow(aArray[i]*msg + bArray[i],e,nArray[i])
    Where they are all encryptions of the same message.
    cArray = Ciphertext Array
    nArray = Modulus Array
    aArray = Array of 'slopes' for the linear padding
    bArray = Array of 'y-intercepts' for the linear padding
    e = public exponent
    """
    if(len(cArray) == len(nArray) == len(aArray) == len(bArray) == e):
        for i in range(e):
            cArray[i] = Integer(cArray[i])
            nArray[i] = Integer(nArray[i])
            aArray[i] = Integer(aArray[i])
            bArray[i] = Integer(bArray[i])
        TArray = [-1]*e
        for i in range(e):
            arrayToCRT = [0]*e
            arrayToCRT[i] = 1
            TArray[i] = crt(arrayToCRT, nArray)
        P.<x> = PolynomialRing(Zmod(prod(nArray)))
        gArray = [-1]*e
        for i in range(e):
            gArray[i] = TArray[i]*(pow(aArray[i]*x + bArray[i], e) - cArray[i])
        g = sum(gArray)
        g = g.monic()
        # Use Sage's inbuilt coppersmith method
        roots = g.small_roots(epsilon=eps)
        if(len(roots) == 0):
            print("No Solutions found")
            return -1
        return roots[0]

    else:
        print("CiphertextArray, ModulusArray, and the linear padding arrays need to be of the same length," +
              "and the same size as the public exponent")

def linearPaddingHastads2(cArray, nArray, aArray, bArray, e=3, eps=1/8):
    cnt = e
    PR = PolynomialRing(ZZ, 'x')
    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(epsilon=1/16)
    if m:
        return m[0]
    else:
        return None

SMUPE 问题#

场景#

在经历了模数相同的相关消息攻击，也看过了模数不同的Hastad攻击，但是我们的指数$e$始终是一致的，SMUPE问题是论文《Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know? 》中提出的，不仅模数不同，且指数$e$也不同，具体如下：

假如我们有$k$个式子，$c_i = (a_ix+b_i)^{e_i} \mod n_i,i=1,2…k $，此时如何求解未知的消息呢

解法#

示例1：以论文中为例，已有4个公钥$(e,N)$分别为$(3,N_1),(3,N_2),(5,N_3),(5,N_4)$，且有$c_i = (a_ix+b_i)^{e_i} \mod N_i,i=1,2…4$

由于阶次不同，无法直接进行CRT，因此需要构造得到同阶次的式子进行CRT。

Cs = [...]
PKs =  [(3,..), (3,..), (5,..), (5,..)]
cnt = 4
A = []
B = []
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]
print(m)

示例2：

也是为了更加深入理解这个构造，在此示例中，$e$分别为2和3

c1 = 
c2 = 
a1 = 
a2 = 
b1 = 
b2 = 

Cs = [c1, c2]
A = [a1, a2]
B = [b1, b2]
cnt = 2
PKs = [(2,n1), (3,n2)]
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]*x, Fs[1]], [ 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(epsilon=1.0/16)[0]
print(m)

PS：small_roots的参数需要根据实际情况进行调整

Let `N` be the characteristic of the base ring this polynomial
  is defined over: ``N = self.base_ring().characteristic()``.
  This method returns small roots of this polynomial modulo some
  factor `b` of `N` with the constraint that `b >= N^\beta`.
  Small in this context means that if `x` is a root of `f`
  modulo `b` then `|x| < X`. This `X` is either provided by the
  user or the maximum `X` is chosen such that this algorithm
  terminates in polynomial time. If `X` is chosen automatically
  it is `X = ceil(1/2 N^{\beta^2/\delta - \epsilon})`.
  The algorithm may also return some roots which are larger than `X`.
  'This algorithm' in this context means Coppersmith's algorithm for finding
  small roots using the LLL algorithm. The implementation of this algorithm
  follows Alexander May's PhD thesis referenced below.
  INPUT:
  - ``X`` -- an absolute bound for the root (default: see above)
  - ``beta`` -- compute a root mod `b` where `b` is a factor of `N` and `b
    \ge N^\beta`. (Default: 1.0, so `b = N`.)
  - ``epsilon`` -- the parameter `\epsilon` described above. (Default: `\beta/8`)
  - ``**kwds`` -- passed through to method :meth:`Matrix_integer_dense.LLL()

参考链接#

• https://xz.aliyun.com/t/6813#toc-2

• https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack-zh/#related-message-attack

• Low-Exponent RSA with Related Messages

• https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/hastads.sage