RSA—1

Intro

从本篇开始，会对一些密码学中常见的加密算法进行研究，同时会给出一些攻击套路。当然，一些在比赛中遇到的相关paper提供的攻击方法也会进行介绍。

与这些加密算法有关的数论知识，有些会介绍，有些会省略。

RSA介绍

RSA涉及三个参数：$n,e,d$，其中$n,e$是公钥，$d$是私钥。$n$是两个素数的乘积，一般记作$p、q$，$phi=(p-1)(q-1)$。一般选取的$e$满足：$gcd(e,phi)=1$。私钥$d$满足：$de\equiv1\ \ (mod\ phi)$。

加密过程：

解密过程：

一般来说，$n,e$ 是公开的，但是由于$n$一般是两个大素数的乘积，所以我们很难求解出 d，所以 RSA 加密就是利用无法快速实现大素数的分解，所存在的一种安全的非对称加密。

对于RSA的做题思路，大多都是通过一些途径分解$n$。

直接分解n

factordb.com 这是一个利用数据库查询分解n的网站

Integer factorization calculator (alpertron.com.ar) 这是利用ecc分解n的网站

sagemath中通过$factor()$函数分解，当然sagemath里还可以指定分解方法。

yafu：一个分解脚本，需要cmd运行。

低加密指数攻击

这里一般e=2或3，同时n取的很大。

from Crypto.Util.number import *
import gmpy2
n=
c=
e=
for i in range(2**16):
    m=gmpy2.iroot(c+i*n,e)
    if m[1]:
        break
print(long_to_bytes(m[0]))

共模攻击

from libnum import n2s,s2n
from gmpy2 import invert
def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  else:
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)

def main():
  n = 
  c1 = 
  c2 = 
  e1 = 
  e2 = 
  s = egcd(e1, e2)
  s1 = s[1]
  s2 = s[2]
  if s1<0:
    s1 = - s1
    c1 = invert(c1, n)
  elif s2<0:
    s2 = - s2
    c2 = invert(c2, n)

  m = pow(c1,s1,n)*pow(c2,s2,n) % n
  print n2s(m)

if __name__ == '__main__':
  main()

以下是其数学原理

若Alice把一条信息m，用了同一个n和两个不同的e分别加密

那么Eva就可以通过$c_1,c_2,e_1,e_2,n$，得到$m$

假设$e_1,e_2$互质，我们就可以通过扩展欧几里得算法得到$s_1,s_2$

于是有

低加密指数广播攻击

如果选取的加密指数较低，并且使用了相同的加密指数给一个接受者的群发送相同的信息，那么可以进行广播攻击得到明文。

这个识别起来比较简单，一般来说都是给了三组加密的参数和明密文，其中题目很明确地能告诉你这三组的明文都是一样的，并且 e 都取了一个较小的数字。

