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是为了保证曲线不存在奇点,即为了保证曲线上每一点都存在切线。

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

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

在这里插入图片描述

3.有限域

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

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

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

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

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

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

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

4.椭圆曲线的加法规则

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

在这里插入图片描述

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

这里A、B两点确定的直线选取还是很有必要的,要保证它是有第三个交点的,假设你现在取B=-A,那么画出来的图形是这样的:
在这里插入图片描述

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

5.椭圆曲线的乘法

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

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

在这里插入图片描述

计算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)上面时,我们的椭圆曲线就成为了下面的样子:

在这里插入图片描述

四.举例计算

1.运算规则

在这里插入图片描述

2.例如

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

绩点:A(0,1)

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

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

在这里插入图片描述

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

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

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

3.老师课堂例子

五.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}")


六.运行结果

在这里插入图片描述

本人也是开始学的过程。

参考链接:

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/33281.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

数据库的操作

前言 在之前的文章中,我们已经了解了什么是数据库,以及为什么有数据库,和数据库有什么作用,有了这些宏观概念之后,本章为大家进一步详细介绍对于数据库在Linux上如何具体操作。 1.创建数据库 1.1创建数据库语法 语法…

第十二章 EfficientNetv2网络详解

系列文章目录 第一章 AlexNet网络详解 第二章 VGG网络详解 第三章 GoogLeNet网络详解 第四章 ResNet网络详解 第五章 ResNeXt网络详解 第六章 MobileNetv1网络详解 第七章 MobileNetv2网络详解 第八章 MobileNetv3网络详解 第九章 ShuffleNetv1网络详解 第十章…

【线程池】史上最全的ThreadPoolExecutor源码详解

目录 一、线程池框架 1.1 第一层结构 1.2 接口简介 1.3 核心实现类 1.4 辅助类 1.5 完成服务 二、ThreadPoolExecutor的成员属性和内部类 2.1 主要成员属性以及工具方法 2.2 五种内部类 2.2.1 拒绝策略内部类(Policy) 2.2.2 工作线程内部类&a…

HHU云计算期末复习(下)Hadoop、虚拟化技术、openstack

文章目录 第五章 Hadoop分布式文件系统HDFS分离元数据和数据:NameNode和DataNode流水线复制 第七章 虚拟化技术7.1 虚拟化技术简介7.2 虚拟机迁移7.3 网络虚拟化 第八章 openstack8.1 计算服务NovaRabbitMQ 8.2 Swift 第九章 云计算数据中心9.1 云数据中心特征9.2 网…

【MySQL数据库】MySQL 高级SQL 语句一

