數論基礎

素數

1.定義： 一個大于1的自然數，除了1和它本身外，不能被其他自然數整除（除0以外）的數稱之為素數（質數）；否則稱為合數。

如：3×4 = 12,不是素數。11除了等于11×1以外，不能表示為其它任何兩個整數的乘積，所以11是一個素數。

2.關于素數的事實：

（1）如果p是素數，且p | ab（表示ab能被p整除），則p | a或 p | b ,即p 至少整除a與b中的一個。

（2）算術基本定理：任何一個大于1的自然數 ，如果N不為質數，都可以唯一分解成有限個質數的乘積，即

（3）素數有無窮多個。

最大公約數與最小公倍數

1.最大公約數

定義：幾個數公有的約數，叫做這幾個數的公約數，其中最大的一個叫做這幾個數的最大公約數。數學上，a和b的最大公約數記為(a, b)，編程中，計算兩個數最大公約數的方法通常記為gcd(a,b)

2.最小公倍數

定義：幾個數公有的倍數，叫做這幾個數的公倍數，其中最小的一個叫做這幾個數的最小公倍數。數學上，a和b的最小公倍數記為[a,b]，編程中，計算兩個數最小公倍數的方法通常記為lcm(a,b)

歐拉函數

1.定義： 在數論中，對正整數n，歐拉函數φ(n)是小于或等于n的正整數中與n互質的數的數目。此函數以其首名研究者歐拉命名，它又稱為φ函數（由高斯所命名）或是歐拉總計函數。例如：φ(8) = 4 ,因為1，3，5，7均與8互質。

2.性質：

歐拉函數是積性函數——若m,n互質，φ(mn)=φ(m)φ(n)

特殊性質：當n為奇數時，φ(2n)=φ(n)

歐幾里得(Euclid)算法

1.定義： 歐幾里得算法又稱為輾轉相除法，用于求兩個數的最大公約數?；谌缦略?#xff1a;兩個整數的最大公約數等于其中較小的數和兩數相除余數的最大公約數，即GCD(x,y) = GCD(y，x mod y) ，x>y。

2.代碼實現：

def GCD(x, y):|if(y==0):return xelse:return GCD(y,x %y) from gmpy2 import* m = gcd(a,b) #from Crypto.Util. number import* #m = GCD(a, b)

擴展歐幾里得算法

1.定理： 擴展歐幾里德算法是歐幾里得算法的擴展。若a和b為正整數，則存在整數x,y使得gcd(a,b)=ax+by;換句話說gcd(a,b)可以表示為a,b的整洗數線性組合。
例如：gcd(6,14)=2,而2=(-2)* 6+1 *14.

2.代碼實現：

from gmpy2 import* x=17 y = 65537 #擴展歐幾里得算法 s = gcdext(x,y) #返回元組tuple,滿足s[1]*x+s[2]*y = 1 print(s) #輸出: (mpz(1)， mpz(30841)， mpz(-8)) print(s[1]*x+s[2]*y) #輸出: 1

同余

1.定義： 設a,b是整數，n≠0，如果n|(a-b)，則稱a和b模n同余，記為a≡b(mod n)，整數n稱為模數。由于n|(a-b) 等價于 -n|(a-b)，所以a≡b(mod n) 與 a≡b(mod (-n))等價。因此，一般我們總假定模數n≥1。

2.性質1：

（1）自反性：a ≡ a (mod m)

（2）對稱性：a ≡ b (mod m)，?b ≡ c (mod m) ?a ≡ c (mod m)

（3）保持基本運算：

模運算

1.定義： a模n的運算給出了a對模n的余數，這種運算稱為模運算。注意：模運算的結果是從0到n-1的一個整數。

2.性質： 模運算就像普通的運算一樣，它是可交換、可結合、可分配的。而且，對每一個中間結果進行模m運算后再進行模m運算，其作用與先進行全部運算，然后再進行模m運算所得到的結果是一樣的。

(a+b)mod m=((a mod m)+(b mod m)) mod m

(a-b)mod m=((a mod m)-(b mod m)) mod m

