选择明文攻击?

这里给出一个例子，假如我们有一个加密 oracle ，但是我们不知道 n 和 e，那

1. 我们可以通过加密 oracle 获取 n。
2. 在 e 比较小（ e<264e<264）时，我们可以利用 Pollard’s kangaroo algorithm 算法获取 e。这一点比较显然。

我们可以加密 2，4，8，16。那么我们可以知道

c2=2emodnc2=2emodn

c4=4emodnc4=4emodn

c8=8emodnc8=8emodn

那么

c22≡c4modnc22≡c4modn

c32≡c8modnc23≡c8modn

故而

c22?c4=knc22?c4=kn

c32?c8=tnc23?c8=tn

我们可以求出 kn 和 tn 的最大公因数，很大概率就是 n 了。我们还可以构造更多的例子从来更加确定性地找 n。

任意密文解密?

假设爱丽丝创建了密文 C=PemodnC=Pemodn 并且把 C 发送给鲍勃，同时假设我们要对爱丽丝加密后的任意密文解密，而不是只解密 C，那么我们可以拦截 C，并运用下列步骤求出 P：

1. 选择任意的 X∈Z?nX∈Zn?，即 X 与 N 互素
2. 计算 Y=C×XemodnY=C×Xemodn
3. 由于我们可以进行选择密文攻击，那么我们求得 Y 对应的解密结果 Z=YdZ=Yd
4. 那么，由于 Z=Yd=(C×Xe)d=CdX=PedX=PXmodnZ=Yd=(C×Xe)d=CdX=PedX=PXmodn，由于 X 与 N 互素，我们很容易求得相应的逆元，进而可以得到 P

RSA parity oracle?

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

原理?

假设

C=PemodNC=PemodN

第一次时，我们可以给服务器发送

C?2e=(2P)emodNC?2e=(2P)emodN

服务器会计算得到

2PmodN2PmodN

这里

• 2P 是偶数，它的幂次也是偶数。
• N 是奇数，因为它是由两个大素数相乘得到。

那么

• 服务器返回奇数，即 2PmodN2PmodN 为奇数，则说明 2P 大于 N，且减去了奇数个 N，又因为 2P<2N2P<2N，因此减去了一个 N， 即 N2≤P<NN2≤P<N，我们还可以考虑向下取整。
• 服务器返回偶数，则说明 2P 小于 N。即 0≤P<N20≤P<N2，我们还可以向下取整。

这里我们使用数学归纳法，即假设在第 i 次时，xN2i≤P<xN+N2ixN2i≤P<xN+N2i

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

C?2(i+1)eC?2(i+1)e

服务器会计算得到

2i+1PmodN=2i+1P?kN2i+1PmodN=2i+1P?kN

0≤2i+1P?kN<N0≤2i+1P?kN<N

kN2i+1≤P<kN+N2i+1kN2i+1≤P<kN+N2i+1

根据第 i 次的结果

2xN2i+1≤P<2xN+2N2i+12xN2i+1≤P<2xN+2N2i+1

那么

• 服务器返回奇数，则 k 必然是一个奇数，k=2y+1， 那么 2yN+N2i+1≤P<2yN+2N2i+12yN+N2i+1≤P<2yN+2N2i+1。与此同时，由于 P 必然存在，所以第 i+1 得到的这个范围和第 i 次得到的范围必然存在交集。所以 y 必然与 x 相等。
• 服务器返回偶数，则 k 必然是一个偶数，k=2y，此时 y 必然也与 x 相等，那么 2xN2i+1≤P<2xN+N2i+12xN2i+1≤P<2xN+N2i+1

进一步我们可以这么归纳

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

这里虽然是整除， 即下取整，但是无所谓我们在最初时已经分析了这个问题。

2018 Google CTF Perfect Secrecy?

这里以 2018 年 Google CTF 的题目为例进行分析

#!/usr/bin/env python3
import sys
import random

from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.backends import default_backend


