侯毅葦++張曉媛+肖倩

摘要：本文首先介紹了密鑰碼體制幾種重要的數(shù)論定理，而后分析了幾種傳統(tǒng)的密鑰碼體制和公開密鑰碼體制的編碼原理，探討來(lái)常見的幾種密鑰碼體制的解碼方法，分析密鑰碼體制的安全性。

Abstract： This paper first introduces several important theorem of key code system， and then analyzes the encoding principle of several traditional key cryptography and public key cryptography system， discusses the decoding method of several common key code systems， and analyzes the security of key code system.

關(guān)鍵詞：密鑰碼體制；數(shù)論；安全性

Key words： key code system；number theory；security

中圖分類號(hào)：O156.2 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2017）07-0220-03

0 引言

數(shù)論是一門古老的純數(shù)學(xué)學(xué)科，高斯曾經(jīng)說(shuō)過(guò)“數(shù)學(xué)是科學(xué)的女王，而數(shù)論則是數(shù)學(xué)的女王”。近年來(lái)，隨著社會(huì)和技術(shù)的發(fā)展，數(shù)論中素?cái)?shù)理論、歐拉定理、同余理論、費(fèi)馬大定理、中國(guó)剩余理論、高次剩余理論等許多基本理論在現(xiàn)代保密通訊、數(shù)字簽名、身份驗(yàn)證等方面獲得了廣泛的應(yīng)用，為信息技術(shù)的發(fā)展提供來(lái)重要的支撐。本文就密碼數(shù)論解碼方法進(jìn)行探討，研究常用密鑰碼體制的安全性。

1 密鑰碼體制中常用的數(shù)論定理

1.1 素?cái)?shù)分布規(guī)律

素?cái)?shù)，又稱質(zhì)數(shù)。自然界中除了自身和1以外，不再有其他因數(shù)的數(shù)字就叫做素?cái)?shù)。素?cái)?shù)有無(wú)限個(gè)，以36N（N+1）為單位，隨著的增大，素?cái)?shù)的個(gè)數(shù)以波浪形式漸漸增多，越往后越無(wú)規(guī)律性。

1.2 歐拉定理

歐拉定理，又稱費(fèi)馬-歐拉定理，若n，a為正整數(shù)，且n，a互質(zhì)，則

aφ （n）≡1（modn），

其中φ（n）為歐拉函數(shù)。

1.3 費(fèi)馬大定理

費(fèi)馬大定理，數(shù)學(xué)史上著名的定理，由法國(guó)17世紀(jì)數(shù)學(xué)家費(fèi)馬提出，又被稱為“費(fèi)馬最后的定理”，提出后，經(jīng)歷三百多年的猜想辯證，在1995年被英國(guó)數(shù)學(xué)家安德魯·懷爾斯徹底證明。定理指出，

當(dāng)n>2時(shí)，關(guān)于x，y，z的方程

xn+yn=zn

沒有正整數(shù)解。

1.4 費(fèi)馬小定理與素?cái)?shù)測(cè)定

若N是素?cái)?shù)，對(duì)于任意1？燮a？燮n-1的整數(shù)有：

an-1modn=1

但它的逆命題就不一定成立了，即an-1modn=1，則n不一定為素?cái)?shù)，比如當(dāng)a=4，n=15時(shí)，414mod15=1，但是4不是素?cái)?shù)而是合數(shù)。

1.5 大整數(shù)分解問(wèn)題

