泄露
from Crypto.Util.number import *
def decrypt(c,dp,dq,p,q):
mp = pow(c,dp,p)
mq = pow(c,dq,q)
# CRT
a = inverse(p,q)
b = inverse(q,p)
m = (mp*p*a + mq*q*b) % (p*q)
return m
泄露
def rsa_nedp(n,e,dp):
for i in range(1,e):
if (dp*e-1) % i == 0:
tmp = (((dp*e-1)//i) + 1)
if n % tmp == 0:
p = tmp
q = n // p
return p,q
RSA LSB Oracle Attack
注：类似 2 % 3 = 2 是偶数，而 4 % 3 = 1 由于 ，取模后奇偶性会发生翻转而变为奇数。以此类推，构造密文 使其解密后为 ，判断 的奇偶性可以知道 和 （或 ） 的大小关系。于是我们就有了一个二分算法，可以在对数时间内将 的范围逼近到一个足够狭窄的空间。
def oracle(c):
'''
c: ciphertext
rev: last bit of plaintext
'''
sh.recvuntil(">")
sh.sendline(str(c))
rev = sh.recvuntil("n")[:-1]
return int(rev)
def lsb_oracle_attck(c,n,t):
L=0
H=n
for i in range(1024):
c = (t*c) % n
if oracle(c) == 0:
H = (L+H) // 2
else:
L = (L+H) // 2
return long_to_bytes(L)
lsb_oracle_attck(c, n, pow(2,e,n))
def lsb_oracle_attack(encrypted_flag, n, e):
flag_count = n_count = 1
flag_lower_bound = 0
flag_upper_bound = n
ciphertext = encrypted_flag
mult = 1
while flag_upper_bound > flag_lower_bound + 1:
ciphertext = (ciphertext * pow(2, e, n)) % n
flag_count *= 2
n_count = n_count * 2 - 1
print("bit = %d" % mult)
mult += 1
data=oracle(str(ciphertext))
if(data==1):
flag_upper_bound = n * n_count // flag_count
else:
flag_lower_bound = n * n_count // flag_count
n_count += 1
return flag_upper_bound
Bleichenbacher’s attack（Chosen Ciphertext Attacks）
PKCSv1.5 填充方案
攻击方案
-
第一阶段 Blinding 给到一个整数 ，随机选取整数 ，通过 oracle 去确认，当 满足 PKCS conforming的时候，我们设定 -
第二阶段 Searching for PKCS conforming message a. Starting the search. 如果 ，我们开始寻找最小的 使得 是 PKCS conforming
b. Searching with more than one interval left. 如果，并且 中的区间数量大于 1，那么继续寻找最小的 使得 是 PKCS conforming
c. Searching with one interval left. 如果 只包含一个区间（即 ），那么从小开始选取 ，其中
直到 是 PKCS conforming -
第三阶段 Narrowing the set of solutions 当找到 后，我们开始计算新的 :
-
第四阶段 computing the solution. 如果 只包含一个长度为 1 的区间（即 ，那么我们就有 ，否则 ，继续回到第二阶段。
注：
1. 在第一阶段中，因为 c 解密后本身就是 PKCS conforming 所以可以跳过这个阶段，然后设置 $s_0 = 1$。
2. 在 2.a 中，我们从 $s_1 = lceil n / 3B rceil$ 开始寻找，因为不可能存在小于该值的 $s_1$ 满足 $m_0s_1$ 符合 PKCS conforming。可以简单计算一下，要使 $m_0s_1$ 满足 PKCS conforming，其中 $s_1 ne 1$，必须要被 n 取余过，也就是 $m_0 s_1 gt n$，因为 $m0 in [2B,3B]$，所以 $s_1 gt frac{n}{m_0} ge frac{n}{3B}$
3. 在 2.c 中 $r_i$ 的选取是因为我们想让新的区间大小为原来一半，（$r_i$ 为原来两倍的时候，$s_i$ 也会为原来两倍左右，而间隔大约为 $B/s_i$）类似于二分法
4. 在第三阶段中，区间边界的选取是在取一个交集，我们根据 $s_i$ 算出来的区间为 $left [ left lceil frac{2B+rn}{s_i} right rceil,left lfloor frac{3B-1+rn}{s_i}) right rfloor right ]$，因为
对于下面 的选取，是需要保证新区间和原来的区间有交集，即新区间的上界要大于原来区间的下界，新区间的下届要小于原来区间的上界
如果在第三阶段中有多个满足条件的 r 值，则 中就会产生多个没有交集的区间，但只有其中一个区间是包含 的，此时进入2.b，另外的无效区间，会在增大 的过程中，由于选取不到合适的 r 值（即 ）而被丢弃。那些无效区间中的值 是和 选取了同样，但是在不同 值下也满足 PKCS conforming，可以说是碰巧，所以解决这种碰巧的方式就是继续增加 ，取这些碰巧区间的交集，他们迟早会是一个空集。当没有碰巧区间的时候，我们就可以进行加速，将剩下的区间进行二分。可以理解为在剩下区间中选一个大小为原来一半的区间，然后查验里面是不是包含 ，显然这样的概率相对来说是很高的，所以到后面的阶段我们选取的 使得 是 PKCS conforming 的可能性也很大。
def Bleichenbachers_attack(e,n,c0,s1):
print("step 1")
e = e
n = n
c = c0
k = 64
B = 2**(8*(k-2))
Mi = set([(2 * B, 3 * B - 1)])
si = 1
count = 1
while True:
print("step 2")
si_1 = si
Mi_1 = Mi
if count == 1:
print("step 2.a")
si = s1
while True:
ans = inter(si)
if ans:
print(si)
break
si+=1
elif len(Mi_1)>1:
print("step 2.b")
si = si_1 + 1
while True:
ans = inter(si)
if ans:
break
si += 1
else:
print("step 2.c")
a = list(Mi_1)[0][0]
b = list(Mi_1)[0][1]
ri = ((b * si_1 - 2 * B) // n) * 2
FLAG = True
while FLAG:
si = (2 * B + ri * n) // b
si_max = (3 * B + ri * n) // a
while si <= si_max:
ans = inter(si)
if ans:
FLAG = False
break
si += 1
ri+=1
Mi = set()
print("step 3")
for a,b in Mi_1:
r = (a * si - 3 * B + 1)// n
r += 1 if ((a * si - 3 * B + 1) % n > 0) else 0
r_max = (b * si - 2 * B) // n
while r <= r_max:
MIN = (2*B+r*n)//si
MIN += 1 if (2*B+r*n) % si > 0 else 0
MIN = max(a,MIN)
MAX = ((((3*B)-1)+(r*n))//si)
MAX = min(b,MAX)
Mi.add((MIN,MAX))
r+=1
print(Mi)
if len(Mi)==1:
print("step 4")
a = list(Mi)[0][0]
b = list(Mi)[0][1]
print('a-b:',a-b)
if a == b:
global TIMES
print(TIMES)
message = long_to_bytes(a)
print(message)
return message
count += 1
小结
原文始发于微信公众号（山石网科安全技术研究院）：RSA专题——泄露与攻击
