RSA进阶

之前学了点Coopersmith，但感觉似懂非懂，现在再学一遍后，很多知识有了新的理解。

也感谢网上一些详细易懂的资源！

Coopersmith方法

首先需要了解一些前置的代数知识

环：抽象代数中，不仅将具体的值当做操作对象进行运算，还把运算符和运算规则也作为一种操作对象进行运算，环就是这样的一个代数系统，它包含两种运算（加法和乘法），但具体运算和环定义有关
有限域（伽罗瓦域）

存在乘法逆元的环是域，在模p下成立的域是有限域。

对于一个模n意义下的e阶多项式，Coopersmith方法可以求解得到两种根：

$1. n^{1/e}以内的小根\\ 2. 给定b,得到模p意义下的小根，其中p>=n^b且为n的因数\\$

也就是说，我们可以求出模多项式的一个小根。

并且，如果题中给出一个模p的多项式，但没有给出p，直接模n也能得到结果。

题目1：m高位泄露

假设m高位是m1,低位为x，

根据c=m^e(mod n)

构造模多项式P(x)=(m1+x)^e−c（modn）

当x<n^1/e时，就能够用coopersmith进行求解得到m

#Sage
n = 
e = 
c = 
mbar = 
kbits = 
beta = 1
nbits = n.nbits()
print("upper {} bits of {} bits is given".format(nbits - kbits, nbits))
PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c
x0 = f.small_roots(X=2^kbits, beta=1)[0]  # find root < 2^kbits with factor = n
print("m:", mbar + x0)

题目2：p高位泄露

假设有模p多项式为f(x)=x (mod p)

但没有p值，也就求不出来模p多项式下的根x，

但根据Coopersmith的第二条，我们可以构建一个模n多项式，这样不仅可以求解模n多项式的小根，还能求解n的因数的小根，此时需要满足p>=n^b（知道p高位是p的位数约1/2就行）

假设p_h为p高位，令p=p_h+x，

$构造P(x)\equiv p_h+x\pmod n$

如果x足够小，我们可以求出。

#Sage
n = 
p4 =  #p去0的剩余位
pbits = 1024
kbits = pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:        
    p = p4 + int(roots[0])
    q = n//p
    print(f'n: {n}')
    print(f'p: {p}')
    print(f'q: {q}')

题目3：d低位泄露

首先我们知道一个条件

在二进制里，一个数除以2^a的余数就是它的低a位 $因为：整数d可以写成d\equiv q*2^a+r \\ (0<=r<2^a)\\ 余数r正好就是低a位$

假设d_l为d的低位，且d_l位数为a位，有

$d_l\equiv d\pmod {2^a}\\ 根据ed=1(mod phi_n),有ed=1+k*phi_n=1+k(n-p-n/p+1)\\展开得到edp-kp(n-p+1)+kn=p\\ 根据上面假设的条件，等式两边同时模2^a,得到ed_lp-kp(n-p+1)+kn=p(mod 2^a)\\$

又因为ed=1+kphi_n,ed约等于k phi_n,而d<phi_n,e也小，所以k必须小，猜测k和e差不多大，就得到k在[1,e)中，遍历得到k。

然后只剩下一个未知数p，通过求解模多项式得到p。

此时我们可以将左边看做一个整体为p_l,显然p_l为p的最低a位，也就是

$p_l\equiv p\pmod {2^a}\\ 此时p=p_l+2^a*p_h\\ 构造模多项式f(x) = 2^\alpha x + p_l \bmod{n}\\ 利用Coopersmith方法得到解X即为p_h\\$

Rabin算法

明白下面这些定理之后可以更好地理解rabin算法

定理1：欧拉判别定理

$c是模p的平方剩余的充要条件是,(c^{1/2})^{\phi (p)} \equiv 1\pmod p$

证明充分性

