科技

GF(p)上的ELGamal型橢圓曲線密碼詳解（Java實現）

Java 加密解密 · 發表 2019-01-26 22:46:00

摘要： GitHub 橢圓曲線密碼橢圓曲線密碼（Elliptic Curve Cryptosystem），簡稱ECC，是Neal Koblitz和Victor Miller於1985年提出的。研究發現，有限域上的橢圓曲線上的一些點構成交換群，而且離散對數問題是難解的。於...

GitHub

橢圓曲線密碼

橢圓曲線密碼（Elliptic Curve Cryptosystem），簡稱ECC，是Neal Koblitz和Victor Miller於1985年提出的。

研究發現，有限域上的橢圓曲線上的一些點構成交換群，而且離散對數問題是難解的。於是在此群上定義ELGamal密碼，並稱為橢圓曲線密碼。

目前，橢圓曲線密碼已成為除RSA密碼之外呼聲最高的公鑰密碼之一。它金鑰短、簽名短、軟體實現規模小、硬體實現電路省電。普遍認為，160位長的橢圓曲線密碼的安全性相當於1024位的RSA密碼，而且運算速度也較快。

GF(p)上的橢圓曲線

設p是大於3的素數，且4a ³ +27b ² ≠0(mod p)，稱曲線

y ² =x ³ +ax+b（a,b∈GF(p)）

為GF(p)上的橢圓曲線。

由橢圓曲線方程可得到一同餘方程：

y ² =x ³ +ax+b(mod p)（a,b∈GF(p)）

其解為一個二元組(x,y)，其中x,y∈GF(p)，表示橢圓曲線上的一個點，稱為該橢圓曲線上的解點。

無窮點O

定義一個點O(∞,∞)表示無窮點，作為0元素。

兩解點相加

設P(x ₁ ,y ₁ )和Q(x ₂ ,y ₂ )是解點，R(x ₃ ,y ₃ )=P(x ₁ ,y ₁ )+Q(x ₂ ,y ₂ )：

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.若x ₁ =x ₂ 且y ₁ =y ₂ ，即P=Q，此時R=P+Q=2P，其中

3.若x1=x2而y1=-y2，此時稱Q點為P點的逆，記為P=-Q，且R=P+Q=O。

4.除上述特殊情況之外的一般情況，即P≠±Q時，R=P+Q，其中

集合E={所有的解點,無窮點O}和加法運算構成加法交換群。設G(G≠O，即G為一個解點)為一個加法群的生成元，則使得nG=G+G+...+G=O的倍數n為該加法群的階。加法群的階整除集合E的階，即n | |E|。

求橢圓曲線的所有解點

當p較小，即GF(p)較小時，可以利用窮舉的方法根據同餘方程y ² =x ³ +ax+b(mod p)（a,b∈GF(p)）求出所有解點。

具體方法為：求出x取0~p-1，x ³ +ax+b(mod p)的結果是否為模p的二次剩餘。如果是，則一個x值可得到兩個對應的y值，也就得到互逆的兩個解點。

e.m.取p=11，橢圓曲線y ² =x ³ +x+6

