“不可破譯”的密碼
時間：
孫宏安1由 分享
密碼在當今社會生活中的作用可以說十分巨大，除了眾所周知的軍事國防方面的應用外，現(xiàn)代金融、貿易、生產等無不在大規(guī)模使用密碼．計算機網(wǎng)絡的廣泛應用，使人們對密碼的依賴達到了新的高度，在千百萬臺計算機聯(lián)結成的因特網(wǎng)上，用戶的識別基本上是靠密碼．密碼被破譯就會產生危及安全的極嚴重的后果．計算機“黑客”的作為，即為密碼破譯的一例，連美國國防部的計算機都未能幸免，可見密碼編制的難度了．
?由大整數(shù)因數(shù)分解的困難，人們研制成功一種“不可破譯”的密碼：ＲＳＡ體制密碼（見本刊2000年第6期《大整數(shù)的因數(shù)分解問題》一文）．ＲＳＡ密碼是一種公開密鑰密碼，說它“不可破譯”是形容破譯之難，不過的確至今尚沒找到破譯的理論工具．
?一般密碼編制理論中，稱要傳遞的原文為“明文”，經加密后實際傳遞的是密碼構成的“密文”，收信方則將其解密，恢復為明文使其可理解，就完成了通信任務．這其中加密和解密要用通信雙方約定的方法，這一方法就稱為密鑰．更一般地，人們首先給定一個加密算法，不太嚴格地說，可把這一算法視為函數(shù)，函數(shù)的值就是密鑰，而解密算法可以說是加密算法的一個反函數(shù)，使用同一個密鑰（原函數(shù)的值）可將密文惟一地譯成明文．
?密碼的關鍵就在于通信雙方約定密鑰而不被外界所知，外界對密碼的破譯也就指向密鑰了．而且為了防止外界可能的破譯，就應盡力使外人不可能積累在同一密鑰下的許多密文，否則可用統(tǒng)計分析法等確定出密鑰，世界戰(zhàn)爭史、外交史上有許多破譯成功的例子．這樣就經常變換密鑰，重要的通信要每天一換甚至通一次信換一次．
?這么頻繁換的密鑰怎樣送給對方？如果隨其他信息（用無線電或網(wǎng)絡）易于失密，每次派專人送又不可能，怎樣解決這一問題呢？這就是ＲＳＡ密碼的長處了，它把密鑰分成加密鑰和解密鑰．如Ａ和Ｂ通信，Ａ把加密鑰公開送達Ｂ（可用明碼電報或與上次通信同時），不怕外人知道，所以叫公開密鑰，而解密鑰留在自己處不送達Ｂ，Ｂ收到公開密鑰后，用它加密要給Ａ的信息，然后送回Ａ（這也無須特別秘密），則Ａ可用手中的解密密鑰解密．
?外人沒有解密密鑰，就無從破譯密碼了，那么加密鑰和解密鑰就沒有關系了嗎？當然不是，否則就無法解密了．不過這種關系正是建立在大整數(shù)因數(shù)分解困難的基礎上．換句話說，由公開密鑰得出解密鑰要進行一個充分大的整數(shù)的因數(shù)分解，你無法分解也就無法破譯．
?具體的編碼過程是，先找出兩個不同的大素數(shù)ｐ和ｑ，再給定一個數(shù)ｒ（一般是用計算機產生一個隨機數(shù)或至少一個偽隨機數(shù)，也可每次一換），使ｒ與數(shù)（ｐ－1）（ｐ－1）互素，這三個數(shù)ｐ、ｑ、ｒ就是解密密鑰．
?再求一個數(shù)ｍ，使（ｒｍ－1）能被（ｐ－1）（ｑ－1）整除．嚴格表述為：求ｍ，使
?ｒｍ≡1（ｍｏｄ（ｐ－1）（ｑ－1））．
?由于ｒ與（ｐ－1）（ｑ－1）互素，所以ｍ是一定可求出來的（有數(shù)論定理保證）．再求出數(shù)ｎ＝ｐｑ．ｍ、ｎ為加密密鑰，即公開密鑰．
?具體的加密方法為，設明文為ｘ，可把ｘ視為（或變?yōu)椋┮粋€大整數(shù)，設ｘ＜ｎ，若ｘ≥ｎ，則將ｘ表示為ｓ進位的形式（ｓ≤ｎ，常用ｓ＝2ｔ形式）的數(shù)，使其每一個數(shù)位上的數(shù)都小于ｎ，再分數(shù)位進行編碼．求一個數(shù)ｙ（0≤ｙ＜ｎ）使
?。?/span>≡ｘｍ（ｍｏｄｎ）（可理解為，使（ｙ－ｘｍ）能被ｎ整除），ｙ就是用ｍ、ｎ密鑰加密后的密文．
?解密過程為，求
?ｚ＝ｙｒ（ｍｏｄｎ）（0≤ｚ＜ｎ），
?在限定的條件（0≤ｙ＜ｎ，0≤ｚ＜ｎ）下有（可嚴格證明）
δ＝ｘ，
即得出明文．
?外人要想破譯密碼，就必須由ｍ、ｎ求出數(shù)ｒ來．
?由此可見，要找到ｒ必須由ｎ得出ｐ和ｑ，即對ｎ進行因數(shù)分解，如ｐ、ｑ取得相當大，即ｎ相當大，由于分解困難，無法破譯這一密碼．
由于運用現(xiàn)代計算機已可分解100位左右數(shù)的因數(shù)，因此ｎ要取得相當大，從而ｐ、ｑ也要取得相當大，比如每個數(shù)80位以上，再求積，這在技術上是可能的．
?是否還應考慮相應計算的復雜性和計算所需要的時間呢？當然有這方面的問題，現(xiàn)在通常用復合編碼法解決，即用其他計算比較簡單、耗時少的編碼方法編碼，而每次編碼所采用的密鑰用ＲＳＡ密碼來傳遞，這既加強了安全性，又加快了速度．
?由大整數(shù)因數(shù)分解的困難，人們研制成功一種“不可破譯”的密碼：ＲＳＡ體制密碼（見本刊2000年第6期《大整數(shù)的因數(shù)分解問題》一文）．ＲＳＡ密碼是一種公開密鑰密碼，說它“不可破譯”是形容破譯之難，不過的確至今尚沒找到破譯的理論工具．
?一般密碼編制理論中，稱要傳遞的原文為“明文”，經加密后實際傳遞的是密碼構成的“密文”，收信方則將其解密，恢復為明文使其可理解，就完成了通信任務．這其中加密和解密要用通信雙方約定的方法，這一方法就稱為密鑰．更一般地，人們首先給定一個加密算法，不太嚴格地說，可把這一算法視為函數(shù)，函數(shù)的值就是密鑰，而解密算法可以說是加密算法的一個反函數(shù)，使用同一個密鑰（原函數(shù)的值）可將密文惟一地譯成明文．
?密碼的關鍵就在于通信雙方約定密鑰而不被外界所知，外界對密碼的破譯也就指向密鑰了．而且為了防止外界可能的破譯，就應盡力使外人不可能積累在同一密鑰下的許多密文，否則可用統(tǒng)計分析法等確定出密鑰，世界戰(zhàn)爭史、外交史上有許多破譯成功的例子．這樣就經常變換密鑰，重要的通信要每天一換甚至通一次信換一次．
?這么頻繁換的密鑰怎樣送給對方？如果隨其他信息（用無線電或網(wǎng)絡）易于失密，每次派專人送又不可能，怎樣解決這一問題呢？這就是ＲＳＡ密碼的長處了，它把密鑰分成加密鑰和解密鑰．如Ａ和Ｂ通信，Ａ把加密鑰公開送達Ｂ（可用明碼電報或與上次通信同時），不怕外人知道，所以叫公開密鑰，而解密鑰留在自己處不送達Ｂ，Ｂ收到公開密鑰后，用它加密要給Ａ的信息，然后送回Ａ（這也無須特別秘密），則Ａ可用手中的解密密鑰解密．
?外人沒有解密密鑰，就無從破譯密碼了，那么加密鑰和解密鑰就沒有關系了嗎？當然不是，否則就無法解密了．不過這種關系正是建立在大整數(shù)因數(shù)分解困難的基礎上．換句話說，由公開密鑰得出解密鑰要進行一個充分大的整數(shù)的因數(shù)分解，你無法分解也就無法破譯．
?具體的編碼過程是，先找出兩個不同的大素數(shù)ｐ和ｑ，再給定一個數(shù)ｒ（一般是用計算機產生一個隨機數(shù)或至少一個偽隨機數(shù)，也可每次一換），使ｒ與數(shù)（ｐ－1）（ｐ－1）互素，這三個數(shù)ｐ、ｑ、ｒ就是解密密鑰．
?再求一個數(shù)ｍ，使（ｒｍ－1）能被（ｐ－1）（ｑ－1）整除．嚴格表述為：求ｍ，使
?ｒｍ≡1（ｍｏｄ（ｐ－1）（ｑ－1））．
?由于ｒ與（ｐ－1）（ｑ－1）互素，所以ｍ是一定可求出來的（有數(shù)論定理保證）．再求出數(shù)ｎ＝ｐｑ．ｍ、ｎ為加密密鑰，即公開密鑰．
?具體的加密方法為，設明文為ｘ，可把ｘ視為（或變?yōu)椋┮粋€大整數(shù)，設ｘ＜ｎ，若ｘ≥ｎ，則將ｘ表示為ｓ進位的形式（ｓ≤ｎ，常用ｓ＝2ｔ形式）的數(shù)，使其每一個數(shù)位上的數(shù)都小于ｎ，再分數(shù)位進行編碼．求一個數(shù)ｙ（0≤ｙ＜ｎ）使
?。?/span>≡ｘｍ（ｍｏｄｎ）（可理解為，使（ｙ－ｘｍ）能被ｎ整除），ｙ就是用ｍ、ｎ密鑰加密后的密文．
?解密過程為，求
?ｚ＝ｙｒ（ｍｏｄｎ）（0≤ｚ＜ｎ），
?在限定的條件（0≤ｙ＜ｎ，0≤ｚ＜ｎ）下有（可嚴格證明）
δ＝ｘ，
即得出明文．
?外人要想破譯密碼，就必須由ｍ、ｎ求出數(shù)ｒ來．
?由此可見，要找到ｒ必須由ｎ得出ｐ和ｑ，即對ｎ進行因數(shù)分解，如ｐ、ｑ取得相當大，即ｎ相當大，由于分解困難，無法破譯這一密碼．
由于運用現(xiàn)代計算機已可分解100位左右數(shù)的因數(shù)，因此ｎ要取得相當大，從而ｐ、ｑ也要取得相當大，比如每個數(shù)80位以上，再求積，這在技術上是可能的．
?是否還應考慮相應計算的復雜性和計算所需要的時間呢？當然有這方面的問題，現(xiàn)在通常用復合編碼法解決，即用其他計算比較簡單、耗時少的編碼方法編碼，而每次編碼所采用的密鑰用ＲＳＡ密碼來傳遞，這既加強了安全性，又加快了速度．