精华内容
下载资源
问答
  • 椭圆曲线密码体制的应用及具体的算法实现如RAS 和 ECC
  • 椭圆曲线应用在密码领域经典之作。作者为该领域专家之一。很不错一本书。
  • 椭圆曲线的确很复杂,涉及理论知识较多,尤其是数学知识太多太多,无法一窥全貌,经过理解,我觉得最需要理解就是,那条经典的椭圆曲线有什么神秘之处,优势如何实现非对称密码加密,如果觉得有用,请给个简短...

    椭圆曲线的确很复杂,涉及理论知识较多,尤其是数学知识太多太多,无法一窥全貌,经过理解,我觉得最需要理解的就是,那条经典的椭圆曲线有什么神秘之处,优势如何实现非对称密码加密的,如果觉得有用,请给个简短评论,我心欢喜。

    椭圆曲线

    椭圆曲线就是下图那样的一个对称曲线,一点都不像椭圆啊!这个主要源于名称来自于椭圆曲线积分,而这个积分主要是因为通过积分计算椭圆边长而得名。所以通过代数(可理解为多项式)定义的椭圆曲线积分函数就是椭圆曲线。我们来看动图理解椭圆曲线:
    椭圆曲线的计算
    (图片来源链接)

    上图就是漂亮的椭圆曲线,基于X轴对称,在曲线上面有A,B两点,可以任意取,做一条直线,一定会与曲线相交于另外一点,做Y轴平行的垂线到另一边,得到点C。这个运算过程就是基于椭圆曲线定义的加法运算,而且在数学上可以保证A+B=C一定成立(如何确保需要不少数学知识)。咱们拓展一下,如果A,B相同,那么一个点就没法画线了,那么聪明的数学家把该点的切线(光滑曲线一定有切线)定义为P点,如果A,B等于P,那么A+B=2P=C,这样就定义了在曲线上的乘法,还包括其他…定义,就构建了一个高大上的名字—群(高阶数学啊)。有了2P的定义,就可以定义3P,4P…nP了,这样就在曲线上形成了无数个离散的点,如下图一样。
    A+B运算的离散点
    上图看起来这些点压根就不像曲线啊,的确不像,那是因为对曲线上的点进行模运算(%运算符),这样在这个空间中,都是曲线上的点取模后绘制的,他们同样满足曲线上定义的规律。
    如同在曲线上做的那样,这些点通过绘制直线,仍然可以依然找到A+B=C的点(注意经过边缘后,会对折到下边(模运算),到了最右边会对折到最左边),而且这些点分布完全没有规律(除了基于X轴对称)。如果把A,B看作是2P,那么给定P点,和数字2,可以很容易找到C点,反过来,知道P点和C点,需要找到C=2P是很难的,可以通过穷举法暴力破解的。这就是加密的核心了,给定一个秘密,验证很容易,破解很复杂。给定一个数字n(这个需要在椭圆曲线中有定义),计算nP=C,就是加密过程了。

    未来后续理解椭圆曲线,数学家们是定义的椭圆曲线:E(p,a,b,G,n,h), 这是一个多元组,这里的p就是定义这个曲线的大小,p越大,这个曲线覆盖面积就越大,穷举难度也越大,a,b定义了椭圆曲线的多项式系数,这个在算法选定的时候就确定下来了。G表示生产元(复杂的概念),简单理解就是曲线上的一个点G,例如(3,10)通过这个点G定义1G, 2G, 3P…nP的一个序列构成的集合,n越大,点集合越大。h是协因子,一般等于1,确保生成元G的点远远少于椭圆曲线定义的所有点数,这样穷举法成功的概率就接近于零了。另外,椭圆曲线有着比RSA算法在同样位数加密下具有更好的加密性能。

    椭圆曲线的加密

    从上节我们知道椭圆曲线定义一个算法P = nG, 通过n可以很容易计算P,知道G,P很难猜测n,这样就构成了加密基础。本节我们看看如何通过这样一个特性,科学家们如何定义非对称加密的。
    首先大家基于同样的椭圆曲线参数进行加密通讯,双方都知道:E(p,a,b,G,n,h)。Alice随机选择一个数ra, 要求小于n, 计算Pa = ra * G,发送给Bob.
    Bob同样随机选择一个数rb, 要求小于n,计算Pb = rb * G,发送给Alice.
    这样Alice和Bob的随机数ra, rb相当于私钥,公开给对方的Pa, Pb相当于公钥。此时,Alice如果需要给Bob发送加密信息,就可以用Bob的公钥加密,Bob可以用自己的私钥进行解密,计算过程如下:
    Alice选择另一个随机数k, 把需要加密的内容Pm(就是需要把原文编码到椭圆曲线定义的空间中),计算出秘文Cm = {k*G, Pm + k * Pb},这里Pb是Bob的公钥,秘文由2个点构成。Bob收到秘文后进行如下计算:
    Pm + k * Pb - rb * (k * G) = Pm + k * rb * G - rb * k * G = Pm
    这个公式稍微解释一下:Bob从网络中接受到Pm + k * Pb的结果,k * G的结果,并有着自己的私钥rb, 因此计算出Pm.
    从而得到原文点Pm.

    另外一个用处就是实现密钥协商,比如https的ECDHE算法密钥协商:
    Alice通过计算得出协商秘钥:Ka = ra * Pb
    Bob通过计算得出协商密钥:Kb = rb * Pa
    可以通过简单计算得到Ka = Kb:
    Ka = ra * Pb = ra * (rb * G) = rb * (ra * G) = rb * Pa = Kb

    神奇吧!非对称密钥是基于数学规律构建的方法。希望通过本文,可以让你对椭圆曲线加密有一个简单的理解。

    展开全文
  • 将RSA密码体制和椭圆曲线密码体制作了比较,提出了在SET协议中使用基于椭圆曲线密码体制认证、数字签名和数字信封方案。
  • 以椭圆曲线加密系统(ECC)为研究对象,系统地说明了椭圆曲线的数学原理和ECC工作原理,分析了ECC所具有的安全性高、密钥短等技术优势。针对数字签名算法对安全性和速度的技术要求,给出了将ECC应用到数字签名中的...
  • 然后,我们将重点放在等质量和非等质量日出积分上,并且我们发展出一种形式主义,使我们能够根据椭圆曲线迭代积分来计算这些费曼积分。 关键思想是使用按部分积分身份来识别一组积分内核,其精确形式由所讨论...
  • 基于椭圆曲线密码系统优势,提出了加速点积运算椭圆曲线密码算法,使用ECC代替RSA改进SSL协议,缩短了密钥长度,使加解密耗时比RSA缩短了30%,从而达到了占用带宽小,连接速度快,同时又很安全目的。
  • 本文从椭圆曲线加密学基础-点倍积开始讲起,完整介绍了椭圆曲线数字签名算法理论基础和实现算法,以及以太坊中是如何调用椭圆曲线数字签名算法进行数字签名操作

    数字签名算法在Ethereum中的应用不少,目前已知至少有两处:一是在生成每个交易(Transaction, tx)对象时,对整个tx对象进行数字签名;二是在共识算法的Clique算法实现中,在针对新区块进行授权/封印的Seal()函数里,对新创建区块做了数字签名。这两处应用的签名算法都是椭圆曲线数字签名加密算法(Elliptic Curve Digital Signature Algorithm,ECDSA)。Ethereum 在采用ECDSA进行数字签名的基础上,基于自身的业务需求,又将数字签名过程所用的公钥作为地址类型(common.Address)对象,在许多应用场景下作为地址(即账户的唯一标识符)使用。

    有关ECDSA的几个理论概念的关系是这样的:椭圆曲线数字加密算法ECDSA是数字签名算法(DSA)的变例之一,ECDSA的基础是椭圆曲线密码学(Elliptic-curve cryptography,ECC),而ECC的理论前提是椭圆曲线上点的倍积(Elliptic curve point multiplication)。本文将从这些概念的原理讲起,试图讲解一下Ethereum所采用ECDSA的来龙去脉。

    1.椭圆曲线点的倍积

    概念知识

    椭圆曲线的点倍积(point multiplication),指的是椭圆曲线上一个点沿着这条曲线不断的与自身相加,最终落在曲线另一个点上的(计算)过程。也许有些地方会把这里的multiplication翻译成“乘积”或“乘法”,那样的话就要特别注意,这种所谓的“点乘积”,是特指一个标量与一个点的乘积,它属于一种标量乘法(scalar multiplication)。所以,个人觉得将这里的point multiplication翻译成“点倍积”会更准确些,本文会沿用这种翻译。

    假设起点是椭圆曲线点P,终点是曲线上点R,于是我们有如下点倍积公式,注意此时标量一定要写在点的左边。

    R = nP

    上式中的结果R点暂时还计算不出来,我们需要多一些准备。理论上,这里的椭圆曲线所选择的几何方程是固定的,它可以表示为:

    y^2 = x^3 + ax + b

    上式中a和b都是普通标量参数,以上方程所绘出的几何曲线如下图所示,其中红色曲线表示(a, b) = (-7, 6)时的椭圆曲线,蓝色曲线表示 (a, b) = (-6, 6)时的椭圆曲线。显然,a和b的取值对曲线形状还是有影响的。



    现在有了椭圆曲线的具体形状和方程,假设曲线上有一个点P,我们想计算它的倍积nP,该怎么做呢?

    这里需要再引入一个概念:椭圆曲线点的相加(point addition)。以上图为例,红色椭圆曲线上有两个点PQ,设定这两个点相加得到一个同样处于曲线上的R点,这个R点来自P, Q两点直连延长线与椭圆曲线的交点(T点)的共轭点,也就是T点沿X轴的对称点R。由于上述椭圆曲线本身必定沿X轴对称,所以这个R点也必定处于曲线上。

    我们从代数的角度重新看下这个问题:

    这里我们用XY坐标来表示P,Q,R每个点,结合设定的椭圆曲线公式 y^2 = x^3 + ax + b,可以得到如下解答:


    通过引入一个参数lambda,我们可以得到P,Q两点相加得到R点的坐标。

    很好,我们再往前跨出一步,如果P点和Q点重合,那么它们相加R点是怎样的呢?这种情况被称之为椭圆曲线点的翻倍或叠加(point double),根据上式,R点的x,y相对坐标不变,我们只需要用一个特殊的lambda值就行了,不过要留意此时的lambda取值跟曲线方程参数a有关:

    好的,在拥有了以上这些基础知识之后,我们终于可以计算出椭圆曲线点的倍积,因为对于 R = nP无论n取何值,我们都可以通过上述“点相加”和“点翻倍”的方法计算出R点坐标

    计算方法

    我们来看下具体的如何计算椭圆曲线点倍积 Q = dP,即已知椭圆曲线点P和标量d,计算出曲线点Q。

    开始写代码前需要将标量d以二进制的方式表示出来,以便于应用“点相加”和“点翻倍”方法。

    上式就是d的二进制表示,代码中将各个系数表示成一个长度为(m+1)的数组d[]即可,d[i]对应于第i个bit位的取值0或1。下列伪代码均来自wiki-PointMultiplication

    最直观的就是迭代型的,比如自底向上的迭代:

    // iterative: index increasing
    N = P; Q = 0;
    for i in [0, m] do:
        if d[i] == 1  then Q = point_add(Q, N)
        N = point_double(N)
    return Q
    还有从顶向下的迭代:

    // iterative: index decreasing
    Q = 0;
    for i in [m, 0] do:
        Q = point_double(Q)
        if d[i] == 1 then Q = point_add(Q,P)
    return Q
    
    可以看出,自顶向下的迭代算法相比前者,计算量其实完全一样,不过可以少用一个局部变量N。

    除了迭代型,当然还有递归型的

    // recursive
    func f(p, n) is 
        if n == 0  then 
            return 0
        else if n == 1 then
            return p
        else if n mod(2) == 1 then
            return point_add(p, f(p, n-1)) 
        else 
            return f(point_double(p), n/2)
    除此之外,还可以针对窗口宽度作优化。注意到之前将d以二进制的形式表示,其中的窗口宽度可以表示为1,即2的幂次每次+1。如果现在选取更合适的窗口宽度w,则可以将d表示为成

    这样得到的m更小,也就是系数数组d[]的长度更小,这就意味着仅需更少的迭代(递归)次数。相关伪代码可见wiki。

    2. 椭圆曲线密码学

    椭圆曲线密码学(Elliptic-curve cryptography,ECC)同当前流行的其他几种密码学类型,也是通过一个公钥 + 一个私钥组成的一对钥匙来进行加密相关操作。它基于有限域上特定椭圆曲线进行操作,最重要的操作是椭圆曲线的点倍积,不夸张的说,椭圆曲线点倍积正是椭圆曲线密码学的基石。

    为什么这么说呢?因为对于点倍积的计算式Q = nP 而言, 在已知起点P和终点Q的情况下,想要计算出n,理论上在目前计算条件下近乎是不可能的!这个数学证明过程比较复杂,这里只想举一个极端的例子。回看上一章节中那幅图,如果这里选用了图中红色椭圆曲线作点倍积运算,注意到它的左边部分是一个封闭的不规则圆弧,如果倍积运算的终点Q恰好落在这个圆弧上面,那么参数n是死活都算不出来的,因为如果增大n,让Q在圆弧上多循环几圈后依旧保持在Q点...

    加密用椭圆曲线的参数组

    ECC的使用场景包括数字签名,安全的伪随机数生成等。在应用中,所采用的椭圆曲线必须用一组完整的参数来加以定义,这组参数被称为域参数。一般的,ECC定义的这组参数可表为

    (p, a, b, G, n, h)

    其中 p 是一个极大的质数,用来表示曲线所有点的范围; a, b 分别是椭圆曲线方程 y^2 = x^3 + ax + b 中的系数;G 是该椭圆曲线上点倍积的基点,对于所有通过点倍积运算得到的曲线上点的集合来说,G可算是它们的生成器(generator);n 是基点G的可倍积阶数,定义为能够使得点倍积nG 不存在的最小的整数nh 是一个整数常量,它跟椭圆曲线运算中得到点的集合以及 n 有关,h 一般取值为1。

    在下一章节中,我们可以看到这些椭圆曲线参数在椭圆曲线数字签名中的应用。

    3. 椭圆曲线数字签名算法理论

    椭圆曲线数字签名算法(ECDSA)是数字签名算法(DSA)的变例之一,它基于椭圆曲线密码学。相比于基于RSA密码学的DSA,ECDSA在计算数字签名时所需的公钥长度可以大大缩短。比如,对于一项安全级别为80 bits的数字签名来说,ECDSA需要的公钥长度仅仅为安全级别的2倍,即160 bits,而同样安全级别要求下的RSA所需公钥长度至少为1024 bits;同时算法所生成的签名长度,不论是ECDSA还是RSA都大约是320 bits,这样一来,ECDSA相对于RSA在应用上的优势就很明显了。

    注:安全级别(security level)的概念是:N bits的安全级别,意味着攻击者大约要经过2^N的运算才能获得本次加密用的私钥。安全级别所代表的bits越长,意味着安全性能越好,越难以被攻破,当然同时在加密时的代价,包括公钥长度和生成签名长度,自然也会相应增加。

    ECDSA基于DSA,DSA定义了数字签名生成过程和验证过程的基本步骤,通过比较可以看出,ECDSA遵循了DSA的这些定义,并在一些特定步骤中,转而采用了椭圆曲线的相关操作。这里由于篇幅所限,就不详细介绍DSA的内容了,有兴趣的朋友可以去wiki上一看。

    数字签名的生成

    下面来看一下ECDSA的签名生成过程,以下内容主要来自wiki_ECDSA

    假设Alice要给Bob发一个经过数字签名的消息,他们首先需要定义一组共同接受的椭圆曲线加密用参数,简单的,这组参数可表示为

    (CURVE, G, n)

    其中,CURVE表示椭圆曲线点域和几何方程;G是所有点倍积运算的基点;n是该椭圆曲线的可倍积阶数(multiplicative order),作为一个很大的质数,n的几何意义在于,nG = 0,即点倍积nG的结果不存在,而对于小于n的任何一个正整数 m = [1,n-1],点倍积mG都可以得到一个合理的处于该椭圆曲线上的点。

    其次,Alice要创建一对钥,即一个私钥和一个公钥。私钥来自于[1, n-1]范围内一个随机数:


    公钥如下,它来自私钥和基点的椭圆曲线点倍积:

    好,准备工作就绪,假设Alice想要对消息m作数字签名,有以下步骤:

    1. 计算 e = HASH(m),HASH是一个哈希加密函数,比如SHA-2,或SHA-3。
    2. 计算 z,来自e的二进制形式下最左边(即最高位)L_n个bits,而L_n是上述椭圆曲线参数中的可倍积阶数n的二进制长度。注意z 可能大于n,但长度绝对不会比 n 更长。
    3. 从 [1, n-1] 内,随机选择一个符合加密学随机安全性的整数k。
    4. 计算一个椭圆曲线上点:
    5. 以下式计算 r 值, 如果r == 0, 则返回步骤3重新计算。

    6. 以下式计算 s 值,如果 s == 0,则返回步骤3重新计算。
    7. 生成的数字签名就是 (r, s)

    特别需要注意的是步骤3中 k 的选择,它不仅要满足加密学的随机安全性要求,要像私钥一样保护起来,更重要的是,在每次生成一个新的数字签名时,这个 k 必须每次都要更新。否则,通过上述数字签名过程中的算式相互换算,很容易从中破译出私钥!具体换算过程可见wiki_ECDSA。

    数字签名的验证

    对于消息的接收方Bob来说,他除了收到数字签名文件外,还会有一份公钥。所以Bob的验证分两部分,首先验证公钥,然后验证签名文件(r, s)。

    公钥的验证

    1. 公钥的坐标应是有效的,不会等于一个极限值空点
    2. 通过公钥的坐标验证它必须是处于该椭圆曲线上的点。
    3. 应有下式成立,即曲线的可倍积阶数 n 与公钥的点倍积不存在

    签名文件的验证

    1. 验证 rs 均是处于[1, n-1]范围内的整型数;否则验证失败
    2. 计算 e = HASH(n),HAHS()即签名生成过程步骤1中使用的哈希函数。
    3. 计算 z,来自 e的最左边L_n个bits。
    4. 计算参数 w

    5. 计算两个参数 u1u2

    6. 计算(x1, y1),如果(x1, y1)不是一个椭圆曲线上的点,则验证失败:
    7. 如果以下恒等式不成立,则验证失败:

    以上就是椭圆曲线数字签名算法(ECDSA)的生成和验证的完整过程,在wiki_ECDSA还可以看到关于上述验证方法正确性的证明过程。无论用何种编程语言实现,其中数字签名的生成和验证必然要遵循以上的理论和步骤

    4. go-ethereum中的椭圆曲线数字签名算法

    go语言安装包中自带的crypto/ecdsa包中包含了关于椭圆曲线的结构体声明和操作函数,以及ECDSA的签名生成和验证到的完整实现代码。不过,以太坊(go-ethereum)并没有采用这个crypto/ecdsa包来实现它自己的数字签名算法。尽管如此,这部分代码仍然很有阅读的必要,原因有二:1.它里面定义的一些行为接口和结构体类型,依然在被go-ethereum中的代码所使用,以方便调用;2. 它关于ECDSA的实现代码写的简洁清晰,非常适合ECDSA的初学者加以研习。

    go语言包中的ecdsa代码包

    go语言包自带的crypto/ecdsa相关的结构体如以下UML图所示:


    对照着上一章节中ECDSA的算法理论,以上的结构体和接口的声明就非常易于理解了。

    • ecdsa.PublicKey结构体通过持有一个elliptic,Curve接口的实现体,可以提供椭圆曲线的所有属性,和相关操作;PublicKey的成员(X,Y),对应于算法理论中公钥 的坐标。
    • elliptic.Curve接口声明了椭圆曲线的相关操作方法,其中Add()方法就是椭圆曲线点倍积中的“点相加”操作,Double()就是点倍积中的“点翻倍”操作,ScalarMult()根本就是一个点倍积运算(参数k是标量),IsOnCurve()检查参数所代表的点是否在该椭圆曲线上;
    • elliptic.CurveParams结构体实现了<Curve>接口的所有方法,另外用成员属性定义了一个具体的椭圆曲线,比如(Gx, Gy) 表示该椭圆曲线的基点,即算法理论中的G点; N 是与基点对应的可倍积阶数n;B是椭圆曲线几何方程中的参数b,注意此处ecdsa代码包中隐含的椭圆曲线方程为y^2 = x^3 - 3x + b,故只需一项参数b即可。
    • ecdsa.PrivateKey是暴露给外部使用的主要结构体类型,它其实是算法理论中的私钥和公钥的集合。它的成员D,才真正对应于算法理论中的(标量)私钥
    • ecdsa.ecdsaSignature对应于生成的数字签名(r, s)。

    由此可见,go语言自带的crypto/ecdsa代码包从结构体的成员到方法的声明,都力图使得其所代表的ECDSA算法理论清晰易懂。关于实现函数,重点推荐ecdsa/ecdsa.go中的两个函数Sign()和Verify()

    // go-1.x/src/crypto/ecdsa/ecdsa.go
    func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error)
    func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool
    
    以上两个函数的实现过程,均严格遵循了上一章节介绍的算法理论中的签名生成和验证的过程逐步执行,对于加密算法实现方面的coding会有些不错的启示,有心的朋友可以找来源代码一看究竟。

    go-ethereum中对ECDSA的调用

    go-ethereum中实际采用的ECDSA函数实现,来自于第三方库libsecp256k1,它是一个C++库,在比特币代码(github_bitcoin)中就有应用,被视为一个经过优化的,针对椭圆曲线secp256k1的一个实现库。secp256k1对应于一组特定的椭圆曲线数字签名参数,包括曲线方程以及签名运算所需的一系列参数等,secp256k1被率先应用在比特币中,关于它的参数细节可见secp256k1,其中所指定的曲线方程为y^2 = x^3 + 7,它的形状如下图所示:


    在go-ethereum源代码中,路径在/crypto/下的代码包负责所有与加密相关的操作,libsecp256k1库的源代码也在其中/secp256k1/的子路径下存放,待编译后以C++库文件的方式被调用。

    处理数字签名

    以go-ethereum中交易对象的代码为例,与ECDSA签名相关的操作,都被放在一个名叫Signer的接口以及它的实现体里了。


    接口<Signer>声明的方法中,Sender()用来从tx对象携带的数字签名里解析出公钥并转换成Address类型变量;SignatureValues()从tx对象里取出数字签名的三个部分R,S,V;Hash()返回当前tx对象需要做数字签名的内容,即tx对象中的部分成员变量作RLP编码后取Hash值;Equal()用来比较Signer实现体对象。由此可见,<Signer>接口及其实现体主要提供对已生成数字签名进行操作的方法,

    Signer的三个实现类中,HomesteadSigner通过持有FrontierSigner对象,可以节省代码。关于EIP155: EIP(Ethereum Improvement Proposals,EIP)是Ethereum的需求汇总。EIP155是其中一个比较重要的需求,加入了一种抵御重现攻击(Replay Attack)的简单方法,要求在对tx作签名(或恢复签名时),在Hash(*Transaction)函数里的RLP编码环节多选择几个成员变量,所以EIP155Signer中的Hash()是重新定义的。

    从数字签名中恢复出公钥(地址)

    从数字签名中恢复(解析)出地址变量的函数叫recoverPlain():

    // core/types/transaction_signing.go
    func recoverPlain(sighash common.Hash, R, S, Vb *big.Int, homestead bool) (common.Address, error) {
        V := byte(Vb.Uint64() - 27)
        if !crypto.ValidateSignatureValues(V, R, S, homestead) {
            return common.Address{}, ErrInvalidSig
        }
    // encode signature in uncompressed format
        r, s := R.Bytes(), S.Bytes()
        sig := make([]byte, 65)
        copy(sig[32-len(r):32], r)
        copy(sig[64-len(s):64], s)
        sig[64] = V
    // recover the public key from the signature
        pub, err := crypto.Ecrecover(sighash[:], sig)
        if err != nil || len(pub) == 0 || pub[0] != 4 {
            return common.Address{}, err
        }
    // convert pubKey to Address
        var addr common.Address
        copy(addr[:], crypto.Keccak256(pub[1:])[12:])
        return addr, nil
    }
    上述recoverPlain()的函数体中,

    首先调用crypto.ValidateSignatureValues()来验证数字签名是否正确有效,crypto包的这个方法正是通过调用libsecp256k1库的API,遵循ECDSA算法理论中有关数字签名验证部分来完成的;

    其次,将R,S,V拼接出所需的数字签名字符串;

    接着,调用crypto.Ecrecover(),凭借被数字签名的内容sighash和签名字符串sig,从中恢复出数字签名所用的公钥,当然,crypto包的方法依然调用libsecp256k1库的API来完成;

    最后,在返回的公钥里,去掉标志头所在的第一个byte(值为4),生成它的SHA-3(256 bits)哈希值,再截取其中的后20bytes,此即最终返回的Address类型变量。

    生成数字签名

    针对某个tx对象生成数字签名的函数叫SignTx()

    // core/types/transaction_signing.go
    func SignTx(tx *Transaction, s Signer, prv *ecdsa.PrivateKey) (*Transaction, error) {
        h := s.Hash(tx)
        sig, err := crypto.Sign(h[:], prv)
        if err != nil {
            return nil, err
        }
        return tx.WithSignature(s, sig)
    }
    从SignTx()函数体可以看出,在Signer.Hash()方法提供要签名的内容(即Transaction对象的部分成员RLP编码后哈希)后,生成签名的主要工作交给crypto.Sign()函数来完成。该Sign()的函数体如下:

    // /crypto/signature_cgo.go
    func Sign(hash []byte, prv *ecdsa.PrivateKey) (sig []byte, err error) {
        if len(hash) != 32 {
            return nil, fmt.Errorf(...)  // hash must be 32 bytes
        }
        seckey := math.PaddedBigBytes(prv.D, n:prv.Params().BitSize/8)
        defer zeroBytes(seckey)
        return secp256k1.Sign(hash, seckey)
    }

    可见crypto.Sign()函数正是通过调用libsecp256k1库的API来完成椭圆曲线数字签名的生成。

    公钥和地址

    以太坊中用到的Address类型地址变量,比如每个账户的地址,都来自于椭圆曲线数字签名用的公钥。在数字签名中,公钥可以在多次签名中重复使用,这反映到以太坊的账户上,就是一个账户下的多次交易,即多个不同的Transaction对象,它们所作的数字签名均使用同一个公钥。

    具体到变量类型上,Address类型是一个长度为20 bytes的字符串,而椭圆曲线数字签名中的公钥,原生含义应该是曲线上的一个点的坐标(X, Y),那么它们之间必然存在格式上的相互转换。在代码中,这涉及到三种不同格式(类型):地址变量是Address类型,长度为20bytes的字符串;publicKey变量是一个字符串,长度未知;椭圆曲线上的公钥,是一个点的坐标,在ecdsa.PublicKey{}中以成员X,Y表示。

    publicKey变量转换成Address类型,在之前提到的core.types.recoverPlain()函数体里介绍过(函数末尾)。

    publicKey字符串类型和ecdsa.PublicKey{}类型的格式转换函数,由crypto代码包定义。

    // crypto/crypto.go
    func ToECDSAPub(pub []byte) *ecdsa.PublicKey {
        x, y := elliptic.Unmarshall(S256(), pub)
        return &ecdsa.PublicKey{Curve:S256(), X:x, Y:y}
    }
    func FromECDSAPub(pub *ecdsa.PublicKey) []byte {
        return elliptic.Marshall(S256(), pub.X, pub.Y)
    }
    
    crypto.ToECDSAPub()函数将一个publicKey的字符串转换成ecdsa.PublicKey{}类型中的点坐标X,Y的形式,FromECDSAPub()函数作相反的操作。所调用的elliptic.Unmarshall()函数的逻辑也很简单,就是将[]byte字符串去掉标志头后,均分成两段,分别赋值给X和Y,然后再由[]byte转换成big.Int,就成了。

    ps, 上述代码中的S256(),是本地代码写的一个转换函数,返回一个elliptic.Curve接口的实现类,它基于secp256k1的椭圆曲线参数,自己实现了<Curve>接口声明的所有曲线操作函数,以方便用go语言包中的结构体/接口类型,去使用secp256k1椭圆曲线。

    小结:

    • 以太坊中的数字签名全部采用椭圆曲线数字加密算法(ECDSA), 它的理论基础是椭圆曲线密码学(ECC),而ECC存在的理论基础是点倍积(point multiplication)算式 Q = dP 中的私钥 d (几乎)不可能被破译。ECC相对于基于大质数分解的RSA,在提供相同安全级别的情况下,仅需长度更短的公钥
    • 以太坊中调用的椭圆曲线数字签名算法实现,来自己libsecp256k1库,这是一个针对特定椭圆曲线secp256k1的、经过优化的C++库,并早已被比特币系统采用。
    • 以太坊中的使用的Address类型,比如每个账户的地址,均来自于椭圆曲线数字签名的公钥
    展开全文
  • 有研究数字签名的同学可以来看一下,关于椭圆曲线的数字签名方面的研究
  • 在VC平台上用C语言实现了一种基于椭圆曲线密码体制数字签名方案,这种方案是建立在目前还没有有效攻击方法有限域上椭圆曲线离散对数问题上,从理论上来说这个方案是安全,并且具有一定实用价值。...
  • 椭圆曲线密码及其在电子商务中的应用 信息安全
  • 椭圆曲线密码体制在SET协议中的应用 哈尔滨工程大学计算机科学与技术学院(150001) 张国印 施 勇 随着Internet的蓬勃发展,电子商务交易的安全性正逐渐引起人们的重视。两大信用卡公司Visa和Mastercard联合推出了基于...
  • 椭圆曲线加密算法在PKI中的应用.pdf
  • 椭圆曲线密码体制在无线城域网中的应用 是信息安全研究的主要内容
  • 椭圆曲线密码及其在无线网络中的应用,一种加密方案。主要运用于无线网络。
  • MMX-椭圆曲线及其在密码学中的应用(英文).pdf 英文本的书籍
  • 椭圆曲线加密算法及其在PKI中应用模型研究
  • 随着信息技术高速发展,人们对信息安全要求越来越高;与此同时日益增强计算能力...经过20年研究,椭圆曲线密码体系开始从学术理论研究阶段逐步走向实际应用阶段,成为目前最被看好最有前途一种公钥密码体系。
  • 椭圆曲线加密

    2019-04-29 20:53:44
    椭圆曲线加密 椭圆曲线加密(ECC)最大的优点就是使用比RSA短得多的密钥得到相同的安全性,因此可以减少...在有限群上的椭圆曲线在计算上没有显而易见的几何解释,但是可以将实数域上的椭圆曲线的几何解释移植过来...

    椭圆曲线加密

    椭圆曲线加密(ECC)最大的优点就是使用比RSA短得多的密钥得到相同的安全性,因此可以减少处理负荷,使公钥密码的应用领域得到拓展。

    基本原理:

    椭圆曲线密码体制使用了在有限Abel群(Zp或者GF(2m))上构造的椭圆曲线,椭圆曲线在有限群的加法符号定义下成为一个单向陷门函数。

    在有限群上的椭圆曲线在计算上没有显而易见的几何解释,但是可以将实数域上的椭圆曲线的几何解释移植过来。为了方便理解,先从实数域上的椭圆曲线开始讲解

    1.  实数域上的椭圆曲线

    椭圆曲线并不是椭圆,而是与椭圆周长的方程相似的三次方程。一般,椭圆曲线方程形为:

        y2 + axy + by = x3 + cx2 + dx + e

    对我们而言将方程限制为以下形式就已足够:

        y2 = x3 + ax + b                 (10.1)

    对于给定的a和b,对x的每一个值,需画出y的正值和负值。

     

    构造Abel群

    将满足式(10.1)的所有点(x , y)和元素O(称为无穷远点或者零点的元素,后面会讨论这个概念)所组成的点集E(a , b)。上图中两条曲线分别可用集合E(-1 , 0)和E(1 , 1)表示。

    若式(10.1)里的参数a和b满足  

        4a3 + 27b2 ≠ 0                    (10.2)

    则基于集合E(a , b)可以定义一个可交换群(Abel群),其加法的运算规则如下:

      1、O是加法的单位元,有O = -O;对椭圆曲线上任何一点P,有P + O = P

      2、点P (x , y)的负元-P = (x , -y)。注意这两点可以用一条垂直的线连接起来,并且P + (-P) = P - P = O

      3、要计算坐标不同的P和Q之和,则在P和Q间作一条直线并找到与曲线的第三个交点R(显然存在唯一的交点R,除非这条直线与P或者Q相切,此时分别取R = P或者R = Q,与下述5相一致)。并定义如下三点上的加法:P + Q = -R。也就是,定义P + Q 为第三个交点相对于x轴的镜像

      4、上述术语的几何解释也适用于具有相同x坐标的两个点P和 -P的情形。用一条垂直的线连接这两点,这可视为在无穷远点与曲线相交,因此有P + (-P) = O,与上述2相一致。

      5、为计算点Q的两倍,画一条切线并找到另一交点S,则Q + Q = 2Q = -S。

    加法的结论

      1、对于不是互为负元的两个不同点P = (xP , yP) 和 Q = (xQ , yQ),连接它们的直线的斜率Δ= (yQ - yP)/(xQ - xP),我们可用如下表示和R = P + Q

        xR =Δ2 - xP - xQ

        yR =Δ(xP - xR) - yP                (10.3)

      2、计算一个点与它自身相加:P + P = 2P = R,则表达式为

        

     

    2.  Zp上的椭圆曲线

    对于Zp上的素曲线,我们使用三次方程,p为素数,其中的变量和系数自集合{0,1,···,p-1}取值,运算为模p运算。

    对Zp上的椭圆曲线,如同实数情形一样,方程如下:

        y2 mod p = (x3 + ax + b) mod p         (10.5)

    可以证明,若(x3 + ax + b) mod p无重复因子,则基于集合Ep(a , b)可定义一个有限Abel群,这等价于以下条件:

        (4a3 + 27b2) mod p ≠ 0             (10.6)

    注意,(10.6)与(10.2)具有相同的形式

     

    Ep(a , b)上的加法运算构造与定义在实数上的椭圆曲线中的描述的代数方法是一致的。对任何点P , Q∈Ep(a , b)

      1、P + O = P

      2、若P = (xP , yP),则点(xP , -yP)是P的负元,记为 -P。例如对E23(1 , 1)上的点P = (13 , 7),有 -P = (13 , -7),而 -7 mod 23 = 16,因此,-P = (13 , 16),该点也在E23(1 , 1)上。

      3、若P = (xP , yP),Q = (xQ , yQ),且P ≠ -Q则R = P + Q = (xR , yR)由下列规则确定:

        xR =λ2 - xP - xQ

        yR =λ(xP - xR) - yP

        其中

        

      4、乘法定义为重复相加。如4P = P + P + P + P

     

     

    为了确定各种椭圆曲线密码的安全性,需要知道定义在椭圆曲线上的有限Abel群中点的个数。在有限群Ep(a , b)中,点的个数N的范围是

     

        p + 1 - 2p1/2 ≤ N ≤ p + 1 + 2p1/2

     

    所以,Ep(a , b)上点的个数约等于Zp中元素的个数,即p个元素。

     

     

    3.  GF(2m)上的椭圆曲线

     

    对于GF(2m)上的椭圆曲线,其变量和系数在GF(2m)内取值,且运算为GF(2m)里的运算。可以证明,GF(2m)上适合于椭圆曲线密码应用的三次方程与Zp上的三次方程有所不同,其形为:

     

        y2 + xy = x3 + ax2 + b                   (10.7)

     

    可以证明,只要b ≠ 0,则可基于集合E2m(a , b)可定义一个有限Abel群。对任何点P , Q∈E2m(a , b),加法的运算规则如下:

     

      1、P + O = P

     

      2、若P = (xP , yP),则P + (xP , xP + yP) = O。点(xP , xP + yP)是P的负元,记为 -P。

     

      3、若P = (xP , yP),Q = (xQ , yQ),且P ≠ -Q,P ≠ Q则R = P + Q = (xR , yR)由下列规则确定:

     

        xR =λ2 +λ+ xP + xQ + a

     

        yR =λ(xP + xR) + xR + yP

     

        其中

        

      

      4、若P = (xP , yP),则R = 2P = (xR , yR)由下列规则确定:

        xR =λ2 + λ+ a

        yR =xP2 + (λ + 1)xR

        其中

        λ= xP + yP/xP 

     

    椭圆曲线密码学

    考虑方程Q = kP,其中Q,P∈Ep(a , b),对给定的k和P计算Q比较容易,而对给定的Q和P计算k则很困难,这就是椭圆曲线的离散对数问题。

    用椭圆曲线实现Diffie-Hellman密钥交换

    首先,挑选一个大整数q以及式(10.5)或式(10.7)中的椭圆曲线参数a和b,这里q为素数p或者是形为2m的整数。由此可以定义出点的椭圆群Eq(a , b)

    其次,在Eq(a , b)中挑选基点G = (x1 , y1),G的阶为一个非常大的数n。椭圆曲线上的点G的阶n是使nG = 0 成立的最小正整数。Eq(a , b)和G是该密码体制中通信各方均已知的参数

    用户A和用户B之间完成密钥交换过程如下:

      1、A选择一个小于n的整数nA作为其私钥,然后产生其公钥PA = nA × G。该公钥是Eq(a , b)中的一个点。B也类似地选择私钥nB并计算公钥PB

      2、A产生秘密钥k = nA × PB,B产生秘密钥k = nB × PA

        nA × PB = nA × (nB × G) = nB × (nA × G) = nB × PA

    要破译这种体制,攻击者必须由G和kG计算k,这被认为很难。

    椭圆曲线加/解密

    首先,我们必须将要发送的消息明文m编码为形为(x , y)的点Pm,并对点Pm进行加密和其后的解密。注意,不能简单地将消息编码为点的x坐标或y坐标,因为并不是左右的坐标都在Eq(a , b)中。将消息m编码为点Pm的方法有很多种,存在比较直接的编码方法。

    像密钥交换系统一样,加/解密系统也需要点G和椭圆群Eq(a , b)这些参数。每个用户选择一个私钥n,并产生公钥P = n × G

    若A要将消息Pm加密后发送给B,则A随机选择一个正整数k,并产生密文Cm,该密文是一个点对:

        Cm = {kG , Pm + kPB}

    注意,此处A使用了B的公钥PB,B要对密文解密,则需用第二个点减去第一个点与B的私钥之积:

        Pm + kPB - nB(kG) = Pm + k(nBG) - nB(kG) = Pm

    椭圆曲线密码的安全性

    ECC的安全性是建立在由kP和P确定k的困难程度之上的,这个问题称为椭圆曲线对数问题。Pollard rho方法是已知的求椭圆曲线对数最快的方法。下表从密码分析所需计算量的角度,通过给出可比较的密钥大小,比较了各种算法。在密钥长度相同时,ECC和RSA所执行的计算量差不多。因此,与具有同等安全性的RSA相比,由于ECC使用的密钥更短,所以ECC所需的计算量比RSA更小。

     

     

    基于非对称密码的伪随机数生成器

    由于非对称算法的速度比对称算法明显慢一些,所以非对称算法不用于生成可扩展的PRNG流,但是,对于生成短的伪随机序列,创建伪随机函数(PRT),非对称的方法还是很有用的。

    Micali-Schnorr PRNG

     

    该PRNG定义如下:

    创建   选择素数p,q;n = pq;φ(n) = (p - 1)(q - 1),选择e使得gcd(e ,φ(n)) = 1。此外N =└log2n┘ + 1(n的位长度)。选择r,k使得r + k = N

    种子   选择位长度为r的随机种子x0

    生成   生成一个长为k × n的伪随机序列,将i从1到m,计算

          yi = xi-1e mod n

          xi = r , yi的最高有效位

          zi = k , yi的最低有效位

    输出   输出序列为z1 || z2 || ··· || zm 

     

    参数n,r,e,k的选择要遵循下面6个要求:

      1、n = pq               n是两个素数的乘积,在RSA中则是密码长度

      2、1 < e < φ(n) ;gcd(e ,φ(n) ) = 1        确保映射s -> se mod n是一对一的

      3、re ≥ 2N               确保求幂运算是有取模过程

      4、r ≥ 2                 防止密码攻击

      5、k,r是8的倍数             应用方便

      6、k ≥ 8;r + k = N              所有位都有效

     

     

     

    展开全文
  • 一种应用椭圆曲线密码体制改进型密钥协商方案,张轩,,椭圆曲线密码体制(ECC)作为一种高强度公钥加密算法广泛应用于各种通信领域。而在此基础上实现密钥协商方案ECDH,ECMQV由于存在
  • 安全椭圆曲线在密码学中有重要的应用,如何选择十分重要。
  • 鉴于椭圆曲线密码高度安全性,利用椭圆曲线生成伪随机序列得到了高度重视,但目前研究主要集中在素域上的椭圆曲线。该文在定义于扩张域上的椭圆曲线上,定义取值在[0,1)区间上伪随机数,并利用这类伪随机数给出...
  • 详细阐述了椭圆曲线密码系统的安全性及其理论,讨论了在有限域F2 n上寻找安全椭圆曲线的基本思想,并利用Eadic的基本思想给出了在特征为2的有限域F2 n上构造安全椭圆曲线的有效算法,设计实现了该算法并获得了实验...
  • 为了增强代理签名的安全性,在分析现有代理签名方案的基础上,提出了一种基于超椭圆曲线的代理签名方案。同时对该方案的安全性进行了分析。本方案通过将代理签名算法移植入超椭圆曲线密码体制,构造出一种基于超椭圆...
  • 椭圆曲线密码学(ECC),是一种基于椭圆曲线数学诞生非对称秘钥加密算法,加密过后只有特定人才能对其进行解密。例如,ECC可用于确保用户在发送电子邮件时,除了收件人之外,没有人可以阅读这封邮件。 椭圆...
  • 分析超椭圆曲线Jacobian 离散对数问题,提出一种新的基于超椭圆曲线的顺序多重盲数字签名方案,该方案同时满足顺序多重签名和盲签名的特点,可广泛应用于数字签名领域。对超椭圆曲线密码体制的分析结果证明了该方案...
  • 重点分析了ECC在移动电子商务安全WPKI中加密及签名算法方面的改进和应用,并在ECC原理与WPKI体系结构的基础上,探讨了ECC在WPKI体系中WTLS证书、无线身份识别模块及WTLS协议的应用,最后论述了基于ECC的身份认证方案...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 871
精华内容 348
关键字:

椭圆曲线的应用