欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

GF(p)上的ELGamal型椭圆曲线密码详解(Java实现)

程序员文章站 2022-04-28 12:51:57
GitHub 椭圆曲线密码 椭圆曲线密码(Elliptic Curve Cryptosystem),简称ECC,是Neal Koblitz和Victor Miller于1985年提出的。 研究发现,有限域上的椭圆曲线上的一些点构成交换群,而且离散对数问题是难解的。于是在此群上定义ELGamal密码, ......

github


椭圆曲线密码

  椭圆曲线密码(elliptic curve cryptosystem),简称ecc,是neal koblitz和victor miller于1985年提出的。

  研究发现,有限域上的椭圆曲线上的一些点构成交换群,而且离散对数问题是难解的。于是在此群上定义elgamal密码,并称为椭圆曲线密码。

  目前,椭圆曲线密码已成为除rsa密码之外呼声最高的公钥密码之一。它密钥短、签名短、软件实现规模小、硬件实现电路省电。普遍认为,160位长的椭圆曲线密码的安全性相当于1024位的rsa密码,而且运算速度也较快。


gf(p)上的椭圆曲线

  设p是大于3的素数,且4a3+27b2≠0(mod p),称曲线

y2=x3+ax+b(a,b∈gf(p))

为gf(p)上的椭圆曲线。

  由椭圆曲线方程可得到一同余方程:

y2=x3+ax+b(mod p)(a,b∈gf(p))

其解为一个二元组(x,y),其中x,y∈gf(p),表示椭圆曲线上的一个点,称为该椭圆曲线上的解点。

无穷点o

  定义一个点o(∞,∞)表示无穷点,作为0元素。

两解点相加

  设p(x1,y1)和q(x2,y2)是解点,r(x3,y3)=p(x1,y1)+q(x2,y2):

  1.若p为无穷点,即p=o,此时r=p+q=q;若q为无穷点,即q=o,此时r=p+q=p;若p和q都为无穷点,即p=q=o,则r=p+q=o。

  2.若x1=x2且y1=y2,即p=q,此时r=p+q=2p,其中

GF(p)上的ELGamal型椭圆曲线密码详解(Java实现) 

  3.若x1=x2而y1=-y2,此时称q点为p点的逆,记为p=-q,且r=p+q=o。

  4.除上述特殊情况之外的一般情况,即p≠±q时,r=p+q,其中

 GF(p)上的ELGamal型椭圆曲线密码详解(Java实现)

  集合e={所有的解点,无穷点o}和加法运算构成加法交换群。设g(g≠o,即g为一个解点)为一个加法群的生成元,则使得ng=g+g+...+g=o的倍数n为该加法群的阶。加法群的阶整除集合e的阶,即n | |e|。

求椭圆曲线的所有解点

  当p较小,即gf(p)较小时,可以利用穷举的方法根据同余方程y2=x3+ax+b(mod p)(a,b∈gf(p))求出所有解点。

  具体方法为:求出x取0~p-1,x3+ax+b(mod p)的结果是否为模p的二次剩余。如果是,则一个x值可得到两个对应的y值,也就得到互逆的两个解点。

  e.m.取p=11,椭圆曲线y2=x3+x+6

GF(p)上的ELGamal型椭圆曲线密码详解(Java实现)

         由此表得到所有的解点:(2,4)、(2,7)、(3,5)、(3,6)、(5,2)、(5,9)、(7,2)、(7,9)、(8,3)、(8,8)、(10,2)、(10,9),再加上无穷点o共13个点的集合e加上加法运算就构成一个加法交换群。

         因为集合e的阶|e|=13为素数,所以该加法群的阶为13。

         取g=(2,7)为生成元,

g=(2,7),2g=(5,2),

3g=(8,3),4g=(10,2),

5g=(3,6),6g=(7,9),

7g=(7,2),8g=(3,5),

9g=(10,9),10g=(8,8),

11g=(5,9),12g=(2,4),

         最终得到13g=o,所以加法群的阶为13。


elgamal型椭圆曲线密码

  1.选择一个素数p,从而确定有限域gf(p),将p公开。

  2.选择元素a,b∈gf(p),从而确定一条gf(p)上的椭圆曲线,确定加法交换群e,将a和b公开。

  3.选择一个大素数n,并确定一个阶为n的基点g(x,y),将n和g(x,y)公开。

  4.余因子h=|e|/n,将h公开。

  5.随机选择一个整数d(0<d<n)作为私钥保密。

  6.定义q=dg作为公钥公开。

加密

  1.随机选择一个整数k(0<k<n)。

  2.计算x1=kg。

  3.计算x2=kq,若x2=∞,则回到第1步。

  4.加密:c=mx2(mod n)。

  5.将(x1,c)作为密文发送。

解密

  1.用私钥d求出x2=dx1

  2.解密:m=cx2-1(mod n)。

推荐椭圆曲线

  nist向社会推荐了5条素域gf(p)上随机选取的椭圆曲线:

