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

2024-04-18 03:20

本文主要是介绍密码学 | 椭圆曲线密码学 ECC 入门(一),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

正文

1  公共密钥密码学的兴起

2  玩具版 RSA 算法

2.1  RSA 基本原理

2.2  RSA 举例说明

1  加密

2  解密

3  不是完美的陷门函数


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

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


正文

椭圆曲线密码学(ECC)是当今广泛使用但最少被理解的一种密码学类型。在 CloudFlare,我们大量使用 ECC 来保护从客户的 HTTPS 连接到我们在数据中心之间传递数据的方式。

从根本上说,我们认为能够理解任何安全系统背后的技术是信任它的关键。为此,我们在寻找一个好的、相对容易理解的 ECC 入门资料以与用户分享,但没有找到。最终,我们决定自己编写一个。以下是你要阅读的内容。

警告:这是一个复杂的话题,不可能将其浓缩成一篇精炼的博客文章。换句话说,准备好进行一次史诗般的旅程,因为有很多内容需要涵盖。如果你只想了解大意,那么长话短说:ECC 是公共密钥密码学的下一代,根据目前理解的数学,它比第一代公共密钥密码学系统如 RSA 提供了更安全的基石。如果你担心确保最高级别的安全同时保持性能,那么采用 ECC 是有意义的。如果你对细节感兴趣,请继续阅读。

1  公共密钥密码学的兴起

密码学的历史可以分为两个时代:古典时代和现代时代。这两个时代之间的分水岭出现在 1977 年,当时 RSA 算法和 Diffie-Hellman 密钥交换算法都被提出。这些新算法之所以具有革命性,是因为它们代表了首批基于数论理论的可行密码学方案;它们是首批能够在不共享秘密的情况下,在两个双方之间进行安全通信的算法。密码学从关于安全地在全球范围内运输秘密密码簿的活动,转变为了能够证明任何两个方之间通信的安全性,而无需担心有人在密钥交换过程中偷听。

本文没有介绍 Diffie-Hellman 密钥交换算法。

现代密码学的基础理念是,你可以公开你用来加密数据的密钥,而用来解密数据的密钥可以保持私密。因此,这些系统被称为公钥密码系统。

这些系统中最先出现,并且至今仍被广泛使用的是 RSA 算法,它以三位首次公开描述该算法的男性的名字首字母命名:Ron Rivest,Adi Shamir 和 Leonard Adleman 。

要让公钥密码系统工作,你需要一套易于单向处理但难以逆向的算法。在 RSA 的案例中,易于处理的算法是两个质数的乘法。如果乘法是易于的算法,那么其难以逆向的配对算法是将乘积分解为两个质数成分。具有这种特性 —— 单向容易,逆向困难 —— 的算法被称为 陷门函数。找到一个好的陷门函数对于建立一个安全的公钥密码系统至关重要。

简单来说:陷门函数中单向和逆向困难的差距越大,基于它的密码系统的安全性就越高。

2  玩具版 RSA 算法

RSA 算法是最流行且最为人理解的公钥密码系统。它的安全性依赖于 因式分解的缓慢和乘法的快速以下是对小型 RSA 系统的工作原理的快速概述。

RSA 算法满足 “单向容易,逆向困难”,其中单向是乘法,逆向是因式分解。

2.1  RSA 基本原理

一般来说,公钥加密系统有两个组成部分,公钥和私钥。加密过程是通过将消息应用数学运算得到一个看起来随机的数字。解密过程是将这个看起来随机的数字应用不同的运算得到原始数字。用公钥进行的加密只能通过用私钥进行解密来解除。

计算机处理任意大小的数字不太合适。我们可以通过选择一个最大数,并且只处理小于最大数的数字来确保我们处理的数字不会太大。我们可以将数字看作是模拟时钟上的数字。任何结果大于最大数的计算都会被绕回到有效范围内的一个数。

由于存储空间的限制,计算机是没有办法存储一个很大的数字的原码的,因此人们引入了补码的概念,也就是对原码进行模运算。—— 计算机系统结构

