Jump to content
  • Hello visitors, welcome to the Hacker World Forum!

    Red Team 1949  (formerly CHT Attack and Defense Team) In this rapidly changing Internet era, we maintain our original intention and create the best community to jointly exchange network technologies. You can obtain hacker attack and defense skills and knowledge in the forum, or you can join our Telegram communication group to discuss and communicate in real time. All kinds of advertisements are prohibited in the forum. Please register as a registered user to check our usage and privacy policy. Thank you for your cooperation.

    TheHackerWorld Official

椭圆曲线密码学:一个温和的介绍 - Andrea Corbellini

 Share


Recommended Posts

  • 知道什么是公钥密码学的人可能已经听说过ECCECDHECDSA。第一个是 Elliptic Curve Cryptography 的首字母缩写,其他是基于它的算法的名称。

    今天,我们可以在TLSPGPSSH 中找到椭圆曲线密码系统,这只是现代网络和 IT 世界所基于的三种主要技术。更不用说比特币和其他加密货币了。

    在 ECC 流行之前,几乎所有的公钥算法都是基于 RSA、DSA 和 DH 的,这是基于模块化算法的替代密码系统。RSA 和朋友今天仍然非常重要,并且经常与 ECC 一起使用。然而,尽管 RSA 和朋友们背后的魔力很容易解释,被广泛理解,并且可以很容易地编写粗略的实现,但 ECC 的基础对大多数人来说仍然是个谜。

    通过一系列博客文章,我将向您简要介绍椭圆曲线密码学的世界。我的目标不是提供 ECC 的完整和详细指南(网络上充满了有关该主题的信息),而是提供一个简单概述 ECC 是什么以及为什么它被认为是安全的,而不会在冗长的数学证明上浪费时间或无聊的实现细节。我还将提供有用的示例以及可视化交互工具和脚本来使用.

    具体来说,以下是我将涉及的主题:

    1. 实数上的椭圆曲线和群定律(在此博客文章中介绍)
    2. 有限域上的椭圆曲线和离散对数问题
    3. 密钥对生成和两种 ECC 算法:ECDH 和 ECDSA
    4. 破解ECC安全的算法,以及与RSA的比较

    为了理解这里所写的内容,您需要了解集合论、几何和模算术的一些基本知识,并熟悉对称和非对称密码学。最后,您需要清楚什么是“简单”问题,什么是“困难”问题,以及它们在密码学中的作用。

    准备好?开始吧!

    椭圆曲线

    首先:什么是椭圆曲线?Wolfram MathWorld 给出了一个极好的和完整的定义。但对于我们的目标,椭圆曲线将只是由方程描述的一组点

    在哪里 (这是排除奇异曲线所必需的)。上面的方程就是所谓的椭圆曲线的_Weierstrass 范式_。

    不同椭圆曲线的不同形状

    不同椭圆曲线的不同形状(, 从 2 到 -3 不等)。

    奇点的类型

    奇点的类型:在左侧,带有尖点的曲线 ()。在右侧,具有自相交的曲线 ()。它们都不是有效的椭圆曲线。

    取决于价值 和 ,椭圆曲线可以在平面上呈现不同的形状。正如可以很容易地看到和验证的那样,椭圆曲线关于-轴。

    为了我们的目标,我们还需要一个无穷远点(也称为理想点)作为曲线的一部分。从现在开始,我们将用符号 0(零)表示无穷远处的点。

    如果我们想明确地考虑无穷远处的点,我们可以改进椭圆曲线的定义如下:

    团体

    数学中的群是一个集合,我们为它定义了一个二元运算,我们称之为“加法”并用符号 + 表示。为了集合 要成为一个组,必须定义加法以使其尊重以下四个属性:

    1. **关闭:**如果 和 是成员 , 然后 是会员 ;
    2. 关联性: ;
    3. 存在一个单位元素0 使得;
    4. 每个元素都有一个,即:对于每个 那里存在 以至于 .

    如果我们添加第五个要求:

    1. 交换性: ,

    那么这个群称为_阿贝尔群_。

    用通常的加法概念,整数集 是一个群(而且,它是一个阿贝尔群)。自然数集 然而不是一个组,因为不能满足第四个属性。

    组很好,因为如果我们能证明这四个属性成立,我们就可以免费获得其他一些属性。例如:标识元素是唯一的;也是逆是唯一的,那就是:每 只有一个 以至于 (我们可以写 作为 )。无论是直接的还是间接的,这些和其他关于群体的事实对我们以后都非常重要。

    椭圆曲线群定律

    我们可以在椭圆曲线上定义一个组。具体来说:

    • 群的元素是椭圆曲线的点;
    • 身份元素是在无限远0点;
    • 点的倒数 是关于对称的 -轴;
    • 加法由以下规则给出给定三个对齐的非零点, 和 ,他们的总和是 .

    三个对齐点

    三个对齐点之和为0。

    注意最后一条规则,我们只需要三个对齐的点,三个点对齐是不分顺序的。这意味着,如果, 和 对齐,然后 . 这样,我们直观地证明了我们的 + 运算符既是结合的又是可交换的:我们在一个阿贝尔群中

    到目前为止,太棒了。但是我们如何实际计算两个任意点的总和呢?

    几何加法

    由于我们在一个阿贝尔群中,我们可以写 作为 . 这个方程,以这种形式,让我们推导出一种几何方法来计算两点之间的总和 和 :如果我们画一条穿过的线 和 ,这条线将与曲线上的第三个点相交, (这是由事实暗示的 , 和 对齐)。如果我们取这个点的倒数,,我们找到了结果 .

    积分加成

    通过画线 和 . 该线与第三个点相交. 与它对称的点,, 是结果 .

    这种几何方法有效,但需要一些改进。特别是,我们需要回答几个问题:

    • 如果 或者 ? 当然,我们不能画任何线(0不在-飞机)。但是鉴于我们已经定义了 0 作为单位元素, 和 ,对于任何 并且对于任何 .

    • 如果 ? 在这种情况下,通过这两个点的线是垂直的,并且不与任何第三个点相交。但是如果 是相反的 ,那么我们有 从逆的定义。

    • 如果 ? 在这种情况下,有无限多条线通过该点。事情开始变得有点复杂。但是考虑一个点. 如果我们让 方法 ,越来越近了吗?

      当Q接近P时P+Q的结果

      当两点靠得更近时,穿过它们的线与曲线相切。

    作为 趋向于 ,通过的线 和 与曲线相切。有鉴于此,我们可以说, 在哪里 是曲线与曲线的切线之间的交点 . *如果,但没有第三点 ? 我们遇到的情况与上一个非常相似。事实上,我们在线路经过的情况下 和 与曲线相切。

    当Q接近P时P+Q的结果

    如果我们的线只与两个点相交,那么这意味着它与曲线相切。很容易看出求和的结果如何对称于两点之一。

    让我们假设 是切点。在前一种情况下,我们会写. 这个等式现在变成. 另一方面,如果 是切点,正确的方程应该是 .

    几何方法现已完成并涵盖所有情况。使用铅笔和尺子,我们可以对任何椭圆曲线的每个点进行加法运算。如果您想尝试,请查看我为计算椭圆曲线总和而构建的HTML5/JavaScript 可视化工具

    代数加法

    如果我们想让计算机进行点加法,我们需要把几何方法变成代数方法。将上述规则转换为一组方程似乎很简单,但实际上它可能非常乏味,因为它需要求解三次方程。为此,我在这里只报告结果。

    首先,让我们摆脱最烦人的角落案例。我们已经知道,我们也知道 . 所以,在我们的方程中,我们将避免这两种情况,我们将只考虑两个非零、非对称点 和 .

    如果 和 是不同的(),通过它们的线有斜率

    这条线与椭圆曲线的交点是第三个点:

    或者,等效地:

    因此 (注意标志并记住 )。

    如果我们想检查这个结果是否正确,我们必须检查是否 是否属于曲线 , 和 对齐。检查点是否对齐是微不足道的,检查 属于曲线不是,因为我们需要解决三次方程,这一点都不有趣。

    相反,让我们看一个例子:根据我们的可视化工具,给定 和 在曲线上 ,他们的总和是 . 让我们看看我们的方程是否一致:

    是的,这是正确的!

    请注意,即使其中之一,这些方程也有效 或者 是一个切点。让我们试试 和 .

    我们得到结果 ,这与视觉工具给出的结果相同。

    案子 需要区别对待:方程 和 是一样的,但鉴于 ,我们必须使用不同的斜率方程:

    请注意,正如我们所期望的,这个表达式为 是一阶导数:

    为了证明这个结果的有效性,检查一下就足够了 属于曲线并且通过的线 和 与曲线只有两个交点。但同样,我们没有证明这个事实,而是用一个例子来尝试:.

    这给了我们 . 正确

    虽然推导出它们的过程可能非常乏味,但我们的方程非常紧凑。这要归功于 Weierstrass 范式:没有它,这些方程可能真的很长很复杂!

    标量乘法

    除了加法,我们还可以定义另一个运算:标量乘法,即:

    在哪里 是一个自然数。我也写了一个用于标量乘法的**可视化工具**,如果你想玩的话。

    以这种形式编写,似乎计算 需要 补充。如果 已 二进制数字,那么我们的算法将是 ,这不是很好。但是存在更快的算法。

    其中之一是双加算法。它的工作原理可以通过一个例子来更好地说明。拿. 它的二进制表示是. 这种二进制表示可以变成 2 的幂之和:

    (我们已经取了每个二进制数字 并将其乘以 2 的幂。)

    有鉴于此,我们可以这样写:

    double 和 add 算法告诉我们要做的是:

    • 拿 .
    • 加倍,这样我们得到.
    • 添加 到 (为了得到结果 )。
    • 双倍的 ,所以我们得到 .
    • _将_其_添加_到我们的结果中(以便我们得到)。
    • 双倍的 要得到 .
    • 不要执行任何涉及的加法 .
    • 双倍的 要得到 .
    • _将_其_添加_到我们的结果中(以便我们得到)。

    最后,我们可以计算 仅执行七次加倍和四次加法。

    如果这还不够清楚,这里有一个实现算法的 Python 脚本:

    def bits(n):
        """
        Generates the binary digits of n, starting
        from the least significant bit.
    
        bits(151) -> 1, 1, 1, 0, 1, 0, 0, 1
        """
        while n:
            yield n & 1
            n >>= 1
    
    def double_and_add(n, x):
        """
        Returns the result of n * x, computed using
        the double and add algorithm.
        """
        result = 0
        addend = x
    
        for bit in bits(n):
            if bit == 1:
                result += addend
            addend *= 2
    
        return result
    

    如果加倍和相加都是 操作,那么这个算法是 (或者 如果我们考虑位长),这是相当不错的。肯定比最初的好很多 算法!

    对数

    给定的 和 ,我们现在至少有一个多项式时间算法来计算 . 但是反过来呢?如果我们知道怎么办 和 并且需要找出 ? 这个问题被称为对数问题。我们称它为“对数”而不是“除法”以符合其他密码系统(其中我们有幂运算而不是乘法)。

    我不知道对数问题有什么“简单”的算法,但是玩乘法很容易看到一些模式。例如,取曲线 和重点 . 我们可以立即验证,如果 很奇怪, 在左半平面的曲线上;如果 甚至, 位于右半平面的曲线上。如果我们进行更多实验,我们可能会发现更多模式,最终可以引导我们编写算法来有效地计算该曲线上的对数。

    但是对数问题有一个变体:_离散_对数问题。正如我们将在下一篇文章中看到的,如果我们减少椭圆曲线的域,标量乘法仍然是“容易”的,而离散对数就变成了一个“困难”的问题。这种对偶性是椭圆曲线密码学的关键。

    下周见

    今天的内容就到这里,希望你喜欢这篇文章!下周我们将发现有限域和**_离散_对数问题**,以及可以使用的示例和工具。如果这些东西对您来说很有趣,那么请继续关注!

Link to post
Link to comment
Share on other sites

 Share

discussion group

discussion group

    You don't have permission to chat.
    • Recently Browsing   0 members

      • No registered users viewing this page.
    ×
    ×
    • Create New...