区块链中的数学 - RSA的共模攻击

写在前面

上一节介绍了RSA的选择密文攻击，这一节我们继续说RSA的共模攻击方法。 阅读本文的基础依然是RSA原理，不了解的回头看看。

共模攻击

假设有两个RSA实例，公钥为（n,$e_1$）,(n,$e_2$), $e_1$,$e_2$互质 这两个实例的特点是模n是相同的，这样的情况叫做共模。

共模攻击是怎么回事呢？

假设我们拦截到上述两个密钥加密的密文$c_1,c_2$,分别是用（n,$e_1$）,(n,$e_2$)加密的。这个时候可以不用去求解对应的私钥d，直接解出加密前的明文m。

我们来看下具体过程： 由于 $e_1,e_2$ 互质（e一般选取是质数）

即

gcd($e_1,e_2$)=1

可得：

$re_1 + se_2 = 1$ [注：这是贝祖定理，之前欧拉定理文章提到过]。

式中，s1、s2皆为整数，但是一正一负。通过扩展欧几里德算法，我们可以得到该式子的一组解（r,s），假设r为正数,s为负数.

因为

$c1=m^{e_1}\ mod\ n$ $c2=m^{e_2}\ mmod\ n$

所以

$(c_1^r c_2^s)mod\ n = ((m^{e_1}modn)^r (m^{e_2}modn)^s)\ mod\ n$

根据模运算性质，可以简化为

$(c_1^r * c_2^s)\ mod\ n =(m^{(e_1r+e_2s)})\ mod\ n = m$

上式利用了 $re_1 + se_2 = 1$。

这样就可以在不知道$（n,e_1）,(n,e_2)$对应的私钥$d_1,d_2$的情况下，得到原始消息M。

代码操练：

纸上得来终觉浅，绝知此事要躬行！

下面用Java代码演示上述过程。

// BigInteger type 扩展欧几里得算法
public BigInteger[] gcdExt(BigInteger a, BigInteger b) {
    BigInteger ans;
    BigInteger[] tuple = new BigInteger[3];
    if (b.compareTo(new BigInteger("0")) == 0) {
      tuple[0] = a;
      //tuple[1] = 1;
      tuple[1] = new BigInteger("1");
      tuple[2] = new BigInteger("0");
      return tuple;
    }
    BigInteger[] temp = gcdExt(b, a.remainder(b));
    ans = temp[0];
    tuple[0] = ans;
    tuple[1] = temp[2];
    tuple[2] = temp[1].subtract(a.divide(b).multiply(temp[2]));
    return tuple;
  }

public void commonModularAttack() {
    BigInteger n = new BigInteger(
        "116547141139745534253172934123407786743246513874292261984447028928003798881819567221547298751255790928878194794155722543477883428672342894945552668904410126460402501558930911637857436926624838677630868157884406020858164140754510239986466552869866296144106255873879659676368694043769795604582888907403261286211");
    BigInteger c1 = new BigInteger(
        "78552378607874335972488545767374401332953345586323262531477516680347117293352843468592985447836452620945707838830990843415342047337735534418287912723395148814463617627398248738969202758950481027762126608368555442533803610260859075919831387641824493902538796161102236794716963153162784732179636344267189394853");
    BigInteger c2 = new BigInteger(
        "98790462909782651815146615208104450165337326951856608832305081731255876886710141821823912122797166057063387122774480296375186739026132806230834774921466445172852604926204802577270611302881214045975455878277660638731607530487289267225666045742782663867519468766276566912954519691795540730313772338991769270201");
    BigInteger e1 = new BigInteger("1804229351");
    BigInteger e2 = new BigInteger("17249876309");
    BigInteger[] coefficient = gcdExt(e1, e2);
    BigInteger r = coefficient[1];
    BigInteger s = coefficient[2];
    // r为负，求c1的摸逆元
    BigInteger c1Inverse = c1.modInverse(n);
    BigInteger m = c1Inverse.modPow(r.multiply(new BigInteger("-1")), n).multiply(c2.modPow(s, n))
        .mod(n);
    // 解出m
    System.out.println(m);
  }

代码使用Java中BigInteger表示位数很大的整数，可直接编译运行。 由此可以得m = 11859814987468385682904193929732856121563109146807186957694593421160017639466355

避免这种攻击的方法是尽量不要使用相同的模n

数学攻击还有一种比较常见的低指数攻击，下面说下。

低指数攻击

低指数攻击是当选取的e比较小的时候容易受到的攻击。下面举例说明： 假设有三个用户的密钥指数e选择为3，有不同的模$n_1,n_2,n_3$ 一用户对相同的消息m使用三个人的公钥加密分别与三人通信，得到密文$c_1,c_2,c_3$

$\begin{cases} m^3 \equiv c_1\ mod\ n_1 \ m^3 \equiv c_2\ mod\ n_2 \ m^3 \equiv c_3\ mod\ n_3 \ \end{cases}$

三个密文若被攻击者截获，利用中国剩余定理（一般$n_1,n_2,n_3$互素）求解出$m^3$ , 即使三个模不互素使用扩展剩余定理也可以求出。 得到 $m^3$自然容易求出m, 当然这里假定m < $n_1,n_2,n_3$.

可见参数的选取越小越不安全。

另外关于RSA还有一个有意思的点，如果存在m使得：

$m^3\ mod\ n = m$

这种情况很特殊，明文和密文一样，这样的点称为不动点。加密并未使其发生变化，起不到保护原文的作用。另外利用不动点可能分解合数n， 实际应用中应避免使用。

小结

本节主要介绍了RSA的两种攻击方法，共模攻击和低指数攻击。

关于安全分析，到这里大概说完了。值得一提的是，安全问题永无止境，是一个动态的发展过程，有不少细节没有足够深入。

RSA除了原理和安全方面，在应用中还有计算方面需要考虑的一些事项，如多次提到的幂模运算，e的选取也不是越大越好等

好了，下一篇继续说幂模运算。

欢迎关注公众号：blocksight