[GYCTF]warm_up

来之不易的warm_up呜呜呜呜,新学到了几个知识点:Rabin算法与这个题中左移的逆运算以及e和φ(n)不互素

题目

from Crypto.Util.number import *
from encode import KEY

q=getPrime(1024)
p=getPrime(1024)
r=getPrime(1024)

s=getPrime(1500)

e1=125794
e2=42373

n1=p*q
n2=p*r
n3=p*q*s
c1=pow(s,e1,n1)
Key=int(KEY.encode('hex'),16)
key_encode=pow(Key,e2,n3)

with open("enc","a")as f:
    f.write("c1: "+str(c1)+"\n")
    f.write("n1: "+str(n1)+"\n")
    f.write("n2: "+str(n2)+"\n")
    f.write("key_encode: "+str(key_encode)+"\n")
from flag import flag
import os


KEY = os.urandom(len(flag))

dec=int(flag.encode('hex'),16)


assert len(bin(dec)[2:])==335
mask=int('1'*335,2)
dec=(dec^dec<<200 )&mask
enc=dec^bytes_to_long(KEY)
print "enc: "+str(enc)

#enc: 17403902166198774030870481073653666694643312949888760770888896025597904503707411677223946079009696809

题目分析

先说个大概思路,后边有详细的分析和知识点记录
①通过求n1,n2的公因数我们可以求出p,进一步分解得到q和r
②从 key_encode=pow(Key,e2,n3)可以看出要想求出key我们必须知道n3,而n3=p*q*s所以我们要通过第一个e和φ(n)不互素类型的RSA求出s
③通过推算可以推导出m * *2 与 c * * b_d同余
④使用rabin算法,算出四个解,长度为1500bit的即为s
⑤知道s后,解出一个由三个素数组成的RSA,求出key
⑥key和给出的enc异或,再进行后续的位操作,即可得到flag

新学习到的知识点

e与φ(n)不互素

学习

推导过程
2159F283E9C0A9BB07475D60797CE006.jpg

Rabin算法

学习
由上面的推断,e=2,使用Rabin算法

推导过程

c ≡ m^2 (mod n)


rabin1.png

rabin2.png
优化

之前计算扩展欧几里得算法ap+bq=gcd(a,b)中a和b,一直用自己写的,现在才知道a=invert(p,q)``b=invert(q,p)

位运算

assert len(bin(dec)[2:])==335
mask=int('1'*335,2)
dec=(dec^dec<<200 )&mask
enc=dec^bytes_to_long(KEY)
print "enc: "+str(enc)

这里有一个陷阱,因为mask全是1,按位与可以省略....我之前没发现这个,还一直想着怎么逆
我们把解出的key和enc异或,得到现在的dec
原来的dec与原来的dec左移200位得到现在的dec


左移.jpg

由于左移后后200位为0,所以现在dec的后200位即为原dec后200位
再从原dec后200位取出后135位,与现在dec前135位异或,即为原dec的前135位

代码

from gmpy2 import *
from Crypto.Util.number import *
import exgcdmoni
n1=15653165971272925436189715950306169488648677427569197436559321968692908786349053303839431043588260338317859397537409728729274630550454731306685369845739785958309492188309739135163206662322980634812713910231189563194520522299672424106135656125893413504868167774287157038801622413798125676071689173117885182987841510070517898710350608725809906704505037866925358298525340393278376093071591988997064894579887906638790394371193617375086245950012269822349986482584060745112453163774290976851732665573217485779016736517696391513031881133151033844438314444107440811148603369668944891577028184130587885396017194863581130429121
n2=16489315386189042325770722192051506427349661112741403036117573859132337429264884611622357211389605225298644036805277212706583007338311350354908188224017869204022357980160833603890106564921333757491827877881996534008550579568290954848163873756688735179943313218316121156169277347705100580489857710376956784845139492131491003087888548241338393764269176675849400130460962312511303071508724811323438930655022930044289801178261135747942804968069730574751117952892336466612936801767553879313788406195290612707141092629226262881229776085126595220954398177476898915921943956162959257866832266411559621885794764791161258015571
c1=9977992111543474765993146699435780943354123551515555639473990571150196059887059696672744669228084544909025528146255490100789992216506586730653100894938711107779449187833366325936098812758615334617812732956967746820046321447169099942918022803930068529359616171025439714650868454930763815035475473077689115645913895433110149735235210437428625515317444853803605457325117693750834579622201070329710209543724812590086065816764917135636424809464755834786301901125786342127636605411141721732886212695150911960225370999521213349980949049923324623683647865441245309856444824402766736069791224029707519660787841893575575974855
e1=125794
e2=42373
key_encode=154190230043753146353030548481259824097315973300626635557077557377724792985967471051038771303021991128148382608945680808938022458604078361850131745923161785422897171143162106718751785423910619082539632583776061636384945874434750267946631953612827762111005810457361526448525422842867001928519321359911975591581818207635923763710541026422076426423704596685256919683190492684987278018502571910294876596243956361277398629634060304624160081587277143907713428490243383194813480543419579737033035126867092469545345710049931834620804229860730306833456574575819681754486527026055566414873480425894862255077897522535758341968447477137256183708467693039633376832871571997148048935811129126086180156680457571784113049835290351001647282189000382279868628184984112626304731043149626327230591704892805774286122197299007823500636066926273430033695532664238665904030038927362086521253828046061437563787421700166850374578569457126653311652359735584860062417872495590142553341805723610473288209629102401412355687033859617593346080141954959333922596227692493410939482451187988507415231993
enc=17403902166198774030870481073653666694643312949888760770888896025597904503707411677223946079009696809
p=gcd(n1,n2)
q=n1//p
phin=(p-1)*(q-1)
b=gcd(e1,phin)
a=e1//b
b_d=invert(a,phin)
c1=pow(c1,b_d,n1)
a,b=exgcdmoni.exgcd(p,q)
r=pow(c1,(p+1)//4,p)
s=pow(c1,(q+1)//4,q)
x1=(a*p*s+b*q*r)%n1
x2=n1-x1
x3=(a*p*s-b*q*r)%n1
x4=n1-x3
s=x3
phin1=(p-1)*(q-1)*(s-1)
d=invert(e2,phin1)
key=pow(key_encode,d,p*q*s)
dec=bin(key^enc)[2:]
dec2=dec[135:]
dec1=bin(int(dec[:135],2)^int(dec2[65:],2))[2:]
dec=int(dec1+dec2,2)
print(long_to_bytes(dec))
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 关于使用python实现RSA加密解密 一、非对称加密算法 1、乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何...
    ttaymm阅读 967评论 0 0
  • 一、RSA的历史 1976 年以前,所有的加密方法都是同一种模式: (1)甲方选择某一种加密规则,对信息进行加密;...
    开着保时捷堵你家门口阅读 2,409评论 0 1
  • 姓名:于川皓 学号:16140210089 转载自:https://baike.baidu.com/item/RS...
    道无涯_cc76阅读 2,643评论 0 1
  • "use strict";function _classCallCheck(e,t){if(!(e instanc...
    久些阅读 2,054评论 0 2
  • 饭香以入鼻, 一切总永记。 粗茶淡饭不比玉, 可我眼中足为惜。 并非穷困困吾志, 而是长辈辈关心。
    严丝阅读 142评论 0 2