劉佳

摘 要：力求用最通俗的語言，以“秘密分享、RSA系統(tǒng)和背包問題”這幾個專題為例，介紹說明數(shù)論方法在現(xiàn)代密碼學中的應用。密碼學的研究與分析離不開大量的數(shù)學知識，不過應用最多的還是數(shù)論知識。所以說數(shù)論對以后學習及深入研究密碼學相關理論都有非常重要的作用。

關鍵詞：秘密分享；RAS系統(tǒng)；背包問題

密碼的歷史極其久遠，其起源可以追溯到幾千年前。人類有記載的通信密碼始于公元前400年。有人說，第一次世界大戰(zhàn)是化學家的戰(zhàn)爭，第二次世界大戰(zhàn)是物理學家的戰(zhàn)爭，如果未來發(fā)生戰(zhàn)爭是數(shù)學家的戰(zhàn)爭，其核心是信息戰(zhàn)中的軍事密碼學問題。在我國古代就不乏以藏頭詩的形式把真正的信息隱藏于整個詩篇中，從而只讓某些掌握了規(guī)律的人知道的例子。又如古羅馬凱撒大帝通過將拼音字母向后移三位的方法向賽查羅發(fā)布命令。更早些時候，古希臘歷史學家波里比阿利用刪去了J的25字母方陣創(chuàng)造出了通過用表示行和列的兩個字母去表示方陣中的一個字母的方法等等。這都可以看作是密碼學的雛形。直到20世紀中葉，密碼學主要應用于軍事或外交方面的消息傳送上，隨著計算機科學的迅速發(fā)展和信息時代的到來，現(xiàn)代密碼學的應用范圍已經(jīng)遠遠超出了軍事與外交領域，在金融、財貿(mào)和商業(yè)等領域也有重要的作用?，F(xiàn)代密碼學是與計算機緊密聯(lián)系的，而它所使用的數(shù)學工具涉及數(shù)論、布爾函Walsh函數(shù)、群論、有限域理論、邏輯學乃至代數(shù)幾何學中的橢圓曲線理論。不過，應用最多的還是數(shù)論。此文的目的則是力求用最通俗的語言說明數(shù)論方法在現(xiàn)代密碼學中的應用，而其對以后學習及深入研究密碼學相關理論都有非常重要的作用。

一、一種秘密分享方案

秘密是一種不公開的信息，自然也是語言。從數(shù)學角度看一個秘密就是一個字母S，古代曾有過在一個重要的鐵門上鎖三把鎖，鑰匙分別由三個人保存，只有三個人都到齊了才能開門的例子?，F(xiàn)代密碼學中也有類似的情況。早在1979年Shamir就提出了秘密分享的理論。在所謂（t，n）門限秘密分享體制中，秘密被分成了n個份額，至少要掌握t個份額才能獲得這個秘密。為了搞清楚什么是秘密分享，我們先看一個我國古代“韓信點兵”中的數(shù)學問題。據(jù)說韓信在統(tǒng)計士兵的人數(shù)時用到了這樣一首詩：

三人同行七十稀，五樹梅花廿一枝。七子團圓正月半，除百去五便得知。

這里“正月半”表示15，計算人數(shù)的方法是：3人一組，分列所剩的人（只能是0，1或2）乘以70；將5人一組，分列所剩的人數(shù)乘以21；將7人一組，分列所剩的人數(shù)乘以15，然后將以上三個結果相加再減去若干個105，就得到士兵的人數(shù)了。比如，若士兵3人一組站立剩一人，5人一組站立剩4人，7人一組站立剩3人，那么，士兵的人數(shù)為1×70+4×21+3×15-105=94。再如，若士兵人數(shù)被3，5和7除所得余數(shù)分別為2，4和5。則士兵人數(shù)可以從2×70+4×21+5×15=299中減去1或2個105而求得。究竟是減去105還是210，對統(tǒng)兵的人來說是很容易的，因為他當然對有多少士兵是心中有數(shù)的。比如，統(tǒng)兵的人知道士兵的人數(shù)是197，那么就應當從299中減去1個105得出194，那么他就會發(fā)現(xiàn)有3人缺席。如果士兵總共有90人，那么則要從299中減去2個105得9，表明有1人缺席。容易看出，105是3，5和7的乘積。至于70，21和15是如何得到的，本文不予細說，因為我們的目的是介紹數(shù)論的這一方法在秘密分享策略中的應用。首先要注意，由已知某數(shù)被3，5和7去除所得的余數(shù)去求某數(shù)，只可能得出某數(shù)的可能值，比如在前面的第二個例子中，士兵的人數(shù)可能是194，也可能是89，再者是減去幾個105還是加上幾個105也是不能完全確定的。比如，在上例中如果給出299加上105所得的數(shù)404被3，5和7除的余數(shù)分別為2，4和5，再加幾個105后分別得509，614，719…等也是滿足同樣的條件。當然如果已知人數(shù)不超過105，那么就只有唯一解89了?，F(xiàn)在假設只告訴某數(shù)被3除余2，被5除余4，而要求出某數(shù)，那么可能的答案就有14，29，44，59，74，89，104，119…。進一步，如果只告訴某數(shù)被3除余2，那么可能的答案就更多了：5，8，11，14，…89，92…如果現(xiàn)在設想89是一個秘密，由3個人分享。第一個人只知道那是一個被3整除余2的數(shù)，第二個人知道那是一個被5除余4的數(shù)，而第三個人則知道那是一個被7除余5的數(shù)。那么這三個人中的每一個人都不可以斷定這個秘密到底是什么。但如果這三個人現(xiàn)在在一起，就可以在一定的條件下很容易得出來結果是89。一種秘密分享方案正是基于這種思想而得出來的。我們先把以上的數(shù)學方法加以推廣。

