[密码学]椭圆曲线和密码学的简单介绍

现在的位置: 首页 > 综合 > 正文

RSS

[密码学]椭圆曲线和密码学的简单介绍

2018年02月15日 ⁄ 综合 ⁄ 共 8803字 ⁄ 字号小中大 ⁄ 评论关闭

一、椭圆曲线的简单介绍

首先介绍下一个著名的方程，魏尔施特拉斯方程（Weierstrass equation），方程形式如下：

椭圆曲线一个重要的应用是已知两个点，求出第三个点，我们以下面的例子为例。

例1：已知椭圆曲线E的方程，显然的，点P=（7，16）、Q=（1，2）是位于该椭圆曲线上的。那么如何求得第三个点R使得该点既在PQ直线上，也在E上呢？

传统的做法：将直线方程求出来，用X表示Y，并且代入曲线E的方程上，则可以求出解。得出解R=（-23/9,170/27）。

现在我们先定义一个加法运算。

通过例1，可以知道，已知两个点P、Q，我们可以求得第三个点R的坐标，我们现在定义运算，PQ=R’，R‘和R是关于x轴对称的。可能有人会好奇？为什么会这样定义？而不是直接定义PQ=R。对这个问题感兴趣的朋友可以去学习下抽象代数的知识（Mordell-Weil定理：椭圆曲线上有理点构成的群是有限生成的。）通过下面的例2，我们可以很快的了解该定理。

例2：椭圆曲线上，仅有16个整点:(-2,3),(-1,4),(2,5),(4,9),(8,23),(43,282),(52,375),(5234,378661)。以及它们关于x轴的对称点，而其上所有的有理点可以由(-2,3),(2,5)通过群上的加法生成。

例2应该很明显的告诉了我们，为什么要这样定义椭圆曲线上的加法了。

二、椭圆曲线上的运算规则

（为了方便，我们将上面的符号简写成+）对于椭圆曲线E上加法运算，其性质有如下：

1、（单位元）P+O=O+P，对于任意的P属于E；

2、（可逆）P+（-P）=O，对于任意P属于E；

3、（结合律）（P+Q）+R=P+（Q+R），对于任意的P、Q和R属于E；

4、（交换律）P+Q=Q+R，对于任意的P、Q属于E。

换句话说，（E，+）构成一个阿贝尔群（Abelian group）。

现在给出加法的具体计算的方法。

假设E上有两点，P=（,），Q=(,)。那么如何计算P+Q。

1、如果P=O，则P+Q=Q；

2、如果=，且，则P+Q=O；

3、

三、在有限域上的椭圆曲线

前面我们说过椭圆曲线的计算，但是是基于实数域上的，要想将其引用到密码学中，那么我们考虑的将是有限域上的曲线了。将通过一个例子来引入。

例3：考虑椭圆曲线（在有限域F13上）。从0到12，我们依次代入，可以求得所有在椭圆曲线E上的点｛O，（1，5），（1，8），（2，3），（2，10），（9，6），（9，7），（12，2），（12，11）｝。下面我们来计算一个例子，P=（9，7），Q=（1，8）。

1、计算P+Q。

解：在有限域中的公式依旧适用，就是运算略有不同（对抽象代数中的运算不清楚的，可以去学习下抽象代数中的相关知识）。计算（最后一步可能部分读者不能理解？Why?一句话概括就是5的逆元是8，），然后计算出

，。所以P+Q=（2，10）。

2、计算2P

计算可得，从而可得2P=（9，6），步骤与上面几乎一致，有兴趣的读者可以验证下。下面我们给出一个计算有限域问题的JAVA代码。

/**
 * 该代码只是一个示例
 * */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.*;

public class PplusQOverFiniteFields {

	private BigInteger A = null;
	private BigInteger B = null;
	private BigInteger Px = null;
	private BigInteger Py = null;
	private BigInteger Qx = null;
	private BigInteger Qy = null;
	private BigInteger Zx = null;
	private BigInteger Zy = null;
	private static BigInteger x = null;
	private static BigInteger y = null;
	private BigInteger P = null;// 需要设置
	private boolean isOutputProcedure = true;

