談到現(xiàn)代密碼學(xué)，其中數(shù)論的影響舉足輕重。計(jì)算機(jī)算法的實(shí)現(xiàn)、密碼算法的構(gòu)造、軟硬件的優(yōu)化，都離不開數(shù)論的理論支持。作為信息安全行業(yè)的工作者和學(xué)生，數(shù)論是我們無法繞開的高山，是心底無法撫平的憂傷。而中國剩余定理，算是***恨交織的那一部分吧。

[[226689]]

遍尋信息安全的數(shù)學(xué)基礎(chǔ)，歐幾里得、歐拉、費(fèi)爾馬、伽羅瓦都是西域來的高山，只有中國剩余定理，那是有古籍為證的咱中國特產(chǎn)。懷著自豪的心去聽，發(fā)現(xiàn)一樣聽不懂。感覺自己白進(jìn)化了兩千年……

研究中國剩余定理以前，必須要了解其對(duì)信息安全行業(yè)的應(yīng)用價(jià)值，以公鑰密碼為例。1976年，Diffie和Hellman提出的DH密鑰協(xié)商協(xié)議開創(chuàng)了基于數(shù)學(xué)難題的公鑰密碼新時(shí)代。公鑰密碼設(shè)計(jì)的基本思路是：尋找一個(gè)公認(rèn)的數(shù)學(xué)難題，在難題的基礎(chǔ)上構(gòu)建密碼算法。例如DH密鑰協(xié)商算法的有效性依賴于計(jì)算離散對(duì)數(shù)的難度，使得有限域中已知明文M計(jì)算密文C簡(jiǎn)單，但已知C計(jì)算M困難。Alice與Bob為了安全通信，需要安全交換一個(gè)密鑰，于是他們倆分別選擇了自己的秘密a和b，g是雙方已知的大素?cái)?shù)的原根，計(jì)算Ca=g^a，Cb=g^b，得到對(duì)方的Ca和Cb后，兩人分別計(jì)算Cab=Ca^b=Cb^a=g^ab，這樣，Alice與Bob偷偷完成了公共密鑰的協(xié)商，以后就可以加密通信啦。計(jì)算g^a，在數(shù)學(xué)家的手里就是一條公式，但真正操作起來，g和a可能是一個(gè)1024或2048位的二進(jìn)制大數(shù)，我們現(xiàn)在的計(jì)算機(jī)CPU也不過能一次性操作64位的二進(jìn)制——草稿紙都寫不下的數(shù)字怎么計(jì)算連乘？沒問題，中國剩余定理來幫你。

中國剩余定理原理

中國剩余定理（Chineseremaindertheorem，CRT），又稱為孫子剩余定理，最早見于《孫子算經(jīng)》的下卷第28題“物不知數(shù)”：

有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之有三，七七數(shù)之有二，問物幾何？

大意是，這邊有一堆物品不知道數(shù)量，有人三個(gè)三個(gè)地?cái)?shù)***剩了兩個(gè)，有人五個(gè)五個(gè)的數(shù)***剩了三個(gè)，有人七個(gè)七個(gè)的數(shù)***剩了兩個(gè)，請(qǐng)問這堆物品應(yīng)該是多少個(gè)？

這道題很像民間傳說“韓信點(diǎn)兵”。秦朝末年，楚漢相爭(zhēng)。一次，韓信與楚王大將李鋒交戰(zhàn)。苦戰(zhàn)一場(chǎng)，楚軍不敵，敗退回營，漢軍也死傷四五百人，于是韓信整頓兵馬也返回大本營。當(dāng)行至一山坡，忽有后軍來報(bào)，說有楚軍騎兵追來。只見遠(yuǎn)方塵土飛揚(yáng)，殺聲震天。漢軍本來已十分疲憊，這時(shí)隊(duì)伍大嘩。韓信兵馬到坡頂，見來敵不足五百騎，便急速點(diǎn)兵迎敵。他命令士兵3人一排，結(jié)果多出2名；接著命令士兵5人一排，結(jié)果多出3名；他又命令士兵7人一排，結(jié)果又多出2名。韓信馬上向?qū)⑹總冃迹何臆娪?073名勇士，敵人不足五百，我們居高臨下，以眾擊寡，一定能打敗敵人。于是漢軍士氣大振，一時(shí)間旌旗搖動(dòng)，鼓聲喧天，漢軍步步進(jìn)逼，楚軍亂作一團(tuán)。交戰(zhàn)不久，楚軍大敗而逃。故事中韓信的點(diǎn)兵方法是中國剩余定理的一種實(shí)際應(yīng)用了。

