ECC加密算法详解+python实现

这篇具有很好参考价值的文章主要介绍了ECC加密算法详解+python实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一.前言

目前比较受欢迎的加密算法一共存在两种,一种是基于大整数因子分解问题(IFP)的RSA算法和基于椭圆曲线上离散对数计算问题(ECDLP)的ECC算法。之前对RSA算法进行过很详细的讲解,但是ECC加密算法还没有讲过,所以给大家在尽量简单易懂不去深究数学概念的情况下讲解一下ECC加密算法的内容。

二.加密过程

这里不可避免的要接触一些数学知识,看不懂加密秘密的过程,请对应过程看我的第三部分解释,保姆级教学了。

1.数学原理

我们假设椭圆曲线上有两个点P和Q,然后k为整数。此时有:

Q = k P Q=kPQ=kP

对于给定的k和P,根据加法法则,计算Q很容易,但是给定P和Q,来求k非常困难

2.加密和解密

  • 选取一条椭圆曲线Ep(a,b),并取椭圆曲线上一点作为基点P
  • 选取一个大数字k为私钥,并且生成公钥Q(Q=kP)
  • 加密:选择随机数r,将明文M生产密文C。密文是一个点对,C=(rP,M+rQ)
  • 解密:M+rQ-k(rP)=M+r(kP)-K(rP)=M

三.数学补充

1.为什么用椭圆曲线

不管是ECC加密算法还是其他的加密算法,加密的基础都是基于一个数学难题,ECC加密就是基于椭圆曲线离散对数问题设计的,我们先来看这个问题的数学原理。

我们假设椭圆曲线上有两个点PQ,然后k为整数。此时有: Q=KP
对于给定的kP,根据加法法则,计算Q很容易,但是给定PQ,来求k非常困难。

这里的Q=KP不是你理解的数学中的乘法,后面我会解释,同时告诉你KPQ是什么东西。

2.什么是椭圆曲线

这里先把你脑袋里面想的数学里面的椭圆抛掉,椭圆曲线并不是一个椭圆。

你脑袋里的椭圆是:x2 /a2 +y2 /b2 =1,

现在椭圆曲线是: y2 = x3 + ax +b,其中还要满足(4a3 + 27b≠0)

其中满足4a^3 + 27b^2 ≠ 0是为了保证曲线不存在奇点,即为了保证曲线上每一点都存在切线。

奇点,也叫瑕点,大学高数里面应该介绍过,忘了记得翻高数,当然在这里不是重点。

这是在网上找的椭圆曲线的图形,大家参考一下:

ECC加密算法详解+python实现

3.有限域

首先我们知道椭圆曲线是连续的,它不适合加密,我们要把椭圆曲线变成离散的点,这些离散的点构成的区域就是有限域。

注意:有限域不是简单的集合,后面写物联网信息安全时我会提到详细域的介绍,这里简单提一下。

是一个可以在其上进行加法、减法、乘法、和除法运算,而结果不会超出域的集合,如:有理数集合、实数集合、复数集合都是域,但整数集合不是。(很明显,使用除法得到的分数或者小数已超出整数集合)

如果域F只包含有限个元素,则称其为有限域,有限域中元素的个数称为有限域的阶。
每个有限域的阶必为素数的幂,即有限域的阶可表示为pn (p是素数,n是正整数),该有限域通常称为Galois域(Galois Fields),记为GF§。

在域的定义基础,上,作如下修改:

  • 1.定义模p加法和模p乘法(加或乘的结果超过p时,模p取余数,p为素数)
  • 2.集合内的元素经过加法和乘法计算,结果仍然在集合内。
  • 3.计算符合交换率、结合率、分配率
  • 4.加法和乘法有单位元素(所有 的集合内的值都有对应的负数,所有集合内非零值都有倒数)。

怎么样保证经过运算后,元素还在有限域内呢?这就需要取模运算。

4.椭圆曲线的加法规则

椭圆曲线的运算法则虽然使用的都是和平时运算一样的加法乘法等,但并不是简单的两点坐标的相加或者相乘,这里我们先的和大家介绍一下椭圆曲线的运算法则是怎么样的,再去介绍如何计算,首先我们来看加法法则,如下图所示:

ECC加密算法详解+python实现

看图理解:这里我们有A、B两个点(在椭圆曲线上),现在把它们的连线与椭圆曲线的交点关于x轴对称的点,才是我们需要计算的A+B的点。

这里A、B两点确定的直线选取还是很有必要的,要保证它是有第三个交点的,假设你现在取B=-A,那么画出来的图形是这样的:
ECC加密算法详解+python实现

这种情况我们可以认为直线与椭圆曲线相交于无穷远点。

5.椭圆曲线的乘法

