密码学 | 椭圆曲线 ECC 密码学入门(二)

目录

4  椭圆曲线:更好的陷门函数

5  奇异的对称性

6  让我们变得奇特


⚠️ 原文地址:A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography

⚠️ 写在前面:本文属搬运博客,自己留着学习。如果你和我一样是小白,那么看完本文我们将仍然不能理解下图具体是在干什么,但能够对 RSA 和椭圆曲线加密的初衷有所了解。


密码学 | 椭圆曲线 ECC 密码学入门(一)文章浏览阅读273次,点赞4次,收藏8次。1 公共密钥密码学的兴起2 玩具版 RSA 算法2.1 RSA 基本原理2.2 RSA 举例说明1 加密2 解密3 不是完美的陷门函数https://blog.csdn.net/m0_64140451/article/details/137672818?spm=1001.2014.3001.5502

4  椭圆曲线:更好的陷门函数

在 RSA 和 Diffie-Hellman 算法被提出之后,研究人员开始探索其他基于数学的密码学解决方案,寻找超越因式分解的其他算法,这些算法可以作为良好的陷门函数。1985 年,基于一种深奥的数学分支 —— 椭圆曲线的密码学算法被提出。

但椭圆曲线究竟是什么,以及其背后的陷门函数是如何工作的呢?不幸的是,与因式分解不同 —— 我们中学生在初中第一次接触到 —— 大多数人对椭圆曲线的数学并不熟悉。数学并不简单,解释起来也不容易,但我会尝试在接下来的几部分中解释。

如果您的眼睛开始变得模糊,您可以跳到最后一部分:“这一切意味着什么?”

椭圆曲线是满足特定数学方程的点的集合。椭圆曲线的方程看起来像这样:

y^2=x^3+ax+b

这个方程定义了一个椭圆曲线,而椭圆曲线具有一系列独特的数学性质,这些性质对密码学家来说非常有兴趣。这个方程的图像如下:

椭圆曲线的其他表示方法有很多,但技术上讲,椭圆曲线是满足两个变量中一个变量的二次方程和另一个变量的三次方程的点的集合。椭圆曲线不仅仅是一张漂亮的图片,它还有一些特性,使它成为密码学的一个良好环境。

5  奇异的对称性

仔细观察上面绘制的椭圆曲线。它有几个有趣的特性。

  • 其中之一是 水平对称性。曲线上的任何点都可以关于 x 轴反射而仍留在同一曲线上。
  • 更有趣的特性是,任何非垂直线将与曲线 最多相交三个点

让我们将这个曲线想象成一个奇怪的台球游戏的场景。

如上图所示,取曲线上任意两点并画一条通过它们的线,它会恰好再与曲线相交一个点。在这个台球游戏中,你在点 A 处取一个球,向点 B 射击。当球碰到曲线时,球会要么直接向上(如果它在 x 轴下方)要么直接向下(如果它在 x 轴上方)弹跳到曲线的另一侧。 

为什么比喻为台球?答:因为在台球运动中,台球撞击到桌子的边沿会反弹。不过现实中的台球反弹方向有无穷多种,而这里的台球只会向上或向下反弹。

我们可以称这种在两点上的台球移动为 “dot” 。曲线上的任何两点都可以 “dot” 在一起得到一个新点。比如:

  • A dot B = C

个人认为,这里把 “dot” 理解成一种自定义的运算就行了(可以按个人喜好起名),类似于小学做的定义新运算题。

我们也可以将台球的移动串联起来,即不断地用 “dot” 操作一个点与自己。

  • A dot A = B
  • A dot B = C
  • A dot C = D
  • ……

这里的意思是:假设初始点是 A,然后让 A 不断和自己做 “dot” 运算。

结果证明,如果你有两个点,一个初始点与自己点运算 n 次后到达一个最终点,而你只知道最终点和第一个点,要找出 n 是困难的。

这里的意思是:假设只告诉你初始点 A 和它最终到达的点 Z,那么你很难求出该过程中做了多少次 “dot” 运算,即求解 n 的值非常困难。

为了继续我们奇怪的台球比喻,想象有一个人在一个房间里独自玩我们的游戏一段时间。他很容易按照上述规则一次又一次地击球。如果稍后有人走进房间,看到球最终停在了哪里,即使他们知道所有的游戏规则和球开始的地点,他们也无法确定球被击打了多少次才能到达那里,除非他们再次重新经历整个游戏,直到球到达同一个点。容易做到,难以撤销:这就是一个非常好的陷门函数的基础。 

椭圆曲线算法也满足 “单向容易,逆向困难”,其中单向是做 “dot” 运算,逆向是求解 n 的值。套用台球的比喻就是,单向是击球,逆向是求解击了多少次球。

6  让我们变得奇特

这个翻译确实很奇特。。。

上面简化后的曲线非常适合观赏和解释椭圆曲线的概念,但它并不代表用于密码学的曲线的样子。为此,我们必须限制自己在一定范围内的数字,就像在 RSA 中那样。我们不是允许曲线上的点有任何值,而是限制自己在固定范围内的整数。

