超椭圆曲线(九)超椭圆曲线密码系统的实现

文章目录

Diffie-Hellman密钥交换[10]是一个协议，两个实体$A$和$B$可以通过公共通道上的一系列传输，就一个秘密的加密密钥达成一致。方法如下。$A$和$B$首先选择一个(乘式写)有限Abel群$G$和某个元素$\alpha\in G$。然后$A$选择一个随机整数$a$且将$\alpha^{a}$传输给$B$，$B$反过来选择一个随机整数$b$且将$\alpha^{b}$传输给$A$。这样$A,B$均能确定$\alpha^{ab}$，作为他们的共享密钥。

窃听者$C$监控$A$与$B$之间的传输将会得到$G,\alpha,\alpha^{a},\alpha^{b}$，选择参数$G$和$\alpha$，使$C$确定$\alpha^{ab}$在计算上是不可行的。事实上，若$C$可以计算$a$或者$b$，则$C$可以确定$\alpha^{ab}$。给定$\alpha,\beta=\alpha^{a}$确定$a$的问题称为离散对数问题。当限制在$[0,order(\alpha)-1]$范围内$a$是唯一的，称为以$\alpha$为底，$\beta$的对数。确定$\alpha^{ab}$与计算$G$上的离散对数问题是否等价还没有定论，在其他安全依赖于离散对数问题的加密协议中，有ElGamal公钥加密和数字签名方案[12]，以及最近采用的美国数字签名标准[29]。

最好的算法以解决离散对数问题在任意$G$组指数平方根攻击(见McCurley[24]),有一个运行时间的平方根成比例最大的质数因子$l$, $l$是$\alpha$的阶。因此，如果选择$G$和$\alpha$，使$l$有一个大的素数因子，那么这些攻击就可以避免。

令$F_{q}$代表阶为$q$的有限域，再令$q=p^{m}$其中$p$是$F_{q}$的特征，Diffie与Hellman最初提议$G=F_{q}^{*}$，$F_{q}$的乘法群，作为实现Diffie-Hellman密钥交换协议的候选。有一些已知的随机次指数时间算法可用于计算$F_{q}$中的对数。关于$q$为质数的情形，请参见Coppersmith，Odlyzko和Schroeppel [9]和Gordon [17]，对于$p=2$的情况，请参见Odlyzko [30]，有关一般情况，请参见Adleman和DeMarrais [1]。这些算法是对上一段中提到的通用算法的渐进改进。 出于加密目的，我们对相应离散对数问题的次指数算法未知的群感兴趣。另外，为了有效和实际地实施，群操作应该相对容易地应用。 对于这样的群，在有限域上定义的超椭圆曲线的雅可比行列式就是一种可能性。

为了使用超椭圆曲线实现离散对数密码系统，必须选择合适的曲线$C$和有限域$K$。 所选曲线和域的理想属性包括：

• 底层有限域K中的算术应该有效地实现； 特征2的有限域似乎是最有吸引力的选择；
• $C$的行列式$J(K)$的阶，表示为$\sharp J(K)$，应该能被大素数整除。给定当前的计算技术，一个安全的要求为$\sharp J(K)$可被至少45位的十进制素数$r$整除。另外，为了避免约化攻击Frey and Ruck [13]，它将$J(K)$中的离散对数问题简化为扩展域$K=F_{q}$中的离散对数问题。对所有的$F_{q^{k}}$中的离散对数可解的小整数$k$，$r$应无法整除$q^{k}-1$($1\leq k\leq 2000/(\log_{2}q)$满足)。

接下来描述一种用于选择超椭圆曲线并计算$\sharp J(K)$的技术。令$J$为定义在$F_{q}$上的超椭圆曲线$C$的雅可比行列式，由方程$v^{2}+h(u)v=f(u)$给定，令$F_{q^{n}}$代表$F_{q}$的$n$次扩展，且令$N_{n}$代表有限Abel群$J(F_{q^{n}})$的阶，$C$上的$F_{q^{n}}$-有理点的个数定义为$M_{n}$。与$C$关联的是zeta函数，定义如下：

定义53(zeta函数)令$J$为定义在$F_{q}$上的超椭圆曲线$C$的雅可比行列式，再令$M_{r}=\sharp C(F_{q^{r}}),r\geq 1$，$C$的zeta函数是幂级数：

$$Z_{C}(t)=exp\left(\sum_{r\geq 1}M_{r}\frac {r} {t^{r}}\right)$$

以下是有关zeta函数的一些众所周知的事实(例如，参见[23])。

定理54(zeta函数的性质)令$C$为定义在$F_{q}$上类为$g$的超椭圆曲线，令$Z_{C}(t)$为$C$的zeta函数。

$\textrm{(i)}\ Z_{C}(t)\in Z(t)$。更确切地说，我们有：

$$Z_{C}(t)=\frac {P(t)} {(1-t)(1-qt)}\tag{9}$$

其中$P(t)$为次数为$2g$的整系数多项式；此外，$P(t)$有如下形式：

$$P(t)=1+a_{1}t+\cdots+a_{g}t^{g}+qa_{g-1}t^{g+1}+q^{2}a_{g-2}t^{g+2}+\cdots+q^{g-1}a_{1}t^{2g-1}+q^{g}t^{2g}\tag{10}$$

$\textrm{(ii)}\ P(t)$分解为：

$$P(t)=\prod_{i=1}^{g}(1-\alpha_{i}t)(1-\bar\alpha_{i}t)\tag{11}$$

其中每个$\alpha_{i}=\sqrt{q}$，$\bar\alpha_{i}$为$\alpha_{i}$的共轭。

$\textrm{(iii)}\ N_{n}=\sharp J(F_{q^{n}})$满足：

$$N_{n}=\prod_{i=1}^{g}|1-\alpha_{i}^{n}|^{2}\tag{12}$$

为了计算$N_{n}$，由它满足$\textrm{(i)}$确定$P(t)$的系数$a_{1},\cdots,a_{g}$，从而确定$P(t)$；$\textrm{(ii)}$分解$P(t)$因此可以确定$\alpha_{i}$；$\textrm{(iii)}$通过等式$(12)$计算$N_{n}$。

 

推论55 令$C$为定义在$F_{q}$上类为$g$的超椭圆曲线，令$N_{n}=\sharp J(F_{q^{n}})$，则$(q^{n/2}-1)^{2g}\leq N_{n}\leq (q^{n/2}+1)^{2g}$；从而$N_{n}\approx q^{ng}$。

原文链接

翻译不当之处还请批评指正，另外文中有些证明等我看明白了再翻译…