橢圓曲線實例

1、 基于橢圓曲線上的離散對數(shù)問題ECC2.實例： 橢圓曲線E23(1,0) 的點的構(gòu)造即y2 = x3 + x在有限域F23上的點的構(gòu)造(其中a=1,b=0)滿足條件的23個點是: (0,0)(1,18) (9,18) (11,13) (13,18) (15,20) (16,15) (17,13) (18,13) (19,22) (20,19) (21,17) (0,0) (1,5) (9,5) (11,10) (13,5) (15,3)(16,8) (17,10)(18,10) (19,1) (20,4) (21,6) 橢圓曲E23線上共有24個點(包括無窮遠點O)。除了(0,0)外，每一個x

2、都對應(yīng)兩個點，它們是互逆的，如p=(1,5)和-p=(1,-5)=(1.-5 mod 23)=(1,18),實際上(0,0)的逆是它本身。 基于橢圓曲線上的離散對數(shù)問題ECC2.實例:(多項式基于有限域GF(2m)上的橢圓曲線) : 考慮多項式 f(x) = x4 + x + 1定義的域GF(24). 元素g = (0010)是生成元.用多項式表示為 g=x , g的冪分別為: g0 = (0001) g1 = (0010) g2 = (0100) g3 = (1000) g4 = (0011) g5 = (0110) g6 = (1100) g7 = (1011) g8 = (0101) g

3、9 = (1010) g10 = (0111) g11 = (1110) g12 = (1111) g13 = (1101) g14 = (1001) g15 = (0001) g2 = x2 = (0100) ， g4 = x4 = x4 mod(x4 + x + 1) = x + 1=(0011) ，其余可類似求得?？紤]橢圓曲線： y2 + xy = x3 + g4x2 + 1. 其中 a = g4 ,b = g0 =1. 點 (g5, g3) 滿足橢圓曲線方程 : y2 + x y = x3 + g4x2 + 1 (g3)2 + g5g3 = (g5)3 + g4g10 + 1 g6 +

4、 g8 = g15 + g14 + 1 (1100) + (0101) = (0001) + (1001) + (0001) (1001) = (1001) 基于橢圓曲線上的離散對數(shù)問題ECC2.滿足方程y2 + xy = x3 + g4x2 + 1. 其中 a = g4 ,b = g0 =1.的15個點是： (0, 1) (1, g6) (g3, g8) (g5, g3) (0, 1) (1, g13) (g3, g13) (g5, g11) (g6, g8) (g9, g10) (g10, g) (g12, 0) (g6, g14) (g9, g13) (g10, g8) (g12, g1

5、2) 上表表明了互逆點，除(0,1)的互逆點使其本身外，如p= (1, g6) ,它的互逆點:-p= (1,1+g6)=(1,(0001)+(1101)=(1,(1101) = (1, g13) 基于橢圓曲線上的離散對數(shù)問題ECC2.逆元：P = (x P, y P)的逆元： -P = (x P, - y P)加法：若 P = (x P , y P)，Q = (x Q , y Q). 若 P 和 Q 是不同的點且 Q 不是 -P, P + Q = R 按如下方法計算： = (y P y Q) / (x P x Q) mod p x R = 2 x P x Q mod p y R = -y P

6、+ (x P x R) mod p求2P ：若 P = (x P , y P) 若 y P 不為 0， 2P = R 按如下方法計算： = (3xP2 + a) / (2yP ) mod p x R = 2 - 2xP mod p y R = -y P + (x P x R) mod p GF(p) GF(p)上的兩點運算上的兩點運算( (用用代數(shù)方法代數(shù)方法表示表示) )： 基于橢圓曲線上的離散對數(shù)問題ECC2.例題：仍以E23(1,1)為例，設(shè)P=(3,10)，Q=(9,7)，求P+Q，2P2337103111mod239362113910917mod2311(317)1016420mod

7、23xy 所以P+Q=（17,20），仍為E23(1,1)中的點。1.22333 31516 mod 23210204633307 mod 236(37)103412 mod 23xy 2.所以2P=(7,12)。 基于橢圓曲線上的離散對數(shù)問題ECC2. GF(2m)GF(2m)上兩點運算上兩點運算( (用用代數(shù)方法代數(shù)方法表示表示): ): 逆元：P = (x P, y P)的逆元 ：-P = (x P, x P + y P)加法：若 P = (x P , y P)，Q = (x Q , y Q)。若 P 和 Q 是不同的點且 Q 不是 -P, P + Q = R 按如下方法計算： = (y

8、P +yQ) / (xP + xQ) xR = 2 + + xP + xQ + a yR = (xP + xR) + xR + yP 求2P ：若 P = (x P , y P) 若 y P 不為 0， 2P = R 按如下方法計算： = (xP 2 + yP )/ xP xR = 2+ + a yR = xP2 + ( + 1) xR 基于橢圓曲線上的離散對數(shù)問題ECC2.例題： 橢圓曲線T=(m=4,f(x)=x4+x+1,g=0010,a=g4,b=g0)點P=(g6,g8)，點Q=(g3,g13)，求點R=P+Q以及R=2P1. =(g8+ g13 )/(g6+ g3)=g X=g2+

9、g+g6+ g3 +g4=1 Y=g(g6+1)+1+ g8 =g13 所以 R=P+Q=(1,g13)2. =(g6 )2 +g8/g6=g3 X=(g3 )2 +g3+g4=g10 Y=g12+(g3+1)g10=g8所以 R=2P=(g10 ,g8) 基于橢圓曲線上的離散對數(shù)問題基于橢圓曲線上的離散對數(shù)問題ECCECC2. 給定橢圓曲線上的點 P 和點 Q , 尋找數(shù) k 使得 k P = Q， 其中k稱為Q基于P的離散對數(shù)。（當(dāng)給定P和Q時計算K相對困難）橢圓曲線密碼體制的依據(jù)就是利用定義在橢圓曲線點群上的離散對數(shù)問題的難解性。例如: 對于橢圓曲線F23：y2 = x3 + 9x + 17, 求點Q = (4,5) 基于點 P = (16,5)的離散對數(shù)k解： 計算k P, 直到Q為止 P =