共模攻击

​ 共模攻击是一种针对RSA加密的攻击方式，当使用相同的模数n和不同的公钥指数e加密相同的消息时，攻击者可以不解密直接获取明文。基础形式的共模攻击要求公钥指数e互素，利用斐蜀定理可以找到解密需要的参数。当e不互素时，可以找到最大公约数，结合模运算的性质也能实施攻击。NSSCTF工坊提供了两个实例题目，展示了共模攻击的具体应用。第一个题目中e互素，直接应用共模攻击原理；第二个题目中e不互素，需要先找到最大公约数，再进行相应的计算。这些题目帮助理解共模攻击的原理和技巧。(该摘要由ai生成)

共模攻击

知识点

基础 n相同，加密了相同的m，用了两个e，公钥中的e互素（两个数最大公因数为1）

• 已知信息

[e1,n] [e2, n] c1 c2 

式子

$$c1 = m^{e1} \mod n$$ $$c2 = m^{e2} \mod n$$

• 解析

因为e1和e2是互素，运用翡镯定理，有

$$e1·s1+e2·s2 = 1$$

而结合上面式子

得到

$$c1^{s1}·c2^{s2}=m^{e1·s1}m^{e2·s2}=m^{e1·s1+e2·s2}=m^{1} \mod n$$

由上，我们得到了一个不用找p和q也能解rsa的攻击方法。

现在问题转移到如何找到这个s1和s2呢？

用拓展欧几里得算法（gmpy2库的gcdext函数）

对应一个方程

$$a·x+b·y=gcd(a,b)$$

一定且有且只有一个整数解（x,y）

代码小样

_,s1,s2 = gmpy2.gcdext(a, b) 

gmpy2.gcdext(a, b, /)→ tuple[mpz,mpz,mpz]

Return a 3-element tuple (g,s,t) such that g == gcd(a,b) and g == as + bt.

gcdext函数返回三个数，第一个是（a,b）的最大公因数，第二，三个是上面的（x，y）整数解

进阶，公钥的e并不互素

• 解析

和上面的区别就是e1和e2不互素，那通过翡镯定理得到的式子就是

$$e1·s1+e2·s2=gcd(e1,e2)$$

解密方程为

$$c1^{s1}c2^{s2}=m^{e1·s1}m^{e2·s2}=m^{e1·s1+e2·s2}=m^{gcd(e1,e2)} \mod n$$

然后在模里开次方

例题

（来自NSSCTF工坊等）

1. P1[RSA2]P8 | NSSCTF]

   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
       '''

   • exp

     from Crypto.Util.number import *
         from gmpy2 import *
         # 已知
         n = 120294155186626082670474649118722298040433501930335450479777638508444129059776534554344361441717048531505985491664356283524886091709370969857047470362547600390987665105196367975719516115980157839088766927450099353377496192206005171597109864609567336679138620134544004766539483664270351472198486955623315909571
         e1 = 38317
         e2 = 63409
         c1 = 42703138696187395030337205860503270214353151588149506110731264952595193757235229215067638858431493587093612397165407221394174690263691095324298012134779703041752810028935711214038835584823385108771901216441784673199846041109074467177891680923593206326788523158180637665813642688824593788192044139055552031622
         c2 = 50460092786111470408945316270086812807230253234809303694007902628924057713984397041141665125615735752600114964852157684904429928771531639899496987905067366415806771003121954852465731110629459725994454904159277228514337278105207721011579794604761255522391446534458815389983562890631994726687526070228315925638
         
         # 处理
         _, s1, s2 = gcdext(e1, e2)
         
         m = pow(c1, s1, n)*pow(c2, s2, n) % n  # 最后别忘记再模上一个n，整体都在模n中
         flag = long_to_bytes(m).decode()
         
         # 输出
         print(flag) # NSSCTF{same_module_attack!}
         

1. P2[RSA3]P8 | NSSCTF]

   from Crypto.Util.number import *
   
   p = getPrime(700)
   q = getPrime(700)
   n = p*q
   
   e1 = 3*getPrime(16)
   e2 = 3*getPrime(16)
   
   flag = b'NSSCTF{******}'
   c1 = pow(bytes_to_long(flag), e1, n)
   c2 = pow(bytes_to_long(flag), e2, n)
   
   print(f'n = {n}')
   print(f'e1 = {e1}')
   print(f'e2 = {e2}')
   print(f'c1 = {c1}')
   print(f'c2 = {c2}')
   
   '''
   n = 17258060066893213074755453373218306582162826137762311133274776357570753221703880922246758313805944651653670388312409120584883194670296622866672717977722186711567375015117429341498055534372807872455441738225834253639068425012163751145785603722177526607324435641434593514768226599401862097301050185867830575469303960864978407638846270971263106481892520999227504152184478241946941685206875783621912245612463394268401327595737        
   e1 = 159897
   e2 = 192273
   c1 = 4595717262826082372249114022806610849627020753616385658397281529962210282956290111008418210778140550163959636029533312923781864970753502714169965973507425352493857361069899079130259227540344021591878554631845093918021212295485108865566378903346061480239406752062655328184620669486561050933167981474236084817766063901438798437061213111422401822238367462990085699301757131570089105471117732589635966783817714928153442984943        
   c2 = 6930904879823636264189052321687613173304614320999504775391013591790100775422558030373964338538540537224825701022993433544854997668153296576460906623734663341340853498020227553815076511099480950225109778895193096753014911735040516576988675988526232648772153671745762684830032445024652478629766700037603250123679920127263565322009118867116958069937438887437206234970465675161823446396025302570020058273271974621280101050077
   '''

   • exp

     from Crypto.Util.number import *
     from gmpy2 import *
     
     # 已知
     n = 17258060066893213074755453373218306582162826137762311133274776357570753221703880922246758313805944651653670388312409120584883194670296622866672717977722186711567375015117429341498055534372807872455441738225834253639068425012163751145785603722177526607324435641434593514768226599401862097301050185867830575469303960864978407638846270971263106481892520999227504152184478241946941685206875783621912245612463394268401327595737
     e1 = 159897
     e2 = 192273
     c1 = 4595717262826082372249114022806610849627020753616385658397281529962210282956290111008418210778140550163959636029533312923781864970753502714169965973507425352493857361069899079130259227540344021591878554631845093918021212295485108865566378903346061480239406752062655328184620669486561050933167981474236084817766063901438798437061213111422401822238367462990085699301757131570089105471117732589635966783817714928153442984943
     c2 = 6930904879823636264189052321687613173304614320999504775391013591790100775422558030373964338538540537224825701022993433544854997668153296576460906623734663341340853498020227553815076511099480950225109778895193096753014911735040516576988675988526232648772153671745762684830032445024652478629766700037603250123679920127263565322009118867116958069937438887437206234970465675161823446396025302570020058273271974621280101050077
     
     # 处理
     # print(gcd(e1, e2))  3
     
     t, s1, s2 = gcdext(e1, e2)
     
     m = iroot(pow(c1, s1, n)*pow(c2, s2, n) % n, t)[0]
     flag = long_to_bytes(m).decode()
     # 输出
     print(flag)  #NSSCTF{9f6c0e27-0c56-4612-974f-b781c06663fa}

2. P3（占位）

解题板子

（无论e1与e2是否互素 大都适用）

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

# 已知
n = 
e1 = 
e2 = 
c1 = 
c2 = 

# 处理
# print(gcd(e1, e2))  3

t, s1, s2 = gcdext(e1, e2)

m = iroot(pow(c1, s1, n)*pow(c2, s2, n) % n, t)[0]
flag = long_to_bytes(m).decode()
# 输出
print(flag)