RSA中的共模攻击和例题讲解

0x01 利用条件

两个用户使用相同的模数 n、不同的私钥（加密指数e不相同）时，加密同一明文m消息，即(n,m)相同，(c,e)不同。且两个加密指数$e_1$和$e_2$满足$gcd(e_1, e_2) = 1$，即$e_1$和$e_2$互为素数。

0x02 攻击原理

已知$e_1$,$e_2$，且$gcd(e_1, e_2) = 1$，由扩展欧几里得算法得，存在一组整数$s_1$, $s_2$，使得：公式（1）
$$
e_1 \times s_1 + e_2 \times s_2 = gcd(e_1, e_2) = 1
$$
又由RSA算法原理可得：公式（2）
$$
\begin{cases}
c_1 \equiv m^{e_1}\ (\bmod n)\\
c_2 \equiv m^{e_2}\ (\bmod n)
\end{cases}
$$

求m的方法一：

由以上(1)(2)可得：
$$
\begin{align*}
m &\equiv m^1\ (\bmod n)\\
&\equiv m^{e_1 \times s_1 + e_2 \times s_2}\ (\bmod n)\\
&\equiv m^{e_1 \times s_1} \times m^{e_2 \times s_2}\ (\bmod n)\\
&\equiv [(m^{e_1})^{s_1}\ (\bmod n)]\times [(m^{e_2})^{s_2}\ (\bmod n)]\\
&\equiv c_1^{s_1}\ (\bmod n) \times c_2^{s_2}\ (\bmod n)
\end{align*}
$$
由于$c_1,c_2,s_1,s_2$都是已知的，所以可求出m的值。

即：公式（3）
$$
m \equiv c_1^{s_1}\ (\bmod n) \times c_2^{s_2}\ (\bmod n)
$$

求m的方法二：

或者由（1）（2）可得：
$$
\begin{align*}
c_{1}^{s_1}c_{2}^{s_2} &\equiv m^{s_1e_1}m^{s_2e_2}\ (\bmod n)\\
&\equiv m^{(s_1e_1+s_2e_2)}\ (\bmod n)\\
&\equiv m\ (\bmod n)
\end{align*}
$$

即：公式（4）
$$
c_{1}^{s_1}c_{2}^{s_2} \equiv m\ (\bmod n)
$$

中间还有两个地方需要注意一下。

一是$s_1$,$s_2$的值有一个为负值，在数论中，求一个数$a$模$n$的$-m$次幂，等于这个数$a$模$n$逆元的$m$次幂。

即有公式（5）
$$
n^{-m} \equiv (n^{-1})^m\ (\bmod n)
$$

0x03 例题分析-1

题目代码如下：

import gmpy2
from Crypto.Util.number import *
import uuid
flag = b"flag{"+str(uuid.uuid4()).encode()+b"}"
m = bytes_to_long(flag)
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n1 = p * q
n2 = p * q
e1 = 2333
e2 = 0x2333
assert GCD(e1,e2)==1
c1 = pow(m, e1, n1)
c2 = pow(m, e2, n2)
print("n1 =",n1)
print("n2 =",n2)
print("e1 =",e1)
print("e2 =",e2)
print("c1 =",c1)
print("c2 =",c2)
'''
n1 = 25977434245383213061502496098095465491298593274819892066680142309644604447122213990193649136640792045616043244452359563096681308111786639428720577613208873073208345373399185801097504934529486981943138422062519093084571490989920108900165063768027454172383479340269594705161727160665663784155005546900956290823300194993982080817820176683256899248006819975050544361436011973694569861482116060287819754562815300267132104496249550156359417476864266926873511338883992689905817979797654219916643111997131400074229578490338679081091020589498111095229814729232804557730207461328006855958086611451644501518923369121332282446387
n2 = 25977434245383213061502496098095465491298593274819892066680142309644604447122213990193649136640792045616043244452359563096681308111786639428720577613208873073208345373399185801097504934529486981943138422062519093084571490989920108900165063768027454172383479340269594705161727160665663784155005546900956290823300194993982080817820176683256899248006819975050544361436011973694569861482116060287819754562815300267132104496249550156359417476864266926873511338883992689905817979797654219916643111997131400074229578490338679081091020589498111095229814729232804557730207461328006855958086611451644501518923369121332282446387
e1 = 2333
e2 = 0x2333
c1 = 18485676710986119075173536683686462950263457469331993885761169971214128938032438063231897522845618680375729397028835700363169782372594587099048372908212345790811034629235715272689844039455428850999889426940076877552005174718119690829981655533087526118363975468542716361201641751206611729446725223668335826884543868459078761494737060952796969364730619523110915396112202826020259561117145528032775008508084399606014601141698178821709270288546823847725591199659655029049623145505102599794072348396882393484944750435097930829667964115769696899896453970102851438725866601300114175722160091587885920442620806302225997894178
c2 = 16695364664928581532800627548063845285532382094248770791332184106311111465138692453038543176627867352470844455051476759173301213222665138578557853047169090740483130873450630219045786462114849315733985964814297323071258057067338599104261584932140969238868725551762047861055560927674158814431522126509606052082877955899865835628409554581388612342235123760360863332450664084011638284740583896249409211202260177051437402683756328647008719984689105698475757077859180489424704827694801729848236720022267059771816763723353599632989669237797090397186374989429083807476909642056936466992945632706494532552043613399250805214165
'''

