費馬小定理和素數(shù)在密碼學的應用

陳政培

【摘要】素數(shù)一直以來都是數(shù)學界研究的重要課題，而素數(shù)的正確利用可以為密碼學提供有效的工具。本文將要介紹獲取并檢驗素數(shù)的方法，以及著名的RSA密碼的原理。

【關(guān)鍵詞】求模運算 ?RSA算法 ?米勒拉賓算法 ?密碼學

【中圖分類號】G642 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻標識碼】A ? ? ?【文章編號】2095-3089（2016）11-0199-02

公元前在古希臘就產(chǎn)生了早期的算術(shù)，直到20世紀初才開始使用數(shù)論這個詞匯。而從早期到中期的這段時間數(shù)論卻幾乎沒有什么發(fā)展，直到19世紀才由費馬、梅森、歐拉、高斯、黎曼、希爾伯特等人發(fā)展起來。而且主要內(nèi)容是尋找素數(shù)通項公式，由初等數(shù)論向解析數(shù)論和代數(shù)數(shù)論轉(zhuǎn)變，但也產(chǎn)生很多無法解決的猜想。20世紀有些猜想得以解決，但現(xiàn)在仍然有很多結(jié)論是以黎曼猜想一類未能被完全證明的猜想為理論基礎的，也就是說假使這些猜想是正確的很多理論也會隨之正確并有可能上升為定理，一旦猜想是錯誤的很多理論也會隨之覆滅。目前解決大多數(shù)猜想的瓶頸就是素數(shù)通項公式，有這樣一個說法“如果找到一個素數(shù)通項公式，一些困難問題就可以由解析數(shù)論轉(zhuǎn)回到初等數(shù)論范圍”，可見，素數(shù)在當今還有很大的研究空間，盡管我們無法確定素數(shù)通項公式是否存在。而我想就當前日益發(fā)展的科技領(lǐng)域談談數(shù)論中素數(shù)的關(guān)鍵地位。

在這個科技化時代，計算機的地位不斷上升，人們對計算機的訴求也不斷增大，可能作為一個普通的程序員對于計算機內(nèi)部的數(shù)據(jù)處理和優(yōu)化沒有太大的需求。而想要使計算機變得更加強大性能更加優(yōu)異，除了在硬件方面的進步，在優(yōu)化算法方面，數(shù)論方面的知識有著廣泛的應用。例如在計算機算術(shù)、計算機設計、計算機理論、計算機復雜度等。而這之后，就會有大量的信息在網(wǎng)絡世界中流通，而這之中不乏一些機密信息，信息安全就顯得日益重要，密碼學也就應運而生。20世紀中后期就產(chǎn)生了一種RSA碼，這種神奇的密碼正是利用了素數(shù)成為至今仍有實用價值的密碼。

隨著人們慢慢注意到素數(shù)的特殊性，人們對這種特殊數(shù)字的研究也更加深入，素數(shù)在密碼學的作用也變得越來越大。

一、素數(shù)測試

如果用最普通的方法獲得素數(shù)，無非就是隨機獲得一個數(shù)，然后對其進行素性測試。素數(shù)的定義就是除了1和它本身以外沒有其它的因子。假定該數(shù)字為p。

用簡單的計算機語言描述就是：

for （int i=1;i<p;++i）

if（p%i==0） continue; ?//p≡0（mod i）即p能被i整除

則p不是素數(shù)。

但是這樣的方法復雜度高達O（n）。如果加以優(yōu)化，只需要試除到：

for （int i=1;i<sqrt（p）;++i）

if（p%i==0） continue; ?//p≡0（mod i）即p能被i整除

這樣復雜度就降到了O（sqrt（n））。

但是如果采用了米勒拉賓素性檢測法，計算將更加簡單。

數(shù)學原理如下：

若p為素數(shù)，a為整數(shù)，且a、p互質(zhì)。

則有ap-1≡1（mod p）

其等價形式為： ? ? ?ap≡a（mod p）

證明如下： ? ? ? ? ?令ap-1=k×p+1

則ap=（k×p+1）*a

也即 ap≡a（mod p）

引理：若p為素數(shù)（p>2），

如果 x2 ≡1 （mod p） 且x既不是1也不是p-1，則稱x為“1模p的非平凡平方根”

