只能被1和本身整除的數(shù)叫質(zhì)數(shù),例如13,質(zhì)數(shù)是無窮多的.得到兩個巨大質(zhì)數(shù)的乘積是簡單的事,但想從該乘積反推出這兩個巨大質(zhì)數(shù)卻沒有任何有效的辦法,這種不可逆的單向數(shù)學(xué)關(guān)系,是國際數(shù)學(xué)界公認(rèn)的質(zhì)因數(shù)分解難題.
R、S、A三人巧妙利用這一假說,設(shè)計(jì)出RSA公匙加密算法的基本原理：1、讓計(jì)算機(jī)隨機(jī)生成兩個大質(zhì)數(shù)p和q,得出乘積n；2、利用p和q有條件的生成加密密鑰e；3、通過一系列計(jì)算,得到與n互為質(zhì)數(shù)的解密密鑰d,置于操作系統(tǒng)才知道的地方；4、操作系統(tǒng)將n和e共同作為公匙對外發(fā)布,將私匙d秘密保存,把初始質(zhì)數(shù)p和q秘密丟棄.
國際數(shù)學(xué)和密碼學(xué)界已證明,企圖利用公匙和密文推斷出明文--或者企圖利用公匙推斷出私匙的難度等同于分解兩個巨大質(zhì)數(shù)的積.這就是Eve不可能對Alice的密文解密以及公匙可以在網(wǎng)上公布的原因.
至于"巨大質(zhì)數(shù)"要多大才能保證安全的問題不用擔(dān)心：利用當(dāng)前可預(yù)測的計(jì)算能力,在十進(jìn)制下,分解兩個250位質(zhì)數(shù)的積要用數(shù)十萬年的時間；并且質(zhì)數(shù)用盡或兩臺計(jì)算機(jī)偶然使用相同質(zhì)數(shù)的概率小到可以被忽略.