在 RSA 中,这个最大值(我们称之为 max)是通过乘以两个随机质数来获得的。公钥和私钥是两个特别选择的数字,它们大于零且小于最大值,我们称它们为 pub 和 priv 。要加密一个数字,你需要将它乘以自身 pub 次,确保当你达到最大值时绕回。要解密消息,你需要将它乘以自身 priv 次,然后你就能回到原始数字。这听起来可能很惊讶,但实际上它是有效的。这一属性在被发现时是一个重大的突破。 

为什么定义最大值 max?答:这个 max 实际上就是模,到时候待加密数字要对它取余。

创建 RSA 密钥对:

  1. 首先随机选择两个质数来获得最大值(max)。
  2. 然后随机选择一个数字作为公钥 pub 。
  3. 只要你知道这两个质数,你就可以根据这个公钥计算出相应的私钥 priv 。

这就是因式分解与破解 RSA 的关系 —— 将最大数分解为其质数成分允许你从公钥计算出某人的私钥,并解密他们的私人消息。

针对 “只要你知道这两个质数,你就可以根据这个公钥计算出相应的私钥 priv”,下文说是根据 “扩展欧几里得算法” 得到的。这又是什么算法。。。

2.2  RSA 举例说明

让我们通过一个例子来使这个概念更具体。取质数 13 和 7,它们的乘积给我们最大值 91 。让我们将公钥设置为数字 5 。然后使用我们知道 7 和 13 是 91 的因数这一事实,并应用扩展欧几里得算法这个算法,我们得到私钥是数字 29 。

这些参数(max: 91, pub: 5, priv: 29)定义了一个完全功能的 RSA 系统。你可以取一个数字,乘以自身 5 次来加密它,然后取那个数字,乘以自身 29 次,你就能得到原始数字。

让我们使用这些值来加密消息 "CLOUD"

1  加密

为了将消息数学化,我们必须将字母转换为数字。拉丁字母的常见表示是 UTF-8 。每个字符对应一个数字。在这种编码下,CLOUD 对应的数字是 67, 76, 79, 85, 68 。每个这些数字都小于我们的最大值 91,所以我们可以单独加密它们。让我们从第一个字母 C 开始。

我们需要将它乘以自身 5 次来得到加密值。

  • 第 1 次:67(本身)
  • 第 2 次:67 × 67 = 4489 = 30
  • 第 3 次:30 × 67 = 2010 = 8
  • 第 4 次:8 × 67 = 536 = 81
  • 第 5 次:81 × 67 = 5427 = 58

这意味着 67 的加密版本是 58 。

只要乘积结果大于最大值(max),我们都需要通过除以 91 来取余数。

对于每个字母重复这个过程,我们得到加密的消息 CLOUD 变成了:

58, 20, 53, 50, 87

2  解密

为了解密这个混乱的消息,我们取每个数字并乘以自身 29 次:

  • 第 1 次:58(本身)
  • 第 2 次:58 × 58 = 3364 = 88
  • 第 3 次:88 × 58 = 5104 = 8
  • ……
  • 第 29 次:9 × 58 = 522 = 67

你看看,我们又回到了 67 。这对于其他数字也有效,结果是原始消息。结论是,你可以取一个数字,乘以自身多次得到一个看起来随机的数字,然后乘以自身一个秘密的次数回到原始数字。

同样地,只要乘积结果大于最大值(max),我们都需要通过除以 91 来取余数。

3  不是完美的陷门函数

RSA 和 Diffie-Hellman 之所以强大,是因为它们伴随着严格的安全性证明。作者证明了破解系统等同于解决一个被认为难以解决的数学问题。

因式分解是一个非常著名的问题,自古以来就有人研究(参见埃拉托斯特尼筛法)。任何突破都会是重大新闻,并会给发现者带来巨大的经济利益。话说回来,因式分解在位对位的基础上并不是最困难的问题。专门算法如二次筛法和一般数域筛法被创造出来解决素数因子分解问题,并且取得了一定的成功。这些算法比简单猜测已知素数的朴素方法更快,计算强度更低。

这些因式分解算法随着被分解数字大小的增加而变得更加高效。因式分解大数字的难度与乘法大数字的难度之间的差距随着数字(即密钥的位长度)的增加而缩小。随着解密数字的计算资源的增加,需要的密钥大小必须增长得更快。这对于计算能力有限的移动和低功耗设备来说是不可持续的。因式分解和乘法之间的差距在长期内是不可持续的。

