精华内容
下载资源
问答
  • 1.确定椭圆曲线 具体包括确定模数P;系数a和b;生成器点A,构造素数阶循环群q. 2.随机选取KPR值 随机选取整数d,且有0<d<q KPR=d 3.计算公钥 B=dA KPB=(P,A,B,q,A,B) 4.生成签名 1.选择临时密钥Ke,其中0<...
  • java借助bouncycastle库实现ECC双向加密解密算法Utils工具包。
  • 椭圆曲线密码系统的实现及安全性分析,内容不错希望能对大家有所帮助
  • 7.6椭圆曲线密码算法

    2020-12-03 21:25:43
    为了保证RSA算法的安全性,其密钥长度不断增加,导致加解密运算负担越来越重,处理速度越来越慢;相比之下,基于椭圆曲线理论的公钥密码体制可以用较短的密钥获得同样的密码强度。

    1、椭圆曲线密码算法

    为了保证RSA算法的安全性,其密钥长度不断增加,导致加解密运算负担越来越重,处理速度越来越慢;相比之下,基于椭圆曲线理论的公钥密码体制可以用较短的密钥获得同样的密码强度。

    1、椭圆曲线密码算法特性

    1、安全性高
    2、密钥量小,运算速度快
    3、密码资源丰富,灵活性好
    

    2、基于身份的公钥密码体制

    1、一个理想的基于身份的密码系统应满足以下特点

    用户只需知道通信双方的身份
    用户不用存储任何证书、公钥之类的列表
    PKG只是在系统的建立阶段提供服务,且用户绝对无条件信任该机构
    

    2、基于身份的密码体制与传统基于证书密码体制的区别
    相同

    1、都属于公开密钥体系
    2、用户的身份都需要认证
    3、公钥和私钥用于加密方案中,都是公钥用于加密,私钥用于解密;用于签名方案中,都是私钥用于签名,公钥用于验证签名
    4、体系的安全性都可以依赖大整数分解,离散对数,椭圆曲线离散对数等数学难题
    
    

    不同
    1、密钥生成过程不同
    2、用户身份信息的获取不同
    3、公钥获取方式不同
    4、公钥保存方式不同。

    习题

    1、简述公钥密码体制的一般定义
    其基本思想是把密钥分成两个部分:公开密钥和私有密钥。公钥密码体制中的公开密钥可被记录在一个公共数据库里或以某种可信的方式公开发放,而私有密钥必须由持有者妥善地秘密保存。
    2、什么是单向陷门函数?如何将其应用于公钥密码体制的设计
    所谓的陷门单向函数是一个可逆函数f(x) ,满足对于
    定义域中的任何 x,计算函数值y=f(x) 都是容易的;但对几乎所有的 x要由 y=f(x)求x在计算上不可行(即使已经知道函数 ),除非知道某些辅助信息(称为陷门信息)。
    在这里插入图片描述
    3、简述公钥密码体制相对单钥密码体制的优势
    1)具有非常高的安全性
    2)在实现消息加解密基本功能的同时简化了密钥分配任务
    3)对密码协商与密钥管理、数字签名与身份认证等密码学问题产生了深刻影响
    4、简述RAS算法的理论基础

    https://blog.csdn.net/u014044812/article/details/80782448?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160700092419195265197324%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=160700092419195265197324&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~rank_v28-1-80782448.pc_first_rank_v2_rank_v28&utm_term=RAS%E7%AE%97%E6%B3%95%E7%9A%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80
    

    5、在RSA体制中,为什么加密指数e必须与模数n的欧拉函数互素?
    如果不互素,无法计算解密钥d
    6、经典公钥密码体制主要建立在哪些数学难题基础之前?
    大整数分解问题------RSA算法
    有限域上的离散对数问题-----ElGmal算法
    椭圆曲线上的离散对数问题—椭圆曲线密码算法
    7、公钥密码体制的概念是在解决单钥密码体制中最难的两个问题时提出的,这两个问题是什么
    1)是由于常规的密钥密码体制的密钥分配问题,
    2)是由于对数字签名的需求。

    展开全文
  • 椭圆曲线密码算法(ECC)

    千次阅读 2019-11-06 18:25:30
    网上有很多关于ECC的文章,但是讲明白的很少,最近发现了一个大佬的博客,里面将ECC...比特币使用椭圆曲线算法生成公钥和私钥,选择的是secp256k1曲线。  椭圆曲线密码学(ECC)是(Elliptic Curve Cryptography)...

    网上有很多关于ECC的文章,但是讲明白的很少,最近发现了一个大佬的博客,里面将ECC的算法讲的比较透彻,我当作自己的笔记来看。其中会对于一些细小的错处做一些修改和添加一些自己的见解(大佬的博客地址和参考资料全部已经放在文章的末尾了)。

    比特币使用椭圆曲线算法生成公钥和私钥,选择的是secp256k1曲线。

      椭圆曲线密码学(ECC)是(Elliptic Curve Cryptography) 的缩写,该算法是基于椭圆曲线数学的一种公钥密码的算法其安全性依赖于椭圆曲线离散对数问题的困难性(这句话能唬人用)。

      在ECC流行起来之前,几乎所有的公钥算法都是基于RSA、DSA和DH ———— 基于模运算的可选加密系统。RSA及其友类算法在当前仍非常重要,经常与ECC一并使用。不过,RSA及其友类算法背后的原理很容易解释,因而被广泛理解,一些简单的实现也可以很容易编写出来;但ECC的实现基础对于大多数人来说仍很神秘。

           具体来说,我将触及以下主题:

      1. 数学上的椭圆曲线及相关概念

      2. 密码学中的椭圆曲线

      3. 椭圆曲线上的加密/解密

           4. 椭圆曲线签名与验证签名

    平行线,永不相交。没有人怀疑吧。不过到了近代这个结论遭到了质疑。平行线会不会在很远很远的地方相交了?事实上没有人见到过。所以“平行线,永不相交”只是假设(大家想想初中学习的平行公理,是没有证明的)。既然可以假设平行线永不相交,也可以假设平行线在很远很远的地方相交了。即平行线相交于无穷远点P∞(请大家闭上眼睛,想象一下那个无穷远点P∞,P∞是不是很虚幻,其实与其说数学锻炼人的抽象能力,还不如说是锻炼人的想象力)。给个图帮助理解一下:

                                                

    直线上出现P∞点,所带来的好处是所有的直线都相交了,且只有一个交点。这就把直线的平行与相交统一了。为与无穷远点相区别把原来平面上的点叫做平常点。

    以下是无穷远点的几个性质:

           ▲直线L上的无穷远点只能有一个。(从定义可直接得出)
      ▲平面上一组相互平行的直线有公共的无穷远点。(从定义可直接得出)
      ▲平面上任何相交的两直线L1,L2有不同的无穷远点。(否则L1L2有公共的无穷远点P ,则L1L2有两个交点AP,故假设错误。)
      ▲平面上全体无穷远点构成一条无穷远直线。(自己想象一下这条直线吧)
      ▲平面上全体无穷远点与全体平常点构成射影平面。

    二、射影平面坐标系

    射影平面坐标系是对普通平面直角坐标系(就是我们初中学到的那个笛卡儿平面直角坐标系)的扩展。我们知道普通平面直角坐标系没有为无穷远点设计坐标,不能表示无穷远点。为了表示无穷远点,产生了射影平面坐标系,当然射影平面坐标系同样能很好的表示旧有的平常点(数学也是“向下兼容”的)。下图为普通平面直角坐标系:

                                                              

     

     我们对普通平面直角坐标系上的点A的坐标(x,y)做如下改造:x=X/Z y=Y/ZZ0);则A点可以表示为(X:Y:Z)。
    变成了有三个参量的坐标点,这就对平面上的点建立了一个新的坐标体系。

    我们也可以得到直线的方程aX+bY+cZ=0(想想为什么?提示:普通平面直角坐标系下直线一般方程是ax+by+c=0)。

    新的坐标体系能够表示无穷远点么?那要让我们先想想无穷远点在哪里。根据上一节的知识,我们知道无穷远点是两条平行直线的交点。那么,如何求两条直线的交点坐标?

    这是初中的知识,就是将两条直线对应的方程联立求解。平行直线的方程是:

    aX+bY+c1Z =0;

    aX+bY+c2Z =0  (c1≠c2);
           我们知道平行线的斜率相同,把这个定理表现在普通直线方程上就是X和Y的系数a和b相等。

     将二方程联立,求解。

            有c2Z= c1Z= -(aX+bY),

             ∵c1≠c2 ∴Z=0  ∴aX+bY=0;
          所以无穷远点就是这种形式(X:Y:0)表示。

            注意,平常点Z≠0,因为平常点的坐标定义为(X/Z,Y/Z),除数不能为0.无穷远点Z=0,因此无穷远直线对应的方程是Z=0。

     

    例2.2:求平行线L1:X+2Y+3Z=0 与L2:X+2Y+Z=0 相交的无穷远点。
            解:因为L1∥L2 所以有Z=0, X+2Y=0;所以坐标为(-2Y:Y:0),Y≠0。即(-2:1:0)(-4:2:0)(-2.4:1.2:0)等形如(-2Y:Y:0),Y≠0的坐标,都表示这个无穷远点。

    看来这个新的坐标体系能够表示射影平面上所有的点,我们就把这个能够表示射影平面上所有点的坐标体系叫做射影平面坐标系。

    三、椭圆曲线

    上一节,我们建立了射影平面坐标系,这一节我们将在这个坐标系下建立椭圆曲线方程。因为我们知道,坐标中的曲线是可以用方程来表示的(比如:单位圆方程是x2+y2=1)。椭圆曲线是曲线,自然椭圆曲线也有方程。

    椭圆曲线的定义:
      一条椭圆曲线是在射影平面上满足方程

    Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3   ----------------[3-1]的所有点的集合,且曲线上的每个点都是非奇异(或光滑)的。

    定义详解:

      ▲ Y2Z+a1XYZ+a3YZ2 = X3+a2X2Z+a4XZ2+a6Z3是Weierstrass方程(维尔斯特拉斯,Karl Theodor Wilhelm Weierstrass,1815-1897),是一个齐次方程。

      ▲ 椭圆曲线的形状,并不是椭圆的。只是因为椭圆曲线的描述方程,类似于计算一个椭圆周长的方程(计算椭圆周长的方程,我没有见过,而对椭圆线积分(设密度为1)是求不出来的。谁知道这个方程,请告诉我呀^_^),故得名。

            我们来看看椭圆曲线是什么样的。

                                                                    

     

    ▲ 所谓“非奇异”或“光滑”的,在数学中是指曲线上任意一点的偏导数Fx(x,y,z),Fy(x,y,z),Fz(x,y,z)不能同时为0。如果你没有学过高等数学,可以这样理解这个词,即满足方程的任意一点都存在切线。

      下面两个方程都不是椭圆曲线,尽管他们是方程[3-1]的形式。

    知道了椭圆曲线上的无穷远点。我们就可以把椭圆曲线放到普通平面直角坐标系上了。因为普通平面直角坐标系只比射影平面坐标系少无穷远点。我们在普通平面直角坐标系上,求出椭圆曲线上所有平常点组成的曲线方程,再加上无穷远点O∞(0:1:0),不就构成椭圆曲线了么?

      我们设x=X/Z ,y=Y/Z代入方程[3-1]得到:
      y2+a1xy+a3y = x3+a2x2+a4x+a6 -------------------------[3-2]

      也就是说满足方程[3-2]的光滑曲线加上一个无穷远点O∞,组成了椭圆曲线。为了方便运算,表述,以及理解,今后论述椭圆曲线将主要使用[3-2]的形式。

      本节的最后,我们谈一下求椭圆曲线一点的切线斜率问题。
      由椭圆曲线的定义可以知道,椭圆曲线是光滑的,所以椭圆曲线上的平常点都有切线。而切线最重要的一个参数就是斜率k。

         

     

    四、椭圆曲线上的加法

      上一节,我们已经看到了椭圆曲线的图象,但点与点之间好象没有什么联系。我们能不能建立一个类似于在实数轴上加法的运算法则呢?天才的数学家找到了这一运算法则

      自从近世纪代数学引入了群、环、域的概念,使得代数运算达到了高度的统一。比如数学家总结了普通加法的主要特征,提出了加群(也叫交换群,或Abel(阿贝尔)群),在加群的眼中。实数的加法和椭圆曲线的上的加法没有什么区别。这也许就是数学抽象把:)。关于群以及加群的具体概念请参考近世代数方面的数学书。

      运算法则:任意取椭圆曲线上两点P、Q (若P、Q两点重合,则做P点的切线)做直线交于椭圆曲线的另一点R’,过R’做y轴的平行线交于R。我们规定P+Q=R。(如图)

                                               

     

    法则详解:
      ▲这里的+不是实数中普通的加法,而是从普通加法中抽象出来的加法,他具备普通加法的一些性质,但具体的运算法则显然与普通加法不同。

    ▲根据这个法则,可以知道椭圆曲线无穷远点O∞与椭圆曲线上一点P的连线交于P’,过P’作y轴的平行线交于P,所以有 无穷远点 O∞+ P = P 。这样,无穷远点 O∞的作用与普通加法中零的作用相当(0+2=2),我们把无穷远点 O∞ 称为 零元。同时我们把P’称为P的负元(简称,负P;记作,-P)。(参见下图)

                                                               

     

    ▲根据这个法则,可以得到如下结论 :如果椭圆曲线上的三个点ABC,处于同一条直线上,那么他们的和等于零元,即A+B+C= O

    ▲k个相同的点P相加,我们记作kP。如下图:P+P+P = 2P+P = 3P。

                                                    

    下面,我们利用P、Q点的坐标(x1,y1),(x2,y2),求出R=P+Q的坐标(x4,y4)。

    解:1)先求点-R(x3,y3)因为P,Q,-R三点共线,故设共线方程为y=kx+b,其中
                 若P≠Q(P,Q两点不重合) 直线斜率k=(y1-y2)/(x1-x2)
               若P=Q(P,Q两点重合) 则直线为椭圆曲线的切线,故由例3.1可知:

        因此P,Q,-R三点的坐标值就是方程组:

               -----------------[1] 

            y=(kx+b)                                            -----------------[2]

       的解。

     将[2]代入[1] 有:

         --------[3]
                [3]化为一般方程,根据三次方程根与系数关系(当三次项系数为1时; 等于常数项系数,等于一次项系数,等于二次项系数。)所以

     (2)利用-RR

       

          化为一般方程

         根据二次方程根与系数关系得:

    ---------------求出点R的纵坐标

      即:


                 本节的最后,提醒大家注意一点,以前提供的图像可能会给大家产生一种错觉,即椭圆曲线是关于x轴对称的。事实上,椭圆曲线并不一定关于x轴对称。如下图的


                                                         
                     

    五、密码学中的椭圆曲线

      我们现在基本上对椭圆曲线有了初步的认识,这是值得高兴的。但请大家注意,前面学到的椭圆曲线是连续的,并不适合用于加密;所以,我们必须把椭圆曲线变成离散的点。

      让我们想一想,为什么椭圆曲线为什么连续?是因为椭圆曲线上点的坐标,是实数的(也就是说前面讲到的椭圆曲线是定义在实数域上的),实数是连续的,导致了曲线的连续。因此,我们要把椭圆曲线定义在有限域上(顾名思义,有限域是一种只有由有限个元素组成的域)。

      域的概念是从我们的有理数,实数的运算中抽象出来的,严格的定义请参考近世代数方面的数。简单的说,域中的元素同有理数一样,有自己得加法、乘法、除法、单位元(1),零元(0),并满足交换率、分配率。

      下面,我们给出一个有限域Fp,这个域只有有限个元素。

    Fp中只有p(p为素数)个元素0,1,2 …… p-2,p-1;
      Fp 的加法(a+b)法则是 a+b≡c (mod p);即,(a+b)÷p的余数 和c÷p的余数相同。
      Fp 的乘法(a×b)法则是  a×b≡c (mod p);
      Fp 的除法(a÷b)法则是  a/b≡c (mod p);即 a×b-1≡c  (mod p);(b-1也是一个0到p-1之间的整数,但满足b×b-1≡1 (mod p) )。
      Fp 的单位元是1,零元是 0。

           同时,并不是所有的椭圆曲线都适合加密。y2=x3+ax+b是一类可以用来加密的椭圆曲线,也是最为简单的一类。下面我们就把y2=x3+ax+b 这条曲线定义在Fp上:

      选择两个满足下列条件的小于p(p为素数)的非负整数a、b
      4a3+27b2≠0 (mod p)
      则满足下列方程的所有点(x,y),再加上 无穷远点O∞ ,构成一条椭圆曲线。
      y2=x3+ax+b  (mod p)
      其中 x,y属于0到p-1间的整数,并将这条椭圆曲线记为Ep(a,b)。

         我们看一下y2=x3+x+1  (mod 23)的图像

    https://bbtcdn.8btc.com/data/attachment/portal/201310/01/014125z8timdmfvsu33o69.gif

    是不是觉得不可思议?椭圆曲线,怎么变成了这般模样,成了一个一个离散的点?
      椭圆曲线在不同的数域中会呈现出不同的样子,但其本质仍是一条椭圆曲线。举一个不太恰当的例子,好比是水,在常温下,是液体;到了零下,水就变成冰,成了固体;而温度上升到一百度,水又变成了水蒸气。但其本质仍是H2O

    例题椭圆曲线已知E23(1,1)上两点P(3,10)Q(9,7),求(1)-P(2)P+Q(3) 2P

    https://images2017.cnblogs.com/blog/1180694/201708/1180694-20170818232047256-215454597.png

    最后,我们讲一下椭圆曲线上点的阶。

      如果椭圆曲线上一点P,存在最小的正整数n,使得数乘nP=O∞,则将n称为P 阶,若n不存在,我们说P是无限阶的。
      事实上,在有限域上定义的椭圆曲线上所有的点的阶n都是存在

    https://images2018.cnblogs.com/blog/762938/201806/762938-20180607222648517-1849608117.png

    计算可得27P=-P=(3,13)

      所以28P=O ∞ P的阶为28

      这些点做成了一个循环阿贝尔群,其中生成元为P,阶数为29。显然点的分布与顺序都是杂乱无章

    三、椭圆曲线上的加密/解密

      公开密钥算法总是要基于一个数学上的难题。比如RSA 依据的是:给定两个素数pq 很容易相乘得到n,而对n进行因式分解却相对困难。那椭圆曲线上有什么难题呢?

      考虑如下等式:
      K=kG  [其中 K,GEp(a,b)上的点,k为小于nn是点G的阶)的整数]
      不难发现,给定kG,根据加法法则,计算K很容易;但给定KG,求k就相对困难了。
      这就是椭圆曲线加密算法采用的难题。

      我们把点G称为基点(base point),

      kk<nn为基点g的阶)称为私有密钥(privte key),

      k称为公开密钥(public="" key)<="" p="">

      现在我们描述一个利用椭圆曲线进行加密通信的过程:

      1、用户A选定一条椭圆曲线Ep(a,b),并取椭圆曲线上一点,作为基点G
      2、用户A选择一个私有密钥k,并生成公开密钥K=kG
      3、用户AEp(a,b)和点KG传给用户B
      4、用户B接到信息后 ,将待传输的明文编码到Ep(a,b)上一点M(编码方法很多,这里不作讨论),并产生一个随机整数rr<n)。
      5、用户B计算点C1=M+rKC2=rG
      6、用户BC1C2传给用户A
      7、用户A接到信息后,计算C1-kC2,结果就是点M

      因为C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M再对点M进行解码就可以得到明文。

      在这个加密通信中,如果有一个偷窥者H ,他只能看到Ep(a,b)KGC1C2 而通过KG k 或通过C2Gr 都是相对困难的。因此,H无法得到AB间传送的明文信息。

    设私钥、公钥分别为k、K,即K = kG,其中G为G点。
     
    公钥加密:
    选择随机数r,将消息M生成密文C,该密文是一个点对,即:
    C = {rG, M+rK},其中K为公钥
     
    私钥解密:
    M + rK - k(rG) = M + r(kG) - k(rG) = M
    其中k、K分别为私钥、公钥。

      ECC技术要求:

      密码学中,描述一条Fp上的椭圆曲线,常用到六个参量:
           T=(p,a,b,G,n,h)
      (p a b 用来确定一条椭圆曲线,G为基点,n为点G的阶,h 是椭圆曲线上所有点的个数mn相除的整数部分)

      这几个参量取值的选择,直接影响了加密的安全性。参量值一般要求满足以下几个条件:

      1p 当然越大越安全,但越大,计算速度会变慢,200位左右可以满足一般安全要求;
      2p≠n×h
      3pt≠1 (mod n)1≤t<20
      44a3+27b2≠0 (mod p)
      5n 为素数;
      6h≤4。
     

    四、椭圆曲线签名与验证签名

       椭圆曲线签名算法,即ECDSA
      设私钥、公钥分别为kK,即K = kG,其中GG点。
      私钥签名:
      1、选择随机数r,计算点rG(x, y)
      2、根据随机数r、消息M的哈希h、私钥k,计算s = (h + kx)/r
      3、将消息M、和签名{rG, s}发给接收方。
      公钥验证签名:
      1、接收方收到消息M、以及签名{rG=(x,y), s}
      2、根据消息求哈希h
      3、使用发送方公钥K计算:hG/s + xK/s,并与rG比较,如相等即验签成功。
      原理如下:
      hG/s + xK/s = hG/s + x(kG)/s = (h+xk)G/s
      = r(h+xk)G / (h+kx) = rG

    参考:
            https://www.cnblogs.com/X-knight/p/9153209.html

            https://www.chainnode.com/tutorial/138

           张禾瑞,《近世代数基础》,高等教育出版社,1978 

           闵嗣鹤 严士健,《初等数论》,高等教育出版社,1982

           https://www.cnblogs.com/Kalafinaian/p/7392505.html



     

     

    展开全文
  • 事实证明,打破228位长的椭圆曲线键将需要与煮沸地球上所有水所需的能量相同的能量。 但是,仅在考虑已知算法和硬件的情况下它才有效,因为严格来说,没有人知道是否存在效率更高的算法或硬件。 228位EC密钥可与...

    tls 1.2加密

    image

    A couple of reader alerts:

    读者警告:

    In order to (somewhat) simplify the description process and tighten the volume of the article we are going to write, it is essential to make a significant remark and state the primary constraint right away — everything we are going to tell you today on the practical side of the problematics is viable only in terms of TLS 1.3. Meaning that while your ECDSA certificate would still work in TLS 1.2 if you wish it worked, providing backwards compatibility, the description of the actual handshake process, cipher suits and client-server benchmarks covers TLS 1.3 only. Of course, this does not relate to the mathematical description of algorithms behind modern encryption systems.

    为了(某种程度上)简化描述过程并收紧我们将要写的文章的数量,有必要做一个重要的评论并立即指出主要的限制,我们今天将在实用上告诉您的一切问题的一面仅在TLS 1.3方面才可行。 这意味着,尽管您希望ECDSA证书能够工作,但仍可以在TLS 1.2中使用,但可以提供向后兼容性,但实际握手过程,密码套件和客户端-服务器基准的描述仅涵盖TLS 1.3。 当然,这与现代加密系统背后的算法的数学描述无关。

    This article was written by neither a mathematician nor an engineer — although those helped to find a way around scary math and reviewed this article. Many thanks to Qrator Labs employees.

    这篇文章既不是由数学家也不是由工程师撰写的,尽管他们帮助找到了解决可怕数学问题的方法,并回顾了这篇文章。 非常感谢Qrator Labs的员工。

    (

    Ë

    ((

    E

    )

    lliptic

    卵状的

    C (C)

    urve)

    urve)

    d (D)

    iffie-

    菲菲

    H (H)

    ellman (

    埃尔曼(

    Ë (E)

    phemeral)

    暂时的)

    Diffie-Hellman在21世纪的遗产 (The Diffie–Hellman legacy in the 21 century)

    Of course, this has started with neither Diffie nor Hellman. But to provide a correct timeline, we need to point out main dates and events.

    当然,这不是从Diffie还是Hellman开始的。 但是,为了提供正确的时间表,我们需要指出主要日期和事件。

    There were several major personas in the development of modern cryptography. Most notably, Alan Turing and Claud Shannon both laid an incredible amount of work over the field of theory of computation and information theory as well as general cryptanalysis, and both Diffie and Hellman, are officially credited for coming up with the idea of public-key (or so-called asymmetric) cryptography (although it is known that in the UK there were made serious advances in cryptography that stayed under secrecy for a very long time), making those two gentlemen pioneers.

    现代密码学的发展有几个主要角色。 最值得注意的是,艾伦·图灵(Alan Turing)和克劳德·香农(Claud Shannon)都在计算和信息论以及通用密码分析领域进行了令人难以置信的大量工作,并且Diffie和Hellman都因提出了公共密钥的想法而被正式认可。 (或所谓的非对称)加密技术(尽管众所周知,在英国,加密技术已经取得了长足的发展,并且长期处于保密状态),这使这两位先生成为了先驱。

    In what exactly?

    到底是什么?

    Well, this may sound peculiar; however, before November 6, 1976, there was no public knowledge of public-key encryption systems. Whitfield Diffie and Martin Hellman (and, by the matter of fact, Ralph Merkle) — mathematicians, computer engineers and enthusiasts, as well as cryptologists were the first.

    好吧,这听起来很奇怪。 但是,在1976年11月6日之前,还没有公众对公用密钥加密系统的了解。 惠特菲尔德·迪菲(Whitfield Diffie)和马丁·海尔曼(Martin Hellman)(实际上是拉尔夫·默克尔(Ralph Merkle))—数学家,计算机工程师和发烧友以及密码学家是第一批。

    For those not aware — due to the role cryptanalysis overtook during the World War II and its enormous impact on keeping information in secret, the two countries that believed they had most advanced cryptography knowledge — the U.S. and U.K. included encryption into their Munitions Lists and leveraged a heavy export ban (simultaneously weakening encryption implementation for domestic private and commercial use). For this reason, the U.K. researchers working at the asymmetric key exchange technique in Government Communications Headquarters and developing an analogous scheme weren’t recognized for this invention until 1997, when restrictions on cryptography algorithms and their description were rendered ineffective.

    对于那些不知道的人-由于二战期间密码分析已超越角色,并且对保密信息具有巨大影响,因此两个国家认为他们拥有最先进的密码学知识-美国和英国将加密纳入了弹药清单并加以利用严格的出口禁令(同时削弱了针对家庭私人和商业用途的加密实施)。 由于这个原因,直到1997年英国政府研究人员在政府通信总部的非对称密钥交换技术上工作并开发类似方案的英国研究人员才意识到这项发明,当时对密码算法的限制及其描述无效。

    Back to our dual inventors — what has Diffie and Hellman revolutionized specifically?

    回到我们的双重发明家-Diffie和Hellman特别革新了什么?

    Let’s take a look at their original paper, perfectly illustrating the giant leap they’ve introduced (even theoretically with their research paper):

    让我们看一下他们的原始论文,完美地说明了他们所引入的巨大飞跃(甚至在理论上与他们的研究论文一起):

    image

    And the following one:

    和以下之一:

    image

    These two pictures perfectly illustrate the huge change Whitfield Diffie and Martin Hellman introduced after cryptography and cryptanalysis centuries of evolution — the establishment of a shared secret key as a result of a cryptographic computation.

    这两张照片完美地说明了在加密和密码分析百年演变之后,Whitfield Diffie和Martin Hellman所进行的巨大变化-加密计算的结果是建立了共享的秘密密钥。

    Let’s take a look at another good picture with colors:

    让我们看一下另一种颜色不错的图片:

    image

    It explains what is going on. Before Diffie and Hellman key agreement invention, there was only one symmetric key — it was used both to encrypt and decrypt the message. If you want to give someone such a “key”, it must be transferred over a “secure” channel. You can imagine all the restrictions of such a previous generation scheme right away — you need an already established secure channel, you cannot reuse the key, and, ideally, the length of the key should be the same as the length of the message.

    它解释了发生了什么。 在Diffie和Hellman密钥协商发明之前,只有一个对称密钥-它既用于加密也用于解密消息。 如果要给某人这样的“密钥”,则必须通过“安全”通道进行转移。 您可以立即想象出这种上一代方案的所有限制-您需要一个已经建立的安全通道, 不能重用密钥 ,并且理想情况下,密钥的长度应与消息的长度相同。

    Claude Shannon in his wartime classified work “Communication Theory of Secrecy Systems” proved that all theoretically unbreakable ciphers must have the same requirements as the one-time pad — famously known as the Vernam cipher, by the author of this symmetrical polyalphabetic stream cipher.

    克劳德·香农(Claude Shannon)在其战时分类的著作“ 保密系统的传播理论 ”中证明,所有理论上均不可破解的密码必须具有与一次性密码垫相同的要求,该密码垫由对称多字母流密码的作者而著称,即一次Vernam密码。

    Again, we’re going to take a look at the original paper:

    再次,我们将看一下原始论文:

    image

    Before we go any further, let’s ask ourselves — how two, even if brilliant, however, human beings came up with such a significant improvement in an applied field with such a history, especially at the time of war?

    在进一步探讨之前,让我们问问自己:两个人,即使是杰出的人,在具有如此悠久历史的应用领域,特别是在战争时期,都取得了如此显着的进步?

    Well, because of the:

    好吧,因为:

    • Information theory, formulated by Claude Shannon;

      信息理论 ,由克劳德·香农(Claude Shannon)提出;

    • Theory of computation influenced by, most notably, Alonzo Church, John von Neumann, and Alan Turing;

      计算理论最受Alonzo Church,John von Neumann和Alan Turing的影响;

    • And, more importantly, computability theory based mostly on Turing’s work, which we could say all developed and matured at the same period of the 20th century. Diffie and Hellman both mentioned Claude Shannon as the most significant influencer of their work.

      而且,更重要的是, 可计算性理论主要基于图灵的工作,我们可以说所有这些理论都是在20世纪同一时期发展和成熟的。 Diffie和Hellman都提到克劳德·香农(Claude Shannon)是他们工作中最重要的影响者。

    Lenstra’s “Universal Security” illustrates the quantity of energy needed to “break” the symmetric cryptosystem with various key lengths. It turned out that breaking a 228-bit long, elliptic curve key would require the same amount of energy that is needed to boil all the water on Earth. It is, however, valid only under consideration of known algorithms and hardware, as, strictly speaking, no one knows if significantly more efficient algorithms or hardware exist. 228-bit EC key is comparable to the 2380-bit long RSA key, more on that later. Although in this estimation both RSA and EC keys are used in an asymmetric encryption scheme, such key lengths are somewhat equivalent to a 128-bit symmetric encryption key.

    Lenstra的“ 通用安全性 ”说明了“破坏”具有各种密钥长度的对称密码系统所需的能量。 事实证明,打破228位长的椭圆曲线键将需要与煮沸地球上所有水所需的能量相同的能量。 但是,仅在考虑已知算法和硬件的情况下它才有效,因为严格来说,没有人知道是否存在效率更高的算法或硬件。 228位EC密钥可与2380位长的RSA密钥相提并论。 尽管在此估计中,RSA和EC密钥都用于非对称加密方案中,但是这种密钥长度在某种程度上等效于128位对称加密密钥。

    It is easy to imagine that something “hard to calculate” would require much energy and/or time needed for the computation. We tend to think that computers can “calculate everything”, but it turns out that it is not true. First, there exist undecidable examples, like the halting problem, though in the field of cryptography, we can avoid this pitfall. Second, if we consider the time needed for a particular algorithm to run, it may be arbitrary high. That is what we exploit in cryptography. A problem is considered “easy” to calculate if the time required to run the respective algorithm depends on the input size (measured in bits) like a polynomial: $inline$T(n) = O(n^k)$inline$ , for some positive constant $inline$k$inline$ . In the computational complexity theory field, such problems form the P complexity class.

    不难想象,“难以计算”的内容将需要大量的能量和/或时间来进行计算。 我们倾向于认为计算机可以“计算一切”,但事实证明事实并非如此。 首先,存在一些不确定的例子,例如停止问题,尽管在密码学领域,我们可以避免这种陷阱。 其次,如果我们考虑运行特定算法所需的时间,则它可能是任意高的。 这就是我们在密码学中所利用的。 计算运行相应算法所需的时间是否像多项式一样取决于输入大小(以位为单位),是一个“容易”计算的问题: $ inline $ T(n)= O(n ^ k)$ inline $ ,对于一些正常数 $ inline $ k $ inline $ 。 在计算复杂度理论领域,此类问题形成了P复杂度类

    The P complexity class is almost central, as it represents the problem for which a deterministic polynomial time algorithm exists. Another complexity class is the NP (the problems that are “hard” to calculate), representing a set of decision problems, i.e., problems requiring “yes” or “no” answer, that have a proof verifiable in polynomial time. You see the word “proof” here? That is where we get to the trapdoor functions, belonging to the NP complexity class.

    P复杂度类别几乎是核心问题,因为它表示存在确定性多项式时间算法的问题。 另一个复杂度类别是NP (难于计算的问题),代表一组决策问题,即需要“是”或“否”答案的问题,并且可以在多项式时间内验证。 您在这里看到“证明”一词吗? 那就是我们进入陷门函数的地方,该函数属于NP复杂度类。

    image

    Credits: xkcd

    积分: xkcd

    单向功能; 活板门功能 (One-way functions; Trapdoor functions)

    By definition, a one-way function is such a function that is easy to compute on every input but is hard to reverse, i.e. compute original input given output only. “Easy” and “hard” refer to the computational complexity theory definitions above. Interestingly, that one-way functions existence is not (mathematically) proved because their existence would prove that the P and NP complexity classes are not equal, while either P equal NP or not is nowadays an open problem. So, keep in mind that all modern cryptography relies on unproven hypotheses.

    根据定义,单向函数就是这样一种函数,它易于在每个输入上进行计算,但难以逆转,即仅计算给定输出的原始输入。 “简单”和“困难”是指上面的计算复杂性理论定义。 有趣的是,单向函数的存在没有(从数学上)得到证明,因为它们的存在将证明P和NP复杂度类不相等,而如今P等于NP或不等于NP是一个开放的问题。 因此,请记住,所有现代加密技术都依赖未经证实的假设。

    Now, in their original paper Diffie and Hellman introduce another generation of the one-way functions they called “trapdoor functions”. How do they differ?

    现在,Diffie和Hellman在他们的原始论文中介绍了另一种称为“活板门功能”的单向功能。 它们有何不同?

    As they explain in their landmark paper:

    正如他们在具有里程碑意义的论文中解释的那样:

    $inline$10^{100}$inline$ instructions). The enciphering key E can be disclosed [in a directory] without compromising the deciphering key D. This enables any user of the system to send a message to any other user enciphered in such a way that only the intended recipient is able to decipher it ...The problem of authentication is perhaps an even more serious barrier to the universal adoption of telecommunications for business transactions than the problems of key distribution…[it]…is at the heart of any system involving contracts and billing. $ inline $ 10 ^ {100} $ inline $ 说明)。 可以在不破坏解密密钥D的情况下[在目录中]公开加密密钥E。这使得系统的任何用户都可以将消息发送给任何已加密的其他用户,使得只有目标接收者才能解密该消息。 ..与密钥分发问题相比,认证问题可能是对电信普遍采用电信进行更为严重的障碍……[它]……是涉及合同和计费的任何系统的核心。
    $inline$n$inline$ and $ inline $ n $ inline $ 和 $inline$g$inline$ with $ inline $ g $ inline $ 与 $inline$1< g< n$inline$ . The selection impacts the security of the system. “The modulus $ inline $ 1 <g <n $ inline $ 。 选择会影响系统的安全性。 “模数 $inline$n$inline$ should be a prime; more importantly $ inline $ n $ inline $ 应该是素数 更重要的是 $inline$(n-1)/2$inline$ should also be a prime <…> and $ inline $(n-1)/ 2 $ inline $ 还应该是素数<...>,并且 $inline$g$inline$ should be a primitive root modulo $ inline $ g $ inline $ 应该是原始的根模 $inline$n$inline$ <…> [and] $ inline $ n $ inline $ <…> [和] $inline$n$inline$ should be <…> at least 512 bits long.” The Diffie–Hellman protocol can be stated in elemental form in 5 steps. $ inline $ n $ inline $ 至少应为<…> 512位。” Diffie-Hellman协议可以用5个步骤以元素形式表示。
    1. Alice chooses $inline$x$inline$ (a large random integer) and computes $inline$X=g^x \bmod n$inline$

      爱丽丝选择 $ inline $ x $ inline $ (一个大的随机整数)并计算 $ inline $ X = g ^ x \ bmod n $ inline $

    2. Bob chooses $inline$y$inline$ (a large random integer) and computes $inline$Y=g^y \bmod n$inline$

      鲍勃选择 $ inline $ y $ inline $ (一个大的随机整数)并计算 $ inline $ Y = g ^ y \ bmod n $ inline $

    3. Alice sends $inline$X$inline$ to Bob, while Bob sends $inline$Y$inline$ to Alice (they keep $inline$x$inline$ and $inline$y$inline$ secret from each other)

      爱丽丝发送 $ inline $ X $ inline $ 给Bob,而Bob发送 $ inline $ Y $ inline $ 给爱丽丝(他们保留 $ inline $ x $ inline $ 和 $ inline $ y $ inline $ 彼此的秘密)

    4. Alice computes $inline$k = Y^x \bmod n$inline$

      爱丽丝计算 $ inline $ k = Y ^ x \ bmod n $ inline $

    5. Bob computes $inline$k' = X^y \bmod n$inline$

      鲍勃计算 $ inline $ k'= X ^ y \ bmod n $ inline $

    As a result Alice and Bob have the same value $inline$k=k'$inline$ that serves as a shared secret.

    结果,爱丽丝和鲍勃的价值相同 $ inline $ k = k'$ inline $ 作为一个共享的秘密。

    Trapdoor function is a one-way function that makes it possible to find its inverse if one has a piece of special information called the “trapdoor”. Sounds easy, though it was rather hard to find such functions — the first feasible method was found in the implementation of a public-key cryptography asymmetric encryption algorithm named RSA after its creators: Ron Rivest, Adi Shamir and Leonard Adleman.

    活板门功能是一种单向功能,如果有一条称为“活板门”的特殊信息,则可以查找其倒数。 听起来很容易,尽管很难找到这样的功能-第一种可行的方法是在实现了以其创建者Ron Rivest,Adi Shamir和Leonard Adleman命名的RSA公用密钥密码非对称加密算法的过程中找到的。

    RSA (RSA)

    In RSA the hardness of inverting the function is based on the fact that factoring (finding prime multipliers of a number) takes much more time than multiplication, or should we say here that no polynomial-time method for factoring large integers on a classical computer has been found, however, it has not been proven that none exists.

    在RSA中,函数求逆的难点是基于以下事实:因式分解(查找一个数的质数乘方)比乘积要花费更多的时间,或者在这里我们应该说,在经典计算机上没有用于分解大整数的多项式时间方法具有但是,尚未证明不存在。

    In RSA, like in any other public-key encryption system, there are two keys: public and private. RSA takes the input message (represented as a bit string) and applies a mathematical operation (exponentiation modulo a big integer) to it to get a result looking indistinguishable from random. Decryption takes this result and applies a similar operation to get back the original message. In asymmetric cryptography, the encryption is made with the public key and decryption with the private one.

    与其他任何公共密钥加密系统一样,在RSA中,有两个密钥:公共和私有。 RSA接受输入消息(表示为位字符串),然后对其应用数学运算(对大整数取模的幂),以得到与随机变量难以区分的结果。 解密将获得此结果,并应用类似的操作以取回原始消息。 在非对称密码学中,加密是用公钥进行的,而解密是用私钥进行的。

    How? Because the operands belong to a finite cyclic group (a set of integers with multiplication in modular arithmetic). Сomputers don’t deal great with arbitrarily big numbers, but, luckily, our cyclic group of integers is to perform an operation called “wrap around” — a number larger than the maximum allowed is wrapped around to a number in the valid range we operate. This allows us to operate with keys of “no longer than” length. In elliptic curve cryptography cyclic (multiplicative) groups are used too but constructed a bit differently as we will see later.

    怎么样? 因为操作数属于有限循环组(在模块化算术中一组带有乘法的整数)。 Сomputers不能很好地处理任意大数字,但是,幸运的是,我们的整数循环组执行的操作称为“环绕”-大于允许的最大值的数字会被包裹为一个有效范围内的数字。 这使我们可以使用“不超过”长度的键进行操作。 在椭圆曲线密码学中,也使用循环(乘法)组,但其构造稍有不同,我们将在后面看到。

    Basically what RSA does is taking two large prime numbers and multiplying them to get the so-called modulus. All the other numbers to be dealt with reside between zero and the modulus. The modulus is to be a part of the public key, and its bit length determines the key length. The second part of the public key is a number chosen between zero and the Euler’s totient (modern RSA implementation takes the Carmichael’s totient instead of Euler’s) of the modulus with some additional restrictions. Finally, the private key is to be calculated by solving some modular equation. To encrypt a number we simply raise it to the power equal to the public key, and to decrypt a number back, we raise it to the power equal to the private key. Thanks to the cyclic nature of the group, we get back the initial number.

    基本上,RSA的工作是取两个大质数并将它们相乘以获得所谓的模数。 所有其他要处理的数字都位于零和模数之间。 模数将成为公共密钥的一部分,并且其位长决定密钥长度。 公用密钥的第二部分是在零和Euler的模数(现代RSA实现采用Carmichael的模数而不是Euler的模数)之间选择的数字,并带有一些其他限制。 最后,通过解决一些模块化方程来计算私钥。 要加密数字,我们只需将其提高到等于公钥的幂,然后解密一个数字,就将它提高到等于私钥的幂。 由于该组具有周期性,因此我们可以获取初始编号。

    There are two significant problems with the RSA nowadays, one being a consequence of the other. As the length of a key (i.e., the number of its bits) grows, the complexity factor grows not so fast as one may expect. That is because there exists sub-exponential (but still super-polynomial) factorisation algorithm. So, in order to keep an appropriate security level, the length of the RSA key needs to grow somewhat faster than the ECC key length. That is why most widespread RSA keys nowadays are either 2048 or 3072 bit long.

    如今,RSA存在两个重大问题,一个是另一个问题的结果。 随着密钥的长度(即其位数)的增加,复杂度因子的增长并不像人们期望的那样快。 那是因为存在次指数(但仍然是超多项式 )分解算法 。 因此,为了保持适当的安全级别,RSA密钥的长度需要比ECC密钥的长度更快地增长。 这就是为什么当今最广泛使用的RSA密钥的长度为2048或3072位。

    A bit later, we will see in numbers how the length of the key affects overall cryptosystem efficiency by comparing the RSA and ECDSA certificate signed with Let’s Encrypt authority.

    稍后,我们将通过比较用Let's Encrypt授权签名的RSA和ECDSA证书,从数字上看到密钥的长度如何影响整体密码系统的效率。

    (

    Ë

    ((

    E

    )

    lliptic

    卵状的

    C (C)

    urve)

    urve)

    d (D)

    igital

    原始的

    小号 (S)

    ignature

    点燃

    一个 (A)

    lgorithm

    算法

    The search for a better trapdoor function eventually led cryptographers to an actively evolving in the mid-80s branch of mathematics dedicated to elliptic curves.

    寻找更好的活板门功能最终导致密码学家积极地发展到80年代中期的椭圆曲线专用数学分支。

    It would be the ultimate task to describe elliptic curve cryptography in one article, so we shall not. Instead, let's take a look at an elliptic curve trapdoor function based on the discrete logarithm problem.

    在一篇文章中描述椭圆曲线密码学将是最终的任务,因此我们不会。 相反,让我们看一下基于离散对数问题的椭圆曲线陷门函数。

    There are many primers and more in-depth introductions into elliptic curve cryptography, and we would especially recommend Andrea Corbellini’s “ECC: a gentle introduction” if you are interested in math.

    椭圆曲线密码学有许多入门和更深入的介绍,如果您对数学感兴趣,我们特别推荐Andrea Corbellini的“ ECC:温和介绍”

    What we are interested in are rather “simple” parameters.

    我们感兴趣的是相当“简单”的参数。

    The elliptic curve is defined by an equation like this: $inline$y^2 = x^3 + ax + b$inline$

    椭圆曲线由以下等式定义: $ inline $ y ^ 2 = x ^ 3 + ax + b $ inline $

    Such a curve is needed to construct a cyclic subgroup over a finite field. Therefore, the following parameters are being used:

    需要这样的曲线才能在有限域上构造循环子组。 因此,正在使用以下参数:

    • The

      主要 $ inline $ p $ inline $ (prime $inline$p$inline$ )

      that specifies the size of the finite field;

      指定有限域的大小;

    • The

      系数 $ inline $ a $ inline $ 和 $ inline $ b $ inline $ (coefficients $inline$a$inline$ and $inline$b$inline$ )

      of the elliptic curve equation;

      椭圆曲线方程

    • The

      基点 $ inline $ G $ inline $ (base point $inline$G$inline$ )

      that generates the mentioned subgroup;

      产生提到的子组;

    • The

      订购 $ inline $ n $ inline $ (order $inline$n$inline$ )

      of the subgroup;

      分组中的

    • The

      辅因子 $ inline $ h $ inline $ (cofactor $inline$h$inline$ )

      of the subgroup.

      子组中的

    In conclusion, the

    总之,

    域参数 (domain parameters)

    for our algorithms is the

    因为我们的算法是

    六胞胎 (sextuplet)

    $inline$(p, a, b, G, n, h)$inline$ . $ inline $(p,a,b,G,n,h)$在线 。

    Such elliptic curves work over the finite field $inline$\mathbb{F}_p$inline$ , where $inline$p$inline$ is a rather large prime number. So we have a set of integers modulo $inline$p$inline$ , where operations, such as addition, subtraction, multiplication, additive inverse, multiplicative inverse are possible. Addition and multiplication work similarly to the modular or so-called “clock” arithmetic we saw in the RSA “wrap arounds”.

    这样的椭圆曲线在有限域上起作用 $ inline $ \ mathbb {F} _p $ inline $ ,在哪里 $ inline $ p $ inline $ 是一个相当大的素数。 所以我们有一组整数取模 $ inline $ p $ inline $ ,其中可以执行加法,减法,乘法,加法逆运算,乘法逆运算等运算。 加法和乘法的工作方式类似于我们在RSA“环绕式”中看到的模块化或所谓的“时钟”算法。

    Since the curve is symmetrical about the x-axis, given any point $inline$P$inline$ , we can take $inline$−P$inline$ to be the point opposite it. We take $inline$−O$inline$ to be just $inline$O$inline$ .

    由于曲线是关于x轴对称的,因此给定任何点 $ inline $ P $ inline $ ,我们可以 $ inline $ -P $ inline $ 正好相反。 我们采取 $ inline $ -O $ inline $ 只是 $ inline $ O $ inline $ 。

    Addition for curve points is defined in a way that given points $inline$P$inline$ and $inline$Q$inline$ , we can draw line intersecting both those points and intersecting curve in a third point $inline$R$inline$ so that $inline$P+Q=-R$inline$ and $inline$P+Q+R=0$inline$ .

    曲线点的加法定义为给定点 $ inline $ P $ inline $ 和 $ inline $ Q $ inline $ ,我们可以画出与这些点相交的线和与第三点相交的曲线 $ inline $ R $ inline $ 以便 $ inline $ P + Q = -R $ inline $ 和 $ inline $ P + Q + R = 0 $ inline $ 。

    Let’s take a look at Marc Hughes explanation:

    让我们来看看Marc Hughes的解释

    image

    A line of constant slope that travels along the surface of the torus is shown above. This line passes through two randomly selected integer points on the curve.

    上面显示了一条沿着圆环表面的恒定斜率线。 这条线穿过曲线上的两个随机选择的整数点。

    image

    To add two points on the graph, draw a line from the first selected point $inline$P$inline$ to the second selected point $inline$Q$inline$ , and extend the line until it intersects another point on the graph $inline$-R$inline$ , extending it across the plot boundaries if necessary.

    要在图形上添加两个点,请从第一个选定点绘制一条线 $ inline $ P $ inline $ 到第二个选定点 $ inline $ Q $ inline $ ,并延长线直到与图上的另一个点相交 $ inline $ -R $ inline $ ,并在必要时将其扩展到绘图边界。

    Once you intercept an integer point, reflect the point vertically across the middle of the graph (an orange dotted line) to find the new point $inline$R$inline$ on the graph. Therefore $inline$P+Q=R$inline$ .

    截取一个整数点后,在图的中间垂直反射该点(橙色虚线)以找到新点 $ inline $ R $ inline $ 在图上。 因此 $ inline $ P + Q = R $ inline $ 。

    $inline$n\cdot P = P + P + P + \dots + P$inline$ (here are $ inline $ n \ cdot P = P + P + P + \点+ P $ inline $ (这是 $inline$n$inline$ summands). $ inline $ n $ inline $ 要求)。

    The trapdoor function here lies within the discrete logarithm (for elliptic curves) problem, not the factorisation we took a look at within the RSA section. The problem is: if we know $inline$P$inline$ and $inline$Q$inline$ , what is such $inline$k$inline$ , that $inline$Q=k\cdot P$inline$ ?

    这里的活板门函数位于离散对数(对于椭圆曲线)问题中,而不是我们在RSA部分中看到的分解。 问题是:如果我们知道 $ inline $ P $ inline $ 和 $ inline $ Q $ inline $ ,这是什么 $ inline $ k $ inline $ , $ inline $ Q = k \ cdot P $ inline $ ?

    Both the factorisation problem (underlying the RSA) and the discrete logarithm for elliptic curves (which is the basis for ECDSA and ECDH) are supposed to be hard, i.e., there are no known algorithms for solving this problem in polynomial time for a given key length.

    分解问题(位于RSA之下)和椭圆曲线的离散对数(这是ECDSA和ECDH的基础)都被认为很困难,即,对于给定的键,在多项式时间内没有解决此问题的已知算法长度。

    While, typically, anyone would be shamed for mixing the key exchange (ECDH) with the signature (ECDSA) algorithm, we need to explain how they work together. A modern TLS certificate contains a public key, in our case, of the elliptic curve algorithm-generated key pair, usually signed by a higher-level authority. The client verifies the signature of the server and obtains the shared secret. The shared secret is used in a symmetric encryption algorithm, such as AES or ChaCha20. However, the principle remains the same: agree upon domain parameters (the sextuplet), get the key pair, where the private key is a randomly selected integer (the multiplicand from $inline$Q=k\cdot P$inline$ ), and the public key is a point at the curve. Signature algorithms use the base point $inline$G$inline$ , which is a generator for a subgroup of large prime order $inline$n$inline$ , such that $inline$n\cdot G=0$inline$ , where 0 is the identity element. The signature proves that the secure connection is being established with the authentic party — a server which has the TLS certificate (public key) signed by some certificate authority for the given server name.

    通常,尽管任何人都会因将密钥交换(ECDH)与签名(ECDSA)算法混合而感到羞耻,但我们需要解释一下它们如何协同工作。 在我们的案例中,现代TLS证书包含一个由椭圆曲线算法生成的密钥对的公钥,通常由更高级别的权威机构签名。 客户端验证服务器的签名并获取共享密钥。 共享密钥用于对称加密算法,例如AES或ChaCha20。 但是,原理仍然是相同的:同意域参数(sextuplet),获得密钥对,其中私钥是随机选择的整数(来自 $ inline $ Q = k \ cdot P $ inline $ ),而公钥是曲线上的一个点。 签名算法使用基点 $ inline $ G $ inline $ ,这是大质数阶子组的生成器 $ inline $ n $ inline $ ,这样 $ inline $ n \ cdot G = 0 $ inline $ ,其中0是标识元素。 签名证明与正当方建立了安全连接,该服务器具有由某些证书颁发机构为给定服务器名称签名的TLS证书(公用密钥)。

    (EC)DH(E)+ ECDSA =当前握手形式 ((EC)DH(E)+ECDSA= Current handshake form)

    In modern TLS (1.3) the client and the server generate their public-private key pair on the fly, while establishing the connection, this is called Ephemeral version of key exchange. Most popular browser TLS libraries support this. Mostly they use Edwards 25519 elliptic curve, introduced by Daniel J. Bernstein (djb), offering 128-bit security. Since 2014 openssh uses this curve for the key pair creation. In 2019 though, browsers still don’t support TLS sessions with servers having a certificate with EdDSA public key.

    在现代TLS(1.3)中,客户端和服务器在建立连接的同时会动态生成其公私密钥对,这称为密钥交换的临时版本。 最流行的浏览器TLS库支持此功能。 大多数情况下,它们使用由Daniel J. Bernstein(djb)引入的Edwards 25519椭圆曲线 ,提供128位安全性。 从2014年开始,openssh使用此曲线创建密钥对。 但是在2019年,浏览器仍然不支持具有带有EdDSA公钥证书的服务器的TLS会话。

    But let’s get back to how things work at the end of 2019 with TLS 1.3.

    但是让我们回到TLS 1.3在2019年底的工作方式。

    The key exchange mechanisms in TLS 1.3 are restricted to (EC)DH(E)-based (with the x25519 is the one supported in client-side TLS libraries of most popular browsers as well as server-side TLS libraries, such as OpenSSL, which we will inspect a bit later), and the cipher suite list contains only three entries: TLS_AES_128_GCM_SHA256, TLS_AES_256_GCM_SHA384 and TLS_CHACHA20_POLY1305_SHA256. For those of you aware of how the cipher suites were named in the TLS 1.2 version it is apparent right away that the key exchange mechanism is now “detached” from the cipher suite name, also the static RSA and static Diffie–Hellman exchange modes removed from the specification entirely. Even the session resumption based on PSK is made over ECDHE in TLS 1.3. It is also true for custom DH parameters, which aren’t allowed now, leaving only those generally agreed to be secure in the final protocol specification.

    TLS 1.3中的密钥交换机制仅限于基于(EC)DH(E)的机制(x25519是大多数流行浏览器的客户端TLS库以及服务器端TLS库(如OpenSSL, (我们将在稍后进行检查),并且密码套件列表仅包含三个条目:TLS_AES_128_GCM_SHA256,TLS_AES_256_GCM_SHA384和TLS_CHACHA20_POLY1305_SHA256。 对于那些了解TLS 1.2版本中密码套件的命名方式的人来说,显而易见的是,密钥交换机制现在已与密码套件名称“分离”,还删除了静态RSA和静态Diffie-Hellman交换模式。完全来自规范。 即使是基于PSK的会话恢复也是在TLS 1.3中通过ECDHE进行的。 对于自定义DH参数(现在不允许),也是如此,仅保留最终协议规范中普遍认为安全的那些参数。

    It is interesting that there is a rather significant difference in how asymmetric encryption algorithms work nowadays. With ECC (and ECDSA certificates in particular) we use smaller keys to get to “convenient” levels of security, compared with RSA. That enables usage of a stronger asymmetric encryption algorithm and key exchange mechanisms on smaller devices and sometimes even in things that are not generally considered a device (smartcard).

    有趣的是,当今非对称加密算法的工作方式存在相当大的差异。 与RSA相比,有了ECC(尤其是ECDSA证书),我们可以使用较小的密钥来达到“便捷”的安全级别。 这样就可以在较小的设备上,有时甚至在通常不被视为设备(智能卡)的设备上使用更强大的非对称加密算法和密钥交换机制。

    First of all, it is necessary to mention what “hybrid cryptosystem” means in terms of TLS 1.3.

    首先,有必要提及TLS 1.3中的“混合密码系统”的含义。

    A hybrid cryptosystem is the one that uses asymmetric (public key) encryption to establish a shared secret, that is further used as a key in a symmetric stream or block cipher.

    混合密码系统是一种使用非对称(公共密钥)加密来建立共享机密的系统,该系统还用作对称流或分组密码中的密钥。

    Secondly, public-key infrastructure and certificates. It is interesting that in his 2004 interview Martin Hellman mentioned an “unsung hero” Loren Kohnfelder, whose MIT bachelor’s thesis introduced a tree structure of what we now know as public key infrastructure. Nevertheless, let’s roll back to certificates.

    其次,公钥基础结构和证书。 有趣的是,马丁·赫尔曼(Martin Hellman)在2004年的采访中提到了“无名英雄”洛伦·科恩菲尔德(Loren Kohnfelder),他的麻省理工学院学士学位论文介绍了我们现在称为公钥基础结构的树形结构。 不过,让我们回退到证书。

    The fact that the server really has the private key is ensured by his signature, which can be verified with the server public key. And the certificate ensures that some public key belongs to a specific server. It means that you are establishing secure communication with the specific party and not with an imposter. Your bank, not a cybercriminal. In TLS 1.3 there is a significant improvement over previous negotiation format — the server signs all the information it has up to this moment: the client hello and the server hello, including negotiated cipher. Let’s take a look at the corresponding section of the RFC 8446:

    服务器确实具有私钥这一事实是通过其签名来确保的,可以通过服务器公钥进行验证。 并且证书确保某些公钥属于特定服务器。 这意味着您正在与特定方而不是冒名顶替者建立安全的通信。 您的银行,而不是网络犯罪分子。 在TLS 1.3中,对以前的协商格式进行了重大改进-服务器对到目前为止拥有的所有信息进行签名:客户端问候和服务器问候,包括协商的密码。 让我们看一下RFC 8446的相应部分:

    Client                                           Server
    
    Key  ^ ClientHello
    Exch | + key_share*
         | + signature_algorithms*
         | + psk_key_exchange_modes*
         v + pre_shared_key*       -------->
                                                      ServerHello  ^ Key
                                                     + key_share*  | Exch
                                                + pre_shared_key*  v
                                            {EncryptedExtensions}  ^  Server
                                            {CertificateRequest*}  v  Params
                                                   {Certificate*}  ^
                                             {CertificateVerify*}  | Auth
                                                       {Finished}  v
                                   <--------  [Application Data*]
         ^ {Certificate*}
    Auth | {CertificateVerify*}
         v {Finished}              -------->
           [Application Data]      <------->  [Application Data]

    In TLS 1.3 client sends the key share (along with needed parameters), signature algorithms right away in the first message (Client Hello). The keys needed to exchange with the server are created in the background, without the user even noticing that fact. They are further exchanged with the server to create a common secret, from pre-master secret keys that were established when the server sent his message (Server Hello) answering the client.

    在TLS 1.3中,客户端立即在第一条消息(客户端Hello)中发送密钥共享(以及所需的参数)和签名算法。 与服务器交换所需的密钥是在后台创建的,而用户甚至没有注意到这一事实。 它们与服务器进一步交换,以根据服务器发送其消息(服务器Hello)来答复客户端时建立的预主密钥来创建公共密钥。

    On the “Server Hello” side you can see the Certificate* being transferred to the client, along with the CertificateVerify* part which verifies that the party possesses the private key for the corresponding public key entry, and creates the session (symmetric) key if everything goes as planned — meaning, that the side requesting the data (client) successfully verified the answering side (server), further creating a common secret.

    在“服务器问候”侧,您可以看到证书*正在转移到客户端,以及证书验证*部分,该部分验证当事方是否拥有相应公共密钥条目的私钥,并在创建会话(对称)密钥时一切都按计划进行,这意味着请求数据的一方(客户端)成功验证了应答方(服务器),从而进一步创建了一个公共机密。

    There are two essential operations hidden in this transmissions — signature creation and signature verification. Those are made on both sides of communication since “signature” is essentially a proof that the party actually has the private key corresponding with the public key, that the data comes from signatory and the message was not altered in transit.

    此传输中隐藏了两个基本操作-签名创建和签名验证。 之所以在通信的两面进行,是因为“签名”本质上是证明该方实际上具有与公钥相对应的私钥,数据来自签名者并且消息在传输过程中没有发生变化。

    With RSA, as we will further see, the signing operation is the most expensive. Since we’re signing with a 2048 or 3072-bit long key, such operation loads the server significantly, much more than it loads the client verifying such a signature.

    正如我们将进一步看到的,使用RSA,签名操作是最昂贵的。 由于我们使用的是2048位或3072位长的密钥进行签名,因此这样的操作将大大增加服务器的负载,远远超过了验证这种签名的客户端的负载。

    With ECDSA, we have smaller keys (we are going to look at the ECDSA with NIST P-256 (or the secp256v1)) but more complex operations. As a result, it could be viewed as the “upside-down” RSA — the client is loaded most, by the signature verification computation, while the server easily handles the signature creation. The measurements verify that, see “A bit of benchmark” section.

    使用ECDSA,我们可以使用较小的密钥(我们将使用NIST P-256(或secp256v1)查看ECDSA),但操作更为复杂。 结果,它可以看作是“上下颠倒”的RSA-客户端通过签名验证计算负载最多,而服务器则可以轻松地处理签名创建。 测量结果证实了这一点,请参阅“一些基准”部分。

    This effect handily scales the nowadays Internet — since modern clients are almost equally powerful as the servers (taking in mind just the CPU core frequency), so they could effectively take the expensive operation to bare. The server, in its turn, can use the freed capabilities to create more signatures and establish more sessions.

    这种效果可以轻松扩展当今的Internet,因为现代客户端的功能几乎与服务器相同(仅考虑CPU核心频率),因此它们可以有效地暴露昂贵的操作。 反过来,服务器可以使用释放的功能来创建更多签名并建立更多会话。

    让我们加密证书签名 (Let’s Encrypt certificate signature)

    So, in order to provide the reader with a bit of practical and handy instructions on how to create a TLS-enabled server with the ECDSA key pair signed by the Let’s Encrypt authority, we decided to illustrate a full process of creating a key pair needed to create a CSR (certificate signing request) for the Let’s Encrypt and, as a result, get the needed ECDSA certificate for our server.

    因此,为了向读者提供一些实用且方便的说明,说明如何使用由Let's Encrypt机构签名的ECDSA密钥对创建启用TLS的服务器,我们决定说明创建所需密钥对的完整过程。为Let's Encrypt创建CSR(证书签名请求),并因此为我们的服务器获取所需的ECDSA证书。

    We have to generate a private key to proceed. We will use the OpenSSL library.

    我们必须生成一个私钥才能继续。 我们将使用OpenSSL库。

    The OpenSSL manual describes the generation of any EC keys through a special command, designated especially to the elliptic curve branch of the generation algorithm.

    OpenSSL手册描述了通过特殊命令的任何EC密钥的生成,该命令特别指定给生成算法的椭圆曲线分支。

    openssl ecparam -genkey -name -secp256v1 -out privatekey.pem

    To check that the OpenSSL library did everything right, we can execute the ec command.

    要检查OpenSSL库是否正确执行了所有操作,我们可以执行ec命令。

    openssl ec -in privatekey.pem -noout -text

    The output will show us the specified curve the key has been created with.

    输出将向我们显示已创建关键点的指定曲线。

    Next step is quite essential to the creation of the CSR — in order to skip the process of filling all the information details needed to obtain the certificate we need the config file. Luckily, Mozilla did the entire work for us, introducing the “SSL Configuration Generator”. There, you can choose from any available server options. The pure OpenSSL config, peculiarly not present at the Generator’s page would look something like this:

    下一步对于创建CSR非常重要-为了跳过填写获取证书所需的所有信息详细信息的过程,我们需要配置文件。 幸运的是,Mozilla为我们做了整个工作,引入了“ SSL配置生成器 ”。 在这里,您可以从任何可用的服务器选项中进行选择。 纯粹在生成器页面上不存在的OpenSSL配置看起来像这样:

    [ req ]
    prompt = no
    encrypt_key = no
    default_md = sha256
    distinguished_name = dname
    req_extensions = reqext
    
    [ dname ]
    CN = example.com
    emailAddress = admin@example.com
    
    [ reqext ]
    subjectAltName = DNS:example.com, DNS:*.example.com
    Note: it is not necessary to have the CNF — if you don’t, you would be asked to fill these details in the command line. 注意:没有必要安装CNF-如果没有,则将要求您在命令行中填写这些详细信息。

    Now, follow the creation of a CSR itself. Here we have a handy OpenSSL command.

    现在,遵循CSR本身的创建。 在这里,我们有一个方便的OpenSSL命令。

    openssl req -new -config -pathtoconfigfile.cnf  -key privatekey.pem -out csr.pem

    We can also verify the correctness of a newly created CSR.

    我们还可以验证新创建的CSR的正确性。

    openssl req -in csr.pem -noout -text -verify

    Here we’ve come to a final phase — using an ACME client, certbot, to pass our certificate signing request to Let’s Encrypt.

    在这里,我们进入了最后阶段-使用ACME客户端certbot将我们的证书签名请求传递给Let's Encrypt。

    Certbot helps you to get the needed certificate and has a whole lot of options. Here said, if you are new to the public-key encryption, and the PKI infrastructure we have in 2019, you better use --dry-run before you try to obtain the certificate for any domain of yours.

    Certbot可帮助您获得所需的证书,并有很多选择。 这里说的是,如果您不--dry-run公钥加密以及我们在2019年拥有的PKI基础结构,则在尝试获取您任何域的证书之前,最好使用--dry-run

    certbot certonly --dry-run --dns-somednsprovider --domain “example.com” --domain “*.example.com” --csr csr.pem

    In this case, the certbot client checks that the requested domains list (in the command line) matches the domains listed in the certificate signing request. In the --dns-somednsprovider command lies a bit of a lie, because there are plenty of ways you could prove Let’s Encrypt you are in possession of a particular part of the Internet traffic. However, if you are using some public cloud hosting provider, say DigitalOcean, Hetzner, Amazon, Azure, anything — there probably would be a more natural way to provide the needed information, because your provider already made some integration tool.

    在这种情况下,certbot客户端会检查所请求的域列表(在命令行中)是否与证书签名请求中列出的域匹配。 在--dns-somednsprovider命令中有一个谎言,因为有很多方法可以证明“让我们加密”是您拥有Internet流量的特定部分。 但是,如果您使用某些公共云托管提供商,例如DigitalOcean,Hetzner,Amazon,Azure等,则可能会提供一种更自然的方式来提供所需的信息,因为您的提供商已经制作了一些集成工具。

    After, if you are sure about the correctness of the parameters you are using in passing your CSR to the Let’s Encrypt via a certbot client — exclude the --dry-run parameter out of your command and proceed.

    之后,如果您确定通过certbot客户端将CSR传递给Let's Encrypt时所用参数的正确性,请从命令中排除--dry-run参数,然后继续。

    If successful, the client would produce several certificates as output: the signed certificate itself, the root and intermediate certs, and the combination of the latter as the last-named certificate chain, all in the .pem file format.

    如果成功,则客户端将生成多个证书作为输出:签名证书本身,根证书和中间证书,以及后者的组合作为姓氏证书链,所有格式均为.pem文件格式。

    OpenSSL has a command we could use to inspect the certificates:

    OpenSSL具有可用于检查证书的命令:

    openssl x509 -in chainfilepath.pem -noout -text

    At this point, it becomes evident that Let’s Encrypt signed the certificate using SHA256 digest. In addition, ECDSA Root and Intermediates signing fall under the “Upcoming Features” section, which effectively means that right now you’d get only RSA intermediates. But that’s okay since you are still using the ECDSA public key.

    在这一点上,很明显,让我们加密使用SHA256摘要对证书进行了签名。 此外,ECDSA根目录和中间件签名属于“即将推出的功能”部分,这实际上意味着,现在您仅会获得RSA中间件。 但这没关系,因为您仍在使用ECDSA公钥。

    At the end of this section, we’d like to say something in connection to the length of keys. In information security, it is common to say the security level is 2^x, where x is the bit length (RSA is a bit of an exception here, as it grows somewhat slower than exponentially). To approximate how keys used for different algorithms correspond to each other, we would refer to the OpenSSL wiki page.

    在本节的最后,我们想说一些与键的长度有关的内容。 在信息安全中,通常说安全级别是2 ^ x,其中x是位长(RSA在这里有点例外,因为它的增长比指数增长要慢)。 要估算用于不同算法的密钥如何彼此对应,请参考OpenSSL Wiki页面

    Symmetric Key Length

    RSA Key Length

    Elliptic Curve Key Length

    801024160
    1122048224
    1283072256
    1927680384
    25615360512

    对称密钥长度

    RSA密钥长度

    椭圆曲线键长

    80 1024 160
    112 2048 224
    128 3072 256
    192 7680 384
    256 15360 512

    已知问题和例外以及国家安全局 (Known issues and exceptions, and THE NSA)

    image

    Credits: xkcd

    积分: xkcd

    Probably, the central issue of using elliptic curve cryptography through the years was the need for a very carefully crafted random number generator, in order to create keys of required security level.

    多年来,使用椭圆曲线密码学的中心问题可能是需要精心设计的随机数生成器,以便创建所需安全级别的密钥。

    There was a massive scandal around the Dual_EC_DRBG (dual elliptic curve deterministic random bit generator) algorithm, which took many years to resolve. Also, there is uncertainty around ECC patents, as it is known that many of them belonged to the Certicom company, which was acquired by Blackberry. There also are companies that are known to be certified the use of ECC from Blackberry. Of course, there is a simple distrust in some NIST standards, which could or could not be affected by the NSA or any other United States enforcement and surveillance institution.

    Dual_EC_DRBG (双椭圆曲线确定性随机位生成器)算法周围发生了大规模丑闻,解决了许多年。 此外,ECC专利存在不确定性,因为众所周知,其中许多专利属于Certicom公司,该公司被黑莓(Blackberry)收购。 也有一些公司被黑莓公司证明可以使用ECC。 当然,在某些NIST标准中存在简单的不信任感,这些标准可能会受到美国国家安全局(NSA)或其他任何美国执法和监视机构的影响,也可能不会受到影响。

    The implementation side of an issue is an entirely different question. In 2010 PlayStation 3 console suffered a Sony private key recovery due to improper implementation of the ECDSA algorithm —they had a static random that made the trapdoor function solvable. OpenSSL also suffered in the following year, however, quickly fixing the vulnerability that allowed retrieval of a private key with the help of a timing attack, for more information look at the original paper.

    问题的实现方面是一个完全不同的问题。 在2010年,由于ECDSA算法的实施不正确,PlayStation 3控制台遭受了索尼私钥恢复,因为它们具有静态随机性,因此可以解决活板门功能。 但是,OpenSSL在第二年也遭受了损失,但很快修复了该漏洞,该漏洞允许在定时攻击的帮助下检索私钥,有关更多信息,请参阅原始文章

    In 2013 at the RSA conference a group of researchers presented their “Randomly Failed!” paper about SecureRandom Java class vulnerabilities. Half a year later it came down to Android Bitcoin wallets, created using not enough cryptographically secure PRNG.

    2013年,在RSA会议上,一组研究人员展示了他们的“ 随机失败! 关于SecureRandom Java类漏洞的文章。 半年后,它归结为使用加密安全性不足的PRNG创建的Android 比特币钱包。

    Due to serious serial vulnerabilities discovered, in the same August 2013, IETF released an RFC 6979, describing a deterministic generation of k used in the key creation. We could say that such a measure fixed the issue, but we won’t — anytime researchers could find issues in numerous implementations due to unnecessary deviation from the protocol specifications.

    由于发现了严重的串行漏洞,2013年8月,IETF发布了RFC 6979 ,描述了密钥创建中使用的确定性k代。 我们可以说这样的措施可以解决问题,但是我们不会-由于不必要地偏离协议规范,研究人员可以在众多实现中发现问题。

    About the NSA. If you haven’t heard about the Dual_EC_DRBG story — reserve some time and read corresponding articles, you won’t regret getting into details. Edward Snowden is a part of this story because the 2013 revelations proved the earlier suspicions. It resulted in many prominent cryptographers losing trust to NIST since that organization designed and described many of the curves and further algorithms, underlying ECDSA.

    关于国家安全局。 如果您还没有听说过Dual_EC_DRBG的故事-请花些时间阅读相应的文章,您将不会后悔获得详细信息。 爱德华·斯诺登(Edward Snowden)是这个故事的一部分,因为2013年的披露证明了早先的怀疑。 由于该组织设计并描述了ECDSA的许多曲线和其他算法,这导致许多杰出的密码学家对NIST失去信任。

    Daniel Bernstein’s 25519 curve and DH function is the answer to both these issues and, as we described earlier, a transition towards EdDSA is slow though evident. Even with the NIST curves, no evidence of their vulnerability has been found yet and, as we have already mentioned, random-related experience has been quite instructive.

    丹尼尔·伯恩斯坦(Daniel Bernstein)的25519曲线和DH函数可同时解决这两个问题,而且正如我们前面所述,向EdDSA的过渡虽然缓慢,但显而易见。 即使使用NIST曲线,也尚未发现其脆弱性的证据,而且正如我们已经提到的,与随机相关的经验也很有启发性。

    To conclude this part, we want to give John von Neumann’s quote: “Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.”

    作为本部分的总结,我们想引用约翰·冯·诺伊曼的话:“任何试图通过确定性手段生成随机数的人当然都处于犯罪状态。”

    有点基准 (A bit of benchmark)

    We used an NGINX 1.16.0 server with OpenSSL 1.1.1d to run these benchmarks with various certificates. As we mentioned earlier, currently Let’s Encrypt allows only prime256v1 and secp384r1 algorithms for certificate signing requests, and does not provide root and intermediary ECDSA certificates, probably working at this feature at the time of us writing this article.

    我们使用带有OpenSSL 1.1.1d的NGINX 1.16.0服务器,以各种证书运行这些基准测试。 如前所述,当前的“加密”仅允许prime256v1和secp384r1算法用于证书签名请求,并且不提供根ECDSA证书和中间ECDSA证书,在撰写本文时,此功能可能起作用。

    Signature type

    Handshakes per second

    ECDSA (prime256v1/nistp256)

    3358.6

    RSA 2048

    972.5

    签名类型

    每秒握手

    ECDSA(prime256v1 / nistp256)

    3358.6

    RSA 2048

    972.5

    Now let’s take a look at the same processor’s OpenSSL -speed results with ECDSA and RSA.

    现在,让我们看看使用ECDSA和RSA的同一处理器的OpenSSL -speed结果。

    Signature type

    sign

    verify

    sign/sec

    verify/sec

    RSA 2048 bit

    717 μs20.2 μs1393.949458.2

    256 bit ECDSA (nistp256)

    25.7 μs81.8 μs38971.612227.1

    签名类型

    标志

    校验

    符号/秒

    验证/秒

    RSA 2048位

    717微秒 20.2微秒 1393.9 49458.2

    256位ECDSA(nistp256)

    25.7微秒 81.8微秒 38971.6 12227.1

    If you are interested in how your CPU performs cryptographic computations you may run a simple openssl speed command. The -rsa, -ecdsa and -eddsa parameters would give you benchmark results for the corresponding signature algorithms.

    If you are interested in how your CPU performs cryptographic computations you may run a simple openssl speed command. The -rsa , -ecdsa and -eddsa parameters would give you benchmark results for the corresponding signature algorithms.

    (Superpositioned) Future ((Superpositioned) Future)

    image

    Credits: djb

    Credits: djb

    It is ironical that while we were preparing this article, Google announced “reaching quantum supremacy”. Does this mean that we’re in danger right now and everything developed up to this moment does not provide any secrecy?

    It is ironical that while we were preparing this article, Google announced “ reaching quantum supremacy ”. Does this mean that we're in danger right now and everything developed up to this moment does not provide any secrecy?

    Well, no.

    Well, no.

    As Bruce Schneier wrote in his essay for IEEE Security and Privacy “Cryptography after the Aliens Lands” a huge blow with powerful enough quantum computer could be done to the public-key (asymmetric) cryptography. Symmetric cryptography would still be strong.

    As Bruce Schneier wrote in his essay for IEEE Security and Privacy “ Cryptography after the Aliens Lands ” a huge blow with powerful enough quantum computer could be done to the public-key (asymmetric) cryptography. Symmetric cryptography would still be strong.

    We want to quote Bruce Schneier with following:

    We want to quote Bruce Schneier with following:

    But if the unimaginable happens, that would leave us with cryptography based solely on information theory: one-time pads and their variants.

    But if the unimaginable happens, that would leave us with cryptography based solely on information theory: one-time pads and their variants.

    This is the area where, except looking for implementation flaws, most issues could be found. If there is a group of well-funded mathematicians, cryptanalysts/cryptographers and computer engineers working on proving or disproving some extraordinary complex mathematical problems (like the P?=NP) and achieving substantial results up to this moment, we could be in trouble. However, such advances in computer science, information and computability theories are unlikely to be hidden, since that fact would write the names of their creators on the pages of History and, specifically, History of the Internet textbooks, which is priceless for anyone that smart. So, such a scenario could be taken out as nearly impossible.

    This is the area where, except looking for implementation flaws, most issues could be found. If there is a group of well-funded mathematicians, cryptanalysts/cryptographers and computer engineers working on proving or disproving some extraordinary complex mathematical problems (like the P?=NP) and achieving substantial results up to this moment, we could be in trouble. However, such advances in computer science, information and computability theories are unlikely to be hidden, since that fact would write the names of their creators on the pages of History and, specifically, History of the Internet textbooks, which is priceless for anyone that smart. So, such a scenario could be taken out as nearly impossible.

    It is not clear, whether in the nearest 5 years there would be any successes with quantum computing, though there already are several cryptography primitives considered suitable for the post-quantum world: lattices, supersingular elliptic curve isogeny-based, hashes and codes. For now, security specialists are just experimenting with them. However, there is no doubt that in the case of a need, humanity would quickly employ such algorithms at a mass scale.

    It is not clear, whether in the nearest 5 years there would be any successes with quantum computing, though there already are several cryptography primitives considered suitable for the post-quantum world: lattices, supersingular elliptic curve isogeny-based, hashes and codes. For now, security specialists are just experimenting with them. However, there is no doubt that in the case of a need, humanity would quickly employ such algorithms at a mass scale.

    For now, elliptic-curve based cryptography seems to be a perfect fit for the future decade, providing security and performance.

    For now, elliptic-curve based cryptography seems to be a perfect fit for the future decade, providing security and performance.

    翻译自: https://habr.com/en/company/qrator/blog/474810/

    tls 1.2加密

    展开全文
  • 基于miracl库实现椭圆曲线算法,包括双线性对的实现,塔式扩张等
  • 一条椭圆曲线可以使用二元三次方程来表示,比如:y2 = x3 + ax + b 下图展示了一些合法的椭圆曲线椭圆曲线定义 定义椭圆曲线上两点相加为:给定曲线两点P,Q,P+Q等于P和Q两点的连线与曲线交点沿X轴的对称点...

    一条椭圆曲线可以使用二元三次方程来表示,比如:y2 = x3 + ax + b

    下图展示了一些合法的椭圆曲线:

    imageimage

    椭圆曲线定义

    定义椭圆曲线上两点相加为:给定曲线两点P,Q,P+Q等于P和Q两点的连线与曲线交点沿X轴的对称点,如果P=Q,则P+P等于P在曲线上的切线与曲线交点沿X轴的对称点

    下图演示了如何计算P+Q=R(P≠Q),将P和Q相连得到和曲线的另一个交点-R,再将-R沿X轴做对称得到最终结果R。

    imageimage

    如果P和Q相等,下图演示了如何计算P+Q=2P=R(P=Q),使用P点的切线得到红点-R,沿着X轴做对称得到R点。

    imageimage

    如果我们从某一点出发(所谓的单位元,比如正整数域的1,代表一个空间里的最基本单元),不停做自增操作(所谓群操作,比如++),枚举出整个空间的集合元素可以用下图表示:

    image

    G点是一般是固定算法推荐的点。随机生成稳定性不可靠

    从G出发,不停做切线,找对称点,依次得到-2G,2G,-4G,4G,-8G,8G... 我们可以想象,如果直接给你一个点 Q ,而且Q = NG,你是无法直接回答N的数值是多少(因为是做的切线,无法轻易的反推回去)。N就是我们的私钥,Q就是我们的公钥。

    N如果是奇数,比如是3,可以使用G点与2G点的连线交易椭圆曲线一点,然后在做x轴的对称点即为3G点

     

    椭圆加解密流程

    流程:

    1. 随机生成K
    2. 公钥即为KG
    3. 生成随机数R,(随机数是通过生成随机数r乘以基点G得到) 。同样的公钥同样的私钥所以每次加密都是不一样的。

    加密就可以完成了C = M +r*k*G

    1. 加密好的数据发送给对方,应该包含两个内容,一个是密文C,另一个是随机数R.
    2. 解密时即可通过私钥k,得到明文 M = C-k*R

    image.png

    椭圆曲线签名验签流程

    原理私钥签名,公钥验签。

    G点是基准基点,然后通过一个随机数r,获取一个R=rG

    模逆元是除法

    私钥是k,公钥是kG

    步骤:

    1. 通过消息散列h,随机数rG,私钥k,生成签名s= r(-1)(h+kx)。然后发送给接收者签名s和随机数rG
    2. 接收者验签,公钥kG,签名s,随机数rG,验证得到结果即为rG ,即表示比对成功。

    image.png

    椭圆曲线 秘钥交换协议ECDH

    步骤:

    A与B协商私钥

    1. A,B生成随机私钥a,b
    2. 首先协商生成一个基点G,发送给B
    3. 通过基点,各自发送自己的公钥 bG,aG
    4. 计算共享秘钥abG
    5. 窃听者无法计算出abG, 前向安全性
    展开全文
  • 椭圆曲线加密算法详解

    千次阅读 2018-10-25 22:26:33
    椭圆曲线加密算法,即:Elliptic Curve Cryptography,简称ECC,是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA,ECC优势是可以使用更短的密钥,来实现与RSA相当或更高的安全。据研究,160位ECC加密安全...
  • 密码学新技术,椭圆曲线、双线性对与群签名的相关课件,
  • 你可以看到两条椭圆曲线,过点P做一条切线与曲线相交与另一个点(原文表述为third point,第三个点,译者注),这个点沿X轴的对称点即为点2P。然后过点2P和点P做一条直线,与曲线相加的点沿X轴对称得到点3P。...
  • 今天在学椭圆曲线密码(Elliptic Curve Cryptography,ECC)算法,自己手里缺少介绍该算法的专业书籍,故在网上查了很多博文与书籍,但是大多数博客写的真的是。。。你懂的。。。真不愧是 ‘天下文章一大抄’ 啊! ...
  • 然后引入对样本数据具有更好的适应性的椭圆-双曲线度量,根据数据统计特性定义椭圆-双曲线马氏度量,给出椭圆-双曲线马氏度量学习算法,从而获取最优的度量矩阵;最后利用椭圆-双曲线马氏度量矩阵将样本变换到新的...
  • 泊松方程是椭圆偏微分方程的一个例子,用于模拟物理系统的稳态时不变响应。 参考: 使用MATLAB:registered:的应用数值方法作者:杨元英,曹文武,钟泰生,约翰·莫里斯首次出版时间:2005年1月14日打印ISBN:...
  • 椭圆曲线乘法

    千次阅读 2018-03-14 20:20:30
    今天终于了解了一番神奇的非对称加密算法:椭圆曲线乘法为什么无法反推了,下面介绍一波. 1.椭圆曲线是一个二维的散点图 这里用NIST设立的一条椭圆曲线函数来介绍,因为这条曲线就是比特币使用的.这条曲线就是secp...
  • ECC 椭圆曲线加解密算法

    千次阅读 2018-11-18 23:53:54
    随着计算机性能的提高,部分算法已经不再安全,但是道高一尺魔高一丈,加密算法也在不断的进步和演化,通常的方法是增加密钥长度,越长越安全,确实也管用,但是性能同样也有损失,本篇要介绍的 ECC 椭圆曲线加密...
  • 圆、椭圆双曲线

    2021-01-31 15:40:01
    一、圆 圆 例 ...二、椭圆 ...椭圆的标椎方程:(右侧常数项为1) ...椭圆的面积:S = πab ...双曲线的标准方程: (右侧常数项为1) x2的系数为正,在x轴找(-a,0)(a,0) y2的系数为正,在y轴找(0,b)(0,
  • 离散对数和椭圆曲线加密原理

    万次阅读 多人点赞 2017-08-03 11:35:05
    现代公钥加密系统中,常用的加密算法除了RSA还有离散对数加密和椭圆曲线加密。这两者原理比较相似,在这里一并介绍。 离散对数问题 我们在中学里学的对数问题是指, 给定正实数aaa和axaxa^x,求xxx。也就是...
  • SM2椭圆曲线

    千次阅读 2019-09-21 18:56:16
    实现SM2椭圆曲线公钥密码算法,对给出的英文消息进行加密得到密文,并能通过密文解密出明文。 环境 Windows10,MinGW-W64-builds-4.3.5,miracl 7.0.1 方案设计 背景 SM2椭圆曲线公钥密码算法,SM3密码杂凑算法 原理...
  • 椭圆曲线加密算法

    千次阅读 2018-06-03 15:34:36
    椭圆曲线加密算法,即:Elliptic Curve Cryptography,简称ECC,是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA,ECC优势是可以使用更短的密钥,来实现与RSA相当或更高的安全。据研究,160位ECC加密安全...
  • 用于椭圆曲线密码学的高通量处理器
  • 椭圆曲线、双线性对学习资料

    千次阅读 2014-04-26 13:58:29
    椭圆曲线 Wikipedia https://en.wikipedia.org/wiki/Elliptic_curve_cryptography   http://www.isg.rhul.ac.uk/~sdg/ecc.html   Elliptic Curve Cryptography   ellipticnews ...
  • 椭圆曲线公钥密码学习

    千次阅读 2018-06-16 20:54:59
     由于椭圆曲线加密进行的运算实际上都是在椭圆曲线上进行的,所以接下来需要定义一些椭圆曲线上的运算。 必须注意的是,这里把这些运算称为“加法”和“乘法”仅仅是方便描述,他们跟平时认知的加法和乘法完全是...
  • 在jPBC中,双线性群的使用都是通过叫做Pairing的对象来实现的。...Type A1曲线需要二个参数:numPrime是阶数N中有几个质数因子;qBit是每个质数因子的比特长度。注意,Type A1涉及到的阶数很大,其...
  • 在构造适用于双线性对的椭圆曲线的方法中,通常将椭圆曲线的参数表示成有理多项式,为有效地生成椭圆曲线,要求复乘方程的次数应小于3。通过将椭圆曲线参数看作数域元素,提出了一种构造合适的有理多项式的方法,使得复乘...
  • 提出一种支持椭圆曲线加密体制的有限域算法。该算法可以同时完成素数域和二进制域上的运算,并且模数p和取模多项式可以任意选取。提出了椭圆曲线加密体制运算单元的设计方法,此运算单元可以同时完成素数域和二...
  • 具有功率分析电阻的椭圆曲线密码学的高通量处理器
  • § 1  圆 1.  圆的方程 ... 椭圆 ... 椭圆基本参数 ... 即双曲线是到两定点(即焦点)的距离之差为常数(实轴)的动点 M 的轨迹(使 r 1 - r 2 =2 a 的点数于双曲线的一支,而使 r 2 - r 1 =2 a  ...
  • 最近在研究椭圆曲线算法和双线性对算法,谁有对应的C代码,求大神指教。
  • JPBC库是一个功能很强大的数学库,用于生成椭圆曲线,双线性等,但网上参考资料很少,重复度极高,该分栏用于安装,JPBC参数解释,生成椭圆曲线群,整数群(不用双线性性质),双线性映射教学。内容原创,禁止任何...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,783
精华内容 2,713
关键字:

双椭圆曲线