整數(shù)分解又稱因子分解，是指：將一個(gè)正整數(shù)寫成幾個(gè)素?cái)?shù)的乘積。大整數(shù)分解是數(shù)論研究的重要內(nèi)容，是許多現(xiàn)代密碼系統(tǒng)的關(guān)鍵所在。如果能夠快速解決整數(shù)分解問(wèn)題，則RSA公鑰算法和Blum Shub隨機(jī)數(shù)發(fā)生器等幾種重要的密鑰碼體系將會(huì)被瓦解。大整數(shù)的分解同素?cái)?shù)測(cè)定問(wèn)題一樣，難度甚至超過(guò)素?cái)?shù)的測(cè)定。比如對(duì)于一個(gè)較大的，有n個(gè)二進(jìn)制數(shù)位長(zhǎng)度的兩個(gè)相差不多的素?cái)?shù)的乘積數(shù)，目前還沒有已知算法可以在O（n）的時(shí)間內(nèi)分解它，最好的漸進(jìn)線性運(yùn)行時(shí)間是普通數(shù)域篩選法（GNFS）。不過(guò)，彼得·肖在1994年發(fā)現(xiàn)了一種可以運(yùn)用量子計(jì)算機(jī)構(gòu)造出2n量子位在多項(xiàng)式時(shí)間來(lái)解決這個(gè)問(wèn)題的算法。2001年，首臺(tái)7量子位的量子計(jì)算機(jī)分解15，驗(yàn)證了算法。對(duì)于現(xiàn)在的計(jì)算機(jī)，GNFS是已知最好的分解n個(gè)二進(jìn)制數(shù)位大素?cái)?shù)的方法。

2 數(shù)論在傳統(tǒng)密鑰碼體制的運(yùn)用

2.1 Ceasar密鑰碼體制

2.2 PH密鑰碼體制

Pohlig和Hellman在1978年，發(fā)表了一種新的加密方法，具體加密方法是：取滿足的（e，p-1）=1奇素?cái)?shù)p和正整數(shù)e作為編碼密鑰，首先對(duì)字母表進(jìn)行變換，如表2。

2.3 “隨機(jī)數(shù)序列”加密

隨機(jī)數(shù)序列加密法方法：

①轉(zhuǎn)換成二進(jìn)制數(shù)；

②隨機(jī)地選擇一個(gè)二進(jìn)制數(shù)，即隨機(jī)數(shù)序列，作為加密密鑰；

③將明碼按照隨機(jī)數(shù)序列的位數(shù)分組，最后一組位數(shù)不足時(shí)，用0補(bǔ)齊；

④把各組明碼與隨機(jī)數(shù)序列按位模加，方法是兩數(shù)相加結(jié)果等于它們的和被2除得的余數(shù)，即0+0=0，0+1=1，1+1=0

例：明碼：01100011101011001

隨機(jī)數(shù)序列：10100001101000011

密碼：11000110000011010

密碼解密的方法：用密鑰隨機(jī)數(shù)序列，與密碼模加。

隨機(jī)數(shù)序列密鑰碼原理被機(jī)械和電子密碼機(jī)廣泛使用。隨機(jī)數(shù)序列密碼的保密性完全取決于密鑰的隨機(jī)性，如果密鑰是真正的隨機(jī)數(shù)，那么這種密鑰碼體制在理論上就是不可破解的。但這種方式所需的的密鑰量大的驚人，在實(shí)際應(yīng)用中不可能實(shí)現(xiàn)。目前一般采用偽隨機(jī)序列來(lái)替代隨機(jī)序列，即現(xiàn)使用的隨機(jī)數(shù)序列密鑰碼都存在一定的循環(huán)周期，周期的長(zhǎng)短決定了加密的強(qiáng)度，一般使用的密鑰周期長(zhǎng)度都大于，最長(zhǎng)的甚至超過(guò)來(lái)。

隨機(jī)數(shù)序列密鑰碼體制的安全性依賴于簡(jiǎn)單的異或運(yùn)算和一次一密的亂碼本，也就是密鑰流發(fā)生器。密鑰流發(fā)生器輸出的密碼越接近隨即，對(duì)密碼分析者來(lái)說(shuō)就越困難。

3 數(shù)論在公開密鑰體制中運(yùn)用

3.1 陷門單向函數(shù)y=fk（x），（k為參數(shù)）

在沒有附加信息的情況下，陷門函數(shù)只能正向計(jì)算，逆向計(jì)算是不可行的，只有在獲得了附加信息后，逆向計(jì)算才可行。

3.2 公開密鑰碼體制

