費(fèi)馬小定理和素?cái)?shù)在密碼學(xué)的應(yīng)用

陳政培

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

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

【中圖分類號(hào)】G642 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻(xiàn)標(biāo)識(shí)碼】A ? ? ?【文章編號(hào)】2095-3089（2016）11-0199-02

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

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

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

一、素?cái)?shù)測試

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

用簡單的計(jì)算機(jī)語言描述就是：

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

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

則p不是素?cái)?shù)。

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

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

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

這樣復(fù)雜度就降到了O（sqrt（n））。

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

數(shù)學(xué)原理如下：

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

則有ap-1≡1（mod p）

其等價(jià)形式為： ? ? ?ap≡a（mod p）

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

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

也即 ap≡a（mod p）

引理：若p為素?cái)?shù)（p>2），

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

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

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

x2≡1（mod p）

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

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

素?cái)?shù)沒有滿足模p余1的非平凡平方根。

即如果一個(gè)數(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的隨機(jī)數(shù)，在這一計(jì)算過程中，如果有任意一個(gè)xi≡1（mod n），根據(jù)引理，則n必為合數(shù)。

二、RSA碼

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

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

1.任意選取素?cái)?shù)p、q，N=p×q。

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

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

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

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

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

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

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

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

答案B就是當(dāng)時(shí)小明實(shí)際想表達(dá)的A。

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

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

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

參考文獻(xiàn)：

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

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

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