在数学上,我们是不是把乘法理解为加法的叠加,在这里亦如此,A+A=2A。

在刚刚的加法基础上,我们让B点无限接近A点,直至重合,此时AB连线相当于做A的切线,该切线与椭圆的交点关于X轴对称位置的点就是A+A,即2A

ECC加密算法详解+python实现

计算3A就是计算A+2A的结果,过A点和2A点做一条直线,然后与椭圆曲线的焦点关于X轴的对称点就是3A

补充:第二部分中的Q=KP,现在理解了吗,其中K就是我们这里2、3……的数字,P就是我们这里举例用的A点,Q就是计算结果。

到这里大家就应该能理解为什么在一开始我们所说的椭圆曲线的数学问题:Q=KP

对于给定的kP,根据加法法则,计算Q很容易。

这里的K可以取很大的,不要以为就简单的2、3,这里是为了举例说明。

6.举例说明

椭圆曲线方程:x3 + x +1

当在有限域GF(23)上面时,我们的椭圆曲线就成为了下面的样子:

ECC加密算法详解+python实现

四.举例计算

1.运算规则

ECC加密算法详解+python实现

2.例如

现在我们假设y2 =x3 + x +1 mod(23)

绩点:A(0,1)

当A=B时,带入计算k=3*02 +1/2=1/2 mod(23)

这里涉及到分数取模运算,我们可以用同余替换来计算:

ECC加密算法详解+python实现

所以,这里的x3计算出来就是6;

同时y3也可以计算出来为19。

这里x3和y3都出来了,关于x轴对称就不说了吧。

3.老师课堂例子

ECC加密算法详解+python实现

五.python实现

def get_points(a, b, p):
    """
     获取有限域下的散点集
    """
    # 计算所有可能的点坐标
    points = []
    for x in range(p):
        y_square = (x ** 3 + a * x + b) % p
        for y in range(p):
            if (y ** 2) % p == y_square:
                points.append((x, y))
    return points


def cal_k(point_A, point_B, p):
    """
    计算斜率k
    """
    if point_A == point_B:
        son = 3 * pow(point_A[0], 2) + a
        mother = 2 * point_A[1]
        # 费马小定理求分数取模
        return (son * pow(mother, p - 2)) % p

    else:
        son = point_B[1] - point_A[1]
        mother = point_B[0] - point_A[0]
        # 费马小定理求分数取模
        return (son * pow(mother, p - 2)) % p


def cal_add(point_A, point_B, p, k):
    """
     椭圆曲线加法
     计算A+B的结果坐标
    :param k: 斜率
    """
    # A+B=C,计算c的坐标
    cx = (k ** 2 - point_A[0] - point_B[0]) % p
    cy = (k * (point_A[0] - cx) - point_A[1]) % p
    return cx, cy


def cal_NA(key, point_A, point_B, p):
    """
    椭圆曲线乘法
    计算NA
    """
    # 执行0~key-1共key次
    for i in range(key - 1):
        k = cal_k(point_A, point_B, p)
        point_B = cal_add(point_A, point_B, p, k)

    return point_B


def encryption(r, Q, m, p):
    """
   加密
    """
    cx = cal_NA(r, A, B, p)
    rQ = cal_NA(r, Q, Q, p)
    k = cal_k(m, rQ, p)
    cy = cal_add(m, rQ, p, k)
    return cx, cy


def decryption(cplantext, key, p):
    """
    解密
    """
    kc2 = cal_NA(key, cplantext[0], cplantext[0], p)
    # 减法即关于x轴对称点的坐标
    kc2 = (kc2[0], -kc2[1])
    k = cal_k(cplantext[1], kc2, p)
    result = cal_add(cplantext[1], kc2, p, k)
    return result


# 测试-------------------------------------------------------------------
# 椭圆曲线的a,b
a = 1
b = 6
# 有限域的阶
p = 11
# 私钥k
key = 7
# 散点表
points = get_points(a, b, p)
print("散点表中的元素:")
print(points, end='')
print("\n-------------------------------------------------------------------")
# ------------------------------------------------------------------------
# A是基点,为散点表中的一点,B是另一个交点,这里初始时相同
A = (2, 7)
B = (2, 7)
# 公钥Q=7A
Q = cal_NA(key, A, B, p)
# 随机数r
r = 3
# --------------------------------------------------------------------------
# 消息
message = (10, 9)
print(f"原始消息:{message}")
# 密文
c = encryption(r, Q, message, p)
print(f"加密后的结果:{c}")
# 解密
result = decryption(c, key, p)
print(f"解密后的结果:{result}")


六.运行结果

ECC加密算法详解+python实现

本人也是开始学的过程。

