◆劉彥鑫

?

基于中國(guó)剩余定理的素?cái)?shù)搜索算法

◆劉彥鑫

（青島理工大學(xué) 山東266520）

公鑰密碼算法是素?cái)?shù)的一個(gè)重要應(yīng)用途徑，例如經(jīng)典的RSA算法現(xiàn)已滲透到人們信息生活的各個(gè)方面，保護(hù)著用戶的信息安全。公鑰密碼算法的優(yōu)點(diǎn)在于不需要像對(duì)稱加密算法一樣采用安全的信道傳輸密鑰，但是公鑰密碼的計(jì)算開(kāi)銷以及前期的素?cái)?shù)產(chǎn)生開(kāi)銷都比較大。針對(duì)素?cái)?shù)產(chǎn)生開(kāi)銷大這一問(wèn)題，本文借助于中國(guó)剩余定理對(duì)素?cái)?shù)在多維空間中的分布規(guī)律進(jìn)行了研究，并在此基礎(chǔ)之上設(shè)計(jì)了一種相對(duì)高效的素?cái)?shù)搜索算法，能夠有效減少在一個(gè)區(qū)間內(nèi)搜索素?cái)?shù)時(shí)所需檢查整數(shù)的數(shù)量，在一定程度上減小了素?cái)?shù)搜索的負(fù)擔(dān)，增加了素?cái)?shù)搜索的效率。

中國(guó)剩余定理；素?cái)?shù)；初等數(shù)論；RSA

1 RSA公鑰密碼算法簡(jiǎn)介

當(dāng)前針對(duì)B/S模式下需要提供保密業(yè)務(wù)的WEB應(yīng)用程序大多選擇RSA算法作為其信息加密方式以保證用戶信息在傳遞過(guò)程中的安全。RSA算法之所以能夠提供足夠的保密性是因?yàn)橥ǔＧ闆r下RSA使用的素?cái)?shù)非常大，選取大素?cái)?shù)將為密碼破解者的破解過(guò)程帶來(lái)非常巨大的計(jì)算量，保證了密碼破解在所期望時(shí)間內(nèi)是無(wú)法做到的，這稱之為計(jì)算上安全。為了更加深入的理解大素?cái)?shù)在RSA算法中的作用，以及高效素?cái)?shù)搜索算法對(duì)于RSA密鑰產(chǎn)生的重要意義，首先介紹RSA算法的密鑰產(chǎn)生過(guò)程：

( 1 ) 選取兩個(gè)保密的大素?cái)?shù)p和q；

( 2 ) 計(jì)算n = p×q以及n的歐拉函數(shù)值φ(n) = (p-1)×(q-1)；

( 3 ) 隨機(jī)選擇一個(gè)整數(shù)e，使之滿足1

( 4 ) 根據(jù)選擇的e計(jì)算與e配對(duì)的d，使d滿足d?e ≡ 1 mod φ(n)。

任何得到公鑰{e,n}的用戶均可對(duì)數(shù)據(jù)進(jìn)行加密發(fā)送給私鑰的所有者，但加密的數(shù)據(jù)卻只能通過(guò)與公鑰配對(duì)的私鑰才能解密，這就保證了加密數(shù)據(jù)除私鑰的所有者外沒(méi)有人能夠解讀。

RSA算法的安全性依據(jù)是基于對(duì)大數(shù)n分解的困難性，要想通過(guò)公鑰中參數(shù)e得到私鑰中參數(shù)d就必須知道φ(n)，也就是必須知道素?cái)?shù)p和q，從而就必須對(duì)n進(jìn)行分解，而n越大，將n分解還原出兩個(gè)素?cái)?shù)就越困難。這就使得如果想要算法保證足夠的安全性就一定要選取足夠大的素?cái)?shù)作為其計(jì)算參數(shù)。

但是大素?cái)?shù)的生成目前是一件相當(dāng)消耗資源的任務(wù)，原因在于檢測(cè)一個(gè)非常大的數(shù)是不是素?cái)?shù)本身就比較費(fèi)時(shí)，而現(xiàn)有素?cái)?shù)搜索算法的時(shí)間復(fù)雜度往往是O(n)級(jí)別，這無(wú)疑更是加重了素?cái)?shù)搜索任務(wù)的開(kāi)銷。而如果能找到素?cái)?shù)分布的大致規(guī)律，縮小素?cái)?shù)搜索的范圍，便可在一定程度上降低素?cái)?shù)搜索的開(kāi)銷。