个人理解,这里的意思是:数字越大,人们所提出的因式分解算法越容易对其进行分解。在这种情况下,“因式分解的难度” 变小了,“乘法的难度” 变大了,从而二者之间的差距变小了。与此同时,RSA 算法又是一种陷门函数,二者差距的减小会导致 RSA 算法所依赖的安全性减少。

所有这些都意味着 RSA 不是密码学未来的理想系统。在理想的陷门函数中,简单方式和困难方式以相同的速率随着被讨论数字的大小变难。我们需要一个基于更好陷门函数的公钥系统。

这篇关于密码学 | 椭圆曲线密码学 ECC 入门(一)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/913639

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题:

Java 创建图形用户界面(GUI)入门指南(Swing库 JFrame 类)概述

概述 基本概念 Java Swing 的架构 Java Swing 是一个为 Java 设计的 GUI 工具包,是 JAVA 基础类的一部分,基于 Java AWT 构建,提供了一系列轻量级、可定制的图形用户界面(GUI)组件。 与 AWT 相比,Swing 提供了许多比 AWT 更好的屏幕显示元素,更加灵活和可定制,具有更好的跨平台性能。 组件和容器 Java Swing 提供了许多

【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant #搭建基本环境 1 背景2 docker下载 hass3 创建容器4 浏览器访问 hass5 手机APP远程访问hass6 更多玩法 1 背景 既然电脑可以IPV6入站,手机流量可以访问IPV6网络的服务,为什么不在电脑搭建Home Assistant(hass),来控制你的设备呢?@智能家居 @万物互联

poj 2104 and hdu 2665 划分树模板入门题

题意: 给一个数组n(1e5)个数,给一个范围(fr, to, k),求这个范围中第k大的数。 解析: 划分树入门。 bing神的模板。 坑爹的地方是把-l 看成了-1........ 一直re。 代码: poj 2104: #include <iostream>#include <cstdio>#include <cstdlib>#include <al

MySQL-CRUD入门1

文章目录 认识配置文件client节点mysql节点mysqld节点 数据的添加(Create)添加一行数据添加多行数据两种添加数据的效率对比 数据的查询(Retrieve)全列查询指定列查询查询中带有表达式关于字面量关于as重命名 临时表引入distinct去重order by 排序关于NULL 认识配置文件 在我们的MySQL服务安装好了之后, 会有一个配置文件, 也就

音视频入门基础:WAV专题(10)——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础:WAV专题(6)——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道,通过FFprobe命令可以打印WAV音频文件每个packet(也称为数据包或多媒体包)的信息,这些信息包含该packet的pts、dts: 打印出来的“pts”实际是AVPacket结构体中的成员变量pts,是以AVStream->time_base为单位的显

C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》 作为一个程序员,我接触 C 语言有十年了。有的朋友让我推荐 C 语言的参考书,我不敢乱推荐,尤其是国内作者写的书,往往七拼八凑,漏洞百出。 但是,李忠老师的《C语言非常道》值得一读。对了,李老师有个官网,网址是: 李忠老师官网 最棒的是,有配套的教学视频,可以试看。 试看点这里 接下来言归正传,讲解指针。以下内容很多都参考了李忠老师的《C语言非

MySQL入门到精通

一、创建数据库 CREATE DATABASE 数据库名称; 如果数据库存在,则会提示报错。 二、选择数据库 USE 数据库名称; 三、创建数据表 CREATE TABLE 数据表名称; 四、MySQL数据类型 MySQL支持多种类型,大致可以分为三类:数值、日期/时间和字符串类型 4.1 数值类型 数值类型 类型大小用途INT4Bytes整数值FLOAT4By

OpenCV结构分析与形状描述符(11)椭圆拟合函数fitEllipse()的使用

操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C++11 算法描述 围绕一组2D点拟合一个椭圆。 该函数计算出一个椭圆,该椭圆在最小二乘意义上最好地拟合一组2D点。它返回一个内切椭圆的旋转矩形。使用了由[90]描述的第一个算法。开发者应该注意,由于数据点靠近包含的 Mat 元素的边界,返回的椭圆/旋转矩形数据