[TOC](MySQL 高级SQL 语句 一、MySQL 高级SQL 语句1.1select -显示表格中一个或数个字段的所有数据记录1.2distinct不显示重复的数据记录1.3where有条件查询1.4and、or且 或1.5in 显示已知的值的数据记录1.6between 显示两个值范围内的数据记录1.7通配符,通常通配符…

一文了解云计算

目录 🍎云服务 🍎云计算类型 🍒公有云 🍒私有云 🍒混合云 🍎云计算服务模式 🍒IaaS基础设施即服务 🍒PaaS平台即服务 🍒SaaS软件即服务 🍒三者之间区别 &…

回波数据adc_data.bin解析(附MATLAB程序)

毫米波雷达系统性能参数分析 1、xWR1642—DCA1000 TI目前有两款采集卡TSW1400和DCA1000,可以为xWR1243/1443和1642毫米波雷达进行回波数据采集。本文将主要介绍几款雷达分别用2款采集卡数据采集的回波数据格式以及MATLAB数据解析程序。 1、xWR1642—DCA1000 &…

打造专属个人模型-私有独立离线模型部署-阿里云GPU服务器配置

阿里云有免费的机器学习 GPU 服务器,免费试用活动页https://free.aliyun.com只要没有申请过 PAI-DSW 资源的新老用户皆可申请 5000CU 的免费额度,3个月内使用。 选择第一个进行立即试用 可以看到试用的界面 如果遇到下面的错误,当前账号没有权…

蓝桥杯专题-试题版-【数字游戏】【城市建设】【最大子阵】【蚂蚁感冒】

点击跳转专栏>Unity3D特效百例点击跳转专栏>案例项目实战源码点击跳转专栏>游戏脚本-辅助自动化点击跳转专栏>Android控件全解手册点击跳转专栏>Scratch编程案例点击跳转>软考全系列点击跳转>蓝桥系列 👉关于作者 专注于Android/Unity和各种游…

基于SpringBoot+vue的职称评审管理系统设计与实现

博主介绍: 大家好,我是一名在Java圈混迹十余年的程序员,精通Java编程语言,同时也熟练掌握微信小程序、Python和Android等技术,能够为大家提供全方位的技术支持和交流。 我擅长在JavaWeb、SSH、SSM、SpringBoot等框架…

基于SpringBoot的家庭理财记账系统的设计与开发

1.引言 随着社会的发展,社会的方方面面都在利用信息化时代的优势。互联网的优势和普及使得各种系统的开发成为必需。 本文以实际运用为开发背景,运用软件工程原理和开发方法,它主要是采用java语言技术和mysql数据库来完成对系统的设计。整个…

CaffeineCache+Redis 接入系统做二层缓存思路实现(借鉴 mybatis 二级缓存、自动装配源码)

本文目录 前言本文术语本文项目地址设计思路开发思路DoubleCacheAble 双缓存注解(如何设计?)动态条件表达式?例如:#a.id?(如何解析?)缓存切面(如何设计?&…

二十三种设计模式第十二篇--组合模式

组合模式是一种结构型设计模式,它允许将对象组合成树形结构来表示整体-部分的层次结构。组合模式使得用户对单个对象和组合对象的使用具有一致性。 在组合模式中,有两种类型的对象:叶子对象和组合对象。叶子对象表示树结构中的叶子节点&…

Matplotlib---雷达图

1. 雷达图 fig plt.figure(figsize(6, 6))x np. linspace(0, 2*np.pi, 6, endpointFalse) y [83, 61, 95, 67, 76, 88]# 保证首位相连 x np.concatenate((x, [x[0]])) y np.concatenate((y, [y[0]]))# 雷达图 axes plt.subplot(111, polarTrue) axes.plot(x, y, o-, l…

第十六届CISCN复现MISC——国粹

国粹 不是我说,我当时比赛的时候,在那里叭叭叭的数的老用心了结果他是一道非常不常规的图片密码题,又是一种我没见过的题型 看了一些大佬的解题,知道他是一个坐标类型的图片拼凑 发现很多都提到了opencv,又是一个知识…

考研算法32天:桶排 【桶排序】

算法介绍 桶排 举个例子,一个数组中的数是:4 1 2 3 5, 然后桶排的顺序是:将每个数应该在的下标算出来,咋算呢?这我们就得考虑两种情况:假设我们设现在这个需要找到自己在数组里位置的数是x。…

【计算机网络】IP 地址处理函数

目录 1.struct sockaddr_in的结构 2.一般我们写的结构 3.常见的“点分十进制” 到 ” uint32_t 的转化接口 3.1. inet_aton 和 inet_ntoa (ipv4) 3.2. inet_pton 和 inet_ntop (ipv4 和 ipv6) 3.3. inet_addr 和 inet_network 3…

哈工大计算机网络课程传输层协议之:拥塞控制原理剖析

哈工大计算机网络课程传输层协议之:拥塞控制原理剖析 哈工大计算机网络课程传输层协议详解之:可靠数据传输的基本原理 哈工大计算机网络课程传输层协议详解之:流水线机制与滑动窗口协议 哈工大计算机网络课程传输层协议详解之:T…

【裸机开发】EPIT 定时器 —— 按键消抖

实际工程中,不能直接通过延时来消抖 ! 这里我们采用定时器来消抖,这也是内核处理消抖的一种方式。 目录 一、基本原理 1、延时消抖的弊端 2、定时器消抖原理 二、按键消抖实现 1、按键中断 2、定时器中断 三、附加:按键 / 定时器中断初…

Qgis加载在线XYZ瓦片影像服务的实践操作

目录 背景 一、XYZ瓦片相关知识 1、xyz瓦片金字塔 2、 瓦片编号 3、瓦片访问 二、在Qgis中加载在线地图 1、Qgis版本 2、瓦片加载 3、地图属性预览 总结 背景 在做电子地图应用的时候,很常见的会提到瓦片(tile)的概念,瓦片…