在利用扩展欧几里得算法之后，注意判断$s_1$和$s_2$的正负情况，然后根据公式(4)或者公式(5)即可求得明文，解题代码如下：

import gmpy2
from Crypto.Util.number import *
n1 = 25977434245383213061502496098095465491298593274819892066680142309644604447122213990193649136640792045616043244452359563096681308111786639428720577613208873073208345373399185801097504934529486981943138422062519093084571490989920108900165063768027454172383479340269594705161727160665663784155005546900956290823300194993982080817820176683256899248006819975050544361436011973694569861482116060287819754562815300267132104496249550156359417476864266926873511338883992689905817979797654219916643111997131400074229578490338679081091020589498111095229814729232804557730207461328006855958086611451644501518923369121332282446387
n2 = 25977434245383213061502496098095465491298593274819892066680142309644604447122213990193649136640792045616043244452359563096681308111786639428720577613208873073208345373399185801097504934529486981943138422062519093084571490989920108900165063768027454172383479340269594705161727160665663784155005546900956290823300194993982080817820176683256899248006819975050544361436011973694569861482116060287819754562815300267132104496249550156359417476864266926873511338883992689905817979797654219916643111997131400074229578490338679081091020589498111095229814729232804557730207461328006855958086611451644501518923369121332282446387
e1 = 2333
e2 = 0x2333
c1 = 18485676710986119075173536683686462950263457469331993885761169971214128938032438063231897522845618680375729397028835700363169782372594587099048372908212345790811034629235715272689844039455428850999889426940076877552005174718119690829981655533087526118363975468542716361201641751206611729446725223668335826884543868459078761494737060952796969364730619523110915396112202826020259561117145528032775008508084399606014601141698178821709270288546823847725591199659655029049623145505102599794072348396882393484944750435097930829667964115769696899896453970102851438725866601300114175722160091587885920442620806302225997894178
c2 = 16695364664928581532800627548063845285532382094248770791332184106311111465138692453038543176627867352470844455051476759173301213222665138578557853047169090740483130873450630219045786462114849315733985964814297323071258057067338599104261584932140969238868725551762047861055560927674158814431522126509606052082877955899865835628409554581388612342235123760360863332450664084011638284740583896249409211202260177051437402683756328647008719984689105698475757077859180489424704827694801729848236720022267059771816763723353599632989669237797090397186374989429083807476909642056936466992945632706494532552043613399250805214165
'''区分s1和s2的正负'''
_, s1, s2 = gmpy2.gcdext(e1,e2)
if s1 < 0 :
    s1 = -s1
    c1 = gmpy2.invert(c1, n1)
if s2 < 0 :
    s2 = -s2
    c2 = gmpy2.invert(c2, n2)
'''带入公式(4)或公式(5)'''
m = pow(c1,s1,n2)*pow(c2,s2,n2) % n1
print(long_to_bytes(m))
'''输出：flag{d8f62d48-43fa-4939-ab70-56a16c577c62}'''

0x04 例题分析-2

题目描述：

{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,773}
{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,839}
message1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
message2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535

题目来源：XMan 一期夏令营课堂练习

可以看出两个公钥的 N 是一样的，并且两者的 e 互素。写一个脚本跑一下：

import gmpy2
n = 6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249
e1 = 773
e2 = 839
message1 = 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
message2 = 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535
# s & t
gcd, s, t = gmpy2.gcdext(e1, e2)
if s < 0:
    s = -s
    message1 = gmpy2.invert(message1, n)
if t < 0:
    t = -t
    message2 = gmpy2.invert(message2, n)
plain = pow(message1, s, n) * pow(message2, t, n) % n
print(plain)

得到：

1 2	➜ python3 exp.py 1021089710312311910410111011910111610410511010710511610511511211111511510598108101125

这时候需要考虑当时明文是如何转化为这个数字了，一般来说是 16 进制转换，ASCII 字符转换，或者 Base64 解密。这个应该是 ASCII 字符转换，进而我们使用如下代码得到 flag

i = 0
flag = ""
plain = str(plain)
while i < len(plain):
    if plain[i] == '1':
        flag += chr(int(plain[i:i + 3]))
        i += 3
    else:
        flag += chr(int(plain[i:i + 2]))
        i += 2
print(flag)
'''输出：flag{whenwethinkitispossible}'''