[[226690]]

古人是如何描述剩余定理的呢？《孫子算經(jīng)》后文給出了“物不知數(shù)”問題的剩余解法，“術(shù)曰：三三數(shù)之，剩二，置一百四十；五五數(shù)之，剩三，置六十三；七七數(shù)之，剩二，置三十。并之，得二百三十三，以二百一十減之，即得。凡三三數(shù)之，剩一，則置七十；五五數(shù)之，剩一，則置二十一；七七數(shù)之，剩一，則置十五。一百六以上，以一百五減之，即得。”“物不知數(shù)”為后來的“大衍求一術(shù)”的起源，被看作是中國數(shù)學(xué)史上最有創(chuàng)造性地成就之一，稱為中國剩余定理。

為方便讀者理解中國剩余定理，用現(xiàn)今的數(shù)論知識(shí)描述此定理如下[1]：

設(shè)m1，m2，…，mk是大于1的k（k≥2）個(gè)兩兩互素的正整數(shù)，b1，b2，…，bk∈Z,由k個(gè)一元一次同余方程聯(lián)立的方程組如下：

下面以我國古代數(shù)學(xué)家楊輝在1275年所寫的《續(xù)古摘奇算法》中的一道題目作為例子詳解中國剩余定理求解過程。

題目：二數(shù)余一，五數(shù)余二，七數(shù)余三，九數(shù)余四，問本數(shù)。

解：由題意有

中國剩余定理歷史發(fā)展演進(jìn)

中國剩余定理歷史發(fā)展演進(jìn)路線如下圖所示:

圖1中國剩余定理歷史發(fā)展演進(jìn)路線簡(jiǎn)圖[2]

中國剩余定理的應(yīng)用

現(xiàn)代密碼學(xué)

在現(xiàn)代密碼學(xué)領(lǐng)域，RSA公鑰密碼體制至今仍被認(rèn)可和采用，是公認(rèn)的安全性良好的密碼體制，也是現(xiàn)階段比較常用的密碼體制。而基于中國剩余定理的單基數(shù)轉(zhuǎn)換法（SRC）和混合基數(shù)轉(zhuǎn)換法（MRC）可以快速實(shí)現(xiàn)RSA的解密，解密速度大約提高四倍左右，這在無論軟件還是硬件實(shí)現(xiàn)RSA密碼算法都是非常重要的[3]。中國剩余定理還可以應(yīng)用在輕量級(jí)密碼設(shè)計(jì)、PKI認(rèn)證系統(tǒng)、通信編碼等等，在信息安全領(lǐng)域中占有非常重要的地位。

多項(xiàng)式

結(jié)語

在一次同余式組問題上，中國剩余定理的研究在古代遠(yuǎn)遠(yuǎn)領(lǐng)先于世界，可以說明中國人的數(shù)學(xué)能力是及其出眾的。古人對(duì)數(shù)學(xué)的貢獻(xiàn)是我們的寶貴財(cái)富，中國剩余定理在密碼學(xué)上的應(yīng)用只是其價(jià)值的部分體現(xiàn)，愿研究者們可以充分利用這些財(cái)富創(chuàng)造更多更大的榮耀。

參考文獻(xiàn)

[1]谷利澤、楊義先.現(xiàn)代密碼學(xué)教程[M].北京郵電大學(xué)出版社出版.2009:53

[2]鄧真崢.中國剩余定理的中外歷史發(fā)展比較[D].四川師范大學(xué),2017.

[3]賀毅朝,劉建芹,陳維海.中國剩余定理在RSA解密中的應(yīng)用[J].河北省科學(xué)院學(xué)報(bào),2003,20(3):138-143.

【本文為51CTO專欄作者“中國保密協(xié)會(huì)科學(xué)技術(shù)分會(huì)”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】

戳這里，看該作者更多好文