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

侯毅葦++張曉媛+肖倩

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

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.

關鍵詞：密鑰碼體制；數論；安全性

Key words： key code system；number theory；security

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

0 引言

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

1 密鑰碼體制中常用的數論定理

1.1 素數分布規律

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

1.2 歐拉定理

歐拉定理，又稱費馬-歐拉定理，若n，a為正整數，且n，a互質，則

aφ （n）≡1（modn），

其中φ（n）為歐拉函數。

1.3 費馬大定理

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

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

xn+yn=zn

沒有正整數解。

1.4 費馬小定理與素數測定

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

an-1modn=1

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

1.5 大整數分解問題

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

2 數論在傳統密鑰碼體制的運用

2.1 Ceasar密鑰碼體制

2.2 PH密鑰碼體制

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

2.3 “隨機數序列”加密

隨機數序列加密法方法：

①轉換成二進制數；

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

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

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

例：明碼：01100011101011001

隨機數序列：10100001101000011

密碼：11000110000011010

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

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

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

3 數論在公開密鑰體制中運用

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

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

3.2 公開密鑰碼體制

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

3.3 RSA方案

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

④設p，q是兩個不相等大素數，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，則可計算歐拉函數φ（n），根據公開密鑰e計算出私人密鑰d，可以看出RSA的安全性在于分解開n的難度（一般令p≠q）。密鑰的長度從40bit到2048bit可變，加密計算時要把明文分塊，各塊的長度也要根據密鑰的長度改變，加密成相同長度的密鑰塊。理論上密鑰碼越長，加密安全性就越高，但加密解密的計算成本也相應增加，目前常用的密鑰碼長度為64位。

4 結論

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

參考文獻：

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

[2]肖國鎮.密碼計算機和通信系統數據安全[M].北京：人民郵電出版社，1993.

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

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