RSA Notes 2

huangx607087学习RSA的笔记(2)

O-情况说明

约定:此博客中如果出现除法,未特殊说明的,均为向下取整的整除!

I-RSA的乘法的同态性

0x01 简介和 得到$m$的二进制位数

​ CTF中有些题目会在给出$e,n,c$的情况下,允许你和服务器交互,发送你自己的密文$c’$,然后告诉你有关$c’$解密后的明文的一些高位比特信息。在这种时候,我们就需要用到RSA乘法具有同态性的这一特殊性质,那么什么是RSA的同态性呢?

​ 我们已经知道,RSA加密函数$c=E(m) \equiv m^e \mod n$。其中$(e,n,c)$作为公钥,都是已知的。不过我们可以推导一下这样的公式:$E(2m)\equiv 2^em^e\equiv 2^e c\mod n$。所以如果在获得对个人密文的解密权的时候,我们就可以通过向服务器发送$2^e c$,这一就可以获得$2m$的值。同理,我们可以发送$2^{ke}c$,得到的解密结果就是$2^{k}m$。所以运行以下代码,我们得到的结果是$(12,24,48,96)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
m=12
p=getPrime(512)
q=getPrime(512)
n=p*q
e=65537
d=inverse(e,(p-1)*(q-1))
c=pow(m,e,n)
print(c)
c2,c3,c4=c*pow(2,e,n)%n,c*pow(2,2*e,n)%n,c*pow(2,3*e,n)%n
print(c2)
m1,m2,m3,m4=pow(c,d,n),pow(c2,d,n),pow(c3,d,n),pow(c4,d,n)
print(m1,m2,m3,m4)

​ 这种方法我们可以确定明文的长度:假如$n$是$2048$位,每次给你最高$8$位,那么被隐藏了$2040$位。假如我们一共移动了$740$位发现高位不再为$0$,那么我们可以确定明文长度为$2040-740=1300$位二进制数。

0x02 RSA确定$m$位数后确定明文$m$的值

​ 假如我们以上面那个为例子,我们确定了明文是$1300$位二进制数,那么我们现在就可以二分了:我们可以设置$L=2^{739},R=2^{740}$进行二分操作。

​ 注意在RSA中,有一个很神奇的式子:
$$
(pm)^e \equiv cp^e \mod n
$$

​ 然后我们可以得到这样的方程:$I=\dfrac {2^{2040}}{m}∈[2^{739},2^{740}]$,也就是$I \in [2×2^{738},4×2^{738}]$。对服务器发送区间中值$M=3×2^{738}$的加密结果乘上$c$的值,如果服务器告诉你最高的$8$位二进制数值不为$0$,则说明我们发送的数字偏大,随后我们就可以换区间右边界$R$为这一次的中值$M$,区间变成$[4×2^{737},6×2^{737}]$。若最后告诉你结果为$0$,那么说明我们发送的值偏小,然后我们可以把左边界换成$M$,然后把区间换成$[6×2^{737},8×2^{737}]$。后面以此类推。

​ 然而,我发现:自己的取值出了一个严重的问题,下面是一次二分过后的运行结果:

2

​ 分析了一下,原因很简单:因为这个时候除数是$2^{739}$到$2^{740}$左右的数量级,被除数是$2^{2040}$数量级,相差过大,于是我重新造数据:把flag的数量级降低到$2^{400}$,二分的$L,R$数量级提升到$2^{1640}$

​ 这一次的的运行结果,很准确:

2

​ 做了几次实验,发现flag规模在$2^{1000}$以下的时候无误差,$2^{1050}$规模的flag有不超过$10$的误差,$2^{1100}$规模的flag有几百的误差,$2^{1200}$的flag有几十万的误差,$2^{1300}$的flag的误差比特已经接近总比特数的一半。目测如果flag在$\sqrt{n}$内的话,就不会出现误差值。

