CTF中的RSA基本套路(2)

第二部分主要是一些Oracle相关的内容

依赖库：

• gmpy2
• pycrypto
• pwntools
• sage

选择密文攻击#

场景#

假设$Alice$创建密文$C=P^e \mod n$，并发送给$Bob$，并且我们有一次选择密文进行解密的机会，此时我们可以拦截$C$，并通过选择密文攻击，求出$P$

解法#

1. 选择任意一个$G(n)$内与$n$互素的$X$(一般就是2啦)
2. 计算$Y=C \times X^e \mod n$
3. 由于选择密文攻击，将$Y$作为密文我们可以得到$Z=Y^d \mod n $
4. 最后由于
   
   可以通过逆元求出$P$

from pwn import *
from gmpy2 import invert
from Crypto.Util.number import long_to_bytes
p = remote(ip,port)
C = 
n = 
e = 
X = 2
X_e = pow（X,e,n)
p.sendline(str((X_e*c)%n)
Z = int(p.recvline())
result = (Z*long(invert(X,n)))%n
print(long_to_bytes(result))

parity oracle#

场景#

假设存在一个 $Oracle$，它会对一个给定的密文进行解密，并且会检查解密的明文的奇偶性，并根据奇偶性返回相应的值，比如 1 表示奇数，0 表示偶数。那么给定一个加密后的密文，我们只需要 $log(N)$ 次就可以知道这个密文对应的明文消息

解法#

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

第一次我们发送$C\times 2^e = (2P)^e \mod N$给服务器，服务器会返回$2P\mod N$

我们知道：

• $2P$是偶数，因此$(2P)^e$也是偶数
• $N$是奇数（不考虑存在因子为2时）

那么：

• 服务器返回奇数时，说明$2P>N$，且减去了奇数个$N$同时我们又知道$P<N$，即$N/2 \leq P < N$
• 服务器返回偶数时，说明$0\leq P < N/2$

归纳：

假设第$i$次时，我们有

$$xN/2^i \leq P < (x+1)N/2^i$$

在第$i+1$次时，我们可以得到

$$2^{i+1}P\mod N=2^{i+1}P-kN$$

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

$$kN/2^{i+1} \leq P < (k+1)N/2^{i+1}$$

根据第$i$次结果我们分子分母同乘2，有

$$2xN/2^{i+1} \leq P < 2(x+1)N/2^{i+1}$$

那么：

• 服务器返回奇数，则$ k$ 必然是一个奇数，$k=2y+1$， 那么 $(2 y N+N) / 2^{i+1} \leq P<(2 y N+2 N) / 2^{i+1}$。与此同时，由于 $P$ 必然存在，所以第 $i+1$ 得到的这个范围和第$ i$ 次得到的范围必然存在交集。所以$ y$ 必然与$ x $相等。
• 服务器返回偶数，则$ k$ 必然是一个偶数，$k=2y$，此时 $y $必然也与 $x $相等，那么$2 x N / 2^{i+1} \leq P<(2 x N+N) / 2^{i+1}$

总结：

lb = 0
ub = N
if server returns 1
    lb = (lb+ub)/2
else:
    ub = (lb+ub)/2

from pwn import *
import time,decimal,binascii
from Crypto.Util.number import long_to_bytes

p = remote(ip,port)

def oracle(c1):
    global p
    p.sendline(str(c1))
    res = int(p.recvuntil("\n").strip())
    if res == 0: return 0
    if res == 1:
        return 1
    else:
        assert (0)


def partial(c, n):
    global c_of_2
    k = n.bit_length()
    decimal.getcontext().prec = k  
    lower = decimal.Decimal(0)
    upper = decimal.Decimal(n)
    for i in range(k):
        possible_plaintext = (lower + upper) / 2
        flag = oracle(c)
        if not flag:
            upper = possible_plaintext  
        else:
            lower = possible_plaintext 
        c = (c * c_of_2) % n  
        print(i,flag,int(upper - lower))
    return int(upper) 
  
e = 
c = 
n = 
c_of_2 = pow(2,e,n)
m = partial((c * c_of_2) % n, n)
print(long_to_bytes(m))

byte oracle#

场景#

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

解法#

是parity oracle的扩展，此时泄露一个byte，因此我们将原来的发送$C\times 2^e$改成$C\times 256 ^e$即可

已知

$$C=P^e \mod N$$

第一次我们发送

$$C\times 256^e = (256P)^e \mod N$$

服务器返回$256P \mod N$

此时有：

• $256P$为偶数
• $N$为奇数

由于$P<N$,我们有$256P \mod N=256P -kN(k<256)$，并且对于不同的$k_1，k_2$,我们有$256P-k_1 n \not\equiv 256P-k_2 n \mod 256$

由于是模$256$，所以$256P-kn \equiv -kn \mod 256$，因此我们首先可以枚举$0-255$情况下的最后一个字节，并得到映射表

当服务器返回最后一个字节b，我们就可以通过映射表得到$k$，即减去了$k$个$N$，有$kN \leq 256P \leq (k+1)N$

归纳：

假设在第$i$次时，有

$$xN/256^i \leq P < (x+1)N/256^i$$

当第$i+1$次时，发送$C*256^{(i+1)e}$，服务器返回

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

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

$$kN/256^{i+1}\leq P<256(x+1)N/256^{i+1}$$

总结：

lb = 0
ub = N
k = mab[b]
interval = (ub-lb)/256
lb = lb + interval * k
ub = lb + interval

from pwn import *
import time
import binascii
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from gmpy2 import invert
p = remote(ip,port)
e =
c = 
n = 
print("e:",e)
print("c:",c)
print("n:",n)
d = {}
for k in range(0,256):
    d[(-k*n)%256] = k
print(d)
lb = 0
ub = n
for i in range(1,256):
    m = (c * pow(256,i*e,n)) %n
    p.sendline(str(m))
    b = int(p.recvline())
    k = d[b]
    interval = int((ub-lb)/256)
    lb = lb + interval * k
    ub = lb + interval
    print("ub-lb:",ub-lb)
print("lb:",lb)
print("ub:",ub)
i = lb
# 没控制好边界，所以最后暴力一段
while(i<=lb+30000):
    m = pow(i,e,n)
    if(m==c):
        print("result:",i)
        p.sendline(str(i))
        print(p.recvline())
        exit(0)
    i+=1
print("no result")

d泄露攻击#

场景#

题目同时给出了$d$、$e$和$N$

解法#

我们知道$ed \equiv 1\mod \varphi(n)$，则存在$k$，使得

$$ed-1 = k \varphi(n)$$

又有$\forall a \in Z^{*}_n $，满足$a^{ed-1} \equiv 1 \mod n$，令

$$ed-1 = 2^s t$$

其中，$t$是一奇数，可以证明对于至少一半的$\forall a \in Z^{*}_n $，存在一个$i \in [1,s]$，使得

成立，如果$a,i$满足上述条件，可以对$n$进行暴力分解

import fractions,random

def factor_modulus(n, d, e):
    """
    Efficiently recover non-trivial factors of n
    See: Handbook of Applied Cryptography
    8.2.2 Security of RSA -> (i) Relation to factoring (p.287)
    http://www.cacr.math.uwaterloo.ca/hac/
    """
    t = (e * d - 1)
    s = 0

    while True:
        quotient, remainder = divmod(t, 2)

        if remainder != 0:
            break

        s += 1
        t = quotient

    found = False

    while not found:
        i = 1
        a = random.randint(1,n-1)

        while i <= s and not found:
            c1 = pow(a, pow(2, i-1, n) * t, n)
            c2 = pow(a, pow(2, i, n) * t, n)

            found = c1 != 1 and c1 != (-1 % n) and c2 == 1

            i += 1

    p = fractions.gcd(c1-1, n)
    q = n // p

    return p, q

n多因子#

场景#

当$n$由多个因子组成时

解法#

多个因子时，我们根据欧拉函数求得对应的$\varphi(n)$即可

$$\varphi(x)=x\prod_{i=1}^n (1-1/p_i)$$

其中$p_i$是$x$的所有质因数

选择明文攻击#

场景#

存在一个加密$Oracle$，能够返回加密后的密文。求出对应的$e$和$n$

解法#

求解e#

当$e$较小时，可以通过$sage$的$bsgs$函数求得$e$

# sage -python script.py
from sage.all import *
n = 
n = Zmod(n)
m = 
m = ZmodN(m)
c = 
c = ZmodN(c)
print(bsgs(m,c,(3, 2 ** 40)))

求解n#

分别加密$2、4、8、16…$

我们可以得到：

$$c_2 = 2^e \mod n$$

$$c_4 = 4^e \mod n$$

$$c_8 = 8^e \mod n$$

那么：

$$c_2^2 \equiv c_4 \mod n$$

$$c_2^3 \equiv c_8 \mod n$$

所以有：

$$c_2^2 -c_4 = kn$$

$$c_2^3 -c_8 = tn$$

最后求得他们的公因子就是$n$，使用的$Oracle$数据越多，公因子是$n$的概率越大

from pwm import *
import libnum
p = remote(ip,port)

p.recvuntil("m: ")
p.sendline("2")
c2 = int(p.recvline())

p.recvuntil("m: ")
p.sendline("4")
c4 = int(p.recvline())

p.recvuntil("m: ")
p.sendline("8")
c8 = int(p.recvline())

p.recvuntil("m: ")
p.sendline("16")
c16 = int(p.recvline())

p.recvuntil("m: ")
p.sendline("32")
c32 = int(p.recvline())

pn = pow(c2,2)-c4
qn = pow(c2,3)-c8
rn = pow(c2,4)-c16
sn = pow(c2,5)-c32

l = []
n = libnum.xgcd(pn,qn)[2]
l.append(n)
n = libnum.xgcd(pn,rn)[2]
l.append(n)
n = libnum.xgcd(pn,sn)[2]
l.append(n)
n = libnum.xgcd(qn,rn)[2]
l.append(n)
n = libnum.xgcd(qn,sn)[2]
l.append(n)
n = libnum.xgcd(rn,sn)[2]
l.append(n)
n = 0
for _ in l:
    if(l.count(_)>=3):
        n = _
if(n==0):
    print("nope")
    exit(0)
else:
    print("n:",n)

参考文献#

• https://github.com/ctf-wiki/ctf-wik
• https://code.felinae98.cn/ctf/crypto/rsa-parity-oracle/
• https://xz.aliyun.com/t/2446
• https://github.com/ius/rsatool/blob/master/rsatool.py