莱芜住房和城乡建设厅网站,php购物商城源码,新闻稿,长沙知名网站题目描述#xff1a; 题目分析#xff1a;
首先明确两个公式#xff1a;
e*d 1 mod (p-1)(q-1)
ed1 e*d - 1 k(p-1)(q-1)想要解出此题#xff0c;我们必须知道n,而要知道n,我们要知道p和q的值通过 e*d 的计算#xff0c;我们知道其长度为2066位#xff0c;而生成p的…题目描述 题目分析
首先明确两个公式
e*d 1 mod (p-1)(q-1)
ed1 e*d - 1 k(p-1)(q-1)想要解出此题我们必须知道n,而要知道n,我们要知道p和q的值通过 e*d 的计算我们知道其长度为2066位而生成p的条件为 getPrime(1024)所以p-1)q-1应该为2048位 此处所说的位数长度是以Bit为单位加一减一都不影响位数相乘的话即为位数相加这些性质记住就好以下是计算代码 from Crypto.Util.number import *
e 65537
d 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
print(gmpy2.bit_length(e*d))
# 2064
p getPrime(1024)
print(gmpy2.bit_length(p))
# 1024
print(gmpy2.bit_length(p-1))
# 1024又 ed1 e*d - 1 k(p-1)(q-1)2064-2048 16所以k值必在 pow(2,15)至pow(2,16)之间所以我们可以利用此条件暴力求解k值从而求出(p-1)*(q-1),间接求出 p 和 q 的值那如何间接法呢首先我们求得了(p-1)(q-1),而p和q是两个相邻的质数所以我们可以使用sympy库对p,q进行求解。思路为先对(p-1)(q-1)开方再求得大于开方所得数和小于开方所得数的质数
p sympy.prevprime(gmpy2.iroot((e*d-1)//i,2)[0])
q sympy.nextprime(p)其中 sympy.prevprime(x)是求大于x最近的质数sympy.nextprime(x)是求小于x最近的质数。解题代码如下
import gmpy2
from Crypto.Util.number import long_to_bytes
import sympy
# e 0x10001
e 65537
d 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
c 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804
p 0
q 0for k in range(pow(2,15),pow(2,16)):# pow(x,y) --- x 的 y 次方# pow(x,y,z) --- x 的 y 次方后取余 zif (e*d-1)%k 0:p sympy.prevprime(gmpy2.iroot((e*d-1)//k,2)[0])# sympy.prevprime(x)是求大于x最近的质数# iroot(x,n) --- x开n次根 ,返回值有两个前一个是开方出来的整数部分后一个是能否开出来若能则为true,不能则为flaseq sympy.nextprime(p)# sympy.nextprime(x)是求小于x最近的质数if (p-1)*(q-1) (e*d-1)//k:breakn p*q
m pow(c,d,n)
m1 long_to_bytes(m)
print(m1)最终得出 flag{70u2_nn47h_14_v3ry_gOO0000000d}
收获与体会
了解了一些字节的相关知识知道了函数 sympy.prevprime(x)和sympy.nextprime(x)的相关知识 sympy.prevprime(x)是求大于x最近的质数 sympy.nextprime(x)是求小于x最近的质数回顾了iroot(x,n) 和 pow(x,y) 的相关知识 iroot(x,n) — x开n次根 ,返回值有两个前一个是开方出来的整数部分后一个是能否开出来若能则为true,不能则为flase pow(x,y) — x 的 y 次方 pow(x,y,z) — x 的 y 次方后取余 z
