Crypto_crackCipher

考点：RSA、共模攻击、小明文攻击

#题目
n:
31934670515243135376544494777800167818741680889482357476043664101552263846965902709062687560949362947553749723524721435747896957912492147193043671762758273928557874925637788128125234989097054621581308987239271864314404632159582139228882592627148471549398446422733460548334634327481394478107361389915143539547418985910098660767096947132861742818924085617776838873128115919283348588325931648893539577018391628362088644594757514603575697434296673391737253417736818781989856674787549446853432501840734261821542854584122792474217519456831119992972697291491227130606752323868696432108995904433
c1:
30844012039330070258536456143761809358862057797854053892630858440607549827193033460787087324464139605654012890812030144340209360634997046801933769493806658354096950161853154223654732670515647323259883550654904887690895032316338986275991996131184156035865626736143044052392910180192210388125839151242363611250480493837180613620038095895598448681833958215693745432776287627165112688548348416744866588794033023405575776579986490123103992662714442506606093897670878390187671611825093216814851078943446973697872672875998366847057357888052222683069587610459869062116880896250860882626078292958
c2:
29376289618101477573845080776626444563736469597151865167336042485301759536784462783567968526685694047477189187540318949323788697287596715848087482575926380828996111996259334495315493477987062604746359839578403800720962544133144995430614683984221525578746985707910306870258697864507359761731111650008286206169103341385599663639278442098324437911561465817861903840747109977213158732239774315834302674212907532925861990950343686568112047401696595811630295514183756734449163322948609350655620291947803969755100787417081253273154808178944403727535343569940717056601055016711889950898679773833
e1*e2=3087

（1）⾸先根据俩e 俩c 只有⼀个n，想到考点为共模攻击

共模攻击条件为俩e互质，那么分解e，选取互质的两个进⾏解题

import gmpy2
from Crypto.Util.number import *

n:...
c1:...
c2:...
ee = 3087

for e1 in range(1, ee):
    if ee % e1 == 0:
        e2 = ee // e1
        if gmpy2.gcd(e1,e2)==1: # 检查e1 , e2 是否互质，不互质就往下⾛，互质就重新循环。
            _, r, s = gmpy2.gcdext(e1, e2)

            m = pow(c1, r, n) * pow(c2, s, n) % n
            print (long_to_bytes(m))

3组结果均不正确，明显非正确答案

（2）考虑e非互质情况

小明文

若e1，e2不互质，可令e1=kE1，e2=kE2 （E1，E2互质）

分别是以下⼏种情况。

k = 3, E1 = 1, E2 = 343, e1 = 3, e2 = 1029

k = 7, E1 = 1, E2 = 63, e1 = 7, e2 = 441

k = 7, E1 = 7 E2 = 9, e1= 49, e2 = 63

可以发现，e此时非常小，可以通过爆破得到k值

⽤到的公式为m^e=k*n+m

通俗的讲就是，原本共模攻击条件是俩e互质，但是现在不互质了，就相当于原来的k次⽅，需要找到k 开k次⽅还原回去

import gmpy2
from Crypto.Util.number import *

n = ...
c1 = ...
c2 = ...

for e1 in range(1, 3087):
    if 3087 % e1 == 0:
        e2 = 3087 // e1
        if gmpy2.gcd(e1,e2)==1: # 检查e1 , e2 是否互质，不互质就往下⾛，互质就重新循环。
            _, r, s = gmpy2.gcdext(e1, e2)
            # m = pow(c1, r, n) * pow(c2, s, n) % n
            # print (long_to_bytes(m))
            continue  #因为上边分析，互质就是正常共模了，但是此题不是正常共模，互质解出来不对，才考虑不正常共模，也就是不互质的情况
            
        up, s, t = gmpy2.gcdext(e1, e2) # 扩展欧几里得算法
        m = pow(c1, s, n) * pow(c2, t, n) % n
        # else:
        #     print(e1)
        #     print(e2)
		
        #小明文攻击
        for k in range(1000):
            temp = m+k*n
            tempRes = gmpy2.iroot(temp,up) #返回⼀个元组 (x, y)，其中 x 为 temp 开 up次⽅的值，y 是判断 x 是否为整数的布尔型变量
            if tempRes[1] == True and b'flag' in long_to_bytes(tempRes[0]):
                print(k)
                print(long_to_bytes(tempRes[0]))