p-192

  p=2192-264-1

  a=-3

  b=64210519 e59c80e7 0fa7e9ab 72243049 feb8deec c146b9b1

  x=188da80e b03090f6 7cbf20eb 43a18800 f4ff0afd 82ff1012

  y=07192b95 ffc8da78 631011ed 6b24cdd5 73f977a1 1e794811

  n=ffffffff ffffffff ffffffff 99def836 146bc9b1 b4d22831

  h=1

p-224

  p=2224-296-1

  a=-3

  b=b4050a85 0c04b3ab f5413256 5044b0b7 d7bfd8ba 270b3943 2355ffb4

  x=b70e0cbd 6bb4bf7f 321390b9 4a03c1d3 56c21122 343280d6 115c1d21

  y=bd376388 b5f723fb 4c22dfe6 cd4375a0 5a074764 44d58199 85007e34

  n=ffffffff ffffffff ffffffff ffff16a2 e0b8f03e 13dd2945 5c5c2a3d

  h=1

p-256

  p=2256-2224+2192+296-1

  a=-3

  b=5ac635d8 aa3a93e7 b3ebbd55 769886bc 651d06b0 cc53b0f6 3bce3c3e 27d2604b

  x=6b17d1f2 e12c4247 f8bce6e5 63a440f2 77037d81 2deb33a0 f4a13945 d898c296

  y=4fe342e2 fe1a7f9b 8ee7eb4a 7c0f9e16 2bce3357 6b315ece cbb64068 37bf51f5

  n=ffffffff 00000000 ffffffff ffffffff bce6faad a7179e84 f3b9cac2 fc632551

  h=1

p-384

  p=2384-2128-296+232-1

  a=-3

  b=b3312fa7 e23ee7e4 988e056b e3f82d19 181d9c6e fe814112 0314088f 5013875a c656398d 8a2ed19d 2a85c8ed d3ec2aef

  x=aa87ca22 be8b0537 8eb1c71e f320ad74 6e1d3b62 8ba79b98 59f741e0 82542a38 5502f25d bf55296c 3a545e38 72760ab7

  y=3617de4a 96262c6f 5d9e98bf 9292dc29 f8f41dbd 289a147c e9da3113 b5f0b8c0 0a60b1ce 1d7e819d 7a431d7c 90ea0e5f

  n=ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff c7634d81 f4372ddf 581a0db2 48b0a77a ecec196a ccc52973

  h=1

p-521

  p=2521-1

  a=-3

  b=00000051 953eb961 8e1c9a1f 929a21a0 b68540ee a2da725b 99b315f3 b8b48991 8ef109e1 56193951 ec7e937b 1652c0bd 3bb1bf07 3573df88 3d2c34f1 ef451fd4 6b503f00

  x=000000c6 858e06b7 0404e9cd 9e3ecb66 2395b442 9c648139 053fb521 f828af60 6b4d3dba a14b5e77 efe75928 fe1dc127 a2ffa8de 3348b3c1 856a429b f97e7e31 c2e5bd66

  y=00000118 39296a78 9a3bc004 5c8a5fb4 2c7d1bd9 98f54449 579b4468 17afbd17 273e662c 97ee7299 5ef42640 c550b901 3fad0761 353c7086 a272c240 88be9476 9fd16650

  n=000001ff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff 51868783 bf2f966b 7fcc0148 f709a5d0 3bb5c9b8 899c47ae bb6fb71e 91386409

  h=1


椭圆曲线密码的安全性

  椭圆曲线密码的安全性建立在椭圆曲线离散对数问题的困难性之上。当素数p和n足够大时椭圆曲线密码是安全的。这就要求椭圆曲线解点群的阶要有大素数因子的根本原因,在理想情况下群的阶本身就是一个大素数。

  为了确保椭圆曲线密码的安全,应当避免使用弱的椭圆曲线。所谓弱的椭圆曲线主要指超奇异椭圆曲线和反常椭圆曲线。

  椭圆曲线密码的密钥越长,自然越安全,但是技术实现也就越困难,效率也越低。一般认为,在目前的技术水平下采用190~256位的椭圆曲线,其安全性就足够了。


java实现

解点类

 1 import java.math.biginteger;
 2 
 3 public class ecpoint {
 4     biginteger x;
 5     biginteger y;
 6 
 7     public ecpoint() {
 8         x = null;
 9         y = null;
10     }
11 
12     public ecpoint(biginteger x, biginteger y) {
13         this.x = x;
14         this.y = y;
15     }
16 
17     @override
18     public string tostring() {
19         if (iso()) 
20             return "o";
21         return "(" + x.tostring(16) + ", " + y.tostring(16) + ")";
22     }
23 
24     boolean iso() {
25         if (x == null && y == null) 
26             return true;
27         return false;
28     }
29 }

