【密碼學原理】橢圓曲線密碼學

要建立基于橢圓曲線的密碼體制，需要有類似因子分解兩個素數之積或者求離散對數這樣的困難問題。

如果對于方程

，其中

，對給定的

和

計算

是容易的，但是對給定的

和

計算

是困難的，我們認為這就是橢圓曲線的離散對數問題。

用橢圓曲線密碼實作Diffie-Hellman密鑰交換

橢圓曲線的方程為

或者

，選擇大整數

和參數

，其中

為素數

，或者形為

的整數。橢圓群

，在

中挑選基點

，

的階為一個非常大的數

，點

的階

使得

成立的最小正整數。

Alice和Bob之間完成密鑰交換的過程如圖所示

要破解這種體制，攻擊者必須由

和

算出

，但這個是困難的。

這裡的密鑰是一對數字。

橢圓曲線加密和解密

首先将明文

編碼為形如

的點

，并對點

加密和解密。

Alice選擇一個私鑰

，産生公鑰

Alice将

加密後發送給Bob，A随機選擇一個正整數

，産生密文

：

Bob對密文解密，需要用第二個點減去第一個點與Bob的私鑰之積：

Alice通過将

和

相加來僞裝消息

，隻有ALice知道

是以除了Alice其他人不能僞裝

，但是在僞裝後的消息中包含了線索，是以在已知私鑰

的時候可以除去僞裝。

要破解這種體制，攻擊者必須由

和

算出

，但這個是困難的。