在计算椭圆曲线公式时,我们使用同样的技巧,当达到最大值时将数字循环。如果我们选择最大值为一个素数,那么椭圆曲线被称为 素数曲线,并具有优秀的密码学特性。

所谓 “数字循环” 也还是取模的意思。假设最大值是 8,当我们数到 8 后又回到 1 这个起点,形成原文所说的数字循环:1, 2, ..., 7, 8, 1, 2, ..., 7, 8, 1, 2, ... 。

下面是一个椭圆曲线对于所有数字的绘图示例:

下面是同一条曲线,但只用整数点表示,最大值为 97 的绘图:

这看起来一点也不像传统意义上的曲线,但实际上它就是。就像原始曲线在边缘被包裹起来,只有那些触及整数坐标的曲线部分被着色。你甚至仍然可以观察到水平的对称性。

竖着一列一列地看,这些点确实是关于 x 轴对称的。

事实上,你仍然可以在这条曲线上玩台球游戏,并且可以将点相互 “dot” 在一起。曲线上的直线方程仍然具有相同的性质。此外,这种 “dot” 操作可以有效地计算。

个人理解,简单来说:假设你选择了曲线上一点 A 作为初始点,并且让它不断和自己做 “dot” 运算,中途会到达 B、C、D 等点,最后你会发现 n 次运算后又会回到 A 点。由此可以认为,A 以及 B、C、D 等点的集合构成了这条椭圆曲线。因此原文说 “同一条曲线,但只用整数点(就可以)表示”。

你可以将两点之间的线想象成一条在边界处环绕直到触及一点的线。仿佛在我们的奇怪台球游戏中,当球击中桌子的边缘(最大值 max)时,它就会神奇地被传送到桌子的另一侧,并继续它的路径直到触及一个点。

在这种新的曲线表示方法中,你可以把一些消息表示为曲线上的若干个点。你可以想象取出一个消息并将其设置为 x 坐标,然后解出 y 以得到曲线上的一个点。在实际中,这个过程比这略微复杂一些,但这是大概的想法。

你会得到以下点:

(70,6), (76,48), ……, (82,6), (69,22)

这一小段讲得确实比较抽象,不知道是不是翻译的原因。

椭圆曲线密码系统可以通过选择一个素数作为最大值、一个曲线方程和曲线上的一个公共点来定义。私钥是一个数字 priv,公钥是公共点与自身相乘 priv 次的结果。在这种密码系统中,从公钥计算私钥的过程被称为 椭圆曲线离散对数函数。这最终是我们一直在寻找的 “陷门函数”。

个人理解:“公共点” 可以理解为前文中提到的起始点 A 点,“相乘” 实际上应该是指前文定义的 “dot” 运算。最后这段话应该算是本文的核心了🥳

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

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

相关文章

leetcode 1702

