據(jù)加密算法與大素數(shù)的運算

【摘 要】大素數(shù)的生成運算是數(shù)據(jù)加密算法的關(guān)鍵。文章從加密算法的原理以及素數(shù)的生成和證明出發(fā)，對加密算法與大素數(shù)的數(shù)據(jù)結(jié)構(gòu)和實現(xiàn)進行了闡述，并為解決大素數(shù)的運算問題提供了幾種方法。

【關(guān)鍵詞】加密算法；大素數(shù)；運算

前言：在現(xiàn)代信息社會中，數(shù)據(jù)加密的技術(shù)是防止信息被假冒、偽造和修改的重要手段，能夠保證信息的完整、準(zhǔn)確和安全。隨著信息技術(shù)的深入發(fā)展，越來越多的數(shù)據(jù)加密算法應(yīng)運而生，例如其中的RSA密碼算法作為一種公認(rèn)的安全加密算法，廣泛的流行應(yīng)用到諸多領(lǐng)域，其安全性來源于對數(shù)論中的大素數(shù)的運算和分解，同時大素數(shù)的運算研究對加密算法的發(fā)展有著重要的作用。

一、加密算法與大素數(shù)的關(guān)系

在眾多的加密算法中，RSA公鑰密碼算法是目前最為流行的一種算法，廣泛應(yīng)用于各種信息領(lǐng)域，1977年由羅納德·李維斯特、阿迪·薩莫爾和倫納德·阿德曼一起提出了RSA加密算法，RSA就是以他們名字的開頭字母命名的[1]。

選取兩個大素數(shù)p和q，需要算出m=pq，φ（m）=（p-1）（q-1），選取一個正整數(shù)e，滿足（e，φ（m））=1，1

針對大數(shù)的因子分解，密鑰長度與分解次數(shù)緊密相關(guān)，分解所需要的時間隨密鑰長度的增加而增加，加密強度會更高，密碼破解也就越來越難，如果m的長度是50位（十進制），嘗試的次數(shù)大約是1.4×1010次，如果m的長度為100位的話，則需要嘗試的次數(shù)是2.3×1015次。目前，如果m的長度為200位的話，需要嘗試的次數(shù)則為2.3×1025次，如果使用一臺1秒鐘能進行1億次因子分解的高速計算機來做這些工作的話，需要的時間分別是2.3分鐘、270天、3800000年，由此可見，為了使RSA加密算法中得出安全可靠的數(shù)據(jù)，要解決的首要問題就是要生成滿足長度要求的兩個大素數(shù)——p和q。

二、大素數(shù)的生成與證明

正整數(shù)序列中素數(shù)的分布不規(guī)則，所以一個指定長度的大素數(shù)是無法用公式直接計算出來的，隨機選擇的大整數(shù)是否是素數(shù)也同樣無法用公式直接證明出來。如果想通過計算并存儲一個全面的素數(shù)表，以備日后所需的話，是不現(xiàn)實的，而且耗費也十分巨大，且p和q的安全也無法得到保障。

當(dāng)前采用的方法為：任意選擇一個大整數(shù)，然后對其做素數(shù)性的檢測，要檢查一個正整數(shù)N是否是素數(shù)的話，可以“試除法”，用小等于的所有素數(shù)去試除N，如果無法整除，N就是素數(shù)，在目前計算機運算水平的基礎(chǔ)上，這種方法的運算是無法大素數(shù)進行正確判斷的。當(dāng)前對一個大整數(shù)進行素數(shù)檢驗的方法法有兩種，分別是確定性素數(shù)法和概率測試法。

一個數(shù)n可以通過確定性素數(shù)法的檢驗方法能夠準(zhǔn)確地驗證出是否為素數(shù)，且準(zhǔn)確驗證一個大整數(shù)是否素數(shù)，目前已有很多方法能夠得出結(jié)論，比如， Demytko提出的定理，通過16bit的素數(shù)，導(dǎo)出的32bit的素數(shù)為，通過又能夠?qū)С?4bit的素數(shù)，以此類推，但是由于構(gòu)成素數(shù)容易產(chǎn)生一定的規(guī)律性，怎樣能夠得到適于加密體系用的素數(shù)還沒有得到解決。

一般來說判定一個大整數(shù)是否為素數(shù)有一定的困難，但是否定其是素數(shù)則比較容易，這里有一個簡便的運算方法能夠淘汰大量的合數(shù)，它是通過利用數(shù)論理論產(chǎn)生的一種算法，針對一個給定的大整數(shù)n，每次完成一次檢測，就給出一個yes，n是素數(shù)的概率是1/2甚至更高，或是no：n，則一定不是素數(shù)。當(dāng)n通過了t次檢測，則n為非素數(shù)的概率為，n是素數(shù)的概率為1-，如果t足夠大，比如：t為100，那么此時n是素數(shù)幾乎可以認(rèn)定出來。如果概率驗證法得出的素數(shù)是合數(shù)（盡管概率很小），也不會產(chǎn)生太大的問題，當(dāng)這種情況出現(xiàn)時，加密體制將會顯示異常，可以馬上發(fā)現(xiàn)問題。這里針對基于加密算法下大素數(shù)的運算方法可采用如下幾種方法：

（一）Lehman計算方法

Lehman是一種簡單的檢測大素數(shù)的方法，對一個小于x大于1的任意整數(shù)a，如果和1或者-1模x同余的話，那么可以確定x不是素數(shù)，否則x不是素數(shù)的概率則要大于或等于1/2，運算步驟為：選擇一個小于x的隨機整數(shù)a，計算modx，如果（modx）不等于1或者-1（modx），那么x一定不是素數(shù)；如果（modx）等于1或者-1（modx），那么x為非素數(shù)的可能性會超過50%。當(dāng)x通過了t次測驗，那么x為非素數(shù)的概率依然是。

（二）Miller-Rabin計算方法

令x=2bm+1，b，m是奇數(shù)，任選一個正整數(shù)，檢測：

當(dāng)a滿足以上兩個條件，則x一定是合數(shù)，通過理論證明得出：如果x通過檢測，那么x為非素數(shù)的概率一定1/4，當(dāng)x通過了t次檢驗，則x是非素數(shù)的概率依然是。

結(jié)論：

綜上所述，文章從加密算法的原理以及素數(shù)的生成和證明出發(fā)，對加密算法與大素數(shù)的數(shù)據(jù)結(jié)構(gòu)和實現(xiàn)進行了闡述，并為解決大素數(shù)的運算問題提供了幾種方法。為了方便用戶使用和操作，可將大素數(shù)的基本運算整理成相應(yīng)的模塊，這種方法對于信息安全、完整有著重要的意義。

參考文獻：

[1]吳明航.DES和RSA混合加密算法的研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2013.

[2]譚祖剛.改進的基于有限域Chebyshev多項式和RSA的公鑰密碼算法[D].長沙：中南大學(xué)，2013.

[3]楊博.RSA加密算法的ASIC實現(xiàn)[D].濟南：山東大學(xué)，2012.

[4]魏瑞良.計算機網(wǎng)絡(luò)通信安全中數(shù)據(jù)加密技術(shù)的研究與應(yīng)用[D].北京：中國地質(zhì)大學(xué)（北京），2013.