共模攻击

条件

1. 模数相同
2. 加密对象相同
3. 每组的 e 互素

nss

源码：

from Crypto.Util.number import *

flag = b'NSSCTF{******}'

p = getPrime(512)
q = getPrime(512)

n = p*q
e1 = getPrime(16)
e2 = getPrime(16)

m = bytes_to_long(flag)

c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

print(f'n = {n}')
print(f'e1 = {e1}')
print(f'e2 = {e2}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

'''
n = 120294155186626082670474649118722298040433501930335450479777638508444129059776534554344361441717048531505985491664356283524886091709370969857047470362547600390987665105196367975719516115980157839088766927450099353377496192206005171597109864609567336679138620134544004766539483664270351472198486955623315909571
e1 = 38317
e2 = 63409
c1 = 42703138696187395030337205860503270214353151588149506110731264952595193757235229215067638858431493587093612397165407221394174690263691095324298012134779703041752810028935711214038835584823385108771901216441784673199846041109074467177891680923593206326788523158180637665813642688824593788192044139055552031622
c2 = 50460092786111470408945316270086812807230253234809303694007902628924057713984397041141665125615735752600114964852157684904429928771531639899496987905067366415806771003121954852465731110629459725994454904159277228514337278105207721011579794604761255522391446534458815389983562890631994726687526070228315925638
'''

分析

加密过程：

$c_1 \equiv m^{e_1} \mod n \\ c_2 \equiv m^{e_2} \mod n$

有两组公钥。(e1,n) (e2,n)
他们有相同的模数n，且加密对象都是m，满足共模攻击

考虑方程：

$s_1 \cdot e_1 + s_2 \cdot e_2 = 1$

假设我们能找到整数解(s1,s2)满足此方程，那么有：

$c_1^{s_1} \cdot c_2^{s_2} \equiv (m^{e_1})^{s_1} \cdot (m^{e_2})^{s_2} \\[1ex] \equiv m^{e_1s_1 + e_2s_2} \\[1ex] \equiv m \pmod{n}$

直接就可以求出m
那么怎么解出(s1,s2)捏
有翡镯定理

$ax + by = gcd(a,b)$

这就是为什么每组的e要互素，这样就可以使$gcd(e1,e2,e3....)=1$

该方程有且仅有一组整数解$(x,y)$, 使用gmpy2中的gcdext()求解

gcdext()
求出 ax+by=gcd(a,b) 的整数解 (x,y)
输入：gcdext(a,b)
输出：一个包含三个元素的元组

1. gcd(a,b) , a和b的最大公约数
2. a
3. b
   所以使用时要注意对输出的处理，要有3个元素接受输出

exp

from Crypto.Util.number import *
from gmpy2 import *

n = 120294155186626082670474649118722298040433501930335450479777638508444129059776534554344361441717048531505985491664356283524886091709370969857047470362547600390987665105196367975719516115980157839088766927450099353377496192206005171597109864609567336679138620134544004766539483664270351472198486955623315909571
e1 = 38317
e2 = 63409
c1 = 42703138696187395030337205860503270214353151588149506110731264952595193757235229215067638858431493587093612397165407221394174690263691095324298012134779703041752810028935711214038835584823385108771901216441784673199846041109074467177891680923593206326788523158180637665813642688824593788192044139055552031622
c2 = 50460092786111470408945316270086812807230253234809303694007902628924057713984397041141665125615735752600114964852157684904429928771531639899496987905067366415806771003121954852465731110629459725994454904159277228514337278105207721011579794604761255522391446534458815389983562890631994726687526070228315925638

_,s1,s2 = gmpy2.gcdext(e1,e2)
m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
print(long_to_bytes(m))