密碼學實驗

密碼學實驗二

一、實驗目的（本次實驗所涉及并要求掌握的知識點）

掌握RSA算法的基本原理并根據給出的RSA算法簡單的實現代碼源程序,以及能夠使用RSA對文件進行加密。
掌握素性測試的基本原理，并且會使用Python進行簡單的素性測試以及初步理解Solovag-Strassen檢測，Lehmam檢測，Rabin-Miller檢測算法。

二、實驗原理和技術路線

（一）RSA編碼實驗

非對稱密碼
對稱密碼算法要求通信雙方通過交換密鑰實現使用同一個密鑰，這在密鑰管理、發布和安全性方面存在很多問題，而非對稱密碼算法解決了這個問題。非對稱密碼算法是指一個加密系統的加密密鑰和解密密鑰是不相同，或者說不能從其中一個推導出另一個。在非對稱密碼算法的兩個密鑰中，一個是用于加密的密鑰，可以公開的稱為公鑰；另一個是用于解密的密鑰，是保密的稱為私鑰。非對稱密碼算法解決了對稱密碼體制中密鑰管理難題，并提供對信息發送人的身份進行驗證的手段，是現代密碼學的最重要的發明和進展。
RSA編碼密碼原理
RSA算法基于一個十分簡單的數論事實：將兩個大素數相乘十分容易，但是想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰。RSA算法是第一個能同時用于加密和數字簽名的算法，也易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現今的三十多年里，經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優秀的公鑰方案之一。由于進行的都是大數計算，使得RSA最快的情況也比DES慢上好幾倍，無論是軟件還是硬件實現，速度一直是RSA的缺陷，一般來說只用于少量數據加密，RSA的速度比對應同樣安全級別的對稱密碼算法要慢1000倍左右。

公鑰：選擇兩個互異的大素數p和q，n是二者的乘積，即n=pq使Φ(n)＝（p-1）(q-1)，Φ(n)為歐拉函數，隨機選取正整數e使其滿足gcd(e，Φ(n))=1即e和Φ(n)互質，則將(n，e)作為公鑰。
私鑰：求出正數d使其滿足e×d=1modΦ(n)則將(n，d)作為私鑰。
加密算法：對于明文M由C=Memodn得到密文C。
解密算法：對于密文C由M=Cdmodn得到明文M如果竊密者獲得了n，e和密文C為了破解密文必須計算出私鑰d為此需要先分解n為p和q為了提高破解難度，達到更高的安全性，一般商業應用要求n的長度不小于1024bit，更重要的場合不小于2048bit。
加密解密算法的數學表達式為：
加密： $c_i=m_i^emodn(1≤i≤t)$
解密： $m_i=c_i^dmodn(1≤i≤t)$

RSA算法缺點
1）產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密。
2）安全性，RSA的安全性依賴于大數的因子分解，但并沒有從理論上證明破譯RSA的難度與大數分解難度等價，而且密碼學界多數人士傾向于因子分解不是NP問題。
3）速度太慢，由于RSA的分組長度太大，為保證安全性，n至少也要600bits以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數量級；且隨著大數分解技術的發展，這個長度還在增加，不利于數據格式的標準化。

（二）素性測試編碼實驗

素數（質數）：質數又稱素數。一個大于1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數。（質數和合數中不包括負數）
素性檢測：在以往判斷一個數a是不是素數時，都是采用i從2到sqrt(a)能否整除a。如果能整除，則a是合數；否則是素數。但是該算法的時間復雜度為O(sqrt(a))，當a較大時，時間性能很差，特別是在網絡安全和密碼學上一般都需要很大的素數。而從目前來看，確定性算法判斷素數的性能都不好，所以可以用MC(蒙特卡洛)概率算法來解決，其中MillerRabin算法就是其中的很經典的解決方法。下面首先介紹下相關的數學理論。
理論基礎：Fermat小定理：若a是素數，則對所有1≤n≤a-1的整數a，有n^{(a-1)moda=1；該定理的逆否命題也成立，即n}(a-1)moda!=1，則n為合數。但是如果a是素數，就不一定成立了，比如當n=4，a=15時，4^14mod15=1，但是4不是素數而是合數。
Fermat素性測試：算法Fermat(n,t)，其中n>2為奇數,t為測試次數。
1）對i從1到t做如下循環：

隨機選擇m，1＜m＜n-1;
計算d=gcd(m,n)，如果d>1，則返回“合數”，否則反之；
計算r≡m^(n-1)(modn)；
若r≠1，則返回“合數”。
2）返回“素數”。
算法主要應用了費馬小定理，但m^(p-1)≡1(modp)僅是素數的必要條件。
上述算法將一個合數判斷為素數的出錯概率為1/2^t，但是返回合數的判定總是對的。只要增加測試次數t，就可以把出錯概率降至趨近于0。

Lehmam素性測試
1）對i從1到t做如下循環：

選擇一個小于n的隨機數a;
計算a^((n-1)/2)modn;
如果a^((n-1)/2)≠1或-1，那么返回合數。（n肯定不是素數）
2）返回素數。（n不是素數的可能性至多是50%）
算法主要運用了上面提到的第一條定理，2是素數且是n-1的素因子，在這里代替了q。

Solovay-Strassen素性測試
1）對i從1到t做如下循環：

選擇一個小于n的隨機數a;
計算j≡a^((n-1)/2)modn;
如果j≠1或－1,則返回n不是素數;
計算Jacobi符號J(a,n)=(a/n);
如果j≠(a/n)，返回n不是素數。
2）返回n是素數
算法中的步驟3同樣使用了第一條定理判斷出合數。而后又用素數性質加強了判斷，所以這一測試準確度更高。

三、實驗方法和步驟（或程序代碼或操作流程）

（1）RSA編碼實驗

運行代碼RSA.py：
在系統中打開文檔進行代碼的查看，在Linux系統命令行中輸入vimcryptography/RSA/RSA.py，系統顯示出來代碼：

#!/usr/bin/env python
#-*-coding: utf-8-*-
import math
def isPrime(number):
i=2
sqrtNumber=int( math. sqrt(number))
for i in range( 2, sqrtNumber+1):
if number%i=0:
return False
i=i+1
return True
if
name_-"_main_":
print"*"*77
Flag =False
while Flag=False
p = int( raw_input( "Please input a prime(P):"))
Flag=isPrime(p)
if Flag=False
print "What you input is not a prime!"
print "The P is:", p
Flag =False
while Flag=False
q = int( raw_input( "Please input a prime(Q):"))
ifp=q
continue
Flag =isPrime(q)
if Flag=False
print "What you input is not a prime!"
print "The Q is:",q)while Flag =False
e =int(raw_input( "Please input a number(E):"))
if (e<1 or e>t):
continue
d=0
while (((e*d)%t)!=1):
d+=1
Flag =True
print "The E is: ", e
print "The D is: ", d
print "The Public Key(E, N) is:",e, n
print "The Private Key(D, N) is:", d, n
print "*"*77
Flag =False
while Flag =False:
plainText =int(raw_input("Please input a plaintext:"))
if (plainText < n):
Flag =True
print "The plaintext is: ", plainText
print "Encrypt"+","*7
cipherText =(plainText**e)%n
print "cipherText is: ", cipherText
print "Decrypt"+","*7
plain =(cipherText**d)%n
print "The plain is: ", plain
print "*"*77
if plainText =plain:
print "RSA Test success, "
else
print "RSA Test unsuccess!")