首页 > 其他分享 >RSA之低加密指数广播攻击------2023.5.22

RSA之低加密指数广播攻击------2023.5.22

时间:2023-05-22 21:48:18浏览次数:44  
标签:ni 22 int sum RSA 2023.5 n1 import n2

使用条件:

模数n,密文C不同,明文m,加密指数e相同。(一般的话e=k,k是题目给出的n和c的组数)

例如:e=k=3

同余式组:

C1≡m^emodn1 C2≡m^emodn2 C3≡m^emodn3

由中国剩余定理:

设n1,n2,n3是两两互素的正整数,M=n1∗n2∗n3
Mi=M/ni (i=1,2,3)
则同余式组: m^e≡Ci mod ni  (i=1,2,3)

有唯一解: m^e=X≡C1M1y1+C2M2y2+C3M3y3(mod M)
其中(Miyi≡1 mod ni,i=1,2,3)

 

关键代码:

from gmpy2 import*
n1=...
n2=...
n3=...
c1=...
c2=...
c3=...
e=3

def CRT(a,n):
    sum = 0
    N = reduce(lambda x,y:x*y,n)   # ni 的乘积,N=n1*n2*n3

    for n_i, a_i in zip(n,a):    # zip()将对象打包成元组
        N_i = N // n_i           #Mi=M/ni
        sum += a_i*N_i*invert(N_i,n_i)   #sum=C1M1y1+C2M2y2+C3M3y3
    return sum % N 

n =[n1,n2,n3] 
c =[c1,c2,c3]

x = CRT(c,n)

m = iroot(x,e)[0]
print(n2s(m))


例题:buuctf rsa4
N = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004 
c = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243

N = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114 
c = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344

N = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323 
c = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242
解题脚本:
from gmpy2 import*
from Crypto.Util.number import*
from libnum import*

# 将5进制数转换为10进制数  int('',5)
N1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)
c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)

N2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5)
c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)

N3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5)
c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)

e=3

n = [N1,N2,N3]
c = [c1,c2,c3]


def CRT(a,n):
    sum = 0
    N = reduce(lambda x,y:x*y,n)   # ni 的乘积,N=n1*n2*n3

    for n_i, a_i in zip(n,a):    # zip()将对象打包成元组
        N_i = N // n_i           #Mi=M/ni
        sum += a_i*N_i*invert(N_i,n_i)   #sum=C1M1y1+C2M2y2+C3M3y3
    return sum % N 

x = CRT(c,n)

m = iroot(x,e)[0]           #开e次方根
print(n2s(m))               #数值转字符串

 另一个脚本:

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

# 将5进制数转换为10进制数 int('',5)
N1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)
c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)

N2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5)
c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)

N3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5)
c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)

e=3

n = [N1,N2,N3]
c = [c1,c2,c3]


def CRT(a,n):
sum = 0
N = reduce(lambda x,y:x*y,n) # ni 的乘积,N=n1*n2*n3

for n_i, a_i in zip(n,a): # zip()将对象打包成元组
N_i = N // n_i #Mi=M/ni
sum += a_i*N_i*invert(N_i,n_i) #sum=C1M1y1+C2M2y2+C3M3y3
return sum % N

x = CRT(c,n)

m = iroot(x,e)[0] #开e次方根
print(n2s(m)) #数值转字符串

 



标签:ni,22,int,sum,RSA,2023.5,n1,import,n2
From: https://www.cnblogs.com/wlwl1234/p/17421810.html

相关文章

  • 2023.5.22——软件工程日报
    所花时间(包括上课):6h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习。我了解到的知识点:1.了解了一些数据库的知识;2.了解了一些python的知识;3.了解了一些英语知识;5.了解了一些Javaweb的知识;4.了解了一些数学建模的知识;6.了解了一些计算机网络的知识;......
  • 5.22模版 初见云雨情
    函数模板模板函数定义的一般形式如下所示:template<typenametype>ret-typefunc-name(parameterlist){//函数的主体}在这里,type是函数所使用的数据类型的占位符名称。这个名称可以在函数定义中使用。下面是函数模板的实例,返回两个数中的最大值:实例#include<iostream>#......
  • RSA之低指数攻击------2023.5.22
    1,e=3的小明文攻击:特点:当e=3时,如果明文过小,导致明文的三次方仍然小于n,那么通过直接对密文开三次方即可得到明文。 即:C=m^e mod n,如果e=3,且m^e<n,则C=m^e,m=c^(1/3) 2.如果明文的三次方比n大,但不是足够大,那么设k有: C=m^e+k∗n 爆破k,如果 C−k∗n 或者 C+k∗n......
  • 5.22 3.1
    一、问题描述求某一范围内完数的个数。如果一个数等于它的因子之和,则称该数为“完数”(或“完全数”。例如,6的因子为1,2,3,而6=1+2+3,因此6是“完数”。二、分析for(i=2;i<=n;i++){....for(j=l;j<i;j++){...}if(s==i)输出当前i是完数}三、代码#include<iostream>usingna......
  • 2023年5月22号
    今天讲了一下团队开发的总结,目前的项目得不到老师认可,我们也要学会反思。我想了一下情况,不一定保真,最后还是要和团队里其他人商量一下。 没有明确的目标和计划在团队开发过程中,没有为项目设定明确的目标和计划会导致混乱。这可能会使团队成员无法集中注意力,并且在项目的不同阶......
  • 在 Windows Server 2022 中,微软取消了一些以前的功能。以下是一些被取消的功能
    在WindowsServer2022中,微软取消了一些以前的功能。以下是一些被取消的功能:InternetStorageNameService(iSNS):iSNS是一个网络服务协议,为iSCSI设备提供自动发现和配置。在WindowsServer2022中,iSNS被取消了,建议使用其他的自动发现和配置方法。PeerNameResolu......
  • 5.22
    #include<stdio.h>main(){intm,n,temp,i;printf("Inputm&n:");scanf("%d%d",&m,&n);for(inti=1;;i++){if(i%m==0&&i%n==0){printf("%d",i);break;}}return0;}......
  • 算法基础上机实验——2023.5.21
    2.#include<cmath>#include<cstdio>#include<iostream>#include<algorithm>usingnamespacestd;intmain(){intn; cin>>n; n=n*100; intcock,hen,chicken; intcount=0; for(cock=0;cock<=n;c......
  • idea中jdk11用maven编译失败 Fatal error compiling: tools.jar not found: XX\Java
    ideamaven编译需要用到jdk的lib包里面的tools.jar文件,但是jdk1.8之后就没有tools.jar了。我这里用的是graalvm的jdk11,编译一直报错,网上也查不到。解决办法: 根据对应路径创建一个lib包,并把jdk1.8的lib下面的tools.jar复制一个放到这个包下面,让这个路径有这个包就行了。我......
  • 2018 ICPC Asia Qingdao (The 1st Universal Cup, Stage 9)
    E看完题想到二分答案直接一步步贪心,没多想直接和队友说了下,感觉贪心会有点问题,放了一会后冷静分析了一下,发现返回造成的浪费是不可避免的,就很对了!点击查看代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=2e5+5;intn;llm;lla[N]......