(a×b)mod m=((a mod m) ×(b mod m)) mod m

(a×(b+c))mod m=((a×b) mod m+(a×c) mod m) mod m

3.用途：

（1）用于判斷一個數是否能被另一個數整除。對 2 取模即可判斷整數的奇偶性；從 2 到 n-1 取模則可判斷一個數是否為質數。
（2）進制之間的轉換。
（3）用于求取最大公約數的輾轉相除法使用取模運算。
（4）密碼學中的應用：從古老的凱撒密碼到現代常用的RSA、橢圓曲線密碼，它們的實現過程均使用了取模運算。

模逆元

1.定義： 模逆元也稱為模倒數，或者模逆元。

一整數a對同余n之模逆元是指滿足以下公式的整數 b

2.求解方法：

（1）擴展歐幾里得算法：設exgcd(a,n)為擴展歐幾里得算法的函數，則可得到ax+ny=g，g是a,n的最大公因數。若g=1，則該模逆元存在；若g≠1，則該模逆元不存在。

（2）歐拉定理：歐拉定理證明當a,n為兩個互素的正整數時，則有a^φ(n)≡1(modn),φ(n)為歐拉函數,其中 a^φ(n)-1即為a關于模n之模逆元

中國剩余定理

中國剩余定理給出了以下的一元線性同余方程組有解的判定條件，并用構造法給出了在有解情況下解的具體形式。

中國剩余定理說明：假設整數m1, m2, … , mn其中任兩數互質，則對任意的整數：a1, a2, … , an，上述一元線性同余方程組有解，并且通解可以用如下方式構造得到：

RSA算法

RSA算法簡介

RSA攻擊方法

思維導圖

常見題型

1.模數分解

題目鏈接（buu平臺）

from flag import FLAG from Cryptodome.Util.number import * import gmpy2 import randome=65537 p = getPrime(512) q = int(gmpy2.next_prime(p)) n = p*q m = bytes_to_long(FLAG) c = pow(m,e,n) print(n) print(c) # n=177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683 # c=1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049

題目為最基礎的RSA加密，其中p q為相鄰的素數?？梢杂脃afu分解

基礎RSA解密:

n=177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683 c=1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049 e=65537 p = 13326909050357447643526585836833969378078147057723054701432842192988717649385731430095055622303549577233495793715580004801634268505725255565021519817179293 q = 13326909050357447643526585836833969378078147057723054701432842192988717649385731430095055622303549577233495793715580004801634268505725255565021519817179231 from Crypto.Util.number import * phi=(p-1)*(q-1) d=inverse(e,phi) m=pow(c,d,n) print(long_to_bytes(m)) # actf{p_and_q_should_not_be_so_close_in_value}

2.n有相同的質因數

題目鏈接（buu平臺）

題面：一份秘密發送給兩個人不太好吧，那我各自加密一次好啦~~~
素數生成好慢呀
偷個懶也……不會有問題的吧？

附件：
public1.pub
public2.pub
flag_encry1
flag_encry2

首先嘗試取出兩份公鑰文件的n,e，測試發現n1 n2有公約數，正好印證了題面給的懶得生成素數，所以共用了其中一個素數。

求解公約數即可：

from Crypto.PublicKey import RSA import gmpy2 from Crypto.Util.number import * f=open("public1.pub","r") rsa1=RSA.import_key(f.read()) n1=rsa1.n e1=rsa1.e f.close() f=open("public2.pub","r") rsa2=RSA.import_key(f.read()) n2=rsa2.n e2=rsa2.e f.close() #print(n1,e1) #print(n2,e2) p=gmpy2.gcd(n1,n2) q=n2//p assert(p*q==n2) phi=(p-1)*(q-1) d=gmpy2.invert(e2,phi) c_bytes=open("flag_encry2","rb").read() c=bytes_to_long(c_bytes) m=pow(c,d,n2) print(long_to_bytes(m)) #afctf{You_Know_0p3u55I}

3.共模攻擊

題目鏈接（BUU平臺）

hint.py如下：

