素數原理的加密演算法

㈠ 利用質數如何加密

非對稱加密。1976年，美國學者Dime和Henman為解決信息公開傳送和密鑰管理問題，提出一種新的密鑰交換協議，允許在不安全的媒體上的通訊雙方交換信息，安全地達成一致的密鑰，這就是「公開密鑰系統」。 相對於「對稱加密演算法」這種方法也叫做「非對稱加密演算法」。

與對稱加密演算法不同，非對稱加密演算法需要兩個密鑰：公開密鑰（publickey）和私有密鑰（privatekey）。公開密鑰與私有密鑰是一對，如果用公開密鑰對數據進行加密，只有用對應的私有密鑰才能解密；如果用私有密鑰對數據進行加密，那麼只有用對應的公開密鑰才能解密。因為加密和解密使用的是兩個不同的密鑰，所以這種演算法叫作非對稱加密演算法。非對稱加密與對稱加密相比，其安全性更好：對稱加密的通信雙方使用相同的秘鑰，如果一方的秘鑰遭泄露，那麼整個通信就會被破解。而非對稱加密使用一對秘鑰，一個用來加密，一個用來解密，而且公鑰是公開的，秘鑰是自己保存的，不需要像對稱加密那樣在通信之前要先同步秘鑰。非對稱加密的缺點是加密和解密花費時間長、速度慢，只適合對少量數據進行加密。

在非對稱加密中使用的主要演算法有：RSA、Elgamal、背包演算法、Rabin、D-H、ECC（橢圓曲線加密演算法）等。不同演算法的實現機制不同，可參考對應演算法的詳細資料。

甲乙之間使用非對稱加密的方式完成了重要信息的安全傳輸。

1、乙方生成一對密鑰（公鑰和私鑰）並將公鑰向其它方公開。

2、得到該公鑰的甲方使用該密鑰對機密信息進行加密後再發送給乙方。

3、乙方再用自己保存的另一把專用密鑰（私鑰）對加密後的信息進行解密。乙方只能用其專用密鑰（私鑰）解密由對應的公鑰加密後的信息。

在傳輸過程中，即使攻擊者截獲了傳輸的密文，並得到了乙的公鑰，也無法破解密文，因為只有乙的私鑰才能解密密文。同樣，如果乙要回復加密信息給甲，那麼需要甲先公布甲的公鑰給乙用於加密，甲自己保存甲的私鑰用於解密。

㈡ 密碼學（三）RSA演算法以及一些因數分解法

RSA演算法詳解：基於公鑰加密系統

RSA演算法，以三位科學家的姓氏命名，構建了現代密碼學中的核心部分。這個廣泛使用的密碼體制基於兩個關鍵步驟：素數選擇與加密解密過程。首先，Alice和Bob需選擇兩個素數p和q，再選定一個數n，滿足n=p*q。他們公開共享公鑰(e)，以及n，其中e與(p-1)*(q-1)互質。

Alice要加密信息m，會將m進行如下操作：m^e mod n。將得到的密文c發送給Bob。Bob接收到密文後，通過計算d（模p-1和模q-1的逆元）進行解密，即c^d mod n，得到原始消息m。

RSA的安全性基於大數分解的難度，但在特殊情況下，如 Woman in the middle attack，如果Eva掌握了加密規則，可以通過精心設計的假密文攻擊。她不需要直接分解n，只需對密文進行簡單的操作，就能輕易獲取信息，破壞系統。

對於素數分解，雖然一般情況下的復雜度是難以克服的，但在某些特定條件下，如Miller-Robin素數判別法，能快速識別非素數，盡管存在Carmichael Number這類特殊情況。Miller-Robin定理基於費馬小定理，對奇素數和奇合數的特性提供判斷依據。

Pollard's p-1分解法和平方差分解法，針對特定情況如兩個素數乘積，提供了分解方法。Pollard's p-1法通過尋找合適倍數，利用費馬小定理尋找因數，而平方差分解則利用兩個數的平方差尋找因子，是目前最快的分解法之一。

最後，數論中的黎曼猜想和素數分布理論為這些分解法提供了理論支持，包括黎曼ζ函數和數域篩法。數域篩法，盡管復雜，但當處理大型數值時，它是最快的素因數分解技術。平方篩法則是其中一種簡化版本，通過篩選和計算，尋找B光滑數，進一步提高分解效率。

㈢ 質數的定義是什麼 大質數加密的原理是什麼

質數的定義：
質數（prime number）又稱素數，有無限個。質數定義為在大於1的自然數中，除了1和它本身以外不再有其他因數的數稱為質數。
大質數加密的原理：
1、讓計算機隨機生成兩個大質數p和q，得出乘積n；
2、利用p和q有條件的生成加密密鑰e；
3、通過一系列計算，得到與n互為質數的解密密鑰d，置於操作系統才知道的地方；
4、操作系統將n和e共同作為公匙對外發布，將私匙d秘密保存,把初始質數p和q秘密丟棄。
國際數學和密碼學界已證明，企圖利用公匙和密文推斷出明文，或者企圖利用公匙推斷出私匙的難度等同於分解兩個巨大質數的積，這就是Eve不可能對Alice的密文解密以及公匙可以在網上公布的原因。
至於"巨大質數"要多大才能保證安全的問題不用擔心，利用當前可預測的計算能力，在十進制下，分解兩個250位質數的積要用數十萬年的時間；並且質數用盡或兩台計算機偶然使用相同質數的概率小到可以被忽略。

㈣ 一個RSA演算法的加密運算，需要完整的演算過程。

RSA演算法非常簡單，概述如下：
找兩素數p和q
取n=p*q
取t=(p-1)*(q-1)
取任何一個數e,要求滿足e<t並且e與t互素（就是最大公因數為1）
取d*e%t==1
這樣最終得到三個數：
n
d
e
設消息為數M
(M
<n)
設c=(M**d)%n就得到了加密後的消息c
設m=(c**e)%n則
m
==
M，從而完成對c的解密。
註：**表示次方,上面兩式中的d和e可以互換。
在對稱加密中：
n
d兩個數構成公鑰，可以告訴別人；
n
e兩個數構成私鑰，e自己保留，不讓任何人知道。
給別人發送的信息使用e加密，只要別人能用d解開就證明信息是由你發送的，構成了簽名機制。
別人給你發送信息時使用d加密，這樣只有擁有e的你能夠對其解密。
rsa的安全性在於對於一個大數n，沒有有效的方法能夠將其分解
從而在已知n
d的情況下無法獲得e；同樣在已知n
e的情況下無法
求得d。
rsa簡潔幽雅，但計算速度比較慢，通常加密中並不是直接使用rsa
來對所有的信息進行加密，
最常見的情況是隨機產生一個對稱加密的密鑰，然後使用對稱加密演算法對信息加密，之後用
RSA對剛才的加密密鑰進行加密。
最後需要說明的是，當前小於1024位的N已經被證明是不安全的
自己使用中不要使用小於1024位的RSA，最好使用2048位的。