密碼學(xué)中數(shù)學(xué)的應(yīng)用分析

馬偉芳 唐國(guó)梅

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

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

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

引言

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

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

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

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

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

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

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

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

2.RSA公鑰算法RSA的基礎(chǔ)是數(shù)論的歐拉函數(shù)，它的安全性依賴于大整數(shù)因子分解的困難性。RSA公鑰密碼體制既可用于加密，也可用于數(shù)字簽名，且具有安全、易懂、易實(shí)現(xiàn)等特點(diǎn)。算法過(guò)程如下：公鑰為n（兩素?cái)?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ù)字簽名方案是一種非確定性的簽名方案，即對(duì)給定的一個(gè)消息，由于選擇的隨機(jī)數(shù)不同而又不同的數(shù)字簽名，并且驗(yàn)證算法能夠?qū)⑺鼈冎械娜魏我粋€(gè)作為有效的簽名而接受。下面簡(jiǎn)要介紹其方案的實(shí)現(xiàn)過(guò)程。

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

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

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

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

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

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

函數(shù)。

（3）驗(yàn)證過(guò)程：簽名接收者B收到消息m和簽名（r，s）后，

首先計(jì)算h（m），然后驗(yàn)證等式：

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

簽名有效；否則簽名無(wú)效。

三、小結(jié)

本文主要基于數(shù)學(xué)中的數(shù)論、線性代數(shù)、近世代數(shù)等理論介紹了它們?cè)诿艽a學(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.