數(shù)論在幾種常見密鑰碼體制中的運用

侯毅葦++張曉媛+肖倩

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

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.

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

Key words： key code system；number theory；security

中圖分類號：O156.2 文獻標識碼：A 文章編號：1006-4311（2017）07-0220-03

0 引言

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

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

1.1 素數(shù)分布規(guī)律

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

1.2 歐拉定理

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

aφ （n）≡1（modn），

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

1.3 費馬大定理

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

當n>2時，關于x，y，z的方程

xn+yn=zn

沒有正整數(shù)解。

1.4 費馬小定理與素數(shù)測定

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

an-1modn=1

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

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

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

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

2.1 Ceasar密鑰碼體制

2.2 PH密鑰碼體制

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

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

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

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

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

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

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

例：明碼：01100011101011001

隨機數(shù)序列：10100001101000011

密碼：11000110000011010

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

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

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

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

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

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

3.2 公開密鑰碼體制

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

3.3 RSA方案

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

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

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

加密過程為：

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

解密過程為：

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

3.4 RSA方案的安全性

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

4 結(jié)論

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

參考文獻：

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

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

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

[4]閔嗣鶴，嚴士健.初等數(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.