2 中國(guó)剩余定理

作為本算法的重要理論支撐，現(xiàn)簡(jiǎn)要介紹中國(guó)剩余定理的基本內(nèi)容。中國(guó)剩余定理又稱為“孫子定理”，是一種求解一次同余方程組的方法，是數(shù)論中一個(gè)重要定理。

在模下有唯一解：

中國(guó)剩余定理不僅提供了一種求解一次同余方程組的方法，同時(shí)還提供了一種數(shù)值映射方法，可將一個(gè)大整數(shù)映射為一組小整數(shù)組成的有序序列，本文將應(yīng)用其數(shù)值映射方法探索素?cái)?shù)的分布規(guī)律，并在算法實(shí)現(xiàn)中應(yīng)用其求解同余方程組的方法確定一次搜索的起點(diǎn)。

3 素?cái)?shù)在多維空間中的分布規(guī)律

圖1 [0,34]區(qū)間整數(shù)映射結(jié)果

圖2 [0,699]區(qū)間整數(shù)映射結(jié)果

4 算法思路及性能分析

圖3 算法性能優(yōu)化程度散點(diǎn)圖

5 算法實(shí)驗(yàn)結(jié)果及結(jié)論驗(yàn)證

表1 算法性能檢驗(yàn)實(shí)驗(yàn)結(jié)果

從實(shí)驗(yàn)結(jié)果不難看出，本文所述算法與一般算法相比，在保證不遺漏區(qū)間內(nèi)任何素?cái)?shù)素?cái)?shù)的前提下所需檢查的整數(shù)數(shù)量更少。分析計(jì)算實(shí)驗(yàn)數(shù)據(jù)可知：在區(qū)間[1,100000]內(nèi)搜索素?cái)?shù)時(shí)，算法性能優(yōu)化程度為19181/100000 = 0.1918100。同樣，在區(qū)間[1,5000000]內(nèi)搜索素?cái)?shù)時(shí)，算法的性能優(yōu)化程度為95904/500000 = 0.191808?？梢?jiàn)，算法在實(shí)際應(yīng)用中確實(shí)可以縮小搜索素?cái)?shù)時(shí)整數(shù)的檢查范圍，且實(shí)際性能與理論分析結(jié)果出入不大。

6 總結(jié)

本文針對(duì)素?cái)?shù)的應(yīng)用之一RSA算法做了簡(jiǎn)要介紹，分析了RSA算法的安全依據(jù)以及開(kāi)銷問(wèn)題。而后對(duì)于本算法的理論基礎(chǔ)中國(guó)剩余定理做了簡(jiǎn)要介紹，并利用中國(guó)剩余定理找到了素?cái)?shù)分布的一個(gè)大致規(guī)律，發(fā)現(xiàn)了多維空間中部分素?cái)?shù)不可能出現(xiàn)的位置，通過(guò)在素?cái)?shù)搜索時(shí)避開(kāi)對(duì)這些位置的檢查，從而達(dá)到了縮小素?cái)?shù)搜索范圍的目的。而后給出了這一算法的實(shí)現(xiàn)思路，并對(duì)算法的性能進(jìn)行了分析，給出了算法的性能優(yōu)化公式以及性能的極限公式。文章最后利用Java語(yǔ)言對(duì)算法進(jìn)行了實(shí)現(xiàn)，并利用真實(shí)的實(shí)驗(yàn)數(shù)據(jù)檢驗(yàn)了理論的正確性。

[1](加)Douglas R.Stinson.密碼學(xué)原理與實(shí)踐（第三版）[M].北京:電子工業(yè)出版社,2016:131-133.

[2]郭亞軍,宋建華,李莉,董慧慧.信息安全原理與技術(shù)(第三版)[M].北京:清華大學(xué)出版社,2013:20-24.

[3]王萍,廖芳燕,廖芳午,張樹(shù)貴.RSA算法中快速生成大素?cái)?shù)方法的改進(jìn)[J].重慶文理學(xué)院學(xué)報(bào)(自然科學(xué)版),2009,28(3):9-11.