【笔记】公钥密码学之RSA
數(shù)論基礎(chǔ)
素數(shù)
1.定義： 一個大于1的自然數(shù)，除了1和它本身外，不能被其他自然數(shù)整除（除0以外）的數(shù)稱之為素數(shù)（質(zhì)數(shù)）；否則稱為合數(shù)。
如：3×4 = 12,不是素數(shù)。11除了等于11×1以外，不能表示為其它任何兩個整數(shù)的乘積，所以11是一個素數(shù)。
2.關(guān)于素數(shù)的事實：
（1）如果p是素數(shù)，且p | ab（表示ab能被p整除），則p | a或 p | b ,即p 至少整除a與b中的一個。
（2）算術(shù)基本定理：任何一個大于1的自然數(shù) ，如果N不為質(zhì)數(shù)，都可以唯一分解成有限個質(zhì)數(shù)的乘積，即
（3）素數(shù)有無窮多個。
最大公約數(shù)與最小公倍數(shù)
1.最大公約數(shù)
定義：幾個數(shù)公有的約數(shù)，叫做這幾個數(shù)的公約數(shù)，其中最大的一個叫做這幾個數(shù)的最大公約數(shù)。數(shù)學(xué)上，a和b的最大公約數(shù)記為(a, b)，編程中，計算兩個數(shù)最大公約數(shù)的方法通常記為gcd(a,b)
2.最小公倍數(shù)
定義：幾個數(shù)公有的倍數(shù)，叫做這幾個數(shù)的公倍數(shù)，其中最小的一個叫做這幾個數(shù)的最小公倍數(shù)。數(shù)學(xué)上，a和b的最小公倍數(shù)記為[a,b]，編程中，計算兩個數(shù)最小公倍數(shù)的方法通常記為lcm(a,b)
歐拉函數(shù)
1.定義： 在數(shù)論中，對正整數(shù)n，歐拉函數(shù)φ(n)是小于或等于n的正整數(shù)中與n互質(zhì)的數(shù)的數(shù)目。此函數(shù)以其首名研究者歐拉命名，它又稱為φ函數(shù)（由高斯所命名）或是歐拉總計函數(shù)。例如：φ(8) = 4 ,因為1，3，5，7均與8互質(zhì)。
2.性質(zhì)：
歐拉函數(shù)是積性函數(shù)——若m,n互質(zhì)，φ(mn)=φ(m)φ(n)
特殊性質(zhì)：當(dāng)n為奇數(shù)時，φ(2n)=φ(n)
歐幾里得(Euclid)算法
1.定義： 歐幾里得算法又稱為輾轉(zhuǎn)相除法，用于求兩個數(shù)的最大公約數(shù)。基于如下原理：兩個整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)，即GCD(x,y) = GCD(y，x mod y) ，x>y。
2.代碼實現(xiàn)：
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為正整數(shù)，則存在整數(shù)x,y使得gcd(a,b)=ax+by;換句話說gcd(a,b)可以表示為a,b的整洗數(shù)線性組合。
例如：gcd(6,14)=2,而2=(-2)* 6+1 *14.
2.代碼實現(xiàn)：
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.定義： 設(shè)a,b是整數(shù)，n≠0，如果n|(a-b)，則稱a和b模n同余，記為a≡b(mod n)，整數(shù)n稱為模數(shù)。由于n|(a-b) 等價于 -n|(a-b)，所以a≡b(mod n) 與 a≡b(mod (-n))等價。因此，一般我們總假定模數(shù)n≥1。
2.性質(zhì)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的余數(shù)，這種運算稱為模運算。注意：模運算的結(jié)果是從0到n-1的一個整數(shù)。
2.性質(zhì)： 模運算就像普通的運算一樣，它是可交換、可結(jié)合、可分配的。而且，對每一個中間結(jié)果進行模m運算后再進行模m運算，其作用與先進行全部運算，然后再進行模m運算所得到的結(jié)果是一樣的。
(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）用于判斷一個數(shù)是否能被另一個數(shù)整除。對 2 取模即可判斷整數(shù)的奇偶性；從 2 到 n-1 取模則可判斷一個數(shù)是否為質(zhì)數(shù)。
（2）進制之間的轉(zhuǎn)換。
（3）用于求取最大公約數(shù)的輾轉(zhuǎn)相除法使用取模運算。
（4）密碼學(xué)中的應(yīng)用：從古老的凱撒密碼到現(xiàn)代常用的RSA、橢圓曲線密碼，它們的實現(xiàn)過程均使用了取模運算。
模逆元
1.定義： 模逆元也稱為模倒數(shù)，或者模逆元。
一整數(shù)a對同余n之模逆元是指滿足以下公式的整數(shù) b
2.求解方法：
（1）擴展歐幾里得算法：設(shè)exgcd(a,n)為擴展歐幾里得算法的函數(shù)，則可得到ax+ny=g，g是a,n的最大公因數(shù)。若g=1，則該模逆元存在；若g≠1，則該模逆元不存在。
（2）歐拉定理：歐拉定理證明當(dāng)a,n為兩個互素的正整數(shù)時，則有aφ(n)≡1(modn),φ(n)為歐拉函數(shù),其中 aφ(n)-1即為a關(guān)于模n之模逆元
中國剩余定理
中國剩余定理給出了以下的一元線性同余方程組有解的判定條件，并用構(gòu)造法給出了在有解情況下解的具體形式。
中國剩余定理說明：假設(shè)整數(shù)m1, m2, … , mn其中任兩數(shù)互質(zhì)，則對任意的整數(shù)：a1, a2, … , an，上述一元線性同余方程組有解，并且通解可以用如下方式構(gòu)造得到：
RSA算法
RSA算法簡介
RSA攻擊方法
思維導(dǎo)圖
常見題型
1.模數(shù)分解
題目鏈接（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題目為最基礎(chǔ)的RSA加密，其中p q為相鄰的素數(shù)。可以用yafu分解
基礎(chǔ)RSA解密:
2.n有相同的質(zhì)因數(shù)
題目鏈接（buu平臺）
題面：一份秘密發(fā)送給兩個人不太好吧，那我各自加密一次好啦~~~
素數(shù)生成好慢呀
偷個懶也……不會有問題的吧？
附件：
public1.pub
public2.pub
flag_encry1
flag_encry2
首先嘗試取出兩份公鑰文件的n,e，測試發(fā)現(xiàn)n1 n2有公約數(shù)，正好印證了題面給的懶得生成素數(shù)，所以共用了其中一個素數(shù)。
求解公約數(shù)即可：
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。
原理：當(dāng)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后，根據(jù)表達(dá)式：c = m256 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：
總結(jié)
以上是生活随笔為你收集整理的【笔记】公钥密码学之RSA的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Cryptohack-RSA write
- 下一篇： 【数据库复习】第一章绪论