环Zn上椭圆曲线的密钥交换协议

设n=pq,p,q为奇素数,环Z_n上的椭圆曲线E_n(a,b)的SOM密钥交换协议与QV密钥交换协议均选取E_n(a,b)上的阶为M_n=lcm{#E_p(a,b),＃E_q(a,b)}的点G作为公钥(称G为基点),并且限定其对应的E_p(a,b)和E_q(a,b)均为循环群,这就限制了这两个协议只能选择一类特殊的椭圆曲线E_n(a,b)构作密钥交换协议.本文指出,E_p(a,b)和Eq(a,b)均为循环群这一限定是不必要的.本文给出了E_n(a,b)上存在阶为M_n的点G的一个充分必要条件,并给出一个例子,其中E_p(a,b)为循环群,E_q(a,b)为非循环群,且对应的E_n(a,b)上有阶为M_n的点G.同时,本文选取E_n(a,b)上阶为lcm{n₁,m₁}的点作为基点,这里n₁,m₁分别为E_p(a,b)和E_q(a,b)的最大循环子群的阶.这样,就能够选择更多的椭圆曲线E_n(a,b),用来构作密钥交换协议(包括将两方之间的密钥交换协议扩展到三方).

The Elliptic Curves over Zn and Key Exchange Protocol

SOM key exchange protocol and QV key exchange protocol were based on an elliptic curve En(a,b) over the ring Z n with a point G of order Mn=lcm{# Ep(a,b),# Eq(a,b)},where n=pq and p,q are odd primes.They pointed out that such a base point G exists if Ep(a,b) and Eq(a,b) are both cyclic groups.This restricts the choice of elliptic curves used to implement their protocols.In this paper we propose a necessary and sufficient condition under which En(a,b) has a point of order Mn=lcm{# Ep(a,b),# Eq(a,b)} and show by an example that En(a,b) may have a point G of order Mn even if Ep(a,b) is a cyclic group and Eq(a,b) is not.Our generalization makes it possible to choose more elliptic curves to establish key exchange protocol.And we give a new three or more users key exchange protocol with a point of order lcm{n 1,m 1} as base point,where n 1,m 1 are respectively the order of the maximal cyclic subgroups of Ep(a,b) and Eq(a,b).