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。文章来源:https://www.toymoban.com/news/detail-495471.html
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}文章来源地址https://www.toymoban.com/news/detail-495471.html
到了这里,关于2023省赛-CRYPTO-RSA的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!