	public void setisOutputProcedure(boolean t) {
		this.isOutputProcedure = false;

	}

	public PplusQOverFiniteFields(BigInteger A, BigInteger B, BigInteger p) {
		this.A = A;
		this.B = B;
		this.P = p;
	}

	public void setP(BigInteger x, BigInteger y) {
		this.Px = x;
		this.Py = y;
	}

	public void setQ(BigInteger x, BigInteger y) {
		this.Qx = x;
		this.Qy = y;
	}

	public BigInteger[] caclu2P() {
		BigInteger[] temp = new BigInteger[2];
		this.Qx = this.Px;
		this.Qy = this.Py;
		this.caculZ();
		temp[0] = Zx;
		temp[1] = Zy;
		return temp;
	}

	public void input() {
		System.out.println("请输入Weierstrass方程的系数A，B：");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			A = new BigInteger(br.readLine());
			B = new BigInteger(br.readLine());
			System.out.println("请输入P点的坐标：");
			Px = new BigInteger(br.readLine());
			Py = new BigInteger(br.readLine());
			System.out.println("请输入Q点的坐标：");
			Qx = new BigInteger(br.readLine());
			Qy = new BigInteger(br.readLine());
		} catch (IOException e) {
			e.printStackTrace();
		}

	}

	public BigInteger[] caculNP(int N) {
		this.Qx = Px;
		this.Qy = Py;
		BigInteger[] res = new BigInteger[2];
		BigInteger[] temp = new BigInteger[2];
		res[0] = BigInteger.ZERO;
		res[1] = BigInteger.ZERO;
		while (N != 0) {
			temp = caclu2P();
			if (N % 2 == 1) {
				PplusQOverFiniteFields pqoff = new PplusQOverFiniteFields(A, B,
						P);
				pqoff.setisOutputProcedure(false);
				pqoff.setP(res[0], res[1]);
				pqoff.setQ(Qx, Qy);
				res = pqoff.caculZ();
			}
			N = N / 2;
			setP(temp[0], temp[1]);
		}
		return res;
	}

	public BigInteger[] caculZ() {
		BigInteger[] temp = new BigInteger[2];
		BigInteger lanbuta = null;
		if ((Qx.signum() == 0 && Qy.signum() == 0)) {
			temp[0] = Px;
			temp[1] = Py;
			return temp;
		}
		if (Px.signum() == 0 && Py.signum() == 0) {
			temp[0] = Qx;
			temp[1] = Qy;
			return temp;
		}
		if (!(Qx.equals(Px) && (Qy.equals(Py)))) {
			lanbuta = (Qy.subtract(Py).mod(P)).multiply(
					inverses_modulo(Qx.subtract(Px), P)).mod(P);
		} else {
			lanbuta = ((new BigInteger("3").multiply(Px).multiply(Px)).add(A)
					.mod(P)).multiply(
					inverses_modulo(new BigInteger("2").multiply(Py), P))
					.mod(P);

		}
		Zx = (lanbuta.multiply(lanbuta)).subtract(Px).subtract(Qx).mod(P);
		Zy = (lanbuta.multiply((Qx.subtract(Zx)))).subtract(Qy).mod(P);
		if (isOutputProcedure) {
			System.out.println("Q" + "(" + Qx + "," + Qy + ")" + "+" + "P"
					+ "(" + Px + "," + Py + ")" + "=" + "Z" + "(" + Zx + ","
					+ Zy + ")");
		}
		temp[0] = Zx;
		temp[1] = Zy;
		return temp;
	}

	private static BigInteger exgcd(BigInteger a, BigInteger b) {

		if (b.equals(new BigInteger("0"))) {
			x = new BigInteger("1");
			y = new BigInteger("0");
			return a;
		}
		BigInteger r = exgcd(b, a.mod(b));
		BigInteger t = x;
		x = y;
		y = t.subtract(a.divide(b).multiply(y));
		return r;
	}

	public BigInteger inverses_modulo(BigInteger a, BigInteger b) {
		exgcd(a, b);
		while (x.signum() == -1)
			x = x.add(b);
		return x;
	}

	public void clear() {
		Px = null;
		Py = null;
		Qx = null;
		Qy = null;
		Zx = null;
		Zy = null;
		x = null;
		y = null;
	}

	public static void main(String args[]) {
		System.out.println("有限域13上的运算");
		PplusQOverFiniteFields test_1 = new PplusQOverFiniteFields(
				new BigInteger("3"), new BigInteger("8"), new BigInteger("13"));
		test_1.setP(new BigInteger("9"), new BigInteger("7"));
		test_1.setQ(new BigInteger("1"), new BigInteger("8"));
		test_1.caculZ();
		test_1.caclu2P();
		test_1.clear();
	}
}