最后贴一下测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from Crypto.Util.number import *
import random
def GetNumberBitz(x):
s=0
while 1:
tmp=random.randint(0,255)
s=s*256+tmp
if(s>(1<<5000)):
break
s=s%(1<<(x+1))
while(s.bit_length()!=x):
s=GetNumberBitz(x)
return s
def GenerateKey(B):
e,p,q=getPrime(random.randrange(16,20)),getPrime(B//2),getPrime(B//2)
n,phi=p*q,(p-1)*(q-1)
d=inverse(e,phi)
return e,n,d
def judg(CC,D,N):
x=pow(CC,D,N)
st=long_to_bytes(x,2048//8)
if(st.startswith(b"\x00")):
return 1
else:
return 0
def Attack(E,N,C,D,B,T):
L,R=2**(B),2**(B+1)
while R-L>1:
if(R-L).bit_length()%50==0:
print(hex(L),hex(R))
M=(L+R)//2
CC=(pow(M,E,N)*C)%N
check=judg(CC,D,N)
if(check==1):
L=M
else:
R=M
return L
#----main below----#
flag=GetNumberBitz(400)
assert flag.bit_length()==400
e,n,d=GenerateKey(2048)
while n.bit_length()!=2048:
e,n,d=GenerateKey(2048)
c=pow(flag,e,n)
print('e=',e)
print('n=',n)
print('c=',c)
print('2**2040//flag=',hex(2**2040//flag))
F=Attack(e,n,c,d,2040-400,2040)
print(hex(2**2040//F))
print(hex(2**2040//(F+1)))
print(hex(flag))

0x03 最后一个比特位泄露破解的原理(摘自CTFWIKI,本废物还不懂)

​ 假设目前存在一个 Oracle,它会对一个给定的密文进行解密,并且会给出明文的最后一个字节。那么给定一个加密后的密文,我们只需要 $\log_{256}n$ 次就可以知道这个密文对应的明文消息。

这个其实算作 RSA parity Oracle 的扩展,既然可以泄露出最后一个字节,那么按道理我们获取密文对应明文的次数应该可以减少。

假设$C=P^e \bmod N$

第一次时,我们可以给服务器发送$C*256^e=(256P)^e \bmod N$

服务器会计算得到$256P \bmod N$

这里

  • $256P$ 是偶数。
  • $N$ 是奇数,因为它是由两个大素数相乘得到。

由于 $P$ 一般是小于$ N$ 的,那么$256P \bmod N=256P-kn, k<256$。而且对于两个不同的 $k_1,k_2$,我们有

$256P-k_1n \not\equiv 256P-k_2n \bmod 256$

我们可以利用反证法来证明上述不等式。同时 $256P-kn$ 的最后一个字节其实就是 $-kn$ 在模 $256$ 的情况下获取的。那么,其实我们可以首先枚举出 $0$~$255 $情况下的最后一个字节,构造一个 k 和最后一个字节的映射表 map

当服务器返回最后一个字节 b,那么我们可以根据上述构造的映射表得知 $k$,即减去了 $k$ 个$N$, 即 $kN \leq 256 P \leq (k+1)N$。

此后,我们使用数学归纳法来获取 P 的范围,即假设在第 i 次时,$\dfrac{xN}{256^{i}} \leq P < \dfrac{xN+N}{256^{i}}$

进一步,在第 i+1 次时,我们可以发送

$C*256^{(i+1)e}$

服务器会计算得到

$256^{i+1}P \bmod N=256^{i+1}P-kN$

$0 \leq 256^{i+1}P-kN<N$

$\dfrac{kN}{256^{i+1}} \leq P < \dfrac{kN+N}{256^{i+1}}$

根据第 $i$ 次的结果

$\dfrac{256xN}{256^{i+1}} \leq P < \dfrac{256xN+256N}{256^{i+1}}$

我们这里可以假设 k=256y+t, 而这里的 t 就是我们可以通过映射表获取的。

$\dfrac{256yN+tN}{256^{i+1}} \leq P < \dfrac{256yN+(t+1)N}{256^{i+1}}$

与此同时,由于 P 必然存在,所以第 i+1 得到的这个范围和第 i 次得到的范围必然存在交集。

所以 y 必然与 x 相等。

进一步我们可以这么归纳,初始情况下

1
2
lb = 0
ub = N

假设服务器返回了 b,那么

1
2
3
4
k = mab[b]
interval = (ub-lb)//256
lb = lb + interval * k
ub = lb + interval

II-关于一些特殊性质的$n$的因数分解

0x01 $n$的值小于$512$位二进制数

​ 可以用yafu或者sagemath直接分解,一般$30$分钟内就可以分解成功

0x02 $p,q$ 是两个相邻的素数

​ 这种方法是非常简单的,我们只需要用gmpy2中的iroot函数直接取整开根。然后设$q$是$\sqrt n$的下一个素数,然后我们就可以得到$p$的值了,进而成功分解$n$

0x03 $|p-q|$过大或者过小的分解

​ $|p-q|$过大的时候,可以直接通过枚举法确定其中一个因数

​ $|p-q|$过小的时候:由基本的平方差公式,有:
$$
\dfrac{(p+q)^2}{4}-n=\dfrac{(p+q)^2}{4}-pq=\dfrac{(p-q)^2}{4}
$$
​ 既然 $|p-q|$较小,那么 $\dfrac{(p-q)^2}{4}$ 自然也比较小,进而 $\dfrac{(p+q)^2}{4}$ 只是比 N 稍微大一点,所以 $\dfrac{p+q}{2}$ 与 $\sqrt{n}$ 相近。

​ 此时我们可以检查$\sqrt n$的每一个整数$x$,知道找到一个$x$使得$x^2-n$是平方数,记作$y^2$。然后根据平方差公式可以分解$n$

0x04 $p-1$光滑(摘自yulige的博客–NCTF2019题解)

0o401 什么是光滑数

​ 首先引入光滑数的定义:若一个数的所有素因子都不超过$B$,那么称这个数为$B$光滑数,例如:由于$72=3^2×2^3$,所有的素因子都不超过$3$,所以$72$是$3$光滑数,当然也是$5,7,11,…$光滑数。

0o402 Pollards $p-1$ 算法

​ 这个时候我们可以使用Pollard’s $p − 1$ 算法来分解 $n$,具体原理如下:

​ 由费马小定理$a^{p-1} – 1 \equiv 0 \mod \ p$可知,$a^{p-1} – 1$ 是 $p$ 的倍数,也就可以认为是$a^{t(p-1)} – 1 =k p$,其中$t,p\in N_+$。因此,简单地观察就可以知道,如果指数$\text{exp}$是 $p-1$ 的倍数,那么$a^\text{exp} – 1 $就会是 $p$ 的倍数。所以,我们只需要找到一个$\text{exp}$使得$a^\text{exp}$是$p$的倍数的时候,那么我们计算$\gcd(a^{\text{exp}},n)$,就可以得到结果,而这个结果就是$p$,所以,这里的关键就是寻找这个合适的$\text{exp}$值。

Pollard的厉害之处就在于此,他发现,如果p-1正好是一些很小的质数的乘积,那么p-1就能整除$n!$,其中$n$是一个不太大的数。假设p-1p1, p2, ..., pk这些质数的乘积,其中最大的质数是pk。那么,很显然pk!=1·2·...·pk肯定包括了p1, p2, ..., pk这些质数的乘积,pk!肯定是p-1的倍数。

​ 也就是说,$n > pk$ 的时候,$n!$很大概率上就能被p-1整除。(考虑到p1, p2, ..., pk中可能有重复的情况)

​ 这导致了Pollard' p-1 method

​ 对于每一个$n = 2, 3, 4, …$,我们任意选择一个底数$a$(事实上,我们可以简单地选择为$2$),并计算
$$
gcd(a^{n!-1}, N)
$$
​ 如果结果落在1和$n$中间,那么我们就成功了。

​ 当然,这里的所有操作都可以在模$N$的操作下进行,也就是计算$a^{n!-1}\ \text{mod}\ N$。并且,我们也不必计算每一个数字,选择一个恰当的间隔(比如$15$)计算可以减少耗时

0o477 代码实现

​ 我们可以上一下代码:这里的的$N$是$104729$光滑的(因为$104729$刚好是第$10000$个素数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
def Pollard_p_1(N):
a = 2
while True:
f = a
# precompute
for i in range(1, 80000):
f = pow(f, i, N)
for i in range(80000, 104729+1):
f = pow(f, i, N)
if i % 15 == 0:
d = GCD(f-1, N)
if 1 < d < N:
return d
print(a)
a += 1

0x05 $p+1$光滑(即$p+1=db^2|_{d<256,\text{isPrime}(d)=\text{True}}$)

​ 这种情况下,我们可以使用William $p+1$算法

0o501 理论基础

​ 从标题中我们可以知道:如果$p+1=db^2$ 的话,我们可以考虑分解$n$的值。而这实际上基于这样一个理论基础:如果$n=pm$,并且$p$是素数,并且如果$4p$可以写成集合{$ 3b^2+1,11b^2+1,19b^2+1,43b^2+1,67b^2+1,163b^2+1$} ,其中${b\in N_+}$ 中的任意一个形式,那么我们可以在$\ln n$的复杂度里找到$p$的真实值。

​ 算法的原理太复杂,这里就不多讲了,直接看代码吧(

0o577 算法代码

​ 最后贴一下代码,$\text{Sagemath 9.1 Notebook}$中的代码,摘自$\text{NCTF 2020 WP}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def qicheng(n: int):
R = Integers(n)
js = [0, (-2 ^ 5) ^ 3, (-2 ^ 5*3) ^ 3, (-2 ^ 5*3*5*11) ^ 3, (-2 ^ 6*3*5*23*29) ^ 3]
p, q = None, None
for _ in range(20):
for j in js:
if j == 0:
a = R.random_element()
E = EllipticCurve([0, a])
else:
a = R(j)/(R(1728)-R(j))
c = R.random_element()
E = EllipticCurve([3*a*c ^ 2, 2*a*c ^ 3])
x = R.random_element()
z = E.division_polynomial(n, x)
g = gcd(z, n)
if g > 1:
p = Integer(g)
q = Integer(n)//p
break
if p:
break
return (p, q)
print(qicheng(1444329727510154393553799612747635457542181563961160832013134005088873165794135221))
#(74611921979343086722526424506387128972933, 19357894679486057806987068960980789709937)

0x06 Pollord Rho算法(时间复杂度$O(\sqrt[4]{n})$)

0o601 算法介绍

​ 这个算法的核心思想就是猜一个数,看看是否为$x$的因数。

​ 我们可以随机地选取两$v,t$个数,然后根据$v=v_{i-1}^2+t \mod x$ ,这样就会构成一个环。然后在循环内部猜测。即可。

​ 代码实现原理也比较复杂(实际上是因为懒,博客写到后面也很累的),自己百度吧。上一个是百度不到的。23333

0o677 代码实现(自己打的代码,Python常数较大,能过洛谷模板题93分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from Crypto.Util.number import *
from random import *
A=0
def culc(x,c,n):
return (x*x+c)%n
def PollardRho(x):
s,t,goal,val=0,0,1,1
c=getrandbits(15)%(x-1)+1
while 1:
for det in range(1,goal+1):
t=culc(t,c,x)
val=val*abs(t-s)%x
if(det%127==0):
d=GCD(val,x)
if(d>1):
return d
d=GCD(val,x)
if(d>1):
return d
goal*=2
s=t
val=1
def factor(x):
global A
if(x<=A or x<2):
return
if(isPrime(x)):
A=max(A,x)
return
p=x
while(p>=x):
p=PollardRho(x)
while((x%p)==0):
x//=p
factor(x)
factor(p)
T=int(input())
while T>0:
T-=1
A=0
a=int(input())
if(isPrime(a)):
print('Prime')
else:
factor(a)
print(A)

RSA Notes 2
http://example.com/2020/11/28/RSA-Notes2/
作者
huangx607087
发布于
2020年11月28日
许可协议