两解点相加

 1 /**
 2  * 两解点相加
 3  * @param p1
 4  * @param p2
 5  * @return
 6  */
 7 ecpoint add(ecpoint p1, ecpoint p2) {
 8     if (p1.iso()) return p2;
 9     if (p2.iso()) return p1;
10     ecpoint p3 = new ecpoint();
11     biginteger lambda;
12     if (p1.x.compareto(p2.x) == 0) {
13         if (p1.y.compareto(p2.y) == 0) {
14             lambda = new biginteger("3").multiply(p1.x.pow(2)).add(a).multiply(new biginteger("2").multiply(p1.y).modpow(new biginteger("-1"), p)).mod(p);
15             p3.x = lambda.pow(2).subtract(new biginteger("2").multiply(p1.x)).mod(p);
16             p3.y = lambda.multiply(p1.x.subtract(p3.x)).subtract(p1.y).mod(p);
17             return p3;
18         }
19         if (p1.y.compareto(p.subtract(p2.y)) == 0) 
20             return p3;
21     }
22     lambda = p2.y.subtract(p1.y).multiply(p2.x.subtract(p1.x).modpow(new biginteger("-1"), p)).mod(p);
23     p3.x = lambda.pow(2).subtract(p1.x).subtract(p2.x).mod(p);
24     p3.y = lambda.multiply(p1.x.subtract(p3.x)).subtract(p1.y).mod(p);
25     return p3;
26 }

倍乘

 1 /**
 2  * 倍乘
 3  * @param p
 4  * @param n
 5  * @return  np
 6  */
 7 ecpoint multiply(ecpoint p, biginteger n) {
 8     ecpoint q = add(p, new ecpoint());
 9     ecpoint r = new ecpoint();
10     do {
11         if (n.and(new biginteger("1")).intvalue() == 1) 
12             r = add(r, q);
13         q = add(q, q);
14         n = n.shiftright(1);
15     } while (n.intvalue() != 0);
16     return r;
17 }

求所有解点

 1 /**
 2  * 求所有解点
 3  * @return
 4  */
 5 list<ecpoint> solutionpoints() {
 6     list<ecpoint> r = new arraylist<ecpoint>();
 7     list<biginteger> l = new arraylist<biginteger>();
 8     for (biginteger y = new biginteger("1"); y.compareto(p.divide(new biginteger("2"))) != 1; y = y.add(new biginteger("1"))) 
 9         l.add(y.modpow(new biginteger("2"), p));
10     for (biginteger x = new biginteger("0"); x.compareto(p) == -1; x = x.add(new biginteger("1"))) {
11         biginteger t = x.pow(3).add(a.multiply(x)).add(b).mod(p);
12         if (isexist(t, l) != -1) {
13             biginteger y = new biginteger(isexist(t, l) + "");
14             r.add(new ecpoint(x, y));
15             r.add(new ecpoint(x, p.subtract(y)));
16         }
17     }
18     r.add(new ecpoint());
19     return r;
20 }
1 static int isexist(biginteger b, list<biginteger> l) {
2     for (int i = 0; i < l.size(); i++) 
3         if (l.get(i).compareto(b) == 0) return (i + 1);
4     return -1;
5 }

求阶

 1 /**
 2  * 求阶
 3  * @param p  生成元
 4  * @return   p对应的阶
 5  */
 6 biginteger o(ecpoint p) {
 7     biginteger r = new biginteger("1");
 8     while (! p.iso()) {
 9         r = r.add(new biginteger("1"));
10         p = multiply(p, r);
11     }
12     return r;
13 }

加密

 1 /**
 2  * 加密
 3  * @param m
 4  * @return
 5  */
 6 biginteger[] encrypt(biginteger m) {
 7     biginteger k;
 8     ecpoint x1, x2;
 9     do {
10         k = new biginteger(n.bitlength(), new random());
11     } while ((x2 = ec.multiply(q, k)).x == null);
12     x1 = ec.multiply(g, k);
13     biginteger[] c = new biginteger[3];
14     c[0] = x1.x;
15     c[1] = x1.y;
16     c[2] = m.multiply(x2.x).mod(n);
17     return c;
18 }

解密

 1 /**
 2  * 解密
 3  * @param c
 4  * @return
 5  */
 6 biginteger decrypt(biginteger[] c) {
 7     ecpoint x1 = new ecpoint(c[0], c[1]);
 8     ecpoint x2 = ec.multiply(x1, d);
 9     biginteger m = c[2].multiply(x2.x.modpow(new biginteger("-1"), n)).mod(n);
10     return m;
11 }

测试

测试数据

  m=1234567890abcdef

  k=abcdef

测试结果

p-192

GF(p)上的ELGamal型椭圆曲线密码详解(Java实现)

p-224

GF(p)上的ELGamal型椭圆曲线密码详解(Java实现) 

p-256

GF(p)上的ELGamal型椭圆曲线密码详解(Java实现)

p-384

GF(p)上的ELGamal型椭圆曲线密码详解(Java实现)

p-521

GF(p)上的ELGamal型椭圆曲线密码详解(Java实现)


参考文献

  张焕国,唐明.密码学引论(第三版).武汉大学出版社,2015年