由此表得到所有的解點：(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.計算X ₁ =kG。

3.計算X ₂ =kQ，若x ₂ =∞，則回到第1步。

4.加密：C=Mx ₂ (mod n)。

5.將(X ₁ ,C)作為密文傳送。

解密

1.用私鑰d求出X ₂ =dX ₁ 。

2.解密：M=Cx ₂ ^-1 (mod n)。

橢圓曲線密碼的安全性

橢圓曲線密碼的安全性建立在橢圓曲線離散對數問題的困難性之上。當素數p和n足夠大時橢圓曲線密碼是安全的。這就要求橢圓曲線解點群的階要有大素數因子的根本原因，在理想情況下群的階本身就是一個大素數。

為了確保橢圓曲線密碼的安全，應當避免使用弱的橢圓曲線。所謂弱的橢圓曲線主要指超奇異橢圓曲線和反常橢圓曲線。

橢圓曲線密碼的金鑰越長，自然越安全，但是技術實現也就越困難，效率也越低。一般認為，在目前的技術水平下采用190~256位的橢圓曲線，其安全性就足夠了。

Java實現

解點類

 1 import java.math.BigInteger;
 2 
 3 public class ECPoint {
 4BigInteger x;
 5BigInteger y;
 6 
 7public ECPoint() {
 8x = null;
 9y = null;
10}
11 
12public ECPoint(BigInteger x, BigInteger y) {
13this.x = x;
14this.y = y;
15}
16 
17@Override
18public String toString() {
19if (isO()) 
20return "O";
21return "(" + x.toString(16) + ", " + y.toString(16) + ")";
22}
23 
24boolean isO() {
25if (x == null && y == null) 
26return true;
27return false;
28}
29 }

兩解點相加

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

倍乘

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

求所有解點

 1 /**
 2* 求所有解點
 3* @return
 4*/
 5 List<ECPoint> solutionPoints() {
 6List<ECPoint> r = new ArrayList<ECPoint>();
 7List<BigInteger> l = new ArrayList<BigInteger>();
 8for (BigInteger y = new BigInteger("1"); y.compareTo(p.divide(new BigInteger("2"))) != 1; y = y.add(new BigInteger("1"))) 
 9l.add(y.modPow(new BigInteger("2"), p));
10for (BigInteger x = new BigInteger("0"); x.compareTo(p) == -1; x = x.add(new BigInteger("1"))) {
11BigInteger t = x.pow(3).add(a.multiply(x)).add(b).mod(p);
12if (isExist(t, l) != -1) {
13BigInteger y = new BigInteger(isExist(t, l) + "");
14r.add(new ECPoint(x, y));
15r.add(new ECPoint(x, p.subtract(y)));
16}
17}
18r.add(new ECPoint());
19return r;
20 }

1 static int isExist(BigInteger b, List<BigInteger> l) {
2for (int i = 0; i < l.size(); i++) 
3if (l.get(i).compareTo(b) == 0) return (i + 1);
4return -1;
5 }

求階

 1 /**
 2* 求階
 3* @param p生成元
 4* @returnp對應的階
 5*/
 6 BigInteger o(ECPoint p) {
 7BigInteger r = new BigInteger("1");
 8while (! p.isO()) {
 9r = r.add(new BigInteger("1"));
10p = multiply(p, r);
11}
12return r;
13 }

加密

 1 /**
 2* 加密
 3* @param M
 4* @return
 5*/
 6 BigInteger[] encrypt(BigInteger M) {
 7BigInteger k;
 8ECPoint X1, X2;
 9do {
10k = new BigInteger(n.bitLength(), new Random());
11} while ((X2 = ec.multiply(Q, k)).x == null);
12X1 = ec.multiply(G, k);
13BigInteger[] C = new BigInteger[3];
14C[0] = X1.x;
15C[1] = X1.y;
16C[2] = M.multiply(X2.x).mod(n);
17return C;
18 }

解密

 1 /**
 2* 解密
 3* @param C
 4* @return
 5*/
 6 BigInteger decrypt(BigInteger[] C) {
 7ECPoint X1 = new ECPoint(C[0], C[1]);
 8ECPoint X2 = ec.multiply(X1, d);
 9BigInteger M = C[2].multiply(X2.x.modPow(new BigInteger("-1"), n)).mod(n);
10return M;
11 }

測試

測試資料

M=1234567890abcdef

k=abcdef

測試結果

P-192

P-224

P-256

P-384

P-521

參考文獻

張煥國，唐明.密碼學引論（第三版）.武漢大學出版社，2015年

來源：部落格園精華區

GF(p)上的ELGamal型橢圓曲線密碼詳解（Java實現）

橢圓曲線密碼

GF(p)上的橢圓曲線

無窮點O

兩解點相加

求橢圓曲線的所有解點

ELGamal型橢圓曲線密碼

加密

解密

推薦橢圓曲線

P-192

P-224

P-256

P-384

P-521

橢圓曲線密碼的安全性

Java實現

解點類

兩解點相加

倍乘

求所有解點

求階

加密

解密

測試

測試資料

測試結果

P-192

P-224

P-256

P-384

P-521

參考文獻

您可能也會喜歡…