leetcode 1702 题目 例子 代码思路 class Solution { public:string maximumBinaryString(string binary) {int n binary.size();int i binary.find(0);if(i string::npos){return binary;}int zeros count(binary.begin(), binary.end(), 0);string s(n, 1);s[izeros-1]…

Python爬虫怎么挣钱?6个Python爬虫赚钱方式,搞搞副业不是问题

1.最典型的就是找爬虫外包活儿 网络爬虫最通常的的挣钱方式通过外包网站,做中小规模的爬虫项目,向甲方提供数据抓取,数据结构化,数据清洗等服务。新入行的程序员大多都会先尝试这个方向,直接靠技术手段挣钱&#xff0…

数据结构复习指导之绪论(算法的概念以及效率的度量)

文章目录 绪论: 2.算法和算法评价 知识总览 2.1算法的基本概念 知识点回顾与重要考点 2.2算法效率的度量 知识总览 1.时间复杂度 2.空间复杂度 知识点回顾与重要考点 归纳总结 绪论: 2.算法和算法评价 知识总览 2.1算法的基本概念 算法( Al…

一辆汽车的节拍时间是怎样的?

节拍时间,又称 takt time,是德语中“节奏”的意思。在汽车制造业中,它指的是按照客户需求和生产计划,生产一辆汽车所需的时间。这个时间是固定的,它决定了生产线上每个工序的操作速度和节奏,是生产线上所有…

一题多解之数塔问题

递归实现:记忆化深度遍历 #include <iostream> #include <algorithm> #include <string> using namespace std; int num[1000][1000],n;//递归实现:记忆化深度遍历 int dfs(int x,int y){int sum0;//记录最大情况if(x>n||y>x) return sum;//实现每次都…

功能测试_验证标题长度合法性_边界值法

验证标题长度合法性&#xff08;标题长度大于0&#xff0c;小于等于30个字符&#xff09; 开内闭外&#xff0c;保留1和31

水电智能远程抄表系统

水电智能远程抄表系统是一种应用先进技术实现水电抄表的智能化管理系统&#xff0c;通过远程抄表、数据传输和智能分析&#xff0c;实现了对水电使用情况的实时监测和管理。本文将从系统特点、构成以及带来的效益三个方面展开介绍。 系统特点 1.远程抄表&#xff1a;系统能够…

cas学习4:自定义登出页面

接上一章学习 cas学习3&#xff1a;自定义登录页面_cas 个性化页面-CSDN博客 后我们要自定义登出页面&#xff0c;因为在配置完cas后各个子系统退出后的都是cas登出页面。不符合实际需要&#xff0c;所以我们要配置自己的登出页面 1.修改application.properties 增加&#…

有效确认手机号机主姓名,避免信息错误

在如今信息爆炸的时代&#xff0c;手机已经成为我们生活中必不可少的一部分。手机号码的重要性已经不仅仅是联系工具&#xff0c;更是诸多场景下的实名认证必备条件&#xff0c;如电商、游戏、直播、金融等。为了保证用户信息的准确性和安全性&#xff0c;挖数据平台上的手机号…

软件测试学习之MySQL学习笔记(完结)

目录 1. 数据库**** 1.1. 概念**** 1.2. 分类**** 1.2.1. 关系型数据库**** 1.2.1.1. SQL**** 1.2.2. 安装**** 1.2.2.1. Navicat**** 2. SQL语句**** 2.1. 常用数据类型**** 2.2. 数据库**** 2.3. 表**** 2.3.1. 字段约束**** 2.4. 数据**** 2.4.1. 增 insert**…

AI革新病历系统-能“读懂”病历,或将能“思考”

Artificial Intelligence&#xff08;人工智能&#xff09;&#xff0c;简称AI。它其实是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。 电子病历系统拖慢了医疗工作流程&#xff0c;人工智能或许能改善这一困境。 一位名叫罗杰的…

典型神经网络模型—自编码器

文章目录 编码器的介绍基本原理编码器的分类 应用案例网络构建训练步骤&#xff1a;调优&#xff1a; 编码器的介绍 基本原理 在神经网络中&#xff0c;编码器&#xff08;Encoder&#xff09;是一种用于将输入数据转换为另一种形式的网络组件或模型部分。编码器的核心任务是…

Teachable Machine模型之TensorFlow使用篇

前言: 使用在teachable machine训练的h5格式模型 tensorflow使用篇 1. 使用teachable machine训练模型 地址: 传送门, 需要梯子翻一下 训练后, 导出的时候可以选择三种类型 导出模型文件 converted_keras.zip (py版) 解压后得到 2. py项目中使用模型 根据你当时使用tea…

FFmpeg: 简易ijkplayer播放器实现--06封装打开和关闭stream

文章目录 流程图stream openstream close 流程图 stream open 初始化SDL以允许⾳频输出&#xff1b;初始化帧Frame队列初始化包Packet队列初始化时钟Clock初始化音量创建解复用读取线程read_thread创建视频刷新线程video_refresh_thread int FFPlayer::stream_open(const cha…

Nginx转发请求错误

说明&#xff1a;记录一次使用Nginx转发请求的错误&#xff1b; 场景 公司内部有两台服务器都跑了后端项目&#xff0c;在使用Nginx做请求分发时&#xff0c;我发现其中有台服务器一直没有处理请求&#xff08;没打印相关的日志信息&#xff09;&#xff0c;于是我修改了下Ng…

企业如何使用SNP Glue将SAP与Snowflake集成?

SNP Glue是SNP的集成技术&#xff0c;适用于任何云平台。它最初是围绕SAP和Hadoop构建的&#xff0c;现在已经发展为一个集成平台&#xff0c;虽然它仍然非常专注SAP&#xff0c;但可以将几乎任何数据源与任何数据目标集成。 我们客户非常感兴趣的数据目标之一是Snowflake。Sno…

SpringBoot集成Skywalking链路追踪

安装skywaling 参考&#xff1a;Centos7搭建 SkyWalking 单机版-CSDN博客 下载Agents https://archive.apache.org/dist/skywalking/java-agent/9.0.0/apache-skywalking-java-agent-9.0.0.tgz 1. 在IDEA中使用skywalking agent 在VM options中填入如下信息 -javaagent后是…

LeetCode-2529题:正整数和负整数的最大计数(原创)

【题目描述】 给你一个按 非递减顺序 排列的数组 nums &#xff0c;返回正整数数目和负整数数目中的最大值。换句话讲&#xff0c;如果 nums 中正整数的数目是 pos &#xff0c;而负整数的数目是 neg &#xff0c;返回 pos 和 neg二者中的最大值。注意&#xff1a;0 既不是正整…

windows ffmpeg7 通过rtsp拉取h265裸流

点击下边那个链接会转到github 下载完成后&#xff0c;添加include、lib到工程。 添加头文件&#xff1a; extern "C" { #include "libavcodec/avcodec.h" #include "libavformat/avformat.h" #include "libavformat/avio.h" #inclu…

【实战JVM】打破双亲委派机制之自定义类加载器

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…