馬偉芳 唐國梅

【摘要】密碼學(xué)是一門交叉學(xué)科，涉及眾多數(shù)學(xué)知識，內(nèi)容豐富，在很大程度上是一門應(yīng)用數(shù)學(xué)學(xué)科。本文著重介紹數(shù)學(xué)在密碼學(xué)各種算法中的基本理論及應(yīng)用，包括數(shù)論、線性代數(shù)、近世代數(shù)等。

【關(guān)鍵詞】模運(yùn)算 歐拉定理 應(yīng)用

【中圖分類號】G633.6 【文獻(xiàn)標(biāo)識碼】A 【文章編號】2095-3089（2018）04-0052-02

引言

信息安全的主要任務(wù)是研究計算機(jī)系統(tǒng)和通信網(wǎng)絡(luò)中信息的保護(hù)方法，其中密碼學(xué)正是實現(xiàn)這些功能的核心技術(shù)。然而密碼學(xué)在很大程度上是一門應(yīng)用數(shù)學(xué)學(xué)科，在先修課程當(dāng)中雖然有高等數(shù)學(xué)、線性代數(shù)、概率論等基礎(chǔ)數(shù)學(xué)知識，但是在密碼學(xué)的學(xué)習(xí)當(dāng)中仍然涉及到數(shù)論、近世代數(shù)等數(shù)學(xué)知識。本文從這一角度出發(fā)，介紹模運(yùn)算、歐拉定理、及熵的基本理論及在密碼學(xué)當(dāng)中的應(yīng)用。

一、傳統(tǒng)密碼應(yīng)用

在1949年香農(nóng)發(fā)表《保密系統(tǒng)的通信理論》之前，密碼體制主要通過字符間的簡單置換和代換實現(xiàn)，一般認(rèn)為這些密碼體制屬于傳統(tǒng)密碼體制范疇。其中置換密碼通常較簡單，通過位置的改變重新排列明文，而在代換密碼當(dāng)中的單表代換密碼中的典型算法仿射密碼當(dāng)中涉及到了模運(yùn)算、模逆元、歐拉函數(shù)的基本理論。

1.仿射密碼仿射密碼的加密算法就是一個線性代換，即對任意的明文字符x，對應(yīng)的密文字符為y=e（x）=ax+b（mod26），其中a，b∈Z26，且要求gcd（a，26）=1，函數(shù)e（x）稱為仿射加密函數(shù)。由歐拉定理可知在Z26上與26互素的數(shù)共有12個，其中歐拉函數(shù)是指對于一個正整數(shù)n，與其互素的且小于等于n的正整數(shù)的個數(shù)可以表示為準(zhǔn)（n）。在y=e（x）=ax+b（mod26）中兩邊同時左乘，a-1a-1ax=（a-1a）x=x=a-1（e（x-b）（mod26）由此可得仿射解密函數(shù)為：x=d（e（x））=a-1（e（x）-b）（mod26）。從仿射求解仿射解密函數(shù)來看，需要求出a在Z26上的乘法逆元a-1∈Z26。

2.Hill密碼，希爾密碼是由數(shù)學(xué)家LesterHill于1929在《American Mathematical Monthly》雜志上首次提出的。其基本思想是利用Z26上的線性變換把n個連續(xù)的明文字母替換為n個密文字母。這個替換是由密鑰決定的，而這個密鑰是一個變換矩陣，解密時只需對密文做一次逆變換即可。

二、現(xiàn)代密碼應(yīng)用

1949年香農(nóng)發(fā)表《保密系統(tǒng)的通信理論》標(biāo)志著現(xiàn)代密碼學(xué)的真正開始。在這片論文中，香農(nóng)首次將信息論引入到密碼學(xué)研究中，他利用概率統(tǒng)計的觀點和熵的概念對信息源、密鑰源、傳輸?shù)拿芪暮兔艽a系統(tǒng)的安全性進(jìn)行了數(shù)學(xué)描述和定量分析，并提出了密碼體制的模型。他的工作為現(xiàn)代密碼學(xué)及密碼分析學(xué)奠定了堅實的理論基礎(chǔ)在現(xiàn)代密碼學(xué)中無論是對稱密碼學(xué)范疇還是公鑰密碼體制思想均應(yīng)用到了數(shù)學(xué)當(dāng)中的數(shù)論及香農(nóng)理論。

1.AES算法AES的處理單位是字節(jié)，128位的輸入明文分組P今兒輸入密鑰K都被分成16個字節(jié)，整體經(jīng)過十輪操作，第一輪到第九輪的論函數(shù)一樣，包括四個操作：字節(jié)代換、行移位、列混合和輪密鑰加。最后一輪迭代不執(zhí)行列混合。值得一提的是在字節(jié)代換中用到的S盒置換運(yùn)用到了近世代數(shù)的知識。

2.RSA公鑰算法RSA的基礎(chǔ)是數(shù)論的歐拉函數(shù)，它的安全性依賴于大整數(shù)因子分解的困難性。RSA公鑰密碼體制既可用于加密，也可用于數(shù)字簽名，且具有安全、易懂、易實現(xiàn)等特點。算法過程如下：公鑰為n（兩素數(shù)p和q的乘積），公鑰e：滿足gcd（e，準(zhǔn)（n））=1，準(zhǔn)（n）=（p-1）（q-1）私鑰d=e-1mod準(zhǔn)（n），加密算法c=memodn，解密算法m=cdmodn。

3.ElGamal簽名體制ElGamal數(shù)字簽名方案是一種非確定性的簽名方案，即對給定的一個消息，由于選擇的隨機(jī)數(shù)不同而又不同的數(shù)字簽名，并且驗證算法能夠?qū)⑺鼈冎械娜魏我粋€作為有效的簽名而接受。下面簡要介紹其方案的實現(xiàn)過程。

（1）初始化：選擇一個滿足安全性要求的大素數(shù)p，然后選擇一個生成元g∈Z*P和隨機(jī)數(shù)

x∈RZ*P-1（其中*表示除去零元，R表示隨機(jī)選取），

計算y=gxmodp。則簽名者A的公鑰為（p，g，y），私鑰為x。

（2）簽名過程：設(shè)待簽消息為m，簽名者選擇隨機(jī)數(shù)

k∈RZ*P，計算：r=gkmodps=[h（m）-xr]k-1mod（p-1）。

則對消息m的數(shù)字簽名為（r，s），其中h為安全的Hash

函數(shù)。

（3）驗證過程：簽名接收者B收到消息m和簽名（r，s）后，

首先計算h（m），然后驗證等式：

yrrs=gh（m）modp，如等式成立，則

簽名有效；否則簽名無效。

三、小結(jié)

本文主要基于數(shù)學(xué)中的數(shù)論、線性代數(shù)、近世代數(shù)等理論介紹了它們在密碼學(xué)中的應(yīng)用，這些數(shù)學(xué)基礎(chǔ)與密碼學(xué)緊密相關(guān)。密碼學(xué)中的加密、解密、破譯都與數(shù)學(xué)聯(lián)系在一起，數(shù)學(xué)密碼已成為密碼學(xué)中的主流學(xué)科。

參考文獻(xiàn)：

[1]谷利澤，等.現(xiàn)代密碼學(xué)教程[M].北京：北京郵電大學(xué)出版社，2009.

[2]潘承洞，等.初等數(shù)論[M].北京：北京大學(xué)出版社，2003.

[3]楊 波.現(xiàn)代密碼學(xué)[M].北京：清華大學(xué)出版社，2003.