buu(前三页第二弹) RSA习题与相关知识总结
生活随笔
收集整理的這篇文章主要介紹了
buu(前三页第二弹) RSA习题与相关知识总结
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
文章目錄
- buu [ACTF新生賽2020]crypto-rsa3 1
- 題目描述：
- 題目分析：
- 收獲與體會：
- buu [WUSTCTF2020]情書 1
- 題目描述：
- 題目分析：
- 收獲與體會：
- buu [NCTF2019]babyRSA 1
- 題目描述：
- 題目分析：
- 收獲與體會：
- buu [RoarCTF2019]babyRSA 1
- 題目描述：
- 題目分析：
- 收獲與體會：
- buu [RoarCTF2019]RSA 1
- 題目描述：
- 題目分析：
- 收獲與體會:
- buu [MRCTF2020]babyRSA 1
- 題目描述:
- 題目分析：
- buu [GWCTF 2019]BabyRSA 1
- 題目描述：
- 題目分析：
- decrypt(解密)
- buu [GUET-CTF2019]BabyRSA 1
- 題目描述：
- 題目分析：
- 以上知識總結(jié)：
- 1.
- 2.
- 3.
- 4.
- 5.
buu [ACTF新生賽2020]crypto-rsa3 1
題目描述：
from flag import FLAG
from Cryptodome.Util.number import *
import gmpy2
import random
e=65537
p = getPrime(512)
q = int(gmpy2.next_prime§)
n = p*q
m = bytes_to_long(FLAG)
c = pow(m,e,n)
print(n)
print( c )
n = 177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683
c = 1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049
題目分析：
- 這題已知量：n,c,e
- 利用 分解n得p,q的在線網(wǎng)站 即可得到 p 與 q
- 此時便可得到 d = gmpy2.invert(e,(p-1)*(q-1))
- 然后便可得到明文 m = pow(c,d,n)
- 最后在轉(zhuǎn)化為字符串即可
- 代碼如下：
收獲與體會：
這是很基礎也很簡單的一道題，但重點是要記得公式 （我一開始便有個字母記錯了，然后怎么也找不到正確的答案）
buu [WUSTCTF2020]情書 1
題目描述：
題目分析：
- 翻譯一下可知：
前提：用0、1、2、……枚舉字母表25
使用RSA系統(tǒng)
加密：0156 0821 1616 0041 0140 2130 1616 0793
公鑰：2537和13
私鑰：2537和937
- 從提示可以得知 n = 2537 , e = 13 , d = 937
- 分解 n ,可知 p = 43 , q = 59
- 做過 buu RSAROLL 1 便可知道此題大致考的什么
- 里面的 “ 0156 0821 1616 0041 0140 2130 1616 0793 ” 即是 c ,只不過是多個 c ,將解出來的明文拼接在一起便可得到 flag
- 代碼如下：
- 得到 flag{iloveyou}
收獲與體會：
- 此題有一個特殊之處，即里面的 c , e , n 都很小，很反常！
- 如果按 buu RSAROLL 1 這道題來寫的話，得不到答案，因為打印 pow(int(i),d,n) 后會得到
8
11
14
21
4
24
14
20
一串很小的數(shù)字，對應ascii碼后會得到一些 特別的東西，沒有字母也沒有數(shù)字
- 所以就會想到可能是按照26個字母表進行轉(zhuǎn)換，位置一一對應即可轉(zhuǎn)化成功得到 flag
- 所以數(shù)字在1~26之間就轉(zhuǎn)字母便，大于26就轉(zhuǎn) ascii 碼
buu [NCTF2019]babyRSA 1
題目描述：
題目分析：
- 首先明確兩個公式：
- 想要解出此題，我們必須知道n,而要知道n,我們要知道p和q的值
- 通過 e*d 的計算，我們知道其長度為2064位，而生成p的條件為 getPrime(1024)，所以（p-1)（q-1）應該為2048位
此處所說的位數(shù)長度是以Bit為單位，加一減一都不影響位數(shù)，相乘的話即為位數(shù)相加，這些性質(zhì)記住就好，以下是計算代碼：
from Crypto.Util.number import * e = 65537 # 轉(zhuǎn)二進 e = 0b10000000000000001,直接數(shù)得到長度為17 d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913 print(gmpy2.bit_length(e*d)) # 2064 p = getPrime(1024) print(gmpy2.bit_length(p)) # 1024 print(gmpy2.bit_length(p-1)) # 1024- 又 ed1 = e*d - 1 = k(p-1)(q-1)，2064-2048 = 16，所以k值必在 pow(2,15)至pow(2,16)之間 （想知道為什么看結(jié)尾的知識總結(jié)，此處專注解題，不深層探究）
- 所以，我們可以利用此條件暴力求解k值，從而求出(p-1)*(q-1),間接求出 p 和 q 的值
- 那如何間接法呢？
- 首先我們求得了(p-1)(q-1),而p和q是兩個相鄰的質(zhì)數(shù)，所以我們可以使用sympy庫對p,q進行求解。思路為先對(p-1)(q-1)開方，再求得大于開方所得數(shù)和小于開方所得數(shù)的質(zhì)數(shù)
- 其中 sympy.prevprime(x)是求大于x最近的質(zhì)數(shù)，sympy.nextprime(x)是求小于x最近的質(zhì)數(shù)。
- 解題代碼如下：
- 最終得出 flag{70u2_nn47h_14_v3ry_gOO0000000d}
收獲與體會：
- 了解了一些字節(jié)的相關(guān)知識
- 知道了函數(shù) sympy.prevprime(x)和sympy.nextprime(x)的相關(guān)知識
sympy.prevprime(x)是求大于x最近的質(zhì)數(shù)
sympy.nextprime(x)是求小于x最近的質(zhì)數(shù)
- 回顧了iroot(x,n) 和 pow(x,y) 的相關(guān)知識
iroot(x,n) —> x開n次根,返回值有兩個，前一個是開方出來的整數(shù)部分，后一個是能否開出來，若能則為true,不能則為flase
pow(x,y) —> x 的 y 次方
pow(x,y,z) —> x 的 y 次方后，取余 z
buu [RoarCTF2019]babyRSA 1
題目描述：
import sympy import randomdef myGetPrime():A= getPrime(513)print(A)B=A-random.randint(1e3,1e5)print(B)return sympy.nextPrime((B!)%A) p=myGetPrime() #A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407 #B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596q=myGetPrime() #A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927 #B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026r=myGetPrime()n=p*q*r #n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733 c=pow(flag,e,n) #e=0x1001 #c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428 #so,what is the flag?題目分析：
- 首先我們先看到 n = p * q * r （n 分解成了三個素數(shù)） ,而 e,c 都知道，所以要求明文 m = pow(c,d,n) 先要求出 d 來
- 而 d = gmpy2.invert(e,phi)
- 其中歐拉函數(shù) phi = (p-1) * (q-1) * (r-1)
- 所以要求 d ,那么要求出 p 與 q
- 代碼中 p = myGetPrime() = sympy.nextPrime((B!)%A)
sympy.nextprime(x) 是求小于x最近的質(zhì)數(shù)
- 所以最終要求 (B!)%A，即B的階乘模A，其中 A,B 都知道，那么B!（B的階乘）怎么求呢？
- 有一個定理可以解決這個問題，即 威爾遜定理
威爾遜定理
當且僅當p為素數(shù)時：( p -1 ) ! ≡ -1 ( mod p ) —> (p-1) ! +1=0 (mod p)
- A = getPrime(513)，可知A為素數(shù)，又 B=A-random.randint(1e3,1e5)，通過威爾遜定理，可知(A-1) ! +1≡0 (mod A)，故B!(B+1)(B+2)…(A-1) ≡ -1 (mod A)，即B ! * C = ≡ -1 ( mod A )，其中C = (A - 1)! / (B) !，也就是B之后的數(shù)字之積
兩邊同時乘上C的逆元C1（C * C1 = 1），B ! = -1 * C1(mod A1) - B ! 求出來了，那么 p = myGetPrime() = sympy.nextPrime((B!)%A) 也就求出來了
- 如此，p,q 都求出來了，r = n // (p * q) ,自此p,q,r,都求出來了，最終flag也就出來了
- 代碼如下：
- 最終flag{wm-CongrAtu1ation4-1t4-ju4t-A-bAby-R4A}
收獲與體會：
- 知道了如何利用代碼求階乘
- 又了解了一種RSA題型
buu [RoarCTF2019]RSA 1
題目描述：
A=(((y%x)**5)%(x%y))**2019+y**316+(y+1)/x p=next_prime(z*x*y) q=next_prime(z) A = 2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724 n = 117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127 c = 41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128題目分析：
- 這題看了大佬的，知道了兩種不同的解題方法
- 第一種是契合題目所給字母，先通過爆破求出x,y，但奇怪的是我用pycharm重寫了一遍他們的代碼，都出現(xiàn)了報錯：
- 上面兩種一個是報錯，一個是直接結(jié)束程序，反正都求不出x,y（我也求不出）
- 所以嘗試了另外一種方法：直接爆破求e,（p,q可以通過n分解得到），所以字母都求出來了，那么最后答案也就差不多了，代碼如下：
- 最終得到flag{wm-l1l1ll1l1l1l111ll}，e = 65537
收獲與體會:
- 真是巧了，e = 65537
- 所以如果以后要求e來求flag的，我們可以先大膽令e = 65537來試一下，沒準就瞎貓碰上死耗子，答案就出來了，省時還省力（但遇上這種題的可能性確實挺小的）
- 為什么會把e的范圍定在1~100000之間？題做多了便知大部分的e的值都處于此范圍內(nèi)。（不排除有特殊情況，到時候有特殊情況再說吧）
buu [MRCTF2020]babyRSA 1
題目描述:
import sympy import random from gmpy2 import gcd, invert from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes from z3 import * flag = b"MRCTF{xxxx}" base = 65537def GCD(A):B = 1for i in range(1, len(A)):B = gcd(A[i-1], A[i])return Bdef gen_p():P = [0 for i in range(17)]P[0] = getPrime(128)for i in range(1, 17):P[i] = sympy.nextprime(P[i-1])print("P_p :", P[9])n = 1for i in range(17):n *= P[i]p = getPrime(1024)factor = pow(p, base, n)print("P_factor :", factor)return sympy.nextprime(p)def gen_q():sub_Q = getPrime(1024)Q_1 = getPrime(1024)Q_2 = getPrime(1024)Q = sub_Q ** Q_2 % Q_1print("Q_1: ", Q_1)print("Q_2: ", Q_2)print("sub_Q: ", sub_Q)return sympy.nextprime(Q)if __name__ == "__main__":_E = base_P = gen_p()_Q = gen_q()assert (gcd(_E, (_P - 1) * (_Q - 1)) == 1)_M = bytes_to_long(flag)_C = pow(_M, _E, _P * _Q)print("Ciphertext = ", _C) ''' P_p : 206027926847308612719677572554991143421 P_factor : 213671742765908980787116579976289600595864704574134469173111790965233629909513884704158446946409910475727584342641848597858942209151114627306286393390259700239698869487469080881267182803062488043469138252786381822646126962323295676431679988602406971858136496624861228526070581338082202663895710929460596143281673761666804565161435963957655012011051936180536581488499059517946308650135300428672486819645279969693519039407892941672784362868653243632727928279698588177694171797254644864554162848696210763681197279758130811723700154618280764123396312330032986093579531909363210692564988076206283296967165522152288770019720928264542910922693728918198338839 Q_1: 103766439849465588084625049495793857634556517064563488433148224524638105971161051763127718438062862548184814747601299494052813662851459740127499557785398714481909461631996020048315790167967699932967974484481209879664173009585231469785141628982021847883945871201430155071257803163523612863113967495969578605521 Q_2: 151010734276916939790591461278981486442548035032350797306496105136358723586953123484087860176438629843688462671681777513652947555325607414858514566053513243083627810686084890261120641161987614435114887565491866120507844566210561620503961205851409386041194326728437073995372322433035153519757017396063066469743 sub_Q: 168992529793593315757895995101430241994953638330919314800130536809801824971112039572562389449584350643924391984800978193707795909956472992631004290479273525116959461856227262232600089176950810729475058260332177626961286009876630340945093629959302803189668904123890991069113826241497783666995751391361028949651 Ciphertext = 1709187240516367141460862187749451047644094885791761673574674330840842792189795049968394122216854491757922647656430908587059997070488674220330847871811836724541907666983042376216411561826640060734307013458794925025684062804589439843027290282034999617915124231838524593607080377300985152179828199569474241678651559771763395596697140206072537688129790126472053987391538280007082203006348029125729650207661362371936196789562658458778312533505938858959644541233578654340925901963957980047639114170033936570060250438906130591377904182111622236567507022711176457301476543461600524993045300728432815672077399879668276471832題目分析：
- 首先我們分析代碼，代碼可以說分為3個模塊，第一個模塊（GCD模塊）個人覺得這里不需要看，后面解題并沒有用它，重點是下面兩模塊，即gen_p和gen_q模塊（生成p和生成q模塊）
- 生成q模塊還好說:
- 重點是生成p模塊，我們先來看生成p的過程：先生成P，P里面有17個質(zhì)數(shù)，且每一個質(zhì)數(shù)之間都有關(guān)系
做此題 必備知識
sympy.prevprime(x)是求大于x最近的質(zhì)數(shù)
sympy.nextprime(x)是求小于x最近的質(zhì)數(shù)
- 由必備知識可知P中有17個質(zhì)數(shù)，后一個數(shù)是大于前一個數(shù)最近的質(zhì)數(shù)，并且具有唯一性，這16個質(zhì)數(shù)相乘得到n,然后通過factor = pow(p,base,n)求得factor , (其中base即為e = 65537)。這是一個典型的歐拉函數(shù)，我們需要求出的便是這17個（P[i]-1）的乘積，其中P[9]是已知的，然而我在上面也說了，每個質(zhì)數(shù)之間都是相聯(lián)系的，且每個質(zhì)數(shù)都是唯一的，所以知道其中一個，那么其他的都能知道，然后通過invert求出d1,之后求出p 。以下是求解p的代碼：
- 完整代碼如下：
- 最后得到flag{sti11_@_b@by_qu3st10n}
buu [GWCTF 2019]BabyRSA 1
題目描述：
import hashlib import sympy from Crypto.Util.number import *flag = 'GWHT{******}' secret = '******'assert(len(flag) == 38)half = len(flag) / 2flag1 = flag[:half] flag2 = flag[half:]secret_num = getPrime(1024) * bytes_to_long(secret)p = sympy.nextprime(secret_num) q = sympy.nextprime(p)N = p * qe = 0x10001F1 = bytes_to_long(flag1) F2 = bytes_to_long(flag2)c1 = F1 + F2 c2 = pow(F1, 3) + pow(F2, 3) assert(c2 < N)m1 = pow(c1, e, N) m2 = pow(c2, e, N)output = open('secret', 'w') output.write('N=' + str(N) + '\n') output.write('m1=' + str(m1) + '\n') output.write('m2=' + str(m2) + '\n') output.close() N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163 m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239 m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546題目分析：
對代碼進行分析可得大致加密過程為：
- 首先給了字符串明文flag和secret，然后對flag對半切得到flag1和flag2
- 隨機生成一個1024位（2進制）的素數(shù)，并將secret(字符串)類型轉(zhuǎn)化為整數(shù)類型，然后將這兩個結(jié)果相乘得到secret_num
拓展：
bytes_to_long(x) —> 字節(jié)轉(zhuǎn)整數(shù) （會將字節(jié)x轉(zhuǎn)化為它的ascii碼）
long_to_bytes(x) —> 整數(shù)轉(zhuǎn)字節(jié)
- 取secret_num的下一個素數(shù)作為p,取p的下一個素數(shù)作為q,得到N=p*q
必備知識：
sympy.prevprime(x)是求大于x最近的質(zhì)數(shù)
sympy.nextprime(x)是求小于x最近的質(zhì)數(shù)
- 將flag1和flag2通過bytes_to_long轉(zhuǎn)化為整數(shù)得到F1和F2
- 將F1,F2設計成方程組得到c1,c2，進一步加密得到m1,m2
- 最后給出運行結(jié)果得到 N,m1,m2
decrypt(解密)
- 題中給出了N,通過以上分析可以得知p,q是兩個相鄰的素數(shù)，所以對N進行開方運算(iroot(N,2))后可以得到一個值x，并且pq
- 通過sympy.prevprime(x)，sympy.nextprime(x) 函數(shù)可以得到p,q，從而可以求得d
- 然后進行RSA解密得出c1和c2
c1 = pow(m1,d,N)
c2 = pow(m2,d,N)
- 至此，我們得到一個方程組：
c1=F1+F2
c2=F13+F23
- 利用sympy庫進行方程組求解：
得到：
{F1: 1141553212031156130619789508463772513350070909, F2: 1590956290598033029862556611630426044507841845}, {F1: 1590956290598033029862556611630426044507841845, F2: 1141553212031156130619789508463772513350070909}- 得到兩組解，但仔細看只是調(diào)換的位置而已，兩組都試一下，便可得到最終flag
- 完整代碼：
- 最后得到flag{f709e0e2cfe7e530ca8972959a1033b2}
buu [GUET-CTF2019]BabyRSA 1
題目描述：
p+q : 0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea (p+1)(q+1) : 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740 e : 0xe6b1bee47bd63f615c7d0a43c529d219 d : 0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5 enc_flag : 0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a題目分析：
- 知道了(p+1)(q+1)與p+q，那么n = p*q便可以知道了，n = (p+1)(q+1) - (p+q) - 1
- enc_flag便是密文c
- 所以明文m = pow(c,d,n) 便求出來了
- 代碼如下：
- 得到flag{cc7490e-78ab-11e9-b422-8ba97e5da1fd}
以上知識總結(jié)：
1.
當出現(xiàn)多個c（并沒有多個n）則想到拼接法。若每個c相對偏小，那么就意味著求出的m相對偏小，若m <= 26 則想到對應26個字母表，若m > 26，則直接 flag += chr(m)
2.
sympy.prevprime(x)是求大于x最近的質(zhì)數(shù)
sympy.nextprime(x)是求小于x最近的質(zhì)數(shù)
3.
我們經(jīng)常會遇到：
p = getPrime(1024)
q = getPrime(1024)
指的是獲得1024長度(2進制)的素數(shù)p,q
此處所說的長度是以Bit為單位（二進制形式），加一減一都不影響位數(shù)，相乘的話即為位數(shù)相加，這些性質(zhì)記住就行（數(shù)字邏輯第一章有此知識），以下是舉例：
from Crypto.Util.number import * e = 0x10001 # 轉(zhuǎn)二進 e = 0b10000000000000001,直接數(shù)得到長度為17 d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913 print(gmpy2.bit_length(e*d)) # 2064 p = getPrime(1024) print(gmpy2.bit_length(p)) # 1024 print(gmpy2.bit_length(p-1)) # 1024留個小問題：pow(2,15)至pow(2,16)中的數(shù) 位數(shù)長度是多少？
解答：問的是處于 2^15 ~ 2^16 中的數(shù)的位數(shù)長度為多少，想要算位數(shù)長度，那么便要將數(shù)轉(zhuǎn)為2進制形式，這里就要用到數(shù)字邏輯中學到的知識了（這些知識記住即可，方便下次做題）：
2^15 轉(zhuǎn)2進制即 1 后面加15個0
2^15 = 1000000000000000 ————>長度為16
同理 2^16 轉(zhuǎn)2進制即 1 后面加16個0
2^16 = 10000000000000000 ————>長度為17
所以處于 2^15 ~ 2^16 中的數(shù)的位數(shù)長度為 16
4.
若：
p = sympy.nextprime(a_num) # 其中 a_num 未知 q = sympy.nextprime(p) n = p * qn 已知，求 p,q
由代碼可知，p，q 是相鄰的兩個素數(shù)，那么直接對 n 開方，求開方得到的數(shù)的整數(shù)部分，然后對該整數(shù)求上一個素數(shù)和下一個素數(shù)，即可得到 p,q 。如：
5.
bytes_to_long(x) 與 long_to_bytes(x) 相關(guān)知識：
bytes_to_long(x) —> 字節(jié)轉(zhuǎn)整數(shù) （會將字節(jié)x轉(zhuǎn)化為它的ascii碼）
long_to_bytes(x) —> 整數(shù)轉(zhuǎn)字節(jié)
總結(jié)
以上是生活随笔為你收集整理的buu(前三页第二弹) RSA习题与相关知识总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 动画设计的12条基本原理
- 下一篇： 第十九篇 -- 学习第十八天打卡2019