RSA—1

发布于 2021-08-31  180 次阅读





RSA

Intro

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

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

RSA介绍

RSA涉及三个参数:,其中是公钥,是私钥。是两个素数的乘积,一般记作。一般选取的满足:。私钥满足:

加密过程:

解密过程:

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

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

直接分解n

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

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

sagemath中通过函数分解,当然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就可以通过,得到

假设互质,我们就可以通过扩展欧几里得算法得到

于是有

低加密指数广播攻击

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

这个识别起来比较简单,一般来说都是给了三组加密的参数和明密文,其中题目很明确地能告诉你这三组的明文都是一样的,并且 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都一样,所以可以用中国剩余定理得到,然后再开根就可以了。

dp泄露

已知,其中

由于,所以。于是由费马小定理可以知道 ,于是,我们只需要取a=2,计算,然后就是正常的RSA解密。

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

由于,于是,若记,那么,所以只需要遍历这个区间,求出即可。

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。

低解密指数攻击

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

其中的都是整数,例如,对于3.245,有

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

勒让德定理(Legendre’s theorem):若整数,满足,那么 的连分数展开式收敛于

结合RSA算法,令上述的

计算,并对其大小估计(放缩)。(维纳攻击原理先咕一阵子,后面补上)

脚本

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)))