算法(施工中)

手机

英国房地产因利率上升陷入困境房价正以2011年来最快速度下跌

宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

家电

算法(施工中)

2023-07-12 11:00:52 来源：博客园

解方程

1，sympy 中的 solve 解法

1 import sympy   # 引入解方程的专业模块sympy 2  3 p,q = sympy.symbols("p q ")   # 申明未知数"p"和"q" 4  5 n = 2230791374046346835775433548641067593691369485828070649075162141394476183565187654365131822111419512477883295758461313983481545182887415447403634720326639070667688614534290859200753589300443797 6 hint = 392490868359411675557103683163021977774935163924606169241731307258226973701652855448542714274348304997416149742779376023311152228735117186027560227613656229190807480010615064372521942836446425717660375242197759811804760170129768647414717571386950790115746414735411766002368288743086845078803312201707960465419405926186622999423245762570917629351110970429987377475979058821154568001902541710817731089463915930932142007312230897818177067675996751110894377356758932 7 flag = sympy.solve([p*q-n,p**3-q**5-hint],[p,q])   # 写入需要解的方程组 8 print(flag) 9 print(flag[0][0])10 print(flag[0][1])11 12 # n = p*q13 # hint = p**3-q**514 # n = 223079137404634683577543354864106759369136948582807064907516214139447618356518765436513182211141951247788329575846131398348154518288741544740363472032663907066768861453429085920075358930044379715 # hint = 392490868359411675557103683163021977774935163924606169241731307258226973701652855448542714274348304997416149742779376023311152228735117186027560227613656229190807480010615064372521942836446425717660375242197759811804760170129768647414717571386950790115746414735411766002368288743086845078803312201707960465419405926186622999423245762570917629351110970429987377475979058821154568001902541710817731089463915930932142007312230897818177067675996751110894377356758932

即可得到 p，q ，后续正常解密即可

如此题：

[BJDCTF 2020]EasyRSA

(资料图)

题目源码：

from Crypto.Util.number import getPrime,bytes_to_longfrom sympy import Derivativefrom fractions import Fractionfrom secret import flagp=getPrime(1024)q=getPrime(1024)e=65537n=p*qz=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:79225478668577614598074915026542162830127761777895115493506729581018102813484022840983101477965494306892538035109948774201355372685494106526544796208586913241103671820256487884070415999430913862275431821577462029470995723896760843927064060843076570001046656966544091550063132039572928857437917151987819742055786547921231915849576652932083904537483691823331528098823124533597061478081989229167627737217266815889771038774541190437448891645293831880774991949329096439186966468769073273647513809531825178831345918108008489717191848087136943429854581030066760134519122210802527359489936926748993998260848486221458154610353211574867762320966747162287218527507025792476601502007280526735983905939328431659588293337228973212727407643458751933330014247301034469480388516855754880120249593322621543776332928024211355652449845755956287290081160205694442396740377762330696188075761324632872961664303262896407293127208586692804597379937471184682515778105696516417850523252424580917923560757156717422882256169788864596855934360837533198809715714526435762673814164655635350099492411587574819831803629689860409700093827219590305673356588015054027536923963779397592332959871600335030825932143675257929100035556043154222969975995514115291470836249448215310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441"""

其实这是道纯数学题，解方程即可，只是关键点在z，z中许多函数不认得

通过搜索引擎即可得到 z 所表示的等式，即 z = p^2 +q^2 , 又 n=p*q，解方程即得 p，q

z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))

exp：

1 import libnum 2 import sympy   # 引入解方程的专业模块sympy 3 import gmpy2 4  5 p,q = sympy.symbols("p q ")   # 申明未知数"x"和"y" 6  7 c = 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035 8 z = 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482 9 n = 1531074516133689541340669000932476620078917924889695194204723544890161235112845930914582554756929847982110124909416186720768653760704744796870875899095013638092474735905257054959409856997063285435182595072975256350228484926373012758638252270395989339232933376092763735305225027419582146902340144384139509641023184359210142659188257340593418867512432699727777523828792840374332429770515173252464121351630658529772219078008818070507035946971986934393910652920479828595751686077438400189277752591616774327241995857205533223205609597944815508246597778148259837199479887191751476750839473044797477032996768176762549539444110 e = 6553711 12 flag = sympy.solve([p*q-n,p**2+q**2-z],[p,q])   # 写入需要解的方程组13 print(flag)14 print(flag[2][0])15 print(flag[2][1])16 print(flag[3][0])17 print(flag[3][1])18 #然后手动输入p，q19 p = 14456483333445607645515664797986269049879669477010052040521893005563359750000957466380395545600443939869966975124962340619954260527118890914596936447634496307859924005818003300044045928155834790987614331394065725273758680305193539259651922696551985947450139196975571209711916392667275358879718081171100420330120 q = 10590919525992134965666457090419924296911090280447773466092733031146099789973162216372896838075729419627726361538652579529308610314213102021512828205030717712596230251548319046856937664375158760601631518573624589643494769152856769627191139817928832960920743539357933293158382935555878430500236087345890702914121 phi = (p-1)*(q-1)22 d = libnum.invmod(e,phi)23 print(libnum.n2s(pow(c,d,n)))24 25 #b"BJD{Advanced_mathematics_is_too_hard!!!}"

2，利用 z3 库解方程

安装库

pip install z3_solver

注意不要安装z3，两个模块不一样，z3 用不了

声明

x = Int("x")#声明整数x = Real("x")#声明实数x = Bool("x")#声明布尔类型a, b, c = Reals("a b c")#批量声明

求解

s = Solver()s.add(p*q==n)s.add(p**2+q**2==z)

输出

check = s.check()print(check)model = s.model()print(model)

一如上题：

1 import libnum 2 from z3 import * 3  4 c = 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035 5 z = 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482 6 n = 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441 7 e = 65537 8  9 p = Int("p")10 q = Int("q")11 s = Solver()12 s.add(p*q==n)13 s.add(p**2+q**2==z)14 check = s.check()15 print(check)16 model = s.model()17 print(model)18 19 #然后手动输入p，q20 p = 14456483333445607645515664797986269049879669477010052040521893005563359750000957466380395545600443939869966975124962340619954260527118890914596936447634496307859924005818003300044045928155834790987614331394065725273758680305193539259651922696551985947450139196975571209711916392667275358879718081171100420330121 q = 10590919525992134965666457090419924296911090280447773466092733031146099789973162216372896838075729419627726361538652579529308610314213102021512828205030717712596230251548319046856937664375158760601631518573624589643494769152856769627191139817928832960920743539357933293158382935555878430500236087345890702914122 phi = (p-1)*(q-1)23 d = libnum.invmod(e,phi)24 print(libnum.n2s(pow(c,d,n)))

z3库的计算学习参考

(66条消息) z3学习笔记（python 3）_python z3_凡_tastic的博客-CSDN博客

运行稍比 sympy 库的solve 解得慢

关键词：

算法(施工中)

解方程

1，sympy 中的 solve 解法

2，利用 z3 库 解方程

2，利用 z3 库解方程