數學基礎
取模運算(“Modulo Operation”)和取餘運算(“Complementation ”)兩個概念有重疊的部分但又不完全一致。主要的區別在於對負整數進行除法運算時操作不同。取模主要是用於計算機術語中。取餘則更多是數學概念。
%是除法取餘運算。 用於整數與整數運算。如5%3=2。
冪模運算轉化為乘模運算。
a*b % n = (a % n)*(b % n) % n
模冪乘運算採用平方乘算法,將模冪乘運算轉化為模乘和模平方運算實現
對於任意指數E,都可採用以下算法計算D=C**E % N:
D=1
WHILE E>0
IF E%2=0
C=C*C % N
E=E/2
ELSE
D=D*C % N
E=E-1
RETURN D
橢圓曲線
橢圓曲線密碼是一種公鑰密碼算法,公鑰密碼算法最根本的原理是利用信息的不對稱性。私鑰擁有者把信息的一部分公開披露,披露的信息記為公鑰。
一個公鑰密碼算法安全的必要條件(非充分)是“由公鑰不能反推出私鑰”。橢圓曲線密碼也是一個基於加法階數難求問題的密碼方案。橢圓曲線密碼裡的加法建立在 “有限域上的二元三次曲線上的點”上 ,組成一個“有限加法循環群”。
這個加法的幾何定義如下面兩個圖,兩個點的加法結果是指這兩點的連線和曲線的交點關於x軸的鏡像。
對橢圓曲線來說最流行的有限域是以素數為模的整數域。
橢圓曲線離散對數問題(ECDLP)就是給定點P和Q,確定整數k使k*P=Q。
給定素數p和橢圓曲線E,對Q=kP,在已知P,Q 的情況下求出小於p的正整數k。可以證明由k和P計算Q比較容易,而由Q和P計算k則比較困難。
將橢圓曲線中的加法運算與離散對數中的模乘運算相對應,將橢圓曲線中的乘法運算與離散對數中的模冪運算相對應。
閱讀更多 程序分享聯盟 的文章