密码学入门:椭圆曲线初步揭秘

Frank Mangone 发布于 2024-10-15 阅读 3463

本文介绍了椭圆曲线在密码学中的应用,解释了椭圆曲线如何通过特定的群操作(如弦切线规则)形成密码学所需的数学结构。文章详细讨论了椭圆曲线群的定义、有限域上的点运算、群单位元的引入以及点加倍操作,并指出这些数学结构为加密和数字签名提供了难以破解的难题基础。

这是密码学系列文章的一部分。如果这是你第一次阅读本系列,强烈建议从系列的开篇开始。

前文中,我们简要讨论了支撑当前广泛使用的密码学技术的一些基本概念。

我们尚未讨论_为什么_群和模算术在密码学中如此有用。但你可能已经猜到,核心思想是它们允许我们构建_极难解决_的问题——即使投入惊人的计算资源,实际上也无法破解。例如,为什么数字签名有效?因为掌握私钥时生成有效签名_相对简单_,但没有私钥时则_难如登天_。

我们稍后会深入探讨这些细节。现在,我认为聚焦于能够使待解决问题_更加困难_的_其他群结构_更有意义——这正是_椭圆曲线_的登场时刻。

什么是椭圆曲线?

曲线_通常由_方程_定义。对于椭圆曲线,方程_E(实际是简化形式,但我们会沿用这个表述)如下所示:

曲线 y² = x³ - x 的图示

但等等... 这和群有什么关系?这毕竟只是一条曲线!

让我们快速回顾已学内容。群由_集合_(记为?)和_二元运算_定义,该运算接收两个?元素并生成另一个?元素。如果我们能找到利用椭圆曲线构造有效_集合_和_二元运算_的方法,就能得到一个群。

而确实存在这样的方法!

群运算

取椭圆曲线上任意两点_P_和_Q_,绘制穿过它们的_直线_。通过基本代数运算可知,(几乎总是)存在_第三个交点_。取该点,以x轴为镜面进行垂直翻转。恭喜,你得到了点_R = P + Q_!

此过程称为_弦切线规则_(chord-and-tangent rule),正是我们寻找的_群运算_。

第一次接触这个概念时,我的反应是"多么奇特的流程"。我不禁自问:究竟为何需要翻转第三个交点?深入探究后,只能说:解释其合理性的原因远超本文范畴。目前请相信一切逻辑都是_严密自洽的_。

椭圆曲线 y² = x³ -x + 1(红色)及运算 P + Q = R 的演示

可通过DesmosGeoGebra等图形工具自行尝试。

至此完成了一个要素,还需构建_集合_。由于_弦切线规则_将椭圆曲线上的两个点映射为另一个点,自然我们需处理_椭圆曲线上的点集_。但存在两个问题:

  • 椭圆曲线上的点多为实数值,即坐标可能非_整数_。这很重要:否则计算_P + Q_时可能出现_舍入误差_
  • 曲线上有_无限_个点,但我们需要_有限_集合

如何解决这些问题?

寻找合适的集合

事实证明,某些椭圆曲线存在无限个整数值点(如_P = (1,2)_)。通过_恰当选择_椭圆曲线,第一个问题神奇消失。假设我们已掌握选择方法,聚焦第二个问题。

将无限整数集转换为有限集有个巧妙技巧——我们_早已见识过_。猜到了吗?没错,就是**模运算**!

椭圆曲线取模23后的点集

例如,若选择q = 11,则曲线上点P' = (11, 13)在群中实际对应元素P = (0, 2)!注意我们对每个坐标应用了模运算

形式上,我们称椭圆曲线定义在_有限域_上,任何"越界"点都通过模运算映射回域内。表示为:

大功告成!现在有了_集合_和"加法"运算方法。但似乎遗漏了什么...

群单位元

观察下图。当尝试计算_P + Q_时会发生什么?

明显_不存在第三个交点_!恐慌随之而来。这是否意味着构造失败?

幸运的是,通过定义新群元素_O_(视为_无穷远点_,虽不准确但便于理解)即可化解危机。该元素具有关键特性:对曲线上任意点_P_,满足:

是否似曾相识?这与任何数加_零_的结果是否如出一辙?

这正是群论中的_单位元_概念——整数群中的_零_与椭圆曲线中的_O_扮演相同角色。添加该元素后,集合完备性得以保证,任意两点的加法运算总能获得有效结果。

但仍有细节待完善。

点加倍(Point Doubling)

计算_P + P_时会发生什么?根据_弦切线规则_:需要穿过两点的直线,但此处_仅有一点_!此时需考虑点_P_处的曲线_切线_。

按惯例找到第三个交点,翻转得到_P + P_,记为**[2]P**。这个操作被命名为_点加倍_。

点加倍操作演示

计算_P + [2]P_的流程依旧:绘制穿过两点的直线,翻转第三个交点,即可得到_[3]P_。重复该过程得_[4]P_。此时可观察到奇特现象:四次相加_P_(P + P + P + P)与两次相加_[2]P_的结果相同!

这个看似简单的现象,实为椭圆曲线应用中的_最强大工具_。假设需要计算_[12384162178627301263]P_,逐点相加耗时极长——但正确应用_点加倍_可_指数级加速_运算!

这正对应本文开头提及的_极难问题_。后续将讨论,此类难题正是基于群的密码学构造得以存在的根基!

总结

我们定义了_椭圆曲线群_。它们是由可进行加法运算的整点构成的集合,通过模运算限定在特定范围内。文献中提及椭圆曲线时,通常指代的是_群_而非曲线本身。若需特指曲线,常称为_仿射曲线_。

如果你此刻的感受是:

每日清晨的我

初次接触确实难以理解,但一旦掌握就会觉得自然。给自己些时间消化,欢迎随时提问!

可通过此网站进行椭圆曲线交互实验。

基础铺垫已完成。在下一篇文章中,我们将探讨如何应用椭圆曲线知识,研究_非对称加密_方案和_数字签名_方案。敬请期待!

  • 原文链接: medium.com/@francomangon...
  • 登链社区 AI 助手,为大家转译优秀英文文章,如有翻译不通的地方,在这里修改,还请包涵~
该文章收录于
密码学101
32 订阅 31 篇内容

0 条评论