rsa


什么时候世界末日了,我就不用学RSA了,太难了

题目平台 BUUCTF

什么叫RSA? 我怎么知道什么叫RSA

想搞懂RSA原理的建议去看这个视频,搞不懂多看几遍,这是我在全网能够找到最通俗易懂的教程了

李永乐讲RSA

什么?还是不懂?我也不懂,直接套公式背公式就完事了

不要和我讲什么:费马定理,欧几里得算法,中国剩余定理,辗转相除法,直接ctrl+c ctrl+v 复制代码,全梭哈 ,梭哈,梭哈!

m:明文     c:密文       e:公钥        d:私钥      n:模     phi(n):欧拉函数值
 n:p*q      phi(n): (p-1) *(q-1) 

我怎么知道N和phi(n)是什么东西,反正有公式,直接套他就完事了

知道m c e d n phi(n)

直接上公式

加密:c = m**e mod n

​ m**e 除以n求余数c

​ 明文的e次幂除以n得出密文¿

解密:m = c**e mod n

​ c**e 除以 n 求余数m

​ 密文的e次幂除以n得出明文¿

知道公式,直接做题

easyrsa

p = 473398607161
q = 4511491
e = 17

知道p q e 典型的求d的出flag

d怎么求?这里要用到辗转相除法,怎么还有定理?直接套公式,一把梭

d = e mod phi(n)

import libnum
p = 473398607161
q = 4511491
e = 17
fn = (p-1)*(q-1)
print(libnum.invmod(e,fn))

easyrsa 1

p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

知道p q e c 典型的求m

直接套公式

c的d次幂除以N求余数m

我们不知道d怎么办?求啊。 怎么求?套公式啊!

d = e mod phi(n)

n = p*q
phi(n) = (q-1) * (p-1)

知道了n和phi(n) 直接解出d

d = (libnum.invmod(e,fn))

知道d你套公式还套不出一个m?

flag = pow(c,d,n)

完整代码

import libnum

n = p*q
fn = (p-1)*(q-1)
d = (libnum.invmod(e,fn))
flag = pow(c,d,n)
print(flag)

RSA1

嘻嘻嘻,出题人NM$L

这题又多了一个dp 和 dq

什么是dp和dq ? 稍微了解就知道了,我搁百度搜了半天也没人给我解释什么是dp和dq,套公式,找大佬脚本,一把梭,全梭哈!

RSA1 大家可以看这篇文章去理解dp的求法,反正我是没看懂,本人老笨比了

dp = d%(p-1)

dq = p%(q-1)

知道dp和dq怎么求的,直接上题

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp =6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq =783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

看题得出知道 p,q,c,dp,dq 直接求M (¿这怎么求) 套公式,一把梭!

m≡(((m2−m1)∗p−1 mod q)p+m1) mod n

本人老笨比了,还是看不懂,直接抄大佬的脚本(嘻嘻)

分析个脚本?

import libnum
    InvQ=libnum.invmod(p,q)    #直接卡在这一步,为什么要用q去模逆p都没搞懂
    mp = pow(c,dp,p)    #mp就是m2 参考中国剩余定理,本人老笨比,看不懂,直接背公式,套就完事了
    mq = pow(c,dq,q)    #mq就是m1  看我上面贴的链接就知道了
    m=(((mp-mq)*InvQ)%p)*q+mq    #卡住了,老笨比了,看了半天也没看懂为什么
    print(libnum.n2s(m))    #数字型转换字符串

呜呜呜,我学了一下午的dp和dq了,就是看不懂,随缘更新吧,说不定哪天我就悟了(不可能)

RSA共模攻击

这比赛怎么喜欢整这些阴间的题目?

我去借鉴(抄)大佬脚本发现脚本不难写,但是要理解欧几里得算法

欧几里得算法就是 用较大数除以较小数,再用得出的余数去除除数,再用第二次出现的余数去除以第一个余数,如此反复,一直到最后的余数是0为止。太绕了?我也看不懂,直接举个例子

*求10和35的最大公约数:*

*25/10 = 3 ······5*

*再用除数10去除以余数5*

*10/5 = 2······0*

*得出10和25的最大公约数 是 5*

理解欧几里得算法,那就看看题?

c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361

n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801

e1=11187289

c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397

e2=9647291

题目给 c1 c2 e1 e2 和n 让你求m

我们知道了欧几里得算法,下一步就是知道共模攻击怎么解

https://www.cnblogs.com/gwind/p/8013154.html 想要理解的可以看这个链接

直接上脚本吧

import libnum
    def gcd(a,b):
        if b == 0:
            return a,0
           else:
            x,y = gcd(b,a%b)
            return y,x - (a//b)*y

s = gcd(e1,e2)
s1 = s[0]
s2 = s[1]

if s1 < 0:
    s1 = -s1
    c1 = libnum.invmod(c1,n)
elif s2 < 0:
    s2 = -s2
    c2 = libnum.invmod(c2,n)

m = pow(c1,s1,n)*pow(c2,s2,n)%n
print(libnum.n2s(m))

文章作者: Fuchenchenle
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Fuchenchenle !
 上一篇
Debian10 搭建 vsftpd Debian10 搭建 vsftpd
FTP (虚拟用户登录) 安装vsftpapt install –y vsftpd安装虚拟数据库apt install db-util创建数据库文件mkdir /etc/vsftpd.txt vim /etc/vsftpd.txt
2020-07-11
下一篇 
BUUCTF-Misc BUUCTF-Misc
别问,问就是菜鸡 平台链接:BUUCTF 金三胖 打开压缩包是一个gif,拖入ps查看图层得出flag flag{he11ohongke} 二维码 扫描后显示secret is here ,我们直接将图片拖到kali利用binwalk
2020-06-03
  目录