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

  • blocksight
  • 更新于 2020-07-07 23:29
  • 阅读 4114

本节主要介绍了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

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
blocksight
blocksight
江湖只有他的大名,没有他的介绍。