[發(fā)明專利]實(shí)現(xiàn)橢圓曲線類型公共密鑰加密算法的電子部件中的對(duì)策方法

有效

• 申請(qǐng)?zhí)枺?/td>: 00805519.X
• 申請(qǐng)日: 2000-03-22
• 公開（公告）號(hào): CN1345496A
• 公開（公告）日: 2002-04-17
• 發(fā)明（設(shè)計(jì)）人: J·S·科龍
• 申請(qǐng)（專利權(quán)）人: 格姆普拉斯公司
• 主分類號(hào): H04L9/30
• 分類號(hào): H04L9/30
• 代理公司: 中國(guó)專利代理(香港)有限公司
• 代理人: 吳立明,張志醒

本發(fā)明涉及在電子部件中實(shí)現(xiàn)橢圓曲線類型公共密鑰加密算法的對(duì)策方法(countermeasure)。

在密鑰加密技術(shù)的傳統(tǒng)模型中，希望通過(guò)一個(gè)非安全信道通信的兩個(gè)人必須先同意一個(gè)加密密鑰K。加密函數(shù)和譯碼函數(shù)實(shí)現(xiàn)相同的密鑰K。密鑰加密系統(tǒng)的缺點(diǎn)是上述系統(tǒng)要求在任何已加密的信息在非安全信道上發(fā)送之前密鑰必須先在兩個(gè)人之間通過(guò)一個(gè)安全信道優(yōu)先通信。實(shí)際上，發(fā)現(xiàn)一個(gè)很安全的通信信道通常是困難的，尤其在分離兩個(gè)人的距離很遠(yuǎn)時(shí)。安全信道意味著對(duì)它來(lái)說(shuō)知悉或修改在它上面通過(guò)的信息是不可能的。這樣的安全信道可以通過(guò)連接由上述兩人所擁有的兩個(gè)終端的電纜來(lái)實(shí)現(xiàn)。

公共密鑰加密概念由Whitfield?Diffie和Martin?Hellman在1976年發(fā)明。公共密鑰加密技術(shù)使解決在非安全信道上密鑰的分布問(wèn)題成為可能。公共密鑰加密的原理在于使用一對(duì)密鑰，一個(gè)公共加密密鑰和一個(gè)私有譯碼密鑰。由觀察的計(jì)算點(diǎn)去從公共加密密鑰找到私有的譯碼密鑰是不可行的。希望與B人交流信息的A人使用B人的公共加密密鑰。只有B人擁有與它的公共密鑰相關(guān)的私有密鑰。因此只有B人能夠破譯送給他的信息。

密鑰加密技術(shù)上公共密鑰加密的另一個(gè)優(yōu)勢(shì)是公共密鑰加密允許用電子簽名授權(quán)。

公共密鑰加密方案的第一個(gè)實(shí)施方案在1977年由Rivest?Shamir和Adleman開發(fā)，他們發(fā)明了RSA加密系統(tǒng)。RSA安全性是基于把一個(gè)是兩個(gè)質(zhì)數(shù)乘積的大數(shù)進(jìn)行因式分解的難度。

其后，提出了很多公共密鑰加密系統(tǒng)，它們的安全性基于不同的計(jì)算問(wèn)題(這個(gè)列表不是詳細(xì)無(wú)遺的)：

-Merckle-Hellman背包(backpack)：

這個(gè)加密系統(tǒng)基于子集的和的問(wèn)題的難度。

-McEliece：

這個(gè)加密系統(tǒng)基于代數(shù)代碼的理論。它基于線性代碼的解碼問(wèn)題。

-E1?Gamal：

這個(gè)加密系統(tǒng)基于有限域中離散對(duì)數(shù)的難度。????

-橢圓曲線：

橢圓曲線加密系統(tǒng)構(gòu)成了對(duì)已有加密系統(tǒng)的修正以把它們應(yīng)用于橢圓曲線領(lǐng)域。

橢圓曲線在加密系統(tǒng)中的使用分別由Victor?Miller和NealKoblitz在1985年提出。橢圓曲線的實(shí)際應(yīng)用早在二十世紀(jì)九十年代就被注意到了。

基于橢圓曲線的密碼系統(tǒng)的優(yōu)勢(shì)是它們用較小的密鑰尺寸提供等價(jià)于其它密碼系統(tǒng)的安全性。密碼尺寸中的這個(gè)存儲(chǔ)減小了存儲(chǔ)要求并縮短了計(jì)算時(shí)間，這使得橢圓曲線的使用尤其適合于智能卡類型的應(yīng)用。

在一個(gè)有限域GF(q^n)(q是一個(gè)質(zhì)數(shù)，n是一個(gè)整數(shù))上的一個(gè)橢圓曲線是點(diǎn)(x，y)的集合且x(X-軸)和y(Y軸)屬于GF(q^n)，方程式的解為：

y^2＝x^3+ax+b

如果q大于或等于3及

y^2+x*y＝x^3+a*x^2+b

如果q＝2

在加密中用得最多的兩類橢圓曲線是下面兩類：

1)在有限域GF(p)(整數(shù)模p的集合，p是一個(gè)質(zhì)數(shù))上

定義的曲線，它的方程為：

y^2＝x^3+ax＝b

2)定義在有限域GF(2^n)上的橢圓曲線，它的方程為：

y^2+xy＝x^3+ax^2+b

對(duì)這兩類曲線中的每一類來(lái)說(shuō)，定義點(diǎn)的加法操作如下：給定兩個(gè)點(diǎn)P和Q，和R＝P+Q是曲線上的一個(gè)點(diǎn)，它的坐標(biāo)按照Alfred?JMenezes的著作“橢圓曲線公共密鑰密碼系統(tǒng)”中所給出的公式用點(diǎn)P和Q的坐標(biāo)來(lái)表示。

這個(gè)加法操作使定義一個(gè)標(biāo)量乘法操作成為可能：給定屬于橢圓曲線的一個(gè)點(diǎn)P和一個(gè)整數(shù)d，P由d標(biāo)量乘的結(jié)果是Q＝P+PP+…..+d次P。

橢圓曲線上加密算法的安全性基于橢圓曲線上離散對(duì)數(shù)的難度，上述問(wèn)題包括，用屬于橢圓曲線E的點(diǎn)Q和P來(lái)找到這樣的整數(shù)x使得Q＝x.P，如果存在這樣的x的話。

有很多基于離散對(duì)數(shù)問(wèn)題的加密算法。

這些算法可以被很容易地移植到橢圓曲線上。這樣就能夠用算法提供鑒定，機(jī)密性，完整性校驗(yàn)和密鑰交換。

基于橢圓曲線的大部分加密算法的一個(gè)共同點(diǎn)是它們包含一個(gè)定義在有限域上的橢圓曲線作為參數(shù)及該橢圓上的一個(gè)點(diǎn)P。私有密鑰是一個(gè)隨機(jī)選中的整數(shù)d。公共密鑰是曲線Q上的一個(gè)點(diǎn)，而Q＝d.P。這些加密算法通常都涉及點(diǎn)R＝d.T的計(jì)算中的標(biāo)量乘法，其中d是密鑰。

在這一節(jié)中描述了一個(gè)基于橢圓曲線的加密算法。這個(gè)方案類似于E1?Gamal加密方案。消息m被加密如下：