$首先有前置知识\\ 由费马小定理知，d^{(p-1)} \equiv1\pmod p\\ p为奇素数，p-1为偶数,上式可拆为(d^{(p-1)/2}-1)(d^{(p-1)/2}+1) \equiv0\pmod p\\ 由此可见 d^{(p-1)/2}在模p下必然与1或-1同余\\ 即d^{(p-1)/2}\equiv1\pmod p\\ 然后来证明若d是模p的平方剩余,则(d^{1/2})^{\phi (p)} \equiv 1\pmod p\\ **证明如下:**\\ 因为d是模p的平方剩余，所以存在x,使得x^2 \equiv d\pmod p\\ d^{(p-1)/2} \equiv x^{p-1}\equiv1\pmod p显然成立$

证明必要性(不太严谨)

$若(d^{1/2})^{\phi (p)} \equiv 1\pmod p,则d是模p的平方剩余,\\ 首先必然存在x=1使得x^2\equiv d\pmod p成立，得证$

定理2：

$二次同余式x^2 \equiv c\pmod p 1式\\ 的解是\\ x=±c^{(p+1)/4}\pmod p\\ **证明如下：**\\ 因为c和p互素，利用欧拉判别定理\\ c是模p的平方剩余的充要条件是,(c^{1/2})^{\phi (p)} \equiv 1\pmod p\\ 所以c^{(p-1)/2}\equiv 1\pmod p 2式\\ 联立12式得到\\ x^2\equiv c*(c^{1/2})^{p-1}\equiv c^{(p+1)/2}\equiv(c^{(p+1)/4})^2\\ 得到x=±c^{(p+1)/4}\pmod p\\$

定理3：

如果整数c满足：

1) c为 p的平方剩余

2) c为 q的平方剩余

则：c 为 p*q的平方剩余

$解 x为：x = \pm \left( c^{\frac{p+1}{4}} \pmod{p} \right) \cdot \left( q^{-1} \pmod{p} \right) \cdot q \pm \left( c^{\frac{q+1}{4}} \pmod{q} \right) \cdot \left( p^{-1} \pmod{q} \right) \cdot p \pmod{p \cdot q}\\ **证明**\\ 二次同余式：x^2 \equiv c \pmod{p \cdot q}\\ 等价于同余式组：\\ x^2 \equiv c \pmod{p} \quad \text{(1)}\\ x^2 \equiv c \pmod{q} \quad \text{(2)}\\ 由定理2\\ (1) 式解为x \equiv \pm c^{\frac{p+1}{4}} \pmod{p}\\ (2) 式解为x \equiv \pm c^{\frac{q+1}{4}} \pmod{q}\\ 由CRT，解为\\ x \equiv \pm \left( c^{\frac{p+1}{4}} \pmod{p} \right) \cdot \left( q^{-1} \pmod{p} \right) \cdot q \pm \left( c^{\frac{q+1}{4}} \pmod{q} \right) \cdot \left( p^{-1} \pmod{q} \right) \cdot p \pmod{p \cdot q}$

参考Van1sh的博客https://jayxv.github.io

Rabin加密

已知p,q为私钥，n=p*q为公钥,密文c

c=m^2%n

c=m^2%n等价于c=m^2%p,c=m^2%q

根据上述定理3，用中国剩余定理解出m

import gmpy2

def rabin_decrypt(c, p, q, e=2):
	n = p * q
	mp = pow(c, (p + 1) // 4, p)
	mq = pow(c, (q + 1) // 4, q)
	yp = gmpy2.invert(p, q)
	yq = gmpy2.invert(q, p)
	r = (yp * p * mq + yq * q * mp) % n
	rr = n - r
	s = (yp * p * mq - yq * q * mp) % n
	ss = n - s
	return (r, rr, s, ss)
 
c = 
p = 
q = 
m = rabin_decrypt(c,p,q)
for i in range(4):
	try:
		print(bytes.fromhex(hex(m[i])[2:]))
	except:
		pass

参考Lazzaro师傅的博客 https://lazzzaro.github.io

参考Van1sh的博客https://jayxv.github.io

参考NSS密码工坊课程RSA(四)