官方公众号企业安全新浪微博
FreeBuf.COM网络安全行业门户，每日发布专业的安全资讯、技术剖析。
FreeBuf+小程序
CTF实战分享 | Crypto-RSA
- 关注
CTF实战分享 | Crypto-RSA
本文由
创作，已纳入「FreeBuf原创奖励计划」，未授权禁止转载
序言
最近对Crypto有点兴趣，所有写个帖子跟进学习。在进行Crypto的CTF解题过程中发现，大多ctf题是以RSA为核心展开的，当然也有很多其他的加密方法。不过，目前仅对rsa感兴趣。其他加密算法可能等等再研究了。对RSA了解的同学，应该知道RSA解密需要对初等数论的知识有些了解。下面我将根据解题思路的不同，对题目进行剖析。有些题目可能存在多种攻击方式，所以在进行题目分类时可能存在出入。
目前题目有点少，不过后面会加，因为还要学习其他的东西。不过保证会把解题思路给一步一步写出来的。
就很多时候我们找到wp看看就过去了，如果我们把wp和解题原理吃透，那么下次我们就可以自己撰写代码啦。
解题是目的也不全是目的哦。
注：关于维纳攻击的部分我觉得z2333师傅写的超级棒，我自己写的话无法像他那要，所以维纳攻击原理部分可以去看他的文章。（文中有参考链接）
RSA基本原理
公钥与私钥的产生：
(1)进行加密之前，首先找出2个不同的大质数p和q
(2)计算n=p*q
(3)根据欧拉函数，求得φ(n)=φ(p)φ(q)=(p−1)(q−1)
(4)找出一个公钥e，e要满足: 1<e<φ(n) 的整数，且使e和φ(N)互质。
(5)根据e*d除以φ(n)余数为1，找到私钥d。
(6)所以,公钥就是(n,e) 私钥就是(n,d)
消息加密:
m^e除以n求余数即为c(密文) c=pow(m,e,n)
消息解密:
c^d除以n求余数即为m(明文) m=pow(c,d,n)
pem公钥文件读取中n,e读取
考虑到一些小伙伴打ctf时会遇到公钥public.pem文件读取n,e的需求,给出下列代码方便获取n,e进行下一步的参数获取
from Crypto.PublicKey import RSA
f=open("C:\\Users\\86191\\Desktop\\111\\public.pem","r")
key = RSA.importKey(f.read())
print(key.n)
print(key.e)
常规RSA
这一类题目，在进行加密时，给出一些参数pq等进行运算后的数字，需要对参数关系进行推导。
[BJDCTF 2020]EasyRSA
题目：
from Crypto.Util.number import getPrime,bytes_to_long from sympy import Derivative from fractions import Fraction from secret import flag p=getPrime(1024) q=getPrime(1024) e=65537 n=p*q z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q)) m=bytes_to_long(flag) c=pow(m,e,n) print(c,z,n) ''' output: 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441 '''
思路：
给出了e c z n
z是p q的经过一些运算的结合 ，n=p*q
z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))
arctan(p):对p的反正切 arth(q)：反双曲线正切
Derivative：分别对上述两个参数的p q求导
得到两个值1/(1+p^2) 1/(1-q^2)
Fraction：是以1为分子，以Derivative(arctan(p),p)或Derivative(arth(q),q)为分母
此时z=p^2+q^2
z有了 n有了
熟悉的初中数学来了
(p+q)^2=z+2n
(p-q)^2=z-2n
计算后分别得出p q
Ф(n)=(p-1)(q-1)
d=gmpy2.invert(e,Ф(n))
m=pow(c,d,n)
解题：
from gmpy2 import * from Crypto.Util.number import * c=mpz(7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035) z=mpz(32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482) n=mpz(15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441) e=65537 pqplus=iroot(z+2*n,2)[0] pqminus=iroot(z-2*n,2)[0] p=(pqminus+pqplus)//2 q=(pqplus-pqminus)//2 phi=(p-1)*(q-1) d=invert(e,phi) m=pow(c,d,n) flag=long_to_bytes(m) print (flag)
[CISCN 2022 西南]rsa
题目：
from Crypto.Util.number import *
import gmpy2
flag = b'XXXXXXXX'
p1 = getPrime(700)
r1 = getPrime(700)
for i in range(10):
q1 = 5*p1+i
n = p1*q1*r1
p3 = pow(p1,3,n)
q3 = pow(q1,3,n)
print(p3)
print(q3)
'''
p3 = 29914513810588158800677413177910972738704129106546850855032986405861482276089830788972187432277517348644647399654780884571794069905291936470934226328931651386658328163535027343107140438177837479649822914209171476632450951930287641742344330471734177295804718555774395704231261550376220154493373703096062950390869299905383682611063374747752091585836452902373843865043412096365874638466683035848817858586173172058756256354758712684819253211761289032789542371351760915771791997388241121078055468403109260493642435791152671979552597191217179672328555740595434990908530985477314228867209314472001848844089467987561661918366232980944933533
q3 = 66208618374366130551979192465001581263127328176551695213970812805980115496523825511250542987452691413485117902772315362811067501379171731387904074565035353566976164797769439898266222919741874340315356585585077141595328441423323822407738375537476582506440045835592730211502035261968878999959340204806442390319739977816872969200022096331677277225467021553564212725120939434924481787524609852608476848761521446441776154400518315701988027274150425936061679275540502720782853648148897480117033152064922234451671636288396704170234613549011854618414776342798740690128675106027908639984431432591397555541420243824539205614036979987830125678
'''
P = getPrime(1024)
Q = getPrime(1024)
N = P * Q
E = 65537
lcm = gmpy2.lcm(P-1, Q-1)
e1 = gmpy2.invert(p1, lcm)
e2 = gmpy2.invert(r1, lcm)
m = bytes_to_long(flag)
c = pow(m, E, N)
print(lcm)
print(c)
print(N)
'''
lcm = 4292158730589770192682795435047249488185453170529228019750042608688907718268448193363838203887391025871515871000364259326343790645215256385842265899206372365402431198699714374850409466996627163968391249416054093529090485677808301343590811445080871279796162536469847469761747058736980603093722710824453312207182881241846080117790728778291633761198069016865260030288832065807438020772711645648333908622890343009942617559434851450007195025869850769670769715654662127278293639938359741401336592219730356884542179574372134014927006215640945952229142436595334916765255426954857520777553915330597952622785359222832224632624
c = 4288727484183191191687364666620023549392656794153112764357730676861570386983002380982803054964588111708662498647767438881892355599604826306427809017097724346976778230464708540600157055782723189971534549543664668430013171469625043063261219462210251726207552819381767396148632877168530609902046293626355744288863460554297860696918890189350721960355460410677203131993419723440382095665713164422367291153108363066159712951217816814873413423853338021627653555202253351957999686659021298525147460016557904084617528199284448056532965033560516083489693334373695545423561715471204868795248569806148395196572046378679014697206
N = 17168634922359080770731181740188997952741812682116912079000170434755630873073792773455352815549564103486063484001457037305375162580861025543369063596825489461609724794798857499401637867986508655873564997664216374116361942711233205374363245780323485119184650145879389879046988234947922412374890843297813248828996855478005656041814919367820336728271583686844991928889831691815821365423570311291064846736832327637944358854661523107817781673029406341843040857813841671405147146887291204140157388049394514390098066284975682117038362207142272098796924412602725857521665773622056312191400612944442008222587867782281556388669
思路：
第一部分和第二部分存在P1 r1的相同点，大概率就是第一部分求p1 r1在第二部分用
第一部分：
n = p1*q1*r1
p3 = pow(p1,3,n)
q3 = pow(q1,3,n)
由于p1没有经过处理，且加密参数e=3直接开三次方根即可，
这时需要求出r1，这里有关系公式
n = p1*q1*r1
需要知道n和q1
q1与p1的关系我们知道
for i in range(10):
q1 = 5*p1+i
但是n不知道
但是由p3 = pow(p1,3,n)
我们知道n|p1^3-p3 再加上n = p1*q1*r1,r1|n =>r1|p1^3-p3,此时分解（p1^3-p3）/r1的结果即可
第二部分：
已知N = P * Q
已知lcm = gmpy2.lcm(P-1, Q-1)最小公倍数
e1 = gmpy2.invert(p1, lcm)
e2 = gmpy2.invert(r1, lcm)
c = pow(m, E, N)
这里比较有趣
因为想要获取D的值
但是Φ(N)=(P-1)(Q-1)，以及ED模Φ(N)等于1=>Φ(N)|ED-1
Φ(N)=lcm(P-1,Q-1)*gcd(P-1,Q-1)=>lcm(P-1,Q-1)|Φ(N)
由于整除的传递性：
lcm(P-1,Q-1)|ED-1
=>ED模lcm(P-1,Q-1)等于1
即 D是E模lcm(P-1,Q-1)的逆元
证毕
？？？所以第一部分完全没啥用了？？？
解题：
import math import gmpy2 from Crypto.Util.number import * lcm = 4292158730589770192682795435047249488185453170529228019750042608688907718268448193363838203887391025871515871000364259326343790645215256385842265899206372365402431198699714374850409466996627163968391249416054093529090485677808301343590811445080871279796162536469847469761747058736980603093722710824453312207182881241846080117790728778291633761198069016865260030288832065807438020772711645648333908622890343009942617559434851450007195025869850769670769715654662127278293639938359741401336592219730356884542179574372134014927006215640945952229142436595334916765255426954857520777553915330597952622785359222832224632624 c = 4288727484183191191687364666620023549392656794153112764357730676861570386983002380982803054964588111708662498647767438881892355599604826306427809017097724346976778230464708540600157055782723189971534549543664668430013171469625043063261219462210251726207552819381767396148632877168530609902046293626355744288863460554297860696918890189350721960355460410677203131993419723440382095665713164422367291153108363066159712951217816814873413423853338021627653555202253351957999686659021298525147460016557904084617528199284448056532965033560516083489693334373695545423561715471204868795248569806148395196572046378679014697206 N = 17168634922359080770731181740188997952741812682116912079000170434755630873073792773455352815549564103486063484001457037305375162580861025543369063596825489461609724794798857499401637867986508655873564997664216374116361942711233205374363245780323485119184650145879389879046988234947922412374890843297813248828996855478005656041814919367820336728271583686844991928889831691815821365423570311291064846736832327637944358854661523107817781673029406341843040857813841671405147146887291204140157388049394514390098066284975682117038362207142272098796924412602725857521665773622056312191400612944442008222587867782281556388669 E = 65537 d=gmpy2.invert(E,lcm) m=pow(c,d,N) print(long_to_bytes(m))
低加密指数分解攻击-e=2密文开平方
低加密指数分解攻击是指，在进行RSA加密时，选择的e太小,此时密文c相当于m的e次方，此时只需要对c进行相应次数的开根号即可。当且仅当e特别小的时候。下面给出几道题，了解一下具体解题过程。
西湖论剑rsa
题目：
已知:
e=2
c=9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529
求明文m?
思路：
题目中给出了c和e,且e=2。由于c = (m ^ e) % n 。直接对c开平方根即可。
解题：
import gmpy2 import libnum c = 9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529 m = gmpy2.isqrt(c) #求平方根 m = int(m) m = libnum.n2s(m) #转换为其对应的二进制字符串 print(m)
低加密指数分解攻击-Rabin加密算法
加密原理可以参考-Rabin加密原理
低加密指数分解攻击
[鹤城杯 2021]Crazy_Rsa_Techv
题目：
from Crypto.Util.number import *
from Crypto.Util.Padding import *
FLAG = bytes_to_long(pad(b"flag{??????}",64))
def init_key():
p, q = getPrime(512), getPrime(512)
n = p*q
e = 9
while(GCD((p-1)*(q-1),e)!=1):
p, q = getPrime(512), getPrime(512)
n = p*q
d = inverse(e,(p-1)*(q-1))
return n,e,d
n_list=list()
c_list=list()
for i in range(9):
N,e,d=init_key()
n_list.append(N)
c=pow(FLAG,e,N)
c_list.append(pow(FLAG,e,N))
assert(pow(c,d,N)==FLAG)
print("n_list:",n_list)
print("c_list:",c_list)
n_list: [71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
c_list: [62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]思路：
看到e=9，以及九组密文c和模数n，挨个爆破
Ci=pow(m,e,Ni) i=1,2,3,....,9
对list_n和list_c遍历爆破
解题：
import gmpy2
import math
from Crypto.Util.number import *
def merge(a1,n1,a2,n2):
d = math.gcd(n1,n2)
c = a2-a1
if c%d!=0:
return 0
c = (c%n2+n2)%n2
c = c//d
n1 = n1//d
n2 = n2//d
c *= gmpy2.invert(n1,n2)
c %= n2
c *= n1*d
c += a1
global n3
global a3
n3 = n1*n2*d
a3 = (c%n3+n3)%n3
return 1
def exCRT(a,n):
a1=a[0]
n1=n[0]
le= len(a)
for i in range(1,le):
a2 = a[i]
n2=n[i]
if not merge(a1,n1,a2,n2):
return -1
a1 = a3
n1 = n3
global mod
mod=n1
return (a1%n1+n1)%n1
def exCRT_getequation(a,n):
a1=a[0]
n1=n[0]
le= len(a)
for i in range(1,le):
a2 = a[i]
n2=n[i]
if not merge(a1,n1,a2,n2):
return -1
a1 = a3
n1 = n3
return (a1,n1)
n = [71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
c = [62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]
m9=exCRT(c,n)
m=gmpy2.iroot(m9,9)[0]
print(long_to_bytes(m))
#flag{H0w_Fun_13_HAstads_broadca5t_AtTack!}
共模攻击
明文m、模数n相同，公钥指数e、密文c不同，gcd(e1,e2)==1也就是e1和e2互质。对同一明文的多次加密使用相同的模数和不同的公钥指数可能导致共模攻击。共模攻击时最常见的攻击方式。在进行解题之前先了解以下解题思路。
假定给出a=(m^e1)mod n b=(m^e2)mod n ,给定a,b,e1,e2,n。
证明：
我直接在纸上写证明过程了，实在不喜欢打字证明。
证明有了下面开始做题吧。
[HGAME 2022 week2]RSA Attack2
题目：
import re
from math import ceil
from Crypto.Util.number import getPrime
from libnum import s2n
from secret import flag
flag_parts = list(map(s2n, re.findall(rf".{{,{ceil(len(flag) / 3)}}}", flag)))
print("# task1")
m = flag_parts[0]
e = 65537
p = getPrime(1024)
q = getPrime(1024)
r = getPrime(1024)
n1 = p * q
c1 = pow(m, e, n1)
n2 = r * q
c2 = pow(m, e, n2)
print("e =", e)
print("n1 =", n1)
print("c1 =", c1)
print("n2 =", n2)
print("c2 =", c2)
print("# task2")
m = flag_parts[1]
e = 7
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c = pow(m, e, n)
print("e =", e)
print("n =", n)
print("c =", c)
print("# task3")
m = flag_parts[2]
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e1 = getPrime(32)
e2 = getPrime(32)
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)
print("n =", n)
print("e1 =", e1)
print("c1 =", c1)
print("e2 =", e2)
print("c2 =", c2)
# task1
e = 65537
n1 = 14611545605107950827581005165327694782823188603151768169731431418361306231114985037775917461433925308054396970809690804073985835376464629860609710292181368600618626590498491850404503443414241455487304448344892337877422465715709154238653505141605904184985311873763495761345722155289457889686019746663293720106874227323699288277794292208957172446523420596391114891559537811029473150123641624108103676516754449492805126642552751278309634846777636042114135990516245907517377320190091400729277307636724890592155256437996566160995456743018225013851937593886086129131351582958811003596445806061492952513851932238563627194553
c1 = 965075803554932988664271816439183802328812013694203741320763105376036912584995031647672348468111310423680858101990670067065306237596121664884353679987689532305437801346923070145524106271337770666947677115752724993307387122132705797012726237073550669419110046308257408484535063515678066777681017211510981429273346928022971149411064556225001287399141306136081722471075032423079692908380267160214143720516748000734987068685104675254411687005690312116824966036851568223828884335112144637268090397158532937141122654075952730052331573980701136378212002956719295192733955673315234274064519957670199895100508623561838510479
n2 = 20937478725109983803079185450449616567464596961348727453817249035110047585580142823551289577145958127121586792878509386085178452171112455890429474457797219202827030884262273061334752493496797935346631509806685589179618367453992749753318273834113016237120686880514110415113673431170488958730203963489455418967544128619234394915820392908422974075932751838012185542968842691824203206517795693893863945100661940988455695923511777306566419373394091907349431686646485516325575494902682337518438042711296437513221448397034813099279203955535025939120139680604495486980765910892438284945450733375156933863150808369796830892363
c2 = 11536506945313747180442473461658912307154460869003392732178457643224057969838224601059836860883718459986003106970375778443725748607085620938787714081321315817144414115589952237492448483438910378865359239575169326116668030463275817609827626048962304593324479546453471881099976644410889657248346038986836461779780183411686260756776711720577053319504691373550107525296560936467435283812493396486678178020292433365898032597027338876045182743492831814175673834198345337514065596396477709839868387265840430322983945906464646824470437783271607499089791869398590557314713094674208261761299894705772513440948139429011425948090
# task2
e = 7
n = 14157878492255346300993349653813018105991884577529909522555551468374307942096214964604172734381913051273745228293930832314483466922529240958994897697475939867025561348042725919663546949015024693952641936481841552751484604123097148071800416608762258562797116583678332832015617217745966495992049762530373531163821979627361200921544223578170718741348242012164115593777700903954409103110092921578821048933346893212805071682235575813724113978341592885957767377587492202740185970828629767501662195356276862585025913615910839679860669917255271734413865211340126544199760628445054131661484184876679626946360753009512634349537
c = 10262871020519116406312674685238364023536657841034751572844570983750295909492149101500869806418603732181350082576447594766587572350246675445508931577670158295558641219582729345581697448231116318080456112516700717984731655900726388185866905989088504004805024490513718243036445638662260558477697146032055765285263446084259814560197549018044099935158351931885157616527235283229066145390964094929007056946332051364474528453970904251050605631514869007890625
# task3
n = 18819509188106230363444813350468162056164434642729404632983082518225388069544777374544142317612858448345344137372222988033366528086236635213756227816610865045924357232188768913642158448603346330462535696121739622702200540344105464126695432011739181531217582949804939555720700457350512898322376591813135311921904580338340203569582681889243452495363849558955947124975293736509426400460083981078846138740050634906824438689712748324336878791622676974341814691041262280604277357889892211717124319329666052810029131172229930723477981468761369516771720250571713027972064974999802168017946274736383148001865929719248159075729
e1 = 2519901323
c1 = 3230779726225544872531441169009307072073754578761888387983403206364548451496736513905460381907928107310030086346589351105809028599650303539607581407627819797944337398601400510560992462455048451326593993595089800150342999021874734748066692962362650540036002073748766509347649818139304363914083879918929873577706323599628031618641793074018304521243460487551364823299685052518852685706687800209505277426869140051056996242882132616256695188870782634310362973153766698286258946896866396670872451803114280846709572779780558482223393759475999103607704510618332253710503857561025613632592682931552228150171423846203875344870
e2 = 3676335737
c2 = 940818595622279161439836719641707846790294650888799822335007385854166736459283129434769062995122371073636785371800857633841379139761091890426137981113087519934854663776695944489430385663011713917022574342380155718317794204988626116362865144125136624722782309455452257758808172415884403909840651554485364309237853885251876941477098008690389600544398998669635962495989736021020715396415375890720335697504837045188626103142204474942751410819466379437091569610294575687793060945525108986660851277475079994466474859114092643797418927645726430175928247476884879817034346652560116597965191204061051401916282814886688467861
思路：
task1存在共同参数 q,直接gcd一下按正常顺序求就可以
task2 e=7 m^e≡c(mod m)
m^7=c+mk
k∈Z 存在整数开根即可
task 3 共模攻击
代码：
import libnum
import gmpy2
import hashlib
from gmpy2 import *
from Crypto.Util.number import *
from gmpy2 import gmpy2
# task1 有共同素数，gcd求q
e = 65537
n1 = 14611545605107950827581005165327694782823188603151768169731431418361306231114985037775917461433925308054396970809690804073985835376464629860609710292181368600618626590498491850404503443414241455487304448344892337877422465715709154238653505141605904184985311873763495761345722155289457889686019746663293720106874227323699288277794292208957172446523420596391114891559537811029473150123641624108103676516754449492805126642552751278309634846777636042114135990516245907517377320190091400729277307636724890592155256437996566160995456743018225013851937593886086129131351582958811003596445806061492952513851932238563627194553
c1 = 965075803554932988664271816439183802328812013694203741320763105376036912584995031647672348468111310423680858101990670067065306237596121664884353679987689532305437801346923070145524106271337770666947677115752724993307387122132705797012726237073550669419110046308257408484535063515678066777681017211510981429273346928022971149411064556225001287399141306136081722471075032423079692908380267160214143720516748000734987068685104675254411687005690312116824966036851568223828884335112144637268090397158532937141122654075952730052331573980701136378212002956719295192733955673315234274064519957670199895100508623561838510479
n2 = 20937478725109983803079185450449616567464596961348727453817249035110047585580142823551289577145958127121586792878509386085178452171112455890429474457797219202827030884262273061334752493496797935346631509806685589179618367453992749753318273834113016237120686880514110415113673431170488958730203963489455418967544128619234394915820392908422974075932751838012185542968842691824203206517795693893863945100661940988455695923511777306566419373394091907349431686646485516325575494902682337518438042711296437513221448397034813099279203955535025939120139680604495486980765910892438284945450733375156933863150808369796830892363
c2 = 11536506945313747180442473461658912307154460869003392732178457643224057969838224601059836860883718459986003106970375778443725748607085620938787714081321315817144414115589952237492448483438910378865359239575169326116668030463275817609827626048962304593324479546453471881099976644410889657248346038986836461779780183411686260756776711720577053319504691373550107525296560936467435283812493396486678178020292433365898032597027338876045182743492831814175673834198345337514065596396477709839868387265840430322983945906464646824470437783271607499089791869398590557314713094674208261761299894705772513440948139429011425948090
q = gmpy2.gcd(n1,n2)
p = n1//q
d = gmpy2.invert(e,(q-1)*(p-1))
m1= libnum.n2s(int(pow(c1,d,n1)))
print(m1)
#task2
# task2 小e，直接开根
e = 7
n = 14157878492255346300993349653813018105991884577529909522555551468374307942096214964604172734381913051273745228293930832314483466922529240958994897697475939867025561348042725919663546949015024693952641936481841552751484604123097148071800416608762258562797116583678332832015617217745966495992049762530373531163821979627361200921544223578170718741348242012164115593777700903954409103110092921578821048933346893212805071682235575813724113978341592885957767377587492202740185970828629767501662195356276862585025913615910839679860669917255271734413865211340126544199760628445054131661484184876679626946360753009512634349537
c = 10262871020519116406312674685238364023536657841034751572844570983750295909492149101500869806418603732181350082576447594766587572350246675445508931577670158295558641219582729345581697448231116318080456112516700717984731655900726388185866905989088504004805024490513718243036445638662260558477697146032055765285263446084259814560197549018044099935158351931885157616527235283229066145390964094929007056946332051364474528453970904251050605631514869007890625
if gmpy2.iroot(c,e)[1]==True: #开根
m2 = libnum.n2s(int(gmpy2.iroot(c,e)[0]))
print(m2)
# task3 共模攻击，求e1 e2逆元和公因数，然后对公因数求根取模得到明文
n = 18819509188106230363444813350468162056164434642729404632983082518225388069544777374544142317612858448345344137372222988033366528086236635213756227816610865045924357232188768913642158448603346330462535696121739622702200540344105464126695432011739181531217582949804939555720700457350512898322376591813135311921904580338340203569582681889243452495363849558955947124975293736509426400460083981078846138740050634906824438689712748324336878791622676974341814691041262280604277357889892211717124319329666052810029131172229930723477981468761369516771720250571713027972064974999802168017946274736383148001865929719248159075729
e1 = 2519901323
c1 = 3230779726225544872531441169009307072073754578761888387983403206364548451496736513905460381907928107310030086346589351105809028599650303539607581407627819797944337398601400510560992462455048451326593993595089800150342999021874734748066692962362650540036002073748766509347649818139304363914083879918929873577706323599628031618641793074018304521243460487551364823299685052518852685706687800209505277426869140051056996242882132616256695188870782634310362973153766698286258946896866396670872451803114280846709572779780558482223393759475999103607704510618332253710503857561025613632592682931552228150171423846203875344870
e2 = 3676335737
c2 = 940818595622279161439836719641707846790294650888799822335007385854166736459283129434769062995122371073636785371800857633841379139761091890426137981113087519934854663776695944489430385663011713917022574342380155718317794204988626116362865144125136624722782309455452257758808172415884403909840651554485364309237853885251876941477098008690389600544398998669635962495989736021020715396415375890720335697504837045188626103142204474942751410819466379437091569610294575687793060945525108986660851277475079994466474859114092643797418927645726430175928247476884879817034346652560116597965191204061051401916282814886688467861
def rsa_gong_N_def(e1, e2, c1, c2, n):
e1, e2, c1, c2, n = int(e1), int(e2), int(c1), int(c2), int(n)
s = gmpy2.gcdext(e1, e2) # 扩展欧几里得算法 t*e1+z*e2=1,求出t和z
t = s[1]
z = s[2]
if t < 0: # 取反求逆
t = - t
c1 = gmpy2.invert(c1, n) # 求c1关于模n的逆元
elif z < 0:
z = -z
c2 = gmpy2.invert(c2, n)
m = (pow(c1, t, n) * pow(c2, z, n)) % n # (c1^s1*c2^s2)%n=m%n=m
return m
result = rsa_gong_N_def(e1, e2, c1, c2, n)
m3=long_to_bytes(result)
print(m3)crypto1
题目：
from gmpy2 import *
from Crypto.Util.number import *
flag = '***************'
p = getPrime(512)
q = getPrime(512)
m1 = bytes_to_long(bytes(flag.encode()))
n = p * q
e1 = getPrime(32)
e2 = getPrime(32)
flag1 = pow(m1, e1, n) # flag1=(m1^e1)%n
flag2 = pow(m1, e2, n) # flag2=(m1^e2)%n (de)mod&n=1 m=(c2^d2)%n
print('flag1= ' + str(flag1))
print('flag2= ' + str(flag2))
print('e1= ' + str(e1))
print('e2= ' + str(e2))
print('n= ' + str(n))
# flag1= 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
# flag2= 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075
# e1= 3247473589
# e2= 3698409173
# n= 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313思路：
题目给出了 flag1,flag2, e1 ,e2 n
1.求出e1和e2的最大公因数gcd(e1,e2)，通过欧几里得算法，求出t*e1+z*e2=gcd(e1,e2)中的t和z
2.根据m^gcd(e1,e2)%n=(flag1^s+flag2^t)%n求出m^gcd(e1,e2)%n的值
3.对mk=m^gcd(e1,e2)%n进行爆破 mk=m^gcd(e1,e2)+n*k 其中k属于整数，遍历k当且仅当mk可以开gcd(e1,e2)时输出。
解题：
import gmpy2
from Crypto.Util.number import long_to_bytes
flag1 = 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
flag2 = 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
n = 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437
e1e2 = 3087
def rsa_gong_N_def(e1, e2, c1, c2, n):
e1, e2, c1, c2, n = int(e1), int(e2), int(c1), int(c2), int(n)
s = gmpy2.gcdext(e1, e2) # 扩展欧几里得算法
s1 = s[1]
s2 = s[2]
if s1 < 0:
s1 = - s1
c1 = gmpy2.invert(c1, n)
elif s2 < 0:
s2 = - s2
c2 = gmpy2.invert(c2, n)
m = (pow(c1, s1, n) * pow(c2, s2, n)) % n # m=(m^7)%n
return int(m)
def de(c, e, n): # 对m^k进行爆破
k = 0
while k < 1000:
mk = c + n * k
flag, true = gmpy2.iroot(mk, e) # 若能开方,则会返回true
if True == true:
return flag
k += 1
for e1 in range(2, e1e2):
if e1e2 % e1 == 0: # 爆破可整除的e1,e2
e2 = e1e2 // e1
c = rsa_gong_N_def(e1, e2, flag1, flag2, n) # 返回的结果为(m^k)%n,(m^7)%n
print(c)
e = gmpy2.gcd(e1, e2) # 求出e1和e2的最大公因数,7
m1 = de(c, e, n)
if m1:
print(long_to_bytes(int(m1)))[SWPUCTF 2021新生赛]crypto2
题目：
from gmpy2 import *
from Crypto.Util.number import *
flag = '***************'
p = getPrime(512)
q = getPrime(512)
m1 = bytes_to_long(bytes(flag.encode()))
n = p * q
e1 = getPrime(32)
e2 = getPrime(32)
flag1 = pow(m1, e1, n) # flag1=(m1^e1)%n
flag2 = pow(m1, e2, n) # flag2=(m1^e2)%n (de)mod&n=1 m=(c2^d2)%n
print('flag1= ' + str(flag1))
print('flag2= ' + str(flag2))
print('e1= ' + str(e1))
print('e2= ' + str(e2))
print('n= ' + str(n))
# flag1= 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
# flag2= 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075
# e1= 3247473589
# e2= 3698409173
# n= 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313思路：
思路与crypto相同，只是不需要爆破，因为gcd(e1,e2)=1
解题：
from gmpy2 import *
from Crypto.Util.number import *
from gmpy2 import gmpy2
flag1 = 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
flag2 = 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075
e1 = 3247473589
e2 = 3698409173
n = 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313
def rsa_gong_N_def(e1, e2, c1, c2, n):
e1, e2, c1, c2, n = int(e1), int(e2), int(c1), int(c2), int(n)
s = gmpy2.gcdext(e1, e2) # 扩展欧几里得算法 t*e1+z*e2=1,求出t和z
t = s[1]
z = s[2]
if t < 0: # 取反求逆
t = - t
c1 = gmpy2.invert(c1, n) # 求c1关于模n的逆元
elif z < 0:
z = -z
c2 = gmpy2.invert(c2, n)
m = (pow(c1, t, n) * pow(c2, z, n)) % n # (c1^s1*c2^s2)%n=m%n=m
return m
result = rsa_gong_N_def(e1, e2, flag1, flag2, n)
print(long_to_bytes(result))
[SWPUCTF 2021 新生赛]crypto1
题目：
from gmpy2 import *
from Crypto.Util.number import *
flag = '****************************'
flag = {"asfajgfbiagbwe"}
p = getPrime(2048)
q = getPrime(2048)
m1 = bytes_to_long(bytes(flag.encode()))
e1e2 = 3087
n = p*q
print()
flag1 = pow(m1,e1,n)
flag2 = pow(m1,e2,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('n= '+str(n))
#flag1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
#flag2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
#n= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437
思路：
flag1 = pow(m1,e1,n)=c1
flag2 = pow(m1,e2,n)=c2
e1e2 = 3087
3087是合数可以分解成两个数e1和e2
3087=3^2*7*3
此时e1在3, 7, 3 * 3, 3 * 7, 7 * 7, 3 * 3 * 7, 3 * 7 * 7, 7 * 7 * 7, 3 * 7 * 7 * 7, 3 * 3 * 7 * 7内取值
爆破
此时flag1 和flag2存在相同的模n,只是e1和e2不同，题目可以进行共模攻击
共模攻击之前先求取e1和e2的最大公因数
g = gcd(e1, e2)
在进行拓展欧几里得算法
_, s, t = gcdext(e1, e2)
得到s,t后，求取M=m^gcd(e1, e2) = pow(c1, s, n) * pow(c2, t, n) % n
此时的到的只是m的gcd(e1, e2)次幂加上n的k倍
对k爆破分解即可
a = iroot(M + k * n, g)
if a[1]:
print(long_to_bytes(a[0]))
解题：
from gmpy2 import *
from Crypto.Util.number import *
c1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
c2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
n= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437
E = 3087
fac = [3, 3, 7, 7, 7]
factor = [3, 7, 3 * 3, 3 * 7, 7 * 7, 3 * 3 * 7, 3 * 7 * 7, 7 * 7 * 7, 3 * 7 * 7 * 7, 3 * 3 * 7 * 7]
for e1 in factor:
assert E % e1 == 0
e2 = E // e1
g = gcd(e1, e2)
print(g)
_, s, t = gcdext(e1, e2)
M = pow(c1, s, n) * pow(c2, t, n) % n
for k in range(1000000):
a = iroot(M + k * n, g)
if a[1]:
print(long_to_bytes(a[0]))
break
共享素数攻击
共享素数是指RSA加密时进行了两次加密，并且给出了加密钥e，两次加密的n1和n2，密文c。
[CISCN 2021初赛]rsa
题目：
from flag import text,flag import md5 from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime assert md5.new(text).hexdigest() == flag[6:-1] msg1 = text[:xx] msg2 = text[xx:yy] msg3 = text[yy:] msg1 = bytes_to_long(msg1) msg2 = bytes_to_long(msg2) msg3 = bytes_to_long(msg3) p1 = getPrime(512) q1 = getPrime(512) N1 = p1*q1 e1 = 3 print pow(msg1,e1,N1) print (e1,N1) p2 = getPrime(512) q2 = getPrime(512) N2 = p2*q2 e2 = 17 e3 = 65537 print pow(msg2,e2,N2) print pow(msg2,e3,N2) print (e2,N2) print (e3,N2) p3 = getPrime(512) q3 = getPrime(512) N3 = p3*q3 print pow(msg3,e3,N3) print (e3,N3) print p3>>200 19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893 (3, 123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009L) 54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610 91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950 (17, 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977L) (65537, 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977L) 59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646 (65537, 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147L) 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902s
思路：
题目给出了一堆参数 梳理一下
密文分成三部分m1 m2 m3
质数p1 q1 p2 q2 p3 q3
模数n1 n2 n3(均已知)
加密参数：e1=3 e2=17 e3=65537
密文：
c1=pow(m1,e1,n1)
c2=pow(m2,e2,n2)
c3=pow(m2,e3,n2)
c4=pow(m3,e3,n3)
第一部分：
c1 e=3 太小了一眼小明文攻击
第二部分：共同的模妥妥的共模攻击
c2 c3 同n2共模攻击
第三部分比较迷糊
一开始以为是共享素数攻击因为存在共同的e3,后面发现还输出了 p3>>200
这里猜测应该是针对p进行一些操作的攻击（因为给出了p的一些位数上的信息，又给出了n3），似乎是一种新的攻击方式。
查了一下果然有，找到了下面几篇文章（！！！！！涨知识啦）
对RSA-Factoring with High Bits Known理解
在进行p高位求解时可以在网站Sage Cell Server (sagemath.org)
本题p高位求解代码如下：
#sage
#p4已知高位
p4 = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
n = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
#全位数
pbits = 512
#缺省位数
kbits = pbits - p4.nbits()#nbits()位数
print (p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
p = p4+x0
print ("p: ", hex(int(p)))
assert n % p == 0得到三个密文拼接后md5加密即可
解题：
from gmpy2 import *
from Crypto.Util.number import *
from hashlib import md5
#第一部分小明文
e = 3
n1 = 123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009
c1 = 19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
k = 0
while 1:
res = iroot(k*n1+c1,e)
if(res[1] == True):
m1 = res[0]
break
k += 1
#第二部分共模攻击
e3 = 65537
e2 = 17
n2 = 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977
c2_1 = 54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
c2_2 = 91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
s = gmpy2.gcdext(e2,e3)
m2_1 = pow(c2_1,s[1],n2)
m2_2 = pow(c2_2,s[2],n2)
m2 = (m2_1*m2_2)%n2
#第三部分p高位泄露攻击
e3 = 65537
n3 = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
c3 = 59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
p3_200 = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
p = int('0xda5f14bacd97f5504f39eeef22af37e8551700296843e536760cea761d334508003e01b886c0c69b4365759fb42a3faaf0c8888106bb9dbb1137769a37d191a7',16)
#需要转成16位后正常求解即可
q = n3 // p
d3 = invert(e3,(p-1)*(q-1))
m3 = pow(c3,d3,n3)
flag = long_to_bytes(m1)+long_to_bytes(m2)+long_to_bytes(m3)
print(md5(flag).hexdigest())[羊城杯 2021 ]BigRSA
题目：
from Crypto.Util.number import *
from flag import *
n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n1)
c = pow(c, e, n2)
print("c = %d" % c)
# output
# c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264上述题目中给出了几个关键的数，n1,n2,e,c。很明显是RSA的题目，但是我们知道RSA题目的目的就是通过获取每一个密文的d对模进行解密。但是题目中并没有给出该d。此时可以猜测n1和n2是否存在共享素数来解题。通过共享素数p=gcd(n1,n2)求取对应模n的q以及欧拉函数Ф(n)，再通过Ф(n)以及e获取对应的d实现求解。由于当前题目只进行了两次加密，因此只需要通过对 对应模n、d和c的两次解密即可。
解题：
import gmpy2 from Crypto.Util.number import * c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264 n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061 n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073 e = 65537 q = gmpy2.gcd(n1, n2)#求n1和n2的最大公因数 p1 = n1 // q p2 = n2 // q fn1 = (q - 1) * (p1 - 1) # 求下面的&n fn2 = (q - 1) * (p2 - 1) # 求上面的&n d1 = gmpy2.invert(e, fn1) # (de)mod((p-1)*(q-1))=1 求到第一次解密密钥d1 d2 = gmpy2.invert(e, fn2) # 求出第二次解密密钥d2 m = pow(c, d2, n2) # 先对第二次加密进行解密 m = pow(m, d1, n1) # 用第二次解密结果继续解密 print(long_to_bytes(m))
[SWPU 2020]happy
题目：
('c=', '0x7a7e031f14f6b6c3292d11a41161d2491ce8bcdc67ef1baa9eL')
('e=', '0x872a335')
#q + q*p^3 =1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586
#qp + q *p^2 = 1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594思路：
发现题目并没有明确给出 n p q 这需要我们根据题目给出的条件自己求
a=q + q*p^3 =q*(1+p)*(p^2-p+1)
b=qp + q *p^2 =q*p*(1+p)
发现a和b存在公约数gcd(a,b)=q*(1+p)
p=b//gcd(a,b)
q=gcd(a,b)//(p+1)
p q 已经给出了只需要根据
n=p*q
Ф(n)=(p-1)*(q-1)
d为e模Ф(n)的逆元
m=pow(c,d,n)
解题：
import gmpy2 from Crypto.Util.number import * a=1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586 b=1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594 p=b//gmpy2.gcd(a,b) q=gmpy2.gcd(a,b)//(1+p) # q = 827089796345539312201480770649 # p = 1158310153629932205401500375817 c = 0x7a7e031f14f6b6c3292d11a41161d2491ce8bcdc67ef1baa9e e = 0x872a335 n = p*q d = gmpy2.invert(e,(p-1)*(q-1)) m = pow(c,d,n) print(long_to_bytes(m))
[BJDCTF 2020]rsa
题目：
from Crypto.Util.number import getPrime,bytes_to_long
flag=open("flag","rb").read()
p=getPrime(1024)
q=getPrime(1024)
assert(e<100000)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print c,n
print pow(294,e,n)
p=getPrime(1024)
n=p*q
m=bytes_to_long("BJD"*32)
c=pow(m,e,n)
print c,n
'''
output:
12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120 13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
'''思路：
题目给出了5个参数c n c1 c2 n2 还有隐藏参数m2
其中
c=m^e(mod n)
c1=294^e(mod n)
c2=m2^e(mod n2)
n1=p*q
n2=p1*q
可以看出来gcd(n1,n2)=q 但是想要知道m还需要知道d的值
d的值需要通过Ф(n)和e来得到，题目已经给出了e的范围，此时可以通过爆破294^e(mod n)对比c2的值得到e p=n//q
e有了通过求取Ф(n)=(p-1)*(q-1)
d=gmpy2.invert(e, Ф(n))
m=pow(c,d,n)
解题:
import gmpy2
from Crypto.Util.number import *
#output:
c = 12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
n = 13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
c1 = 381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
c2 = 979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721
n2 = 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
q = gmpy2.gcd(n,n2)
p = n // q
for e in range(100000):
if c1 == pow(294,e,n):
print('e = ',e)
break
m = pow(c, gmpy2.invert(e, (q-1) * (p-1)), n)
print(long_to_bytes(m))[闽盾杯 2021]decode
题目：
n1: 15228664629164509105936278301396170708905691970126305196584505186788860519598413718493859625462561931380632032431490419378905593909771649295663481782473029836321132574188559245931660756414915507930357509270674460219615256962333464689419869130366867401404262606367700782040693275068101244535880649261286041921882470460606034302142183971677715439862839410834231609821777031530457674591868138859358815039755085358568037032478394036448363183057305077227769673701227083943898736796552550712057417053897722979700329662099072959306298177351997084389916443815546425080826441671985030755256185725913397986385179516049927425591 n2: 28182418532443955655250943929828439725377604572088962537896240628709829618999901367131159759359513146864646169253348651905865895468151210748207509325666501438590382812326109260537618829438786609626137074778638549998280533912080708785604673270460635181275360847313985764185991865570533815651261638439461846512012164531330949433517277559149828806588070421852157781670188281908625986974579194819272643409859915715455134433970119584552350648013116998668938513347083566970423327936691885137812528912263666957628197241313496232397910546498542303925205356813548741679943691886217742767778075067797422624969714343428365022749 n3: 18355811159408154065817199279776805621878757240392366715869421799780946779485225342662736231980532326015283372375030686507311099745671828649419794838611580909610100636296701054995302819692794479292794716441442731393027118795245239019609474743841061251498233337758043553376098591254587406941205804917663153256036922860462415387926973551020540123742773938055950168965005226319984869124543783579240130888344231027912143592472823564266887957101575622993773291455143915263715932280728961208233983782906070719786115187115449430196335973764600533097718947377609348244073036523422892353195107093782201003551217830556519184839 e1: 65537 e2: 27751 e3: 65537 c1: 5368342382489380107251269030258282008067103595899117880173297169710980852124379736420135829984131832023988667774795223808420069001078159756328642298736759964890517323144475742861501409284299556459601222657540302786301791897975932176538612601162552795835603779910738886150925504885639254302406755008796950704938463132687940418772021406619622090999564746948113296328739593309200238996686945891130656599419832796482095787039339269564880847130379179831744694000940207887150388411084465949903406848727641093033681144598595895383689139227400553234701993087147186292040330589331703587405822925483701667354935313494938769206 c2: 21521672635651854919517759696514027081496995002884626306313384597771682621826437868933822942195279941318573525337109548152966094293276717095298929811895186384560362917891928656637913236676702009205642367801075592458101830488916914437754803979953027152373619293870115731171449223105986403604973873007338969000153480949617700626516389419935352576014084068271819009465242491467427642787306345049280205827574043586767133396458785487959251540831856187380154825027964867977651727983254127239427622549059938701125498520279503972702883327594442747467858234391945790597844344295786118320620376681461727686876948563884520137741 c3: 13940747781246179701167820858098775936269078279837839169409057305686612176371099274767269714494905207551971162649902129137425806839867713157472497469542260664882313041602553845621113546259276402534229231780532278276697961222319054833980226978574905974878218905613341365260453461080117407529132948986104191917111000811731784483944945364091757083949827612260904757837644538366763161154611658652020868326985526984718638276184626634240096213703958275241215175054246685206226179114590838833694648062135027841593419815101363262701960507235056752424778384286627997500871204804629047307688466887868894491042058198480775705486
思路：
给出了三组n e c分别是n1 e1 c1 n2 e2 c2 n3 e3 c3，其中e1=e3,e相同，n不同的情况直接共享素数攻击啦。
遇到这种只给多组参数的情况首选共享素数攻击。
先gcd n1 n2 n3两两之间的共享素数然后直接Ф(n1),Ф(n2),Ф(n3),在然后mi=pow(ci,Ф(ni),ni)
解题：
import libnum e1 = 65537 e2 = 27751 e3 = 65537 n1 = 15228664629164509105936278301396170708905691970126305196584505186788860519598413718493859625462561931380632032431490419378905593909771649295663481782473029836321132574188559245931660756414915507930357509270674460219615256962333464689419869130366867401404262606367700782040693275068101244535880649261286041921882470460606034302142183971677715439862839410834231609821777031530457674591868138859358815039755085358568037032478394036448363183057305077227769673701227083943898736796552550712057417053897722979700329662099072959306298177351997084389916443815546425080826441671985030755256185725913397986385179516049927425591 n2 = 28182418532443955655250943929828439725377604572088962537896240628709829618999901367131159759359513146864646169253348651905865895468151210748207509325666501438590382812326109260537618829438786609626137074778638549998280533912080708785604673270460635181275360847313985764185991865570533815651261638439461846512012164531330949433517277559149828806588070421852157781670188281908625986974579194819272643409859915715455134433970119584552350648013116998668938513347083566970423327936691885137812528912263666957628197241313496232397910546498542303925205356813548741679943691886217742767778075067797422624969714343428365022749 n3 = 18355811159408154065817199279776805621878757240392366715869421799780946779485225342662736231980532326015283372375030686507311099745671828649419794838611580909610100636296701054995302819692794479292794716441442731393027118795245239019609474743841061251498233337758043553376098591254587406941205804917663153256036922860462415387926973551020540123742773938055950168965005226319984869124543783579240130888344231027912143592472823564266887957101575622993773291455143915263715932280728961208233983782906070719786115187115449430196335973764600533097718947377609348244073036523422892353195107093782201003551217830556519184839 c1 = 5368342382489380107251269030258282008067103595899117880173297169710980852124379736420135829984131832023988667774795223808420069001078159756328642298736759964890517323144475742861501409284299556459601222657540302786301791897975932176538612601162552795835603779910738886150925504885639254302406755008796950704938463132687940418772021406619622090999564746948113296328739593309200238996686945891130656599419832796482095787039339269564880847130379179831744694000940207887150388411084465949903406848727641093033681144598595895383689139227400553234701993087147186292040330589331703587405822925483701667354935313494938769206 c2 = 21521672635651854919517759696514027081496995002884626306313384597771682621826437868933822942195279941318573525337109548152966094293276717095298929811895186384560362917891928656637913236676702009205642367801075592458101830488916914437754803979953027152373619293870115731171449223105986403604973873007338969000153480949617700626516389419935352576014084068271819009465242491467427642787306345049280205827574043586767133396458785487959251540831856187380154825027964867977651727983254127239427622549059938701125498520279503972702883327594442747467858234391945790597844344295786118320620376681461727686876948563884520137741 c3 = 13940747781246179701167820858098775936269078279837839169409057305686612176371099274767269714494905207551971162649902129137425806839867713157472497469542260664882313041602553845621113546259276402534229231780532278276697961222319054833980226978574905974878218905613341365260453461080117407529132948986104191917111000811731784483944945364091757083949827612260904757837644538366763161154611658652020868326985526984718638276184626634240096213703958275241215175054246685206226179114590838833694648062135027841593419815101363262701960507235056752424778384286627997500871204804629047307688466887868894491042058198480775705486 p1 = libnum.gcd(n1,n2) p2 = libnum.gcd(n2,n3) q1 = n1//p1 q2 = n2 //p1 q3 = n3// p2 phi_1 = (p1-1)*(q1-1) phi_2 = (p1-1)*(q2-1) phi_3 = (p2-1)*(q3-1) d1 = libnum.invmod(e1,phi_1) d2 = libnum.invmod(e2,phi_2) d3 = libnum.invmod(e3,phi_3) print(libnum.n2s(pow(c1,d1,n1))) print(libnum.n2s(pow(c2,d2,n2))) print(libnum.n2s(pow(c3,d3,n3)))
已知高位攻击 CopperSmith
参考文献：
对RSA-Factoring with High Bits Known理解
找到的了V师傅的三篇文章 他很好得翻译了《Coppersmith’s Method and Related Applications》这篇文章中关于Coppersmith攻击的数学方面的论证，同时他在第三篇文章给出了几种关于已知高位攻击的几种类型的题目以及相关代码和数学论证。V师傅翻译的比较好，我就不在这里献丑了。大家去看他的文章就行了。
密码学学习笔记之Coppersmith’s Method （二）
密码学学习笔记之Coppersmith’s Method （三）
[鹤城杯 2021]BabyRSA
题目：
from Crypto.Util.number import getPrime, bytes_to_long from secret import flag p = getPrime(1024) q = getPrime(1024) n = p * q e = 65537 hint1 = p >> 724 hint2 = q % (2 ** 265) ct = pow(bytes_to_long(flag), e, n) print(hint1) print(hint2) print(n) print(ct) hint1=1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479 hint2=40812438243894343296354573724131194431453023461572200856406939246297219541329623 n=21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969 ct=19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
思路：
第一眼直接锁定p已知高位攻击
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
此时我们注意到两个值hint1和hint2
hint1 = p >> 724 左移724位
hint2 = q % (2 ** 265)=>q≡hint2 mod(2 ** 265)
n=p*q
上面三个公式是存在关联的
不过公式2是取余
那么我们对第三个公式也取余看看
令m=pow(2,265)=2^265
n%m=(p*q)%m
->n%m=((p%m)*(q%m))%m
此时令
p0=(p%m)
则上述推导可以变成
n%m=(p0*(q%m))%m
由于公式2
q≡hint2 mod m
此时 将公式2带入
n%m=(p0*hint2)%m
变成同余的形式
n≡(p0*hint2)mod m
此时对两边取hint2的逆
可以得到
p0≡n*hint2^-1 mod m
此时得到了关于p的模m的余数
换成代码就是
p0=n*invert(hint2,mod)%mod
ok
此时我们知道了
hint1是p二进制的右移724位
前面较小的724位被吃掉
如果此时我们直接令
p1=hint1<<724
则此时p1的表达形式为(hint1)00000000 一共724个0
但是在上面我们以及求出了p模2^265的余数
令p2=p1+p0可以得到(hint1)0000.....0(p0)的表达形式
此时我们知道了p的300位高位和265位低位(可能吧，谁知道模掉后的是多少位呢反正我去不算低位
ok此时我们还有两个重要条件
n=p*q
hint2 = q % (2 ** 265)
hint2是q模去m后的低位
接下来就是最重要的部分
coppersmith部分
研究中
找到了一个wp的代码不知道是不是可行的 仅供参考
下列代码需要下载sage math
解题：
from gmpy2 import *
from Crypto.Util.number import *
p1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q0 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
mod=pow(2,265)
p0=n*invert(q0,mod)%mod
pbar=(p1<<724)+p0
PR.<x> = PolynomialRing(Zmod(n))
for i in range(32):
f=pbar+x*mod*32
f=f.monic()
pp=f.small_roots(X=2^454,beta=0.4)
if(pp):
break
pbar+=mod
p=pbar+pp[0]*32*mod
assert n%p==0
print(p)
q=n//p
phi=(p-1)*(q-1)
e=65537
d=invert(e,phi)
c=19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
m=pow(c,d,n)
print(long_to_bytes(m))
#flag{ef5e1582-8116-4f61-b458-f793dc03f2ff}
维纳攻击
特征是e的值（位数）非常接近n
在通过维纳攻击解题时，需要考虑两个问题
1.什么样的题目可以通过维纳攻击解题
换句话说就是可以用维纳攻击解题的题目有哪些特征
2.维纳攻击的攻击可行性
首先是第一个问题：
1.什么样的题目可以通过维纳攻击求解呢？
上面给出了特征：e较大的时候可以通过维纳攻击求解
当然如果通过题目只给出了n,c,e(远大于3，较小的时候可以直接开放)，且符合上述特征的时候可以考虑维纳攻击。
2.维纳攻击的攻击方式
维纳攻击是一种依靠连分数进行渐进覆盖的一种攻击方式。
ok 这里我们需要证明根据维纳攻击给出的条件，我们所需要的结果是符合渐进数收敛的。
需要证明收敛需要依赖形如下理论
保证维纳攻击通过连分数的攻击形式是有解的
证明如：Wiener's Attack Ride(维纳攻击法驾驭) 这篇文章写的超好
证明收敛之后，可以将e/N以连分数的方式展开，筛选出可以被整除的数即为所求。
参考文献 ：
Wiener's Attack Ride(维纳攻击法驾驭) z2333师傅大作
[HGAME 2022 week3]RSA attack 3
题目：
from Crypto.Util.number import getPrime
from gmpy2 import invert
from libnum import s2n
from secret import flag
p = getPrime(2048)
q = getPrime(2048)
n = p * q
d = getPrime(64)
e = invert(d, (p - 1) * (q - 1))
c = pow(s2n(flag), e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
n = 507419170088344932990702256911694788408493968749527614421614568612944144764889717229444020813658893362983714454159980719026366361318789415279417172858536381938870379267670180128174798344744371725609827872339512302232610590888649555446972990419313445687852636305518801236132032618350847705234643521557851434711389664130274468354405273873218264222293858509477860634889001898462547712800153111774564939279190835857445378261920532206352364005840238252284065587291779196975457288580812526597185332036342330147250312262816994625317482869849388424397437470502449815132000588425028055964432298176942124697105509057090546600330760364385753313923003549670107599757996810939165300581847068233156887269181096893089415302163770884312255957584660964506028002922164767453287973102961910781312351686488047510932997937700597992705557881172640175117476017503918294534205898046483981707558521558992058512940087192655700351675718815723840568640509355338482631416345193176708501897458649841539192993142790402734898948352382350766125000186026261167277014748183012844440603384989647664190074853086693408529737767147592432979469020671772152652865219092597717869942730499507426269170189547020660681363276871874469322437194397171763927907099922324375991793759
e = 77310199867448677782081572109343472783781135641712597643597122591443011229091533516758925238949755491395489408922437493670252550920826641442189683907973926843505436730014899918587477913032286153545247063493885982941194996251799882984145155733050069564485120660716110828110738784644223519725613280140006783618393995138076030616463398284819550627612102010214315235269945251741407899692274978642663650687157736417831290404871181902463904311095448368498432147292938825418930527188720696497596867575843476810225152659244529481480993843168383016583068747733118703000287423374094051895724494193455175131120243097065270804457787026492578916584536863548445813916819417857064037664101684455000184987531252344582899589746272173970083733130106407810619258077266603898529285634495710846838011858287024329514491058790557305041389614650730267774482954666726949886313386881066593946789460028399523245777171320319444673551268379126203862576627540177888290265714418064334752499940587750374552330008143708562065940245637685833371348603338834447212248648869514585047871442060412622164276894766238383894693759347590977926306581080390685360615407766600573527565016914830132066428454738135380178959590692145577418811677639050929791996313180297924833690095
c = 165251729917394529793163344300848992394021337429474789711805041655116845722480301677817165053253655027459227404782607373107477419083333844871948673626672704233977397989843349633720167495862807995411682262559392496273163155214888276398332204954185252030616473235814999366132031184631541209554169938146205402400412307638567132128690379079483633171535375278689326189057930259534983374296873110199636558962144635514392282351103900375366360933088605794654279480277782805401749872568584335215630740265944133347038070337891035560658434763924576508969938866566235926587685108811154229747423410476421860059769485356567301897413767088823807510568561254627099309752215808220067495561412081320541540679503218232020279947159175547517811501280846596226165148013762293861131544331444165070186672186027410082671602892508739473724143698396105392623164025712124329254933353509384748403154342322725203183050328143736631333990445537119855865348221215277608372952942702104088940952142851523651639574409075484106857403651453121036577767672430612728022444370874223001778580387635197325043524719396707713385963432915855227152371800527536048555551237729690663544828830627192867570345853910196397851763591543484023134551876591248557980182981967782409054277224
思路：
乍一看题目很简单 ，常规的RSA题目
但是题目比常规RSA缺少了关于pq的提示，题目中只有 两点与常规RSA不同的地方，
(1)m=s2n(flag) 字符串转为二进制无关紧要
(2)e是一个相当大的数字
考虑到n=p*q d=gmpy2.invert(e,(p-1)*(q-1))
d特别小
查了一下：维纳攻击
解题：
import gmpy2
import libnum
def continuedFra(x, y):
cf = []
while y:
cf.append(x // y)
x, y = y, x % y
return cf
def gradualFra(cf):
numerator = 0
denominator = 1
for x in cf[::-1]:
numerator, denominator = denominator, x * denominator + numerator
return numerator, denominator
def solve_pq(a, b, c):
par = gmpy2.isqrt(b * b - 4 * a * c)
return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):
gf = []
for i in range(1, len(cf) + 1):
gf.append(gradualFra(cf[:i]))
return gf
def wienerAttack(e, n):
cf = continuedFra(e, n)
gf = getGradualFra(cf)
for d, k in gf:
if k == 0: continue
if (e * d - 1) % k != 0:
continue
phi = (e * d - 1) // k
p, q = solve_pq(1, n - phi + 1, n)
if p * q == n:
return d
n= 507419170088344932990702256911694788408493968749527614421614568612944144764889717229444020813658893362983714454159980719026366361318789415279417172858536381938870379267670180128174798344744371725609827872339512302232610590888649555446972990419313445687852636305518801236132032618350847705234643521557851434711389664130274468354405273873218264222293858509477860634889001898462547712800153111774564939279190835857445378261920532206352364005840238252284065587291779196975457288580812526597185332036342330147250312262816994625317482869849388424397437470502449815132000588425028055964432298176942124697105509057090546600330760364385753313923003549670107599757996810939165300581847068233156887269181096893089415302163770884312255957584660964506028002922164767453287973102961910781312351686488047510932997937700597992705557881172640175117476017503918294534205898046483981707558521558992058512940087192655700351675718815723840568640509355338482631416345193176708501897458649841539192993142790402734898948352382350766125000186026261167277014748183012844440603384989647664190074853086693408529737767147592432979469020671772152652865219092597717869942730499507426269170189547020660681363276871874469322437194397171763927907099922324375991793759
e= 77310199867448677782081572109343472783781135641712597643597122591443011229091533516758925238949755491395489408922437493670252550920826641442189683907973926843505436730014899918587477913032286153545247063493885982941194996251799882984145155733050069564485120660716110828110738784644223519725613280140006783618393995138076030616463398284819550627612102010214315235269945251741407899692274978642663650687157736417831290404871181902463904311095448368498432147292938825418930527188720696497596867575843476810225152659244529481480993843168383016583068747733118703000287423374094051895724494193455175131120243097065270804457787026492578916584536863548445813916819417857064037664101684455000184987531252344582899589746272173970083733130106407810619258077266603898529285634495710846838011858287024329514491058790557305041389614650730267774482954666726949886313386881066593946789460028399523245777171320319444673551268379126203862576627540177888290265714418064334752499940587750374552330008143708562065940245637685833371348603338834447212248648869514585047871442060412622164276894766238383894693759347590977926306581080390685360615407766600573527565016914830132066428454738135380178959590692145577418811677639050929791996313180297924833690095
c= 165251729917394529793163344300848992394021337429474789711805041655116845722480301677817165053253655027459227404782607373107477419083333844871948673626672704233977397989843349633720167495862807995411682262559392496273163155214888276398332204954185252030616473235814999366132031184631541209554169938146205402400412307638567132128690379079483633171535375278689326189057930259534983374296873110199636558962144635514392282351103900375366360933088605794654279480277782805401749872568584335215630740265944133347038070337891035560658434763924576508969938866566235926587685108811154229747423410476421860059769485356567301897413767088823807510568561254627099309752215808220067495561412081320541540679503218232020279947159175547517811501280846596226165148013762293861131544331444165070186672186027410082671602892508739473724143698396105392623164025712124329254933353509384748403154342322725203183050328143736631333990445537119855865348221215277608372952942702104088940952142851523651639574409075484106857403651453121036577767672430612728022444370874223001778580387635197325043524719396707713385963432915855227152371800527536048555551237729690663544828830627192867570345853910196397851763591543484023134551876591248557980182981967782409054277224
d=wienerAttack(e, n)
m=pow(c, d, n)
print(libnum.n2s(m).decode())[羊城杯 2020]RRRRRRRSA
题目：
import hashlib
import sympy
from Crypto.Util.number import *
flag = 'GWHT{************}'
flag1 = flag[:19].encode() #两截flag
flag2 = flag[19:].encode()
assert(len(flag) == 38)
P1 = getPrime(1038)
P2 = sympy.nextprime(P1) #p2>p1
assert(P2 - P1 < 1000)
Q1 = getPrime(512)
Q2 = sympy.nextprime(Q1) #q2>q1
N1 = P1 * P1 * Q1
N2 = P2 * P2 * Q2
E1 = getPrime(1024)
E2 = sympy.nextprime(E1)
m1 = bytes_to_long(flag1)
m2 = bytes_to_long(flag2)
c1 = pow(m1, E1, N1)
c2 = pow(m2, E2, N2)
output = open('secret', 'w')
output.write('N1=' + str(N1) + '\n')
output.write('c1=' + str(c1) + '\n')
output.write('E1=' + str(E1) + '\n')
output.write('N2=' + str(N2) + '\n')
output.write('c2=' + str(c2) + '\n')
output.write('E2=' + str(E2) + '\n')
output.close()
N1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347 c1=55094296873556883585060020895253176070835143350249581136609315815308788255684072804968957510292559743192424646169207794748893753882418256401223641287546922358162629295622258913168323493447075410872354874300793298956869374606043622559405978242734950156459436487837698668489891733875650048466360950142617732135781244969524095348835624828008115829566644654403962285001724209210887446203934276651265377137788183939798543755386888532680013170540716736656670269251318800501517579803401154996881233025210176293554542024052540093890387437964747460765498713092018160196637928204190194154199389276666685436565665236397481709703644555328705818892269499380797044554054118656321389474821224725533693520856047736578402581854165941599254178019515615183102894716647680969742744705218868455450832 E1=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820423103 N2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121 c2=39328446140156257571484184713861319722905864197556720730852773059147902283123252767651430278357950872626778348596897711320942449693270603776870301102881405303651558719085454281142395652056217241751656631812580544180434349840236919765433122389116860827593711593732385562328255759509355298662361508611531972386995239908513273236239858854586845849686865360780290350287139092143587037396801704351692736985955152935601987758859759421886670907735120137698039900161327397951758852875291442188850946273771733011504922325622240838288097946309825051094566685479503461938502373520983684296658971700922069426788236476575236189040102848418547634290214175167767431475003216056701094275899211419979340802711684989710130215926526387138538819531199810841475218142606691152928236362534181622201347 E2=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820425393
思路：
先查看特征：
e位数较大，盲猜winner
不过：这次N不大一样，是由三个素数相乘获得
N1 = P1 * P1 * Q1=P1^2*Q1
N2 = P2 * P2 * Q2=P2^2*Q2
同时也给出了c1和c2
此不能直接用winnerAttack的
但是题目中给出了其他的提示：
P1 = getPrime(1038)
P2 = sympy.nextprime(P1) #p2>p1
assert(P2 - P1 < 1000)
Q1 = getPrime(512)
Q2 = sympy.nextprime(Q1) #q2>q1
大小关系
大小关系唯一有用的地方就是比值了，此时我们根据winner攻击想到连分数的展开覆盖
ok思路有了
接下来就是写代码
代码的核心为两部分
第一部分：以维纳攻击相同的攻击方式连分数的渐进数求解
N1/N2 <p1/p2 ; N1/N2<q1/q2
所以q1/q2在区间(N1/N2,1)之间。
尝试对N1/N2进行连分数展开并求其各项渐进分数，记为ti/si，并验证N1%ti==0是否成立。
如果成立,那么return。
第二部分：N1 =P1^2*Q1 对此类N的e求d
参考一下数论的知识
解题：（Z2333师傅的代码，上面那篇关于winner攻击的文章也是Z2333师傅写的）
import gmpy2
N1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
c1=55094296873556883585060020895253176070835143350249581136609315815308788255684072804968957510292559743192424646169207794748893753882418256401223641287546922358162629295622258913168323493447075410872354874300793298956869374606043622559405978242734950156459436487837698668489891733875650048466360950142617732135781244969524095348835624828008115829566644654403962285001724209210887446203934276651265377137788183939798543755386888532680013170540716736656670269251318800501517579803401154996881233025210176293554542024052540093890387437964747460765498713092018160196637928204190194154199389276666685436565665236397481709703644555328705818892269499380797044554054118656321389474821224725533693520856047736578402581854165941599254178019515615183102894716647680969742744705218868455450832
E1=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820423103
N2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
c2=39328446140156257571484184713861319722905864197556720730852773059147902283123252767651430278357950872626778348596897711320942449693270603776870301102881405303651558719085454281142395652056217241751656631812580544180434349840236919765433122389116860827593711593732385562328255759509355298662361508611531972386995239908513273236239858854586845849686865360780290350287139092143587037396801704351692736985955152935601987758859759421886670907735120137698039900161327397951758852875291442188850946273771733011504922325622240838288097946309825051094566685479503461938502373520983684296658971700922069426788236476575236189040102848418547634290214175167767431475003216056701094275899211419979340802711684989710130215926526387138538819531199810841475218142606691152928236362534181622201347
E2=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820425393
def continuedFra(x, y):
cF = []
while y:
cF += [x // y]
x, y = y, x % y
return cF
def Simplify(ctnf):
numerator = 0
denominator = 1
for x in ctnf[::-1]:
numerator, denominator = denominator, x * denominator + numerator
return (numerator, denominator)
def getit(c):
cf=[]
for i in range(1,len(c)):
cf.append(Simplify(c[:i]))
return cf
#求渐进分数
def wienerAttack(e, n):
cf=continuedFra(e,n)
for (p2,p1) in getit(cf):
if p1 == 0:
continue
if N1%p1==0 and p1!=1:
return p1
print('not find!')
q1=wienerAttack(N1,N2)
#p1=11628371843051760370952910026406764366191062991235308941262037248377376991693250742343307155422036713746576338866595433599862614339347536916226536644210947
print(q1)
p1=gmpy2.iroot(N1//q1,2)[0]
p2=gmpy2.next_prime(p1)
q2=gmpy2.next_prime(q1)
phi1=p1*(p1-1)*(q1-1)
phi2=p2*(p2-1)*(q2-1)
d1=gmpy2.invert(E1,phi1)
d2=gmpy2.invert(E2,phi2)
from Crypto.Util import number
m1=number.long_to_bytes(gmpy2.powmod(c1,d1,N1))
m2=number.long_to_bytes(gmpy2.powmod(c2,d2,N2))
print((m1+m2))
威尔逊定理
这里先给出威尔逊定理的定义
这里解释一下威尔逊定理
素数p一定是奇数（若是偶数一定会被整除）
（p-1）！=1*2*.....*p-1
这里我们定义一个乘群（完全符合乘群的特征,这里不做证明）
1.乘法封闭
2.单位元存在于群中
3.元素可逆，且逆元在群中
Zp×={1，2，3，........，p-1}(乘群下不考虑0这个元素，因为0元素没有逆)
（这里的每一个元素都代表各自的剩余类比如1+Zp,2+Zp,）
因为是乘群，所以每个元素都有对应的逆元，此时我们并不知道每个元素这个逆元在哪里。
但是在群中逆元只有两种可能性
- 元素等于逆元，即a=a^-1
- 元素不等于逆元，即a≠a^-1
此时我们仅考虑第一种，a=a^-1
a*a^-1≡1(mod p)=>a^2≡1(mod p)=>a^2-1≡0(mod p)=>(a-1)(a+1)≡0(mod p)
即p|(a-1)或者p|(a+1)
=>a=p+1或者a=p-1
Ok
此时找到了元素等于逆元的两个元素了1和p-1
即p-1≡-1(mod p)(可能有人会觉得这是废话，但是这是我们需要的，我们这里证明的是除了这两个元素之外没有其他元素的逆是自身的)
此时我们考虑第二种：元素不等于逆元，即a≠a^-1
除了1和p-1这两个元素外，其他元素的逆都是可配对的，而此时群中元素个数为偶数。ok，相乘后模p全是1
因此此1*2*.....*p-1=（p-1）！≡1*1*....*(p-1)≡-1(mod p)
证毕
[RoarCTF 2019]babyRSA
题目：
import sympy
import random
def myGetPrime():
A= getPrime(513)
print(A)
B=A-random.randint(1e3,1e5)
print(B)
return sympy.nextPrime((B!)%A)
p=myGetPrime()
#A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
#B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
q=myGetPrime()
#A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
#B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
r=myGetPrime()
n=p*q*r
#n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
#e=0x1001
#c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
#so,what is the flag?思路：
只有两个A,B直接输出的
但是三个参数p,q,r比较难确定
但是根据myGetPrime()
返回的值为(B!)%A
B!,A，返回值为余数
锁定威尔逊定理
以p为例子
p = sympy.nextPrime((B1!)%A1)
不考虑sympy.nextPrime（）//这里为比当前数更大的下一个素数
p=(B1!)%A1
此时我们需要知道(B1!)模A1得到的余数，正常算的话太难了
根据威尔逊定理
(A1-1) !≡ -1 ( mod A1 )
变换一下
(B1)!*[(A1-1) !/(B1)!]≡ -1 ( mod A1 )
在变换一下
(B1)!≡-1*[(B1) !/(A1-1)!] ( mod A1 )
此时只需要计算k=-1*[(B1) !/(A1-1)!] ( mod A1 )的值即可，因为上下怼掉之后去掉了很多数
但是A明显大于B因此-1*[(B1) !/(A1-1)!] ( mod A1 )需要取反取逆
此时再通过p = sympy.nextPrime(k)就可以得到p的值
同理于q,
由于n=p*q*r
知道n,p,q自然能得到r
剩下的，关于求d的值，三个值都不一样，直接挨个减一相乘即可
解题：
import gmpy2 import sympy import gmpy2 from Crypto.Util.number import * def getPrime(A, B): k = 1 for i in range(B+1, A): k = (k*i) % A res = (-gmpy2.invert(k, A)) % A return sympy.nextprime(res)
A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407 B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596 A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927 B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026 n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733 e=0x1001 c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428 p = getPrime(A1, B1) q = getPrime(A2, B2) r = n//(p*q) d = gmpy2.invert(e,(p-1)*(q-1)*(r-1)) m = gmpy2.powmod(c, d, n) print(m) //m=49562188096458630410563044417358818341913265571373725266976612126526106528404944745044614126232074073813936259453 //出来的数据还带处理一下 print(long_to_bytes(m))
已在FreeBuf发表 0 篇文章
本文为 独立观点，未经允许不得转载，授权请联系FreeBuf客服小蜜蜂，微信：freebee2022
被以下专辑收录，发现更多精彩内容
+ 收入我的专辑
+ 加入我的收藏
相关推荐
- 0 文章数
- 0 关注者
文章目录