import binascii,gmpy2
n =  [,,]
c =  [,,]
def CRT(mi, ai):
    assert(reduce(gmpy2.gcd,mi)==1)
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M / m) * gmpy2.invert(M / m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M
e=
m=gmpy2.iroot(CRT(n, c), e)[0]
print(binascii.unhexlify(hex(m)[2:].strip("L")))

由于e都一样，所以可以用中国剩余定理得到$m^e$，然后再开根就可以了。

dp泄露

已知$dp,n,e,c$，其中$dp\equiv d\ \ (mod\ p-1)$。

由于$ed\equiv 1\ \ (mod \ (p-1)(q-1))$，所以$e*dp\equiv 1\ \ (mod\ p-1)$。于是由费马小定理可以知道 $a^{e*dp}\equiv 1\ \ (mod\ p)$，于是$a^{e*dp}-1=kp$，我们只需要取a=2，计算$GCD(2^{e*dp-1},n)=p$，然后就是正常的RSA解密。

当然，这里还有另一种解法：由前面的推导我们可以知道

由于$dp<p-1$，于是$e>k_2(q-1)-k_1$，若记$x=k_2(q-1)-k_1$，那么$1<x<e$，所以只需要遍历这个区间，求出$p-1$即可。

def getd(n,e,dp):
    for i in range(1,e):
        if (dp*e-1)%i == 0:
            if n%(((dp*e-1)//i)+1)==0:
                p=((dp*e-1)//i)+1
                q=n//(((dp*e-1)//i)+1)
                phi = (p-1)*(q-1)
                d = gmpy2.invert(e,phi)%phi
                return d

dp、dq泄露

这类题是已知p、q、dp、dq、c，求m。

由已知可以知道的是，$m\equiv c^{d}\ \ (mod\ n)$，所以$m\equiv c^d\equiv c^{dp}\ \ (mod\ p),m\equiv c^d\equiv c^{dq}\ \ (mod\ q)$。然后这里直接用中国剩余定理，求出m。

低解密指数攻击

首先介绍连分数，其形式如下

其中的$a_i$都是整数，例如，对于3.245，有

每一部分都是先取整数，然后计算小数部分的倒数，每次重复这两个步骤。

有勒让德定理(Legendre’s theorem)：若整数$p,q$，满足$|\alpha-\frac{p}{q}|\leq\frac{1}{2q^2}$，那么 $\alpha$ 的连分数展开式收敛于 $\frac{p}{q}$ 。

结合RSA算法，令上述的$p,q$为$e,d$。

计算$|n-\phi|$，并对其大小估计（放缩）$|n-\phi|=|p+q-1|<3\sqrt{n}$。(维纳攻击原理先咕一阵子，后面补上)

脚本

from __future__ import print_function
import libnum
def continued_fractions_expansion(numerator,denominator):#(e,N)
	result=[]
	divident = numerator % denominator
	quotient = numerator // denominator
	result.append(quotient)
	while divident != 0:
		numerator = numerator - quotient * denominator
		tmp = denominator
		denominator = numerator
		numerator = tmp
		divident = numerator % denominator
		quotient = numerator // denominator
		result.append(quotient)
	return result
def convergents(expansion):
	convergents=[(expansion[0], 1)]
	for i in range(1, len(expansion)):
		numerator = 1
		denominator = expansion[i]
		for j in range(i - 1, -1, -1):
			numerator += expansion[j] * denominator
			if j==0:
				break
			tmp = denominator
			denominator = numerator
			numerator = tmp
		convergents.append((numerator, denominator)) #(k,d)
	return convergents
def newtonSqrt(n):
	approx = n // 2
	better = (approx + n // approx) // 2
	while better != approx:
	    approx = better
	    better = (approx + n // approx) // 2
	return approx
def wiener_attack(cons, e, N):
	for cs in cons:
		k,d = cs
		if k == 0:
			continue
		phi_N = (e * d - 1) // k
		#x**2 - ((N - phi_N) + 1) * x + N = 0
		a = 1
		b = -((N - phi_N) + 1)
		c = N
		delta = b * b - 4 * a * c
		if delta <= 0:
			continue
		x1 = (newtonSqrt(delta) - b)//(2 * a)
		x2 = -(newtonSqrt(delta) + b)//(2 * a)
		if x1 * x2 == N:
			return [x1, x2, k, d]
if __name__ == "__main__":
    n = 
    e = 
    c = 
    expansion = continued_fractions_expansion(e, n)
    cons = convergents(expansion)
    p, q, k, d = wiener_attack(cons, e, n)
    m = pow(c, d, n)
    print(libnum.n2s(m))

已知明文高位

n = 
e = 
m = randrange(n)
c = pow(m, e, n)
beta = 1
epsilon = beta^2/7
nbits = n.nbits()
kbits=   #明文被掩盖的位数
print(nbits,kbits)
mbar = #已知的不完整的m值
c = 
print ("upper %d bits (of %d bits) is given" % (nbits-kbits, nbits))
PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c
print (m)
x0 = f.small_roots(X=2^kbits, beta=1)[0]  # find root < 2^kbits with factor = n1
print( mbar + x0)

已知p高位

n = 
p_fake = #已知的不完整的p值
pbits = p_fake.bit_length()
kbits = #p失去的低位位数
pbar = p_fake & (2^pbits-2^kbits)
print ("upper %d bits (of %d bits) is given" % (pbits-kbits, pbits))
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  
p= x0 + pbar
print (p)

已知d低位

def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.bit_length()
    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)
def find_p(d0, kbits, e, n):
    X = var('X')
    for k in xrange(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p:
                return p
if __name__ == '__main__':
    n = 
    e = 
    d = #已知d的低位
    beta = 0.5
    epsilon = beta^2/7
    nbits = n.bit_length()
    print ("nbits:%d:"%(nbits))
    kbits = nbits - d.bit_length()-1
    print ("kbits:%d"%(kbits))
    d0 = d & (2^kbits-1)
    print ("lower %d bits (of %d bits) is given" % (kbits, nbits))
    p = find_p(d0, kbits, e, n)
    print ("found p: %d" % p)
    q = n//p
    print (d)
    print (inverse_mod(e, (p-1)*(q-1)))