ECC椭圆曲线密码学的原理、公式推导、例子、Python实现和应用

关注
ECC椭圆曲线密码学的原理、公式推导、例子、Python实现和应用www.shan-machinery.com

椭圆曲线密码学(Elliptic Curve Cryptography, ECC),又称椭圆曲线密码体制椭圆曲线加密算法等。

椭圆曲线加密算法在比特币、区块链上有着广泛的应用。

本文首先回顾了椭圆、离散对数、离散对数问题(DLP)、数论等椭圆曲线密码学相关的数学基础概念;接着,引出椭圆曲线、有限域、有限域加法法则(给出Python代码实现)、椭圆曲线离散对数问题(ECDLP)、ELGAMAL,EC ELGAMAL;然后,基于Python实现了ECC加密解密,并介绍了ECC在比特币(ECDSA、Secp256k1)上的应用;最后,对ECC进行总结,并对比了ECC与RSA,指出二者的一些区别。

本文层层推进,从ECC椭圆曲线密码学的概念、原理、公式推导、例子、Python实现、应用等来构建椭圆曲线密码学的完整体系,使读者对ECC有系统概览。文章的目录如下:

一、ECC基础1、椭圆2、离散对数3、数论二、ECC原理1、椭圆曲线2、求解3、加法法则4、ECDLP5、ELGAMAL6、EC ELGAMAL三、ECC应用1、Python实现ECC2、比特币四、ECC总结1、RSA VS ECC2、密码学

直接上PPT。

ECC椭圆曲线密码学

一、ECC基础ECC基础的目录

1、椭圆

介绍椭圆、椭圆参数方程、椭圆周长、椭圆积分是为了引出椭圆曲线而做的基础铺垫。

什么是椭圆?

什么是椭圆?

什么是椭圆的周长?

什么是椭圆的周长?

什么是椭圆积分?

椭圆积分丰富内涵可以参考维基百科:

椭圆积分​zh.wikipedia.org什么是椭圆积分?

其中,第二类完全椭圆积分E的定义:

第二类完全椭圆积分E注意:上面推导过程,阐述了为什么叫椭圆曲线。

2、离散对数

介绍离散对数、DLP是为了引出ECDLP椭圆曲线离散对数问题而做的基础铺垫。

什么是离散对数?

什么是离散对数?

什么是DLP离散对数问题?

离散对数问题(Discrete LogarithmProblem, DLP)。

什么是DLP离散对数问题?

举个例子说明离散对数问题(DLP)。

离散对数问题的例子

3、数论

群、域、域上四则法则是椭圆密码学的基础,所有的ECC加密解密都是围绕这些基本性质展开的。

什么是阿贝尔群?

什么是阿贝尔群?

什么是环?

什么是环?

什么是域?

什么是域?

什么是域上四则运算?

这是ECC计算的基本原理,是ECC最重要、最重要、最重要的知识点。

域上四则运算

二、ECC原理ECC原理的目录

1、椭圆曲线

什么是椭圆曲线?

什么是椭圆曲线?

椭圆曲线的名字是怎么来的?

椭圆曲线的名字是怎么来的?

2. 求解

求解椭圆曲线上的点集。

求解椭圆曲线上的点集

举个求椭圆曲线上的点集的例子。

求椭圆曲线上的点集的例子

Python代码如下:

# ECC在Fp域上的点集Python实现def show_points(p, a, b):return [(x, y) for x in range(p) for y in range(p) if (y*y - (x*x*x + a*x + b)) % p == 0]print(show_points(p=23, a=1, b=1))

3、加法法则

椭圆曲线有限域上的加法法则。

椭圆曲线有限域上的加法法则

加法法则P+Q例2。

加法法则P+Q例2

nP(倍运算)的例3。

nP(倍运算)的例3

例2、例3的Python实现代码

例2、例3的Python实现代码

Python实现代码