四、倍加算法（The Double-and-Add Algorithm）

上面我们提到了Q=2P的计算，但是当计算Q=nP的时候，如果是在一个大素数下有限域且n的值较大，那么Q=nP的计算将会十分复杂。这里我们介绍一种算法。以例4来介绍该算法。

例4：考虑椭圆曲线E：，在有限域F(3623)下，P=（6，730），下面我们计算Q=947P。

传统的做法是不停的+P，这样的话，需要执行947-1次加法，但是这样的算法我们是不提倡的，如果n足够大，那么该算法的执行时间将十分长。因此才出现了The Double-and-Add算法。

首先将947写成二进制的表达形式。这样只需要9次双倍运算和6次加法运算即可得出结果。

具体计算结果可参见下表：

表1：计算947*(6,730) 在椭圆曲线E：在F（3623）上

下面给出该算法的JAVA测试代码（里面用到的类在上面的代码中）。

import java.math.BigInteger;

public class NPcacultest {
	public static void main(String args[]) {
		PplusQOverFiniteFields test_2 = new PplusQOverFiniteFields(
				new BigInteger("14"), new BigInteger("19"), new BigInteger(
						"3623"));
		test_2.setP(new BigInteger("6"), new BigInteger("730"));
		BigInteger[] res = new BigInteger[2];
		res = test_2.caculNP(947);
		System.out.println(res[0] + "  " + res[1]);
	}
}

五、其它应用

有限域上椭圆曲线可以应用于Diffie-Hellman密钥交换和ElGamal公钥体制（椭圆曲线版本，与一般的ElGamal略有不同）。

有兴趣的读者可以参考《An Introduction to Mathematical Cryptography》第五章，编者Jeffrey Hoffstein 等。

下面给出这两个的体制的JAVA代码。

（1）Diffie-Hellman密钥交换