下面是國際上通稱的“中國剩余定理”，也可以稱為“孫子剩余定理”或“孫子定理”，它的證明并不復雜，我們演示如下：

孫子定理內(nèi)容：

設m1，…，mk是兩兩既約的正整數(shù)，那么，對于任意的整數(shù)a1，…，ak一次同余方程組x≡aj（modmj），1≤j≤k①必有解，且解數(shù)為1，事實同余方程組①的解是x≡M1M1-1a1+…+MkMk-1ak（modm）②

這里m=m1…mk，m=mjMj（1≤j≤k），以及Mj-1是滿足MjMj-1≡1（modmj），1≤j≤k③的一個整數(shù)（即是Mj對模mj的逆）

證：先證明解的存在性。

再證明解的唯一性：

若x1，x2是適合于同余式組的任意兩個整數(shù)：x1≡bi（modmi），x2≡bi（modmi），i=1，2，…k，所以x1≡x2（modmi），i=1，2，…k，又（mi，mj）=1，i≠j，從而x1≡x2（modmi），i=1，2，…k，故解是唯一的，證畢。

二、RSA系統(tǒng)

一種應用非常廣泛的密碼系統(tǒng)，由Rivest、Shamir和Adleman提出，就是如今被稱為RSA的密碼系統(tǒng)。RSA公鑰密碼體制是基于大整數(shù)分解的公開密鑰體制的代表算法。大整數(shù)分解問題可以被表述為：已知整數(shù)n，n是兩個素數(shù)p、q的乘積，即n=pq，求解p和q的值。

首先，回憶一下數(shù)論中的有關概念：設n是正整數(shù)用ψ（n）=1{0≤x

1.加密方法

2.還原定理

設n，e，d如下所述，則ω=[（ωe，modn）d，modn]

3.解密方法

所謂解密就是要從c=ωe密文恢復出來，由還原定理知共需將密文c再d次方，然后再模n進行約簡即得ω如密文c=1281，由d=157知由c157模去若干個n即得明文（1281157，mod2773）=1901。

注：在上例中曾涉及（190117，mod2773）與（1281157，mod2773）的計算，看起來似乎計算量大得驚人，其實不然，以第一個計算為例：19012≡582（mod2773）也容易算出來。因此，不容易得出19014≡252≡1625（mod2773）最后得出190117625×1901≡1281（mod2773）

三、背包問題

在最初提出公鑰密碼思想的時候，還沒有一個這樣的實例。兩年后首先由Merkle和Hellman提出一個基于組合數(shù)學中背包問題的公鑰密碼系統(tǒng)。這個背包系統(tǒng)稱為MH背包問題。

背包問題是這樣的：已知有n個物品，它們重量分別為a1，a2…an，現(xiàn)在其中裝有某些物品，重量為b的背包，問裝的是哪些物品？

需要注意的是，并非所有的背包問題都沒有有效算法求解。如序列a1，a2，…，an滿足條件：ai>■aji=2，3，…n成立時，有多項式解法。這樣的序列稱為超遞增序列。如1，3，6，13，27，52是一個超遞增序列，而1，3，4，9，15，25則不是。

超遞增背包問題的解是容易找到的。將總質(zhì)量與序列中最大的數(shù)比較，如果總質(zhì)量小于這個數(shù)，則它不在背包中；如果總質(zhì)量大于這個數(shù)，則它在背包中，用背包質(zhì)量減去這個數(shù)，轉(zhuǎn)向考察序列下一個最大的數(shù)，重復直到結束。如果總質(zhì)量變?yōu)榱悖敲从幸粋€解，否則無解。

背包公鑰密碼系統(tǒng)的實現(xiàn)方案就是選取一組正整數(shù)a1，a2，…，an作為公鑰予以公布m=m1m2…，mn，是n位0，1明文符號串。利用公鑰加密如下：

于是從超遞增序列得此序列時，從外表上不再具有超遞增假定已知：

參考文獻：

[1]蔡樂才.應用密碼學.北京：中國電力出版社，2005.

[2]章照止.現(xiàn)代密碼學基礎.北京郵電大學出版社，2004.

[3]劉木蘭，龔奇敏.密碼學進展.北京：科學出版社，1998.

[4]楊義先.現(xiàn)代密碼新理論.北京：科學出版社，2002.

[5]潘承洞，潘永彪.初等數(shù)論.北京大學出版社，2003.

（作者單位 上海市民辦交大——飛達中學）