参考链接:文章来源地址https://www.toymoban.com/news/detail-511886.html

  • 1.ECC算法博客
  • 2.ECC加密视频

到了这里,关于ECC加密算法详解+python实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • python目前哪个版本最稳定,python什么版本比较稳定

    大家好,本文将围绕python目前哪个版本最稳定展开说明,python什么版本比较稳定是一个很多人都想弄明白的事情,想搞清楚python哪个版本好用2020需要先了解以下几个事情。 大家好,小编来为大家解答以下问题,python安装哪个版本比较好,python一般安装哪个版本,现在让我们

    2024年01月25日
    浏览(43)
  • 通俗易懂,十分钟读懂DES,详解DES加密算法原理,DES攻击手段以及3DES原理。Python DES实现源码

    DES(Data Encryption Standard)是一种 对称加密 算法。它是在20世纪70年代初期由IBM研发的。它的设计目标是提供高度的数据安全性和性能,并且能够在各种硬件和软件平台上实现。 DES使用56位的密钥和64位的明文块进行加密。DES算法的分组大小是64位,因此,如果需要加密的明文长

    2024年02月03日
    浏览(71)
  • 祖冲之加密算法详解及代码实现

    祖冲之加密由上层的线性反馈移位寄存器(LFSR)和中层的比特重组(BR)以及下层的非线性函数F组成。 线性反馈移位寄存器的输出作为比特重组的输入,比特重组的输出供下层的F函数输出密钥。 线性反馈移位寄存器由16个31比特寄存器单元变量s0,s1…s15组成,以有限域( )上

    2024年02月04日
    浏览(36)
  • RSA加密算法Python实现

    1977年,三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法.RSA算法的特征如下: RSA算法是非对称加密算法,及算法的加密密钥与解密密钥不同 RAS是基于大数分解问题实现的算法, RSA算法的密钥长度一般为

    2024年01月18日
    浏览(44)
  • 【Python】使用文件哈希算法快速比较两个文件是否相同(代码实现)

    哈希值(Hash Value),也称为哈希码、散列值或摘要,是一种将任意长度的输入数据转换为固定长度字符串(通常是一串数字和字母)的算法的结果。哈希值通常用于唯一标识数据,以便快速检索或比较数据。哈希值的特点包括: 固定长度:无论输入数据的大小如何,哈希函

    2024年01月21日
    浏览(53)
  • 国密算法 SM4加密算法 Python完整实现

    SM4算法是一种 对称加密算法 ,也被称为国密算法。它是由中国密码学家设计的,已被列入国家密码局的标准。 SM4算法使用 128位的密钥和分组大小 ,使用 32轮迭代 加密,可以用于加密数据和验证消息认证码。它的加密效率很高,安全性也很好,被广泛应用于各种安全领域,

    2024年02月11日
    浏览(52)
  • OpenSSL 3.1.1 ECC 加密、解密、签名、验签(国密 sm2、sm3)

    openssl 3 默认废弃了 旧版本 (opessl 1.x) 的部分api 导致部分旧ecc 代码无法使用(可以通过配置编译选项打开) ,这里展示如何使用新接口用ECC 进行加密解密。 新接口是真的方便,基本上你都不需要懂啥密码学知识,对我们这种密码白痴来说太好了 头文件 生成密钥对 导出公

    2024年02月05日
    浏览(61)
  • 国密算法 SM4 对称加密 分组密码 python实现完整代码

    目前,python实现的国密算法库主要是 python-gmssl 库和 snowland-smx ( pysmx )库,二者都对SM2(仅公钥加解密和数字签名)、SM3、SM4进行了细致而优雅的实现。 GMSSL. https://github.com/duanhongyi/gmssl snowland-smx. https://gitee.com/snowlandltd/ snowland-smx-python PyCryptodome. https://www.pycryptodome.org 最近用

    2024年02月06日
    浏览(54)
  • ECC算法学习(一)算法公式

    ECC全称为“Ellipse Curve Ctyptography”,是一种基于椭圆曲线数学的公开密钥加密算法。与传统的基于大质数分解难题的加密算法不同,该加密方式基于 “离散对数” 这种数学难题。 椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别独立提出的。 优缺点 优点:

    2024年04月22日
    浏览(64)
  • 在Python中应用RSA算法实现图像加密:基于Jupyter环境的详细步骤和示例代码

    一、引言 在当今的数字化社会中,信息安全问题备受关注。随着数字图像在生活中的应用越来越广泛,图像的安全性和隐私性也成为人们关心的焦点。如何在网络上安全地传输和存储图像已经成为一项重要的挑战。RSA(Rivest-Shamir-Adleman)算法作为一种被广泛应用的公钥密码体

    2024年02月13日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包