/**
 * Diffie-Hellman密钥交换的一种简单实现
 * */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Diffie_Hellman {
	static BigInteger P, A, B; 

	public static void main(String args[]) throws NumberFormatException,
			IOException {
		PplusQOverFiniteFields ppp = new PplusQOverFiniteFields(new BigInteger(
				"324"), new BigInteger("1287"), new BigInteger("3851"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int Alice = Integer.parseInt(br.readLine());
		int Bob = Integer.parseInt(br.readLine());
		BigInteger[] res1 = new BigInteger[2];
		BigInteger[] res2 = new BigInteger[2];
		BigInteger[] res3 = new BigInteger[2];
		ppp.setP(new BigInteger("920"), new BigInteger("303"));
		ppp.setisOutputProcedure(false);//不输出中间过程
		res1=ppp.caculNP(Alice);
		System.out.println("Alice计算得到的结果：("+res1[0]+","+res1[1]+")");
		ppp.setP(new BigInteger("920"), new BigInteger("303"));
		res2=ppp.caculNP(Bob);
		System.out.println("Bob计算得到的结果：("+res2[0]+","+res2[1]+")");
		//他们分享的密钥如下
		ppp.setP(res2[0],res2[1]);
		res3=ppp.caculNP(Alice);
		System.out.println("Alice计算得到的秘密：("+res3[0]+","+res3[1]+")");
		ppp.setP(res1[0],res1[1]);
		res3=ppp.caculNP(Bob);
		System.out.println("Bob计算得到的秘密：("+res3[0]+","+res3[1]+")");
		System.out.println("分享秘密成功！");
	}
}

下面为上述代码的执行结果：

（2）ElGamal椭圆曲线版本的实现

/**
 * Elgamal椭圆曲线版本的实现
 * */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Random;

public class ElGamalTest {
	static BigInteger P, A, B,g;

	public static void getRandomP() {
		int alpha=50;
		Random r = new Random();
		BigInteger q = null;
		while (true) {
			q = BigInteger.probablePrime(alpha, r);
			if (q.bitLength() != alpha)
				continue;
			if (q.isProbablePrime(10)) // if q is prime ,contiune
			{
				P = q.multiply(new BigInteger("2")).add(BigInteger.ONE);
				if (P.isProbablePrime(10)) // if p is prime,then break
					break;
			}
		}
		while (true) {
			g = BigInteger.probablePrime(P.bitLength() - 1, r);
			if (!g.modPow(BigInteger.ONE, P).equals(BigInteger.ONE)
					&& !g.modPow(q, P).equals(BigInteger.ONE)) {
				break;
			}
		}
	}
	public static void main(String args[]) throws NumberFormatException,
			IOException {
		getRandomP();
		System.out.println("可信方随机得到的大素数P："+P);
		PplusQOverFiniteFields ppp = new PplusQOverFiniteFields(new BigInteger(
				"324"), new BigInteger("1287"), P);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.println("请输入Alice的私钥：");
		int Alice = Integer.parseInt(br.readLine());
		ppp.setP(new BigInteger("920"), new BigInteger("303"));
		ppp.setisOutputProcedure(false);// 不输出中间过程
		BigInteger[] res1 = new BigInteger[2];
		res1 = ppp.caculNP(Alice);
		System.out
				.println("Alice计算得到的结果(公钥)：(" + res1[0] + "," + res1[1] + ")");
		ppp.setP(new BigInteger("920"), new BigInteger("303"));
		int BobEphemeral = (int) (Math.random() * 10000);
		BigInteger[] C1 = ppp.caculNP(BobEphemeral);
		System.out.println("请输入明文：");
		BigInteger PlainText = new BigInteger(br.readLine().getBytes());
		BigInteger CopyOfPlainText = PlainText;
		ppp.setP(res1[0], res1[1]);
		BigInteger[] CTemp = ppp.caculNP(BobEphemeral);
		ppp.setP(CTemp[0], CTemp[1]);
		ppp.setQ(PlainText, CopyOfPlainText);
		BigInteger[] C2 = ppp.caculZ();
		System.out.println("密文：((" + C1[0] + "," + C1[1] + "),(" + C2[0] + ","
				+ C2[1] + "))");

		ppp.setP(C1[0], C1[1]);
		CTemp=ppp.caculNP(Alice);
		ppp.setP(C2[0], C2[1]);
		ppp.setQ(CTemp[0], CTemp[1].negate());
		BigInteger[] res=ppp.caculZ();
		String mingwen =new String(res[0].toByteArray());
		System.out.println(mingwen);
	}
}

执行结果如下：

笔者水平有限，难免有错误，欢迎交流！

【上篇】[Android] adb shell 显示 error: device not found 的解决办法
【下篇】[网络]NIO学习笔记

作者: wswxlkkk

该日志由 wswxlkkk 于6年前发表在综合分类下，最后更新于 2018年02月15日.
转载请注明: [密码学]椭圆曲线和密码学的简单介绍 | 学步园 +复制链接

抱歉!评论已关闭.

学步园

[密码学]椭圆曲线和密码学的简单介绍

作者: wswxlkkk

书签

最新文章New

本站推荐

返回首页