1976年，美國(guó)學(xué)者Diffile和Hellman為解決密鑰碼的分發(fā)與管理問(wèn)題，以陷門單向函數(shù)為基礎(chǔ)提出來(lái)公開密鑰碼體制：為用戶（假定為A）創(chuàng)建一個(gè)密鑰對(duì)（e，d），其中e由A作為公開密鑰對(duì)外公開，d則是私人密鑰由A保密。根據(jù)陷門函數(shù)單向性可知，明文使用公開密鑰利用陷門單向函數(shù)加密后，可以向A發(fā)送加密信息，由于只有A保存有陷門密鑰，故密文可以安全的發(fā)送到A。從而解決來(lái)陌生人之間的保密通訊問(wèn)題。

3.3 RSA方案

公開密鑰碼體制算法中使用最廣泛的是RSA。RSA一對(duì)密鑰由公共密鑰和專用密鑰組成，公共密鑰用來(lái)加密而專用密鑰則是用來(lái)解密。該算法是1977年由麻省理工（MIT）的Rivest、Shamir和Adleman基于歐拉定理利用陷門單向函數(shù)實(shí)現(xiàn)的密鑰碼體制。RSA方案實(shí)現(xiàn)原理如下：

④設(shè)p，q是兩個(gè)不相等大素?cái)?shù)，n=pq（其中p，q保密，n公開）。

明文空間M=密文空間C=Zn，隨機(jī)生成e，且ed≡1modn，將（n，e）作為公開密鑰，（n，d）為私人密鑰；

加密過(guò)程為：

fe：M→C即y≡xemodn其中x∈M，y∈C。

解密過(guò)程為：

fd：C→M即x≡ydmodn其中x∈M，y∈C

3.4 RSA方案的安全性

已知p或q，則可計(jì)算歐拉函數(shù)φ（n），根據(jù)公開密鑰e計(jì)算出私人密鑰d，可以看出RSA的安全性在于分解開n的難度（一般令p≠q）。密鑰的長(zhǎng)度從40bit到2048bit可變，加密計(jì)算時(shí)要把明文分塊，各塊的長(zhǎng)度也要根據(jù)密鑰的長(zhǎng)度改變，加密成相同長(zhǎng)度的密鑰塊。理論上密鑰碼越長(zhǎng)，加密安全性就越高，但加密解密的計(jì)算成本也相應(yīng)增加，目前常用的密鑰碼長(zhǎng)度為64位。

4 結(jié)論

密鑰碼實(shí)質(zhì)是整數(shù)性質(zhì)的具體應(yīng)用，是數(shù)論研究領(lǐng)域的一個(gè)分支。隨著信息技術(shù)的爆炸性發(fā)展，數(shù)字城市，工業(yè)4.0，物聯(lián)網(wǎng)，個(gè)人支付，社交網(wǎng)絡(luò)等技術(shù)正在逐步滲透進(jìn)社會(huì)生活的方方面面。保密通訊，密鑰碼體制不再局限于國(guó)防和商業(yè)領(lǐng)域，已經(jīng)進(jìn)入到了每個(gè)人日常生活中。數(shù)論這門古老的純數(shù)學(xué)學(xué)科，也走出了象牙塔，煥發(fā)出勃勃生機(jī)，深刻的影響著每個(gè)人的生活。

參考文獻(xiàn)：

[1][加]Douglas R.Stinson（馮登國(guó)譯）.密碼學(xué)原理與實(shí)踐[M].北京：電子工業(yè)出版社，2003.

[2]肖國(guó)鎮(zhèn).密碼計(jì)算機(jī)和通信系統(tǒng)數(shù)據(jù)安全[M].北京：人民郵電出版社，1993.

[3]胡向東，魏琴芳.應(yīng)用密碼學(xué)教程[M].北京：電子工業(yè)出版設(shè)，2005.

[4]閔嗣鶴，嚴(yán)士健.初等數(shù)論[M].北京：高等教育出版社，2003，7.

[5]Koblitz N. A Course in Number Theory and Cryptography[M]. New York： Springer2Verlag， 1987.

[6]Kranakis E. Primality and Cryptography[M]. New York ： John Wiley and Sons ， 1986.