def ReadPrivateKey(filename):
  return serialization.load_pem_private_key(
      open(filename, 'rb').read(), password=None, backend=default_backend())


def RsaDecrypt(private_key, ciphertext):
  assert (len(ciphertext) <=
          (private_key.public_key().key_size // 8)), 'Ciphertext too large'
  return pow(
      int.from_bytes(ciphertext, 'big'),
      private_key.private_numbers().d,
      private_key.public_key().public_numbers().n)


def Challenge(private_key, reader, writer):
  try:
    m0 = reader.read(1)
    m1 = reader.read(1)
    ciphertext = reader.read(private_key.public_key().key_size // 8)
    dice = RsaDecrypt(private_key, ciphertext)
    for rounds in range(100):
      p = [m0, m1][dice & 1]
      k = random.randint(0, 2)
      c = (ord(p) + k) % 2
      writer.write(bytes((c,)))
    writer.flush()
    return 0

  except Exception as e:
    return 1


def main():
  private_key = ReadPrivateKey(sys.argv[1])
  return Challenge(private_key, sys.stdin.buffer, sys.stdout.buffer)


if __name__ == '__main__':
  sys.exit(main())

可以看出

• 我们可以给服务器两个数，服务器会根据解密后的密文内容来决定使用哪一个。
• 服务器会使用 random.randint(0, 2) 来生成随机数，并输出相关的随机 01 字节 c。

乍一看，似乎是完全随机的，仔细查一下 random.randint(0, 2) 可以知道其生成随机数是包括边界的，因此其生成偶数的概率大于生成奇数的概率，那么 c 与 p 同奇偶的概率为 ?。进而我们通过设置 m0 和 m1 就可以知道解密后的密文的最后一位是 0 还是 1 。这其实就是 RSA parity oracle。

exp 如下

import gmpy2
from pwn import *
encflag = open('./flag.txt').read()
encflag = encflag.encode('hex')
encflag = int(encflag, 16)
#context.log_level = 'debug'
m = ['\x00', '\x07']
n = 0xDA53A899D5573091AF6CC9C9A9FC315F76402C8970BBB1986BFE8E29CED12D0ADF61B21D6C281CCBF2EFED79AA7DD23A2776B03503B1AF354E35BF58C91DB7D7C62F6B92C918C90B68859C77CAE9FDB314F82490A0D6B50C5DC85F5C92A6FDF19716AC8451EFE8BBDF488AE098A7C76ADD2599F2CA642073AFA20D143AF403D1
e = 65537
flag = ""



def guessvalue(cnt):
    if cnt[0] > cnt[1]:
        return 0
    return 1


i = 0
while True:
    cnt = dict()
    cnt[0] = cnt[1] = 0
    p = remote('perfect-secrecy.ctfcompetition.com', 1337)
    p.send(m[0])
    p.send(m[1])
    tmp = pow(2, i)
    two_inv = gmpy2.invert(tmp, n)
    two_cipher = gmpy2.powmod(two_inv, e, n)
    tmp = encflag * two_cipher % n
    tmp = hex(tmp)[2:].strip('L')
    tmp = '0' * (256 - len(tmp)) + tmp
    tmp = tmp.decode('hex')
    assert (len(tmp) == 128)
    p.send(tmp)
    #print tmp
    data = ""
    while (len(data) != 100):
        data += p.recv()
    for c in data:
        cnt[u8(c)] += 1
    p.close()
    flag = str(guessvalue(cnt)) + flag
    print i, flag
    i += 1

结果如下

6533021797450432625003726192285181680054061843303961161444459679874621880787893445342698029728203298974356255732086344166897556918532195998159983477294838449903429031335408290610431938507208444225296242342845578895553611385588996615744823221415296689514934439749745119968629875229882861818946483594948270 6533021797450432625003726192285181680054061843303961161444459679874621880787893445342698029728203298974356255732086344166897556918532195998159983477294838449903429031335408290610431938507208444225296242342845578895553611385588996615744823221415296689514934439749745119968629875229882861818946483594948270

解码后就可以得到 flag

CTF{h3ll0__17_5_m3_1_w45_w0nd3r1n6_1f_4f73r_4ll_7h353_y34r5_y0u_d_l1k3_70_m337}

题目?

• 2016 Plaid CTF rabit
• 2016 sharif CTF lsb-oracle-150
• 2018 Backdoor CTF BIT-LEAKER
• 2018 XMAN 选拔赛 baby RSA

RSA Byte Oracle?

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

原理?

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

假设

C=PemodNC=PemodN

第一次时，我们可以给服务器发送

C?256e=(256P)emodNC?256e=(256P)emodN

服务器会计算得到

256PmodN256PmodN

这里

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

由于 P 一般是小于 N 的，那么256PmodN=256P?kn,k<256256PmodN=256P?kn,k<256。而且对于两个不同的 k1,k2k1,k2，我们有

256P?k1n≡?256P?k2nmod256256P?k1n?256P?k2nmod256

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

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

此后，我们使用数学归纳法来获取 P 的范围，即假设在第 i 次时，xN256i≤P<xN+N256ixN256i≤P<xN+N256i

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

C?256(i+1)eC?256(i+1)e

服务器会计算得到

256i+1PmodN=256i+1P?kN256i+1PmodN=256i+1P?kN

0≤256i+1P?kN<N0≤256i+1P?kN<N

kN256i+1≤P<kN+N256i+1kN256i+1≤P<kN+N256i+1

根据第 i 次的结果

256xN256i+1≤P<256xN+256N256i+1256xN256i+1≤P<256xN+256N256i+1

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

256yN+tN256i+1≤P<256yN+(t+1)N256i+1256yN+tN256i+1≤P<256yN+(t+1)N256i+1

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

所以 y 必然与 x 相等。

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

lb = 0
ub = N

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

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

2018 HITCON lost key?

这是一个综合题目，首先没有给出 n，我们可以使用选择明文攻击的方式获取 n，当然我们也可以进一步获取 e，最后利用代码如下

from pwn import *
import gmpy2
from fractions import Fraction
p = process('./rsa.py')
#p = remote('18.179.251.168', 21700)
#context.log_level = 'debug'
p.recvuntil('Here is the flag!\n')
flagcipher = int(p.recvuntil('\n', drop=True), 16)


def long_to_hex(n):
    s = hex(n)[2:].rstrip('L')
    if len(s) % 2: s = '0' + s
    return s


def send(ch, num):
    p.sendlineafter('cmd: ', ch)
    p.sendlineafter('input: ', long_to_hex(num))
    data = p.recvuntil('\n')
    return int(data, 16)


if __name__ == "__main__":
    # get n
    cipher2 = send('A', 2)
    cipher4 = send('A', 4)
    nset = []
    nset.append(cipher2 * cipher2 - cipher4)

    cipher3 = send('A', 3)
    cipher9 = send('A', 9)
    nset.append(cipher3 * cipher3 - cipher9)
    cipher5 = send('A', 5)
    cipher25 = send('A', 25)
    nset.append(cipher5 * cipher5 - cipher25)
    n = nset[0]
    for item in nset:
        n = gmpy2.gcd(item, n)

    # get map between k and return byte
    submap = {}
    for i in range(0, 256):
        submap[-n * i % 256] = i

    # get cipher256
    cipher256 = send('A', 256)

    back = flagcipher

    L = Fraction(0, 1)
    R = Fraction(1, 1)
    for i in range(128):
        print i
        flagcipher = flagcipher * cipher256 % n
        b = send('B', flagcipher)
        k = submap[b]
        L, R = L + (R - L) * Fraction(k, 256
                                     ), L + (R - L) * Fraction(k + 1, 256)
    low = int(L * n)
    print long_to_hex(low - low % 256 + send('B', back)).decode('hex')

RSA parity oracle variant?

原理?

如果 oracle 的参数会在一定时间、运行周期后改变，或者网络不稳定导致会话断开、重置，二分法就不再适用了，为了减少错误，应当考虑逐位恢复。 要恢复明文的第 2 低位，考虑

{(c(2?1?e1modN1))d1modN1}(mod2)≡m?2?1{(c(2?1?e1modN1))d1modN1}(mod2)≡m?2?1

m?(2?1modN1)mod2=(logm?1∑i=0ai?2i)?2?1mod2=[2(logm?1∑i=1ai?2i?1)+a0?20]?2?1mod2=logm?1∑i=1ai?2i?1+a0?20?2?1mod2≡a1+a0?20?2?1≡y(mod2)m?(2?1modN1)mod2=(∑i=0logm?1ai?2i)?2?1mod2=[2(∑i=1logm?1ai?2i?1)+a0?20]?2?1mod2=∑i=1logm?1ai?2i?1+a0?20?2?1mod2≡a1+a0?20?2?1≡y(mod2)

y?(a0?20)?2?1=(m?2?1mod2)?(a0?20)?2?1≡a1(mod2)y?(a0?20)?2?1=(m?2?1mod2)?(a0?20)?2?1≡a1(mod2)

类似的

{(c(2?2?e2modN2))d2modN2}(mod2)≡m?2?2{(c(2?2?e2modN2))d2modN2}(mod2)≡m?2?2

m?(2?2modN2)mod2=(logm?1∑i=0ai?2i)?2?2mod2=[22(logm?1∑i=2ai?2i?2)+a1?21+a0?20]?2?2mod2=logm?1∑i=2ai?2i?1+(a1?21+a0?20)?2?2mod2≡a2+(a1?21+a0?20)?2?2≡y(mod2)m?(2?2modN2)mod2=(∑i=0logm?1ai?2i)?2?2mod2=[22(∑i=2logm?1ai?2i?2)+a1?21+a0?20]?2?2mod2=∑i=2logm?1ai?2i?1+(a1?21+a0?20)?2?2mod2≡a2+(a1?21+a0?20)?2?2≡y(mod2)

y?(a1?21+a0?20)?2?2=(m?2?2mod2)?(a1?21+a0?20)?2?2≡a2(mod2)y?(a1?21+a0?20)?2?2=(m?2?2mod2)?(a1?21+a0?20)?2?2≡a2(mod2)

我们就可以使用前 i-1 位与 oracle 的结果来得到第 i 位。注意这里的2?12?1 是2121 模N1N1 的逆元。所以对剩下的位，有

{(c(2?i?eimodNi))dimodNi}(mod2)≡m?2?iai≡(m?2?imod2)?i?1∑j=0aj?2j(mod2),i=1,2,...,logm?1{(c(2?i?eimodNi))dimodNi}(mod2)≡m?2?iai≡(m?2?imod2)?∑j=0i?1aj?2j(mod2),i=1,2,...,logm?1

其中2?i2?i 是2i2i 模NiNi 的逆元。

就可以逐步恢复原文所有的位信息了。这样的时间复杂度为O(logm)O(logm)。

exp:

from Crypto.Util.number import *
mm = bytes_to_long(b'12345678')
l = len(bin(mm)) - 2

def genkey():
    while 1:
        p = getPrime(128)
        q = getPrime(128)
        e = getPrime(32)
        n = p * q
        phi = (p - 1) * (q - 1)
        if GCD(e, phi) > 1:
            continue
        d = inverse(e, phi)
        return e, d, n

e, d, n = genkey()
cc = pow(mm, e, n)
f = str(pow(cc, d, n) % 2)

for i in range(1, l):
    e, d, n = genkey()
    cc = pow(mm, e, n)
    ss = inverse(2**i, n)
    cs = (cc * pow(ss, e, n)) % n
    lb = pow(cs, d, n) % 2
    bb = (lb - (int(f, 2) * ss % n)) % 2
    f = str(bb) + f
    assert(((mm >> i) % 2) == bb)
print(long_to_bytes(int(f, 2)))