欲證明素數(shù)沒有滿足模p余1的非平凡平方根存在。

證明：假設x是一個模p余1的非平凡平方根，則有：

x2≡1（mod p）

（x+1）（x-1）≡0（mod p）

因為x是非平凡的，就有（x+1）與（x-1）和x互質(zhì)，就是說（x+1）和（x-1）都不能被p整除，因此（x+1）（x-1）不能被p整除，矛盾。證畢

素數(shù)沒有滿足模p余1的非平凡平方根。

即如果一個數(shù)模p余1下有非平凡平方根，則n必為合數(shù)。

由該引理可知，若存在x2≡1（mod p），則p必為合數(shù)。

利用以上這些性質(zhì)，產(chǎn)生了著名的米勒-拉賓素性檢測算法：

定義

x02≡1（mod n）

x12≡1（mod n）

…

xtt-12≡1（mod n）

xi是滿足1<xi<n-1的隨機數(shù)，在這一計算過程中，如果有任意一個xi≡1（mod n），根據(jù)引理，則n必為合數(shù)。

二、RSA碼

RSA碼的發(fā)明就是對素數(shù)實際運用的例子。由歐幾里得證明的算數(shù)基本定理可知任何一個自然數(shù)都可以分解為素數(shù)的乘積。但是將一個大整數(shù)分解只能用較小的素數(shù)依次嘗試，這種方法無疑是很耗時的。大可在一段固定的時間就更換一次，這樣的密碼策略堪稱無懈可擊。

接下來有N、a、X、p、q，其獲得過程如下：

1.任意選取素數(shù)p、q，N=p×q。

2.中間量r=（p-1）×（q-1）。

3.選取a和X兩個互質(zhì)的數(shù)，使之滿足aX≡1（mod r）。

4.徹底銷毀p、q，公開N和a，將X作為解密關(guān)鍵。

小明想把數(shù)字A（A要小于N）傳送給小芳，他并不是直接把A發(fā)出去因為這樣有可能會被其他人截獲，于是我將A連續(xù)乘a次，再除以N，將余數(shù)發(fā)給小芳。小芳手里有一個小明都不知道的數(shù)字X，她將余數(shù)連乘X次，然后除以N，得到的余數(shù)就是A。

即小明需要執(zhí)行的程序是：

temp=pow（A，a）; temp=temp%N; //temp是一個中間量

然后將temp發(fā)給小芳，小芳需要執(zhí)行的程序是：

temp=pow（temp，X）; B=temp%N;

答案B就是當時小明實際想表達的A。

只要素數(shù)p、q足夠大，N也就很大，a和X的推導過程都是由p和q決定的，只要我銷毀p、q，破密的人則需要對N進行整數(shù)分解，那將是一個非常龐大的計算量。而且只要N足夠大，可以表達的A也就非常大。

這種加密方式其實是公開了打亂一個特定信息的方式，任何人都可以用我公開的方法加密信息，但是由于計算量太大，最終能夠整理混亂的信息解出最終答案的人只有我自己。可是有人會說利用現(xiàn)有的費馬小定理加上概率測試素數(shù)法，在一個較短的可以接受的時間內(nèi)是可以算出幾十位數(shù)的分解結(jié)果的。即便是一百多位的數(shù)，利用現(xiàn)在的網(wǎng)絡技術(shù)無數(shù)臺電腦通過交流信息將這個龐大的計算任務細分化，也就是云計算的方式，也是可以解決的。但是試想現(xiàn)在已經(jīng)計算出的素數(shù)位數(shù)早已上千位，兩個千位級別的素數(shù)相乘之后得到的數(shù)字恐怕計算機技術(shù)有再大的突破也是難以匹敵的。

綜上所述RSA碼成功的秘訣就是能夠獲得很大的素數(shù)，米勒算法就是一個獲得素數(shù)的不錯算法。將兩者結(jié)合起來就形成了著名的RSA密碼。

參考文獻：

[1]張爾光.正整數(shù)的方冪的方陣與費馬定理——費馬定理不成立的必要條件[J].數(shù)學學習與研究，2012.12.

[2]袁樹雄，韓鳳英.密碼學基礎研究[J].科技資訊，2008.5.

[3]張麗媛.RSA密碼算法的研究與實現(xiàn)[D].山東科技大學，2005.5.