RSA

一、题目分析

1、标题：RSA

2、关键字：共模攻击变形

3、比赛：2023年省赛

4、工具：python

二、开始

1、题目

from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long
from gmpy2 import gcdext, iroot, invert

def genFlag(prefix='flag'):
    from uuid import uuid4

    flag = '%s{%s}'%(prefix, uuid4())
    return flag

def task():
    flag = genFlag().encode()
    nbits = 1024

    m = bytes_to_long(flag)

    print(m.bit_length())

    p = getPrime(nbits//2)
    q = getPrime(nbits//2)
    n = p*q


    e1 = getPrime(17)
    e2 = getPrime(15)


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

    print(f'n1 = {n}')
    print(f'e1 = {e1}')
    print(f'c1 = {c1}\n')

    print(f'n2 = {n}')
    print(f'e2 = {e2}')
    print(f'c2 = {c2}\n')

'''

n1 = 80711311928352902694710422970688903606000218692452273911269506769045761705914159133473529264067420955208544069064894951745789822539451286660678312774363283201953736629540550292370742491108053112199867197895749984341885442147728874118323739015205440938518279504759997984775115237492397919379649329850180516261
e1 = 122887
c1 = 59033614245900316909832395678886393276053552915366208621342665332906000721989599030642668957599760516307635849097487785938534526719743083784460303954510364242152451728228357026496644050040514126525518041776661349930706074330888887527845299823685416190405985296818688531105417063538797056226598104927423951627

n2 = 80711311928352902694710422970688903606000218692452273911269506769045761705914159133473529264067420955208544069064894951745789822539451286660678312774363283201953736629540550292370742491108053112199867197895749984341885442147728874118323739015205440938518279504759997984775115237492397919379649329850180516261
e2 = 17257
c2 = 24570094655507396044175375285895366917522198543208218187367223947903249085115185954083311837533185455954612955943018854461433930046296166535549766237187235744710407038811075574034164364122395012692826524642415319528298639367539163546531362754569139791468430890745419711862360528332490543816870699102197775513

'''

    



if __name__ == '__main__':
    task()

2、分析

（1）初步看是共模攻击，即n相同，不同的c1、c2、e1、e2

（2）再分析下加密过程，发现加密的m不同，m是经过一次RSA的。

（3）比赛的时候直接懵逼了，没有想到去推演下计算过程，而是一根筋的去想怎么还原出第一次加密的结果再进行一次共模攻击，结果就没有结果了。

（4）赛后请教了做出来的兄弟，原来就是最简单的数学。

已知n,e1,e2,c1,c2，且

c1 ≡ (m^{3e1}\quad mod \quad n)^{e1} \quad mod \quad n

c2 ≡ (m^{3e2}\quad mod \quad n)^{e2} \quad mod \quad n

简单的数学，初中水平吧，就可以得到

c1 ≡ m^{3{e1}^2}\quad mod \quad n

c2 ≡ m^{3{e2}^2}\quad mod \quad n

即

c1 ≡ ({m^3})^{{e1}^2}\quad mod \quad n

c2 ≡ ({m^3})^{{e2}^2}\quad mod \quad n

这下就又是我们熟悉的共模攻击了，只是m变成了m的三次方。e变成了各自e的平方。那思路就很清晰了：

第一步：共模攻击求出m的三次方

第二步：开立方得到m，case close。

3、solve.py

#!python3
# -*- coding: utf-8 -*-
# @Time : 2023/6/22 12:30
# @Author : A.James
# @FileName: solve.py



# 共模攻击
import gmpy2
import libnum
from Crypto.Util.number import *

n = 80711311928352902694710422970688903606000218692452273911269506769045761705914159133473529264067420955208544069064894951745789822539451286660678312774363283201953736629540550292370742491108053112199867197895749984341885442147728874118323739015205440938518279504759997984775115237492397919379649329850180516261
e1 = 122887
e2 = 17257
c1 = 59033614245900316909832395678886393276053552915366208621342665332906000721989599030642668957599760516307635849097487785938534526719743083784460303954510364242152451728228357026496644050040514126525518041776661349930706074330888887527845299823685416190405985296818688531105417063538797056226598104927423951627
c2 = 24570094655507396044175375285895366917522198543208218187367223947903249085115185954083311837533185455954612955943018854461433930046296166535549766237187235744710407038811075574034164364122395012692826524642415319528298639367539163546531362754569139791468430890745419711862360528332490543816870699102197775513
e3 = e1**2
e4 = e2**2

s0, s1, s2 = gmpy2.gcdext(e3, e4) #求s1,s2,扩展欧几里得算法
if s1 < 0:
    s1 = -s1
    c1 = gmpy2.invert(c1, n)#求c1的模反数
elif s2 < 0:
    s2 = -s2
    c2 = gmpy2.invert(c2, n)#求c2的模反数
m = gmpy2.powmod(c1, s1, n)*gmpy2.powmod(c2, s2, n) % n
print (m)
print ('-------')
m11 = gmpy2.iroot(m,3)
print (m11)
print ('-------')
m12 = m11[0]
print (m12)
print ('-------')
print (long_to_bytes(m12))
#print '[-]flag is:',libnum.n2s(m)

4、get flag

flag{aad084d1-9593-4e8d-968f-5ea2c382b730}