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