RSA LSB Oracle Attack

Posted by JHSN on April 18, 2018

预备知识:同余数论基础

RSA 简介

一开始我们选择了两个素数 $p, q$,然后我们就有了 $n=pq$,因为 $p,q$ 互质,所以我们有

再由欧拉定理可得

选择一个数 $e$,当满足 $\gcd(e, \varphi(n)) = 1$ 时,由裴蜀定理 / 贝祖等式可知,存在正整数 $d$ 满足

选择一个数 m,令 $c \equiv m^e \pmod{n}$,则有

简而言之,选定 $p,q,e,m$,你将得到 $n,d,c$ 满足

综上所述,RSA 的密码学意义:$m$ 为明文,$c$ 为密文,$n,e$ 为公钥,$n,d$ 为私钥。加密即为 $m^e$ % $n$,解密即为 $c^d$ % $n$。形式看似非常简单的 RSA 系统其实有着很深的数学涵义,从数的结合上来看,$p,q$ 相乘奠定了 RSA 的基础;从数的层次上来看,底数与幂次两个层次上的一些奇妙性质相合构成了 RSA。

RSA LSB Oracle Attack

已知 $n,e,c$,以及一个函数 lsb_oracle(x):返回 $x^d$ % $n$ % $2$,求 $m$。RSA LSB Oracle Attack 意即为利用对密文解密结果最低位的奇偶校验进行攻击。如何攻击呢?

考虑二分答案,显然 $m \in [0, n)$,$n$ 为奇数。

  • 若 $m\in [0, \frac{n}{2})$,则 $2m\in [0, n)$,则有 2m % n % 2 = 2m % 2 = 0
  • 若 $m\in [\frac{n}{2}, n)$,则 $2m\in [n, 2n)$,则有 2m % n % 2 = (2m - n) % 2 = 1

若 $m\in [0, \frac{n}{2})$

  • 若 $m\in [0, \frac{n}{4})$,则 $4m\in [0, n)$,则有 4m % n % 2 = 4m % 2 = 0
  • 若 $m\in [\frac{n}{4}, \frac{n}{2})$,则 $4m\in [n, 2n)$,则有 4m % n % 2 = (4m - n) % 2 = 1

若 $m\in [\frac{n}{2}, n)$

  • 若 $m\in [\frac{n}{2}, \frac{3n}{4})$,则 $4m\in [2n, 3n)$,则有 4m % n % 2 = (4m - 2n) % 2 = 0
  • 若 $m\in [\frac{3n}{4}, n)$,则 $4m\in [3n, 4n)$,则有 4m % n % 2 = (4m - 3n) % 2 = 1

若 $m \in [L,R)$,$R-L = 2^{-k}n$,令 $M = \frac{L+R}{2}n$,则有

$m$ $2^{k+1}m$ $2^{k+1} m$ % $n$ 奇偶性
$[L, M)$ $[2^{k+1}L,2^{k+1}L+n)$ $2^{k+1} m - 2^{k+1}L$
$[M, R)$ $[2^{k+1}L+n, 2^{k+1}L+2n]$ $2^{k+1} m - 2^{k+1}L - n$

所以直接按照奇偶即可判定是左区间还是右区间即可。因为小数计算不精确,所以在具体实现的时候保存了分子和分母进行计算,并在区间内的整数少于 3 个时直接退出进行 check。

Code:

def lsb_oracle_attack(n, e, c, lsb_oracle):
    '''
    RSA LSB Oracle Attack
    :param lsb_oracle: lsb_oracle(x) == pow(x, d, n) % 2
    :return: m or None if not found
    '''
    l, r, k2 = 0, 1, 1
    while n * l // k2 + 1 < n * r // k2:
        m = l + r
        l <<= 1
        r <<= 1
        k2 <<= 1
        if lsb_oracle(c * pow(k2, e, n) % n) == 1:
            l = m
        else:
            r = m
    m = n * l // k2
    if pow(m, e, n) == c:
        return m
    m = n * r // k2
    if pow(m, e, n) == c:
        return m
    return None

完整测试代码:https://gist.github.com/Chrstm/fe25e02c9620cf2e8e2c5854b96dc5dd




评论区加载中