RSA算法教程
互聯(lián)網(wǎng) 發(fā)布時(shí)間:2008-10-08 19:02:09 作者:佚名
我要評(píng)論

它是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作,也很流行。算法的名字以發(fā)明者的名字命名:Ron Rivest, Adi Shamir 和Leonard Adleman。但RSA的安全性一直未能得到理論上的證明。它經(jīng)歷了各種攻擊,至今未被完全攻破。
一、RSA算法 :
首先,
它是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作,也很流行。算法的名字以發(fā)明者的名字命名:Ron Rivest, Adi Shamir 和Leonard Adleman。但RSA的安全性一直未能得到理論上的證明。它經(jīng)歷了各種攻擊,至今未被完全攻破。
一、RSA算法 :
首先, 找出三個(gè)數(shù), p, q, r,
其中 p, q 是兩個(gè)相異的質(zhì)數(shù), r 是與 (p-1)(q-1) 互質(zhì)的數(shù)......
p, q, r 這三個(gè)數(shù)便是 private key 接著, 找出 m, 使得 rm == 1 mod (p-1)(q-1).....
這個(gè) m 一定存在, 因?yàn)?r 與 (p-1)(q-1) 互質(zhì), 用輾轉(zhuǎn)相除法就可以得到了.....
再來(lái), 計(jì)算 n = pq.......
m, n 這兩個(gè)數(shù)便是 public key 編碼過(guò)程是, 若資料為 a, 將其看成是一個(gè)大整數(shù), 假設(shè) a < n....
如果 a >= n 的話, 就將 a 表成 s 進(jìn)位 (s <= n, 通常取 s = 2^t),
則每一位數(shù)均小於 n, 然後分段編碼......
接下來(lái), 計(jì)算 b == a^m mod n, (0 <= b < n),
b 就是編碼後的資料...... 解碼的過(guò)程是, 計(jì)算 c == b^r mod pq (0 <= c < pq),
於是乎, 解碼完畢...... 等會(huì)會(huì)證明 c 和 a 其實(shí)是相等的 :) 如果第三者進(jìn)行竊聽(tīng)時(shí), 他會(huì)得到幾個(gè)數(shù): m, n(=pq), b......
他如果要解碼的話, 必須想辦法得到 r......
所以, 他必須先對(duì) n 作質(zhì)因數(shù)分解.........
要防止他分解, 最有效的方法是找兩個(gè)非常的大質(zhì)數(shù) p, q,
使第三者作因數(shù)分解時(shí)發(fā)生困難.........
<定理>
若 p, q 是相異質(zhì)數(shù), rm == 1 mod (p-1)(q-1),
a 是任意一個(gè)正整數(shù), b == a^m mod pq, c == b^r mod pq,
則 c == a mod pq 證明的過(guò)程, 會(huì)用到費(fèi)馬小定理, 敘述如下:
m 是任一質(zhì)數(shù), n 是任一整數(shù), 則 n^m == n mod m
(換另一句話說(shuō), 如果 n 和 m 互質(zhì), 則 n^(m-1) == 1 mod m)
運(yùn)用一些基本的群論的知識(shí), 就可以很容易地證出費(fèi)馬小定理的........ <證明>
因?yàn)?rm == 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) 1, 其中 k 是整數(shù)
因?yàn)樵?modulo 中是 preserve 乘法的
(x == y mod z and u == v mod z => xu == yv mod z),
所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1) 1) mod pq 1. 如果 a 不是 p 的倍數(shù), 也不是 q 的倍數(shù)時(shí),
則 a^(p-1) == 1 mod p (費(fèi)馬小定理) => a^(k(p-1)(q-1)) == 1 mod p
a^(q-1) == 1 mod q (費(fèi)馬小定理) => a^(k(p-1)(q-1)) == 1 mod q
所以 p, q 均能整除 a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1
即 a^(k(p-1)(q-1)) == 1 mod pq
=> c == a^(k(p-1)(q-1) 1) == a mod pq 2. 如果 a 是 p 的倍數(shù), 但不是 q 的倍數(shù)時(shí),
則 a^(q-1) == 1 mod q (費(fèi)馬小定理)
=> a^(k(p-1)(q-1)) == 1 mod q
=> c == a^(k(p-1)(q-1) 1) == a mod q
=> q | c - a
因 p | a
=> c == a^(k(p-1)(q-1) 1) == 0 mod p
=> p | c - a
所以, pq | c - a => c == a mod pq 3. 如果 a 是 q 的倍數(shù), 但不是 p 的倍數(shù)時(shí), 證明同上 4. 如果 a 同時(shí)是 p 和 q 的倍數(shù)時(shí),
則 pq | a
=> c == a^(k(p-1)(q-1) 1) == 0 mod pq
=> pq | c - a
=> c == a mod pq
Q.E.D.
這個(gè)定理說(shuō)明 a 經(jīng)過(guò)編碼為 b 再經(jīng)過(guò)解碼為 c 時(shí), a == c mod n (n = pq)....
但我們?cè)谧鼍幋a解碼時(shí), 限制 0 <= a < n, 0 <= c < n,
所以這就是說(shuō) a 等於 c, 所以這個(gè)過(guò)程確實(shí)能做到編碼解碼的功能..... 二、RSA 的安全性 RSA的安全性依賴于大數(shù)分解,但是否等同于大數(shù)分解一直未能得到理論上的證明,因?yàn)闆](méi)有證明破解 RSA就一定需要作大數(shù)分解。假設(shè)存在一種無(wú)須分解大數(shù)的算法,那它肯定可以修改成為大數(shù)分解算法。目前, RSA 的一些變種算法已被證明等價(jià)于大數(shù)分解。不管怎樣,分解n是最顯然的攻擊方法。現(xiàn)在,人們已能分解多個(gè)十進(jìn)制位的大素?cái)?shù)。因此,模數(shù)n 必須選大一些,因具體適用情況而定。 三、RSA的速度 由于進(jìn)行的都是大數(shù)計(jì)算,使得RSA最快的情況也比DES慢上倍,無(wú)論是軟件還是硬件實(shí)現(xiàn)。速度一直是RSA的缺陷。一般來(lái)說(shuō)只用于少量數(shù)據(jù)加密。 四、RSA的選擇密文攻擊 RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝( Blind),讓擁有私鑰的實(shí)體簽署。然后,經(jīng)過(guò)計(jì)算就可得到它所想要的信息。實(shí)際上,攻擊利用的都是同一個(gè)弱點(diǎn),即存在這樣一個(gè)事實(shí):乘冪保留了輸入的乘法結(jié)構(gòu):
( XM )^d = X^d *M^d mod n
前面已經(jīng)提到,這個(gè)固有的問(wèn)題來(lái)自于公鑰密碼系統(tǒng)的最有用的特征--每個(gè)人都能使用公鑰。但從算法上無(wú)法解決這一問(wèn)題,主要措施有兩條:一條是采用好的公鑰協(xié)議,保證工作過(guò)程中實(shí)體不對(duì)其他實(shí)體任意產(chǎn)生的信息解密,不對(duì)自己一無(wú)所知的信息簽名;另一條是決不對(duì)陌生人送來(lái)的隨機(jī)文檔簽名,簽名時(shí)首先使用One-Way HashFunction 對(duì)文檔作HASH處理,或同時(shí)使用不同的簽名算法。在中提到了幾種不同類型的攻擊方法。 五、RSA的公共模數(shù)攻擊 若系統(tǒng)中共有一個(gè)模數(shù),只是不同的人擁有不同的e和d,系統(tǒng)將是危險(xiǎn)的。最普遍的情況是同一信息用不同的公鑰加密,這些公鑰共模而且互質(zhì),那末該信息無(wú)需私鑰就可得到恢復(fù)。設(shè)P為信息明文,兩個(gè)加密密鑰為e1和e2,公共模數(shù)是n,則:
C1 = P^e1 mod n
C2 = P^e2 mod n
密碼分析者知道n、e1、e2、C1和C2,就能得到P。
因?yàn)閑1和e2互質(zhì),故用Euclidean算法能找到r和s,滿足:
r * e1 s * e2 = 1
假設(shè)r為負(fù)數(shù),需再用Euclidean算法計(jì)算C1^(-1),則
( C1^(-1) )^(-r) * C2^s = P mod n
另外,還有其它幾種利用公共模數(shù)攻擊的方法??傊?,如果知道給定模數(shù)的一對(duì)e和d,一是有利于攻擊者分解模數(shù),一是有利于攻擊者計(jì)算出其它成對(duì)的e’和d’,而無(wú)需分解模數(shù)。解決辦法只有一個(gè),那就是不要共享模數(shù)n。
RSA的小指數(shù)攻擊。 有一種提高 RSA速度的建議是使公鑰e取較小的值,這樣會(huì)使加密變得易于實(shí)現(xiàn),速度有
所提高。但這樣作是不安全的,對(duì)付辦法就是e和d都取較大的值。
RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法,也易于理解和操作。RSA是被研究得最廣泛的公鑰算法,從提出到現(xiàn)在已近二十年,經(jīng)歷了各種攻擊的考驗(yàn),逐漸為人們接受,普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。RSA的安全性依賴于大數(shù)的因子分解,但并沒(méi)有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)。即RSA的重大缺陷是無(wú)法從理論上把握它的保密性能如何,而且密碼學(xué)界多數(shù)人士?jī)A向于因子分解不是NPC問(wèn)題。 RSA的缺點(diǎn)主要有:A)產(chǎn)生密鑰很麻煩,受到素?cái)?shù)產(chǎn)生技術(shù)的限制,因而難以做到一次一密。B)分組長(zhǎng)度太大,為保證安全性,n 至少也要 600 bits 以上,使運(yùn)算代價(jià)很高,尤其是速度較慢,較對(duì)稱密碼算法慢幾個(gè)數(shù)量級(jí);且隨著大數(shù)分解技術(shù)的發(fā)展,這個(gè)長(zhǎng)度還在增加,不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。目前,SET( Secure Electronic Transaction )協(xié)議中要求CA采用比特長(zhǎng)的密鑰,其他實(shí)體使用比特的密鑰。
其中 p, q 是兩個(gè)相異的質(zhì)數(shù), r 是與 (p-1)(q-1) 互質(zhì)的數(shù)......
p, q, r 這三個(gè)數(shù)便是 private key 接著, 找出 m, 使得 rm == 1 mod (p-1)(q-1).....
這個(gè) m 一定存在, 因?yàn)?r 與 (p-1)(q-1) 互質(zhì), 用輾轉(zhuǎn)相除法就可以得到了.....
再來(lái), 計(jì)算 n = pq.......
m, n 這兩個(gè)數(shù)便是 public key 編碼過(guò)程是, 若資料為 a, 將其看成是一個(gè)大整數(shù), 假設(shè) a < n....
如果 a >= n 的話, 就將 a 表成 s 進(jìn)位 (s <= n, 通常取 s = 2^t),
則每一位數(shù)均小於 n, 然後分段編碼......
接下來(lái), 計(jì)算 b == a^m mod n, (0 <= b < n),
b 就是編碼後的資料...... 解碼的過(guò)程是, 計(jì)算 c == b^r mod pq (0 <= c < pq),
於是乎, 解碼完畢...... 等會(huì)會(huì)證明 c 和 a 其實(shí)是相等的 :) 如果第三者進(jìn)行竊聽(tīng)時(shí), 他會(huì)得到幾個(gè)數(shù): m, n(=pq), b......
他如果要解碼的話, 必須想辦法得到 r......
所以, 他必須先對(duì) n 作質(zhì)因數(shù)分解.........
要防止他分解, 最有效的方法是找兩個(gè)非常的大質(zhì)數(shù) p, q,
使第三者作因數(shù)分解時(shí)發(fā)生困難.........
<定理>
若 p, q 是相異質(zhì)數(shù), rm == 1 mod (p-1)(q-1),
a 是任意一個(gè)正整數(shù), b == a^m mod pq, c == b^r mod pq,
則 c == a mod pq 證明的過(guò)程, 會(huì)用到費(fèi)馬小定理, 敘述如下:
m 是任一質(zhì)數(shù), n 是任一整數(shù), 則 n^m == n mod m
(換另一句話說(shuō), 如果 n 和 m 互質(zhì), 則 n^(m-1) == 1 mod m)
運(yùn)用一些基本的群論的知識(shí), 就可以很容易地證出費(fèi)馬小定理的........ <證明>
因?yàn)?rm == 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) 1, 其中 k 是整數(shù)
因?yàn)樵?modulo 中是 preserve 乘法的
(x == y mod z and u == v mod z => xu == yv mod z),
所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1) 1) mod pq 1. 如果 a 不是 p 的倍數(shù), 也不是 q 的倍數(shù)時(shí),
則 a^(p-1) == 1 mod p (費(fèi)馬小定理) => a^(k(p-1)(q-1)) == 1 mod p
a^(q-1) == 1 mod q (費(fèi)馬小定理) => a^(k(p-1)(q-1)) == 1 mod q
所以 p, q 均能整除 a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1
即 a^(k(p-1)(q-1)) == 1 mod pq
=> c == a^(k(p-1)(q-1) 1) == a mod pq 2. 如果 a 是 p 的倍數(shù), 但不是 q 的倍數(shù)時(shí),
則 a^(q-1) == 1 mod q (費(fèi)馬小定理)
=> a^(k(p-1)(q-1)) == 1 mod q
=> c == a^(k(p-1)(q-1) 1) == a mod q
=> q | c - a
因 p | a
=> c == a^(k(p-1)(q-1) 1) == 0 mod p
=> p | c - a
所以, pq | c - a => c == a mod pq 3. 如果 a 是 q 的倍數(shù), 但不是 p 的倍數(shù)時(shí), 證明同上 4. 如果 a 同時(shí)是 p 和 q 的倍數(shù)時(shí),
則 pq | a
=> c == a^(k(p-1)(q-1) 1) == 0 mod pq
=> pq | c - a
=> c == a mod pq
Q.E.D.
這個(gè)定理說(shuō)明 a 經(jīng)過(guò)編碼為 b 再經(jīng)過(guò)解碼為 c 時(shí), a == c mod n (n = pq)....
但我們?cè)谧鼍幋a解碼時(shí), 限制 0 <= a < n, 0 <= c < n,
所以這就是說(shuō) a 等於 c, 所以這個(gè)過(guò)程確實(shí)能做到編碼解碼的功能..... 二、RSA 的安全性 RSA的安全性依賴于大數(shù)分解,但是否等同于大數(shù)分解一直未能得到理論上的證明,因?yàn)闆](méi)有證明破解 RSA就一定需要作大數(shù)分解。假設(shè)存在一種無(wú)須分解大數(shù)的算法,那它肯定可以修改成為大數(shù)分解算法。目前, RSA 的一些變種算法已被證明等價(jià)于大數(shù)分解。不管怎樣,分解n是最顯然的攻擊方法。現(xiàn)在,人們已能分解多個(gè)十進(jìn)制位的大素?cái)?shù)。因此,模數(shù)n 必須選大一些,因具體適用情況而定。 三、RSA的速度 由于進(jìn)行的都是大數(shù)計(jì)算,使得RSA最快的情況也比DES慢上倍,無(wú)論是軟件還是硬件實(shí)現(xiàn)。速度一直是RSA的缺陷。一般來(lái)說(shuō)只用于少量數(shù)據(jù)加密。 四、RSA的選擇密文攻擊 RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝( Blind),讓擁有私鑰的實(shí)體簽署。然后,經(jīng)過(guò)計(jì)算就可得到它所想要的信息。實(shí)際上,攻擊利用的都是同一個(gè)弱點(diǎn),即存在這樣一個(gè)事實(shí):乘冪保留了輸入的乘法結(jié)構(gòu):
( XM )^d = X^d *M^d mod n
前面已經(jīng)提到,這個(gè)固有的問(wèn)題來(lái)自于公鑰密碼系統(tǒng)的最有用的特征--每個(gè)人都能使用公鑰。但從算法上無(wú)法解決這一問(wèn)題,主要措施有兩條:一條是采用好的公鑰協(xié)議,保證工作過(guò)程中實(shí)體不對(duì)其他實(shí)體任意產(chǎn)生的信息解密,不對(duì)自己一無(wú)所知的信息簽名;另一條是決不對(duì)陌生人送來(lái)的隨機(jī)文檔簽名,簽名時(shí)首先使用One-Way HashFunction 對(duì)文檔作HASH處理,或同時(shí)使用不同的簽名算法。在中提到了幾種不同類型的攻擊方法。 五、RSA的公共模數(shù)攻擊 若系統(tǒng)中共有一個(gè)模數(shù),只是不同的人擁有不同的e和d,系統(tǒng)將是危險(xiǎn)的。最普遍的情況是同一信息用不同的公鑰加密,這些公鑰共模而且互質(zhì),那末該信息無(wú)需私鑰就可得到恢復(fù)。設(shè)P為信息明文,兩個(gè)加密密鑰為e1和e2,公共模數(shù)是n,則:
C1 = P^e1 mod n
C2 = P^e2 mod n
密碼分析者知道n、e1、e2、C1和C2,就能得到P。
因?yàn)閑1和e2互質(zhì),故用Euclidean算法能找到r和s,滿足:
r * e1 s * e2 = 1
假設(shè)r為負(fù)數(shù),需再用Euclidean算法計(jì)算C1^(-1),則
( C1^(-1) )^(-r) * C2^s = P mod n
另外,還有其它幾種利用公共模數(shù)攻擊的方法??傊?,如果知道給定模數(shù)的一對(duì)e和d,一是有利于攻擊者分解模數(shù),一是有利于攻擊者計(jì)算出其它成對(duì)的e’和d’,而無(wú)需分解模數(shù)。解決辦法只有一個(gè),那就是不要共享模數(shù)n。
RSA的小指數(shù)攻擊。 有一種提高 RSA速度的建議是使公鑰e取較小的值,這樣會(huì)使加密變得易于實(shí)現(xiàn),速度有
所提高。但這樣作是不安全的,對(duì)付辦法就是e和d都取較大的值。
RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法,也易于理解和操作。RSA是被研究得最廣泛的公鑰算法,從提出到現(xiàn)在已近二十年,經(jīng)歷了各種攻擊的考驗(yàn),逐漸為人們接受,普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。RSA的安全性依賴于大數(shù)的因子分解,但并沒(méi)有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)。即RSA的重大缺陷是無(wú)法從理論上把握它的保密性能如何,而且密碼學(xué)界多數(shù)人士?jī)A向于因子分解不是NPC問(wèn)題。 RSA的缺點(diǎn)主要有:A)產(chǎn)生密鑰很麻煩,受到素?cái)?shù)產(chǎn)生技術(shù)的限制,因而難以做到一次一密。B)分組長(zhǎng)度太大,為保證安全性,n 至少也要 600 bits 以上,使運(yùn)算代價(jià)很高,尤其是速度較慢,較對(duì)稱密碼算法慢幾個(gè)數(shù)量級(jí);且隨著大數(shù)分解技術(shù)的發(fā)展,這個(gè)長(zhǎng)度還在增加,不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。目前,SET( Secure Electronic Transaction )協(xié)議中要求CA采用比特長(zhǎng)的密鑰,其他實(shí)體使用比特的密鑰。
相關(guān)文章
- “CMOS密碼”就是通常所說(shuō)的“開(kāi)機(jī)密碼”,主要是為了防止別人使用自已的計(jì)算機(jī),設(shè)置的一個(gè)屏障2023-08-01
QQScreenShot之逆向并提取QQ截圖--OCR和其他功能
上一篇文章逆向并提取QQ截圖沒(méi)有提取OCR功能, 再次逆向我發(fā)現(xiàn)是可以本地調(diào)用QQ的OCR的,但翻譯按鈕確實(shí)沒(méi)啥用, 于是Patch了翻譯按鈕事件, 改為了將截圖用百度以圖搜圖搜索.2023-02-04- QQ截圖是我用過(guò)的最好用的截圖工具, 由于基本不在電腦上登QQ了, 于是就想將其提取出獨(dú)立版目前除了屏幕錄制功能其他都逆出來(lái)了, 在此分享一下2023-02-04
非系統(tǒng)分區(qū)使用BitLocker加密導(dǎo)致軟件無(wú)法安裝的解決方法
很多電腦用戶在考慮自己電腦磁盤(pán)分區(qū)安全時(shí)會(huì)采用 Windows 自帶的 BitLocker 加密工具對(duì)電腦磁盤(pán)分區(qū)進(jìn)行加密。但有些人加密后就會(huì)忘記自己設(shè)置的密碼從而導(dǎo)致在安裝其它軟2020-11-25防止離職員工帶走客戶、防止內(nèi)部員工泄密、避免華為員工泄密事件的發(fā)生
這篇文章為大家詳細(xì)介紹了如何才能防止離職員工帶走客戶、防止內(nèi)部員工泄密、避免華為員工泄密事件的發(fā)生,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-06-27徹底防止計(jì)算機(jī)泄密、重要涉密人員離職泄密、涉密人員離崗離職前防范舉
近些年企業(yè)商業(yè)機(jī)密泄漏的事件屢有發(fā)生,這篇文章主要教大家如何徹底防止計(jì)算機(jī)泄密、重要涉密人員離職泄密、告訴大家涉密人員離崗離職前的防范舉措,具有一定的參考價(jià)值,2017-06-27量子計(jì)算機(jī)輕松破解加密算法 如何破解加密算法?
最近有電腦用戶反應(yīng)量子計(jì)算機(jī)可以破解下載的所有的加密算法嗎?其實(shí)也不是不可以,下面虛擬就為大家講解買臺(tái)量子計(jì)算機(jī),如何分分鐘破解加密算法2016-09-26怎么破解Webshell密碼 Burpsuite破解Webshell密碼圖文教程
webshell是以asp、php、jsp或者cgi等網(wǎng)頁(yè)文件形式存在的一種命令執(zhí)行環(huán)境,一種網(wǎng)頁(yè)后門。黑客通常會(huì)通過(guò)它控制別人網(wǎng)絡(luò)服務(wù)器,那么怎么破解webshell密碼呢?一起來(lái)看看吧2016-09-19針對(duì)Linux系統(tǒng)全盤(pán)加密的啟動(dòng)攻擊
本文討論了針對(duì)Linux系統(tǒng)全盤(pán)加密的冷啟動(dòng)攻擊,大家都認(rèn)為這種攻擊是可行的,但執(zhí)行這么一次攻擊有多難?攻擊的可行性有多少呢?需要的朋友可以參考下2015-12-28防止泄露公司機(jī)密、企業(yè)數(shù)據(jù)防泄密軟件排名、電腦文件加密軟件排行
面對(duì)日漸嚴(yán)重的內(nèi)部泄密事件,我們?nèi)绾问刈o(hù)企業(yè)的核心信息,如何防止內(nèi)部泄密也就成了擺在各個(gè)企業(yè)領(lǐng)導(dǎo)面前的一大問(wèn)題。其實(shí),針對(duì)內(nèi)網(wǎng)安全,防止內(nèi)部信息泄漏早已有了比較2015-12-17