# ECC在Fp域上加法、倍乘运算# 求value在Fp域的逆——用于分数求逆def get_inverse(value, p):for i in range(1, p):if (i * value) % p == 1:return ireturn -1# 求最大公约数——用于约分化简def get_gcd(x, y):if y == 0:return xelse:return get_gcd(y, x % y)# 计算P+Q函数def calculate_p_q(x1,y1,x2,y2,a,b,p):flag = 1# 控制符号位# 若P = Q,则k=[(3x1^2+a)/2y1]mod pif x1 == x2 and y1 == y2:member = 3 * (x1 ** 2) + a# 计算分子denominator = 2 * y1# 计算分母# 若P≠Q,则k=(y2-y1)/(x2-x1) mod pelse:member = y2 - y1denominator = x2 - x1 if member* denominator 什么是椭圆曲线离散对数问题?

举个例子来说明椭圆曲线离散对数问题。

椭圆曲线离散对数问题的例子

5. ElGamal

ElGamal加密算法是基于迪菲-赫尔曼(DHM)密钥交换的非对称加密算法。

1985年,塔希尔·盖莫尔(Taher Elgamal)在他的论文《A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms》提出ElGamal算法。

A public key cryptosystem and a signature scheme based on discrete logarithms​ieeexplore.ieee.orgElGamal

ElGamal加密算法的原理。

ElGamal加密算法的原理

6. EC ElGamal

椭圆曲线在密码学中的使用是在1985年,分别由Koblitz、Miller独立提出:

Neal Koblitz的论文Elliptic curve cryptosystems, Mathematics of Computation》

American Mathematical Society​www.ams.org图标

Victor Miller, "Use of elliptic curves in cryptography", CRYPTO 85, 1985.

Use of Elliptic Curves in Cryptography​link.springer.com图标

分别独立提出。

EC ElGamal

Elliptic CurveElGamal(ECElGamal)椭圆曲线ElGamal密码体制。

EC ElGamal是ECC的一种,把ElGamal移植到椭圆曲线上来实现。

EC ElGamal加密算法的原理。

EC ElGamal加密算法的原理

EC ElGamal加密算法的例子。

EC ElGamal加密算法的例子

三、ECC应用ECC应用的例子

1、Python实现ECC

Python实现ECC

Python实现ECC加密解密如下:(个人推荐这种,思想清晰)

来源:https://blog.csdn.net/qq_38130747/article/details/85053660# -*- coding: utf-8 -*-"""ECC在Fp域上的加解密"""def get_inverse_element(value, max_value):"""计算value在1-max_value之间的逆元"""for i in range(1, max_value):if (i * value) % max_value == 1:return ireturn -1def gcd_x_y(x, y):"""计算最大公约数"""if y == 0:return xelse:return gcd_x_y(y, x % y)def calculate_p_q(x1,y1,x2,y2, a, p):"""计算p+q"""flag = 1# 定义符号位if x1 == x2 and y1 == y2:member = 3 * (x1 ** 2) + a# 计算分子denominator = 2 * y1# 计算分母else:member = y2 - y1denominator = x2 - x1 if member* denominator = 10:print(p-1-j, end=" ")else: print(p-1-j, end="")for i in range(p):print(x_y[i][p-j-1], end="")print()print(" ",end="")for i in range(p):if i >= 10:print(i, end=" ")else:print(i, end="")print()def calculate_np(G_x, G_y, private_key, a, p):"""计算nG"""temp_x = G_xtemp_y = G_ywhile private_key != 1:p_value = calculate_p_q(temp_x,temp_y, G_x, G_y, a, p)temp_x = p_value[0]temp_y = p_value[1]private_key -= 1return p_valuedef ecc_encrypt_and_decrypt():while True:a = int(input("请输入椭圆曲线的参数a:"))b = int(input("请输入椭圆曲线的参数b:"))p = int(input("请输入椭圆曲线的参数p(p为质数):"))if (4*(a**3) + 27*(b**2)) % p ==0:print("选取的椭圆曲线不能用于加密,请重新选择\n")else:break# 输出该椭圆曲线的散点图draw_graph(a,b,p)print("在上图中选出一个点作为生成元G")G_x = int(input("你选取的横坐标G_x:"))G_y = int(input("你选取的纵坐标G_y:"))# 获取该椭圆曲线的阶n = get_order(G_x, G_y, a, b, p)# 获取私钥并且key < 椭圆曲线的阶nprivate_key = int(input("输入私钥key(https://www.shan-machinery.com