from gmpy2 import * from Crypto.Util.number import * from secret import hintm = bytes_to_long(hint) p = getPrime(256) c = pow(m, 256, p) print(p)p, q = getPrime(256), getPrime(256) n = p * q e1, e2 = getPrime(32), getPrime(32) c1, c2 = pow(c, e1, n), pow(c, e2, n) print(n) print(e1, c1) print(e2, c2)''' 107316975771284342108362954945096489708900302633734520943905283655283318535709 6807492006219935335233722232024809784434293293172317282814978688931711423939629682224374870233587969960713638310068784415474535033780772766171320461281579 2303413961 1754421169036191391717309256938035960912941109206872374826444526733030696056821731708193270151759843780894750696642659795452787547355043345348714129217723 2622163991 1613454015951555289711148366977297613624544025937559371784736059448454437652633847111272619248126613500028992813732842041018588707201458398726700828844249 '''

task.py如下：

from gmpy2 import * from Crypto.Util.number import * from secret import flagflag = flag.strip(b"npuctf{").strip(b"}") m = bytes_to_long(flag)p, q = getPrime(512), getPrime(512) n = p * q e1, e2 = p, q c1, c2 = pow(m, e1, n), pow(m, e2, n)print(n) print(c1) print(c2)''' 128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149 96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198 9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585 '''

共模攻擊，用擴展歐幾里得算法求出c。

原理：當GCD(e1, e2) == 1時，由擴展歐幾里得算法得，存在s1, s2使 e1s1 + e2s2 = 1，m = pow(m, e1s1 + e2s2, n)，而pow(m, e1s1 + e2s2, n) = pow(m, e1s1, n) * pow(m, e2s2, n) = pow(c1, s1, n) * pow(c2, s2, n)

由c和p可以求得m。得到c后，根據表達式：c = m²⁵⁶ mod p，可以借助Python的sympy庫nthroot_mod方法，最終由m得到hint：# m =“m.bit_length() < 400”

from gmpy2 import* from sympy import* from Crypto.Util.number import * p = 107316975771284342108362954945096489708900302633734520943905283655283318535709e1 = 2303413961 c1 = 1754421169036191391717309256938035960912941109206872374826444526733030696056821731708193270151759843780894750696642659795452787547355043345348714129217723e2 = 2622163991 c2 = 1613454015951555289711148366977297613624544025937559371784736059448454437652633847111272619248126613500028992813732842041018588707201458398726700828844249 n = 6807492006219935335233722232024809784434293293172317282814978688931711423939629682224374870233587969960713638310068784415474535033780772766171320461281579s = gcdext(e1,e2) c = pow(c1,s[1],n)*pow(c2,s[2],n) % n print(c) #c = 19384002358725759679198917686763310349050988223627625096050800369760484237557m = nthroot_mod(c,256,p) print(long_to_bytes(m))# m ="m.bit_length() < 400"

參考博客
求m：

from Crypto.Util.number import*n = 128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149 c1 = 96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198 c2 = 9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585a = c1+c2 b = c1*c2print(a) print(b)# a = 106427507401691650533776606268030543324548306805584488340881108460215302001780649045082140067384306297497785054794169701530927082798998717147796265177082494273319180022953309137549878052025764276170773098393102683446915458123682447310617265418188192465923366892572673596378919944244343124060963227516817375783 # b = 926651656671911333597022401968870409343942400492881255142377951759176631494915016941991504123810265329862246592861145719213675502795378053564904818765377025096483601036025012267103260702787555612216755188521913405305861451125814149409508425602231670292131422273268728629782633354498648021859614223672123489318899205627785426402597996319440198218774038390809403281952702730883306007226797632389267386912707857093556335846269954270572920361347019614365402744026533713442449916555425678184406380167614011131702418493073759816310890056281917310110034453007210415242707924141697749818907383248545179118594511927630223830flag = 4242839043019782000788118887372132807371568279472499477998758466224002905442227156537788110520335652385855 print(long_to_bytes(flag)) # verrrrrrry_345yyyyyyy_rsaaaaaaa_righttttttt?

總結

以上是生活随笔為你收集整理的【笔记】公钥密码学之RSA的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。