本文目录一览:
ECDSA(椭圆曲线数字签名算法)
ECDSA(Elliptic Curve Digital Signature Algorithm)
在现实工作和生活中,我们使用签名的方式表达对一份文件的认可,其他人可以识别出你的签名并且无法伪造你的签名。数字签名就是对显示签名的一种电子实现,它不仅可以完全达到现实签名的特点,甚至能够做的更好。
常用的数字签名算法有RSA(Rivest-Shamir-Adleman Scheme)、DSS(Digital Signature Standard)等。 比特币使用ECDSA来生成账户的公私钥以及对交易和区块进行验证。
1.Alice(密码学中常用A到Z开头的人名代替甲乙丙丁等,字母越靠后出现频率越低)生成一对密钥,一个是sk(signing key),是非公开的;另一个是vk(verification key),是公开的。
这一对密钥同时生成,并且在数学上是相互关联的,同时,根据vk无法推测出关于sk的任何信息。
2.数字签名算法接收两个输出:信息M和sk,生成一个数字签名Sm
3.验证函数接收信息M、Sm以及vk作为输入,,返回结果是yes或者no。这一步的目的是为了验证你看到的针对信息M的数字签名确实是由Alice的sk来签发的,用于确认信息与签名是否相符。
与手写签名不同,手写签名基本都是相似的,但是数字签名却受输入影响很大。对输入轻微的改变都会产生一个完全不同的数字签名。一般不会对信息直接进行数字签名,而是对信息的哈希值进行签名。由加密哈希函数的无碰撞性可知,这样和对原信息进行签名一样安全。
在数学上,任何满足以下方程的点所形成的曲线称为随机椭圆曲线: 并且 ,a和b可以为任意值。下面展示几个随机椭圆函数的示例:
在了解如何通过基于secp256k1椭圆曲线的ECDSA算法生成公私钥之前,我们需要了解在随机椭圆曲线里,点的加法是如何实现的。
首先定义椭圆曲线上点的加法。设椭圆曲线上有两点,A和B点,那么作过这两点的直线与该曲线相交于第三点(C点),然后关于X轴对称得到D点,则D为这两个点的和,记作D=A+BD=A+BD=A+B。很明显,D点也在该曲线上。所以椭圆曲线上两点之和也是曲线上的点。
特例:
1.如果两点重合,则做该点的切线,与曲线相交点的对称点为和,即A+A=C
如图:
有了加法以后,乘法实现是不过是进行多次加法运算。有了一个基准点P以后,我们可以对其进行乘法运算,最后可以得到曲线上的另外一个点。
设PPP是椭圆曲线上的一个点,那么正整数kkk乘以点PPP的结果由下面的式子定义,注意式子中的加法是上面提到的椭圆曲线上点的加法:
点的运算满足结合律:
很显然,通过累加 的方式计算 是一种很笨的办法,其时间复杂度是线性的。上面我们提到过,椭圆曲线上点的加法是满足结合律的,即 ,扩展一下,就有
于是就有这么一种骚操作,比如计算 ,我们可以先计算 ;然后计算 ;再计算 ;最后计算 。这里我们把15次加法减少到了4次。
当然,k的值不可能总是2的幂。实际上上面的操作可以推广到k为任意正整数的情况。比如计算23P,首先计算 ,然后
因为 ,所以 。总共只需要7次加法。
分析一下,对于任意正整数k,我们都可以利用这个方法将计算k∗P所需的加法计算次数降低到
也就是说,从时间复杂度的角度来看,这个算法是一个 的算法。
这个方法被称为快速幂算法,原本常用于快速计算某个数的k次幂,这里将其推广到椭圆曲线点乘的快速计算中。
为什么要在介绍了椭圆曲线上点的乘法后突然冒出一个快速幂算法?快速幂算法对于椭圆曲线加密有什么意义?因为数学家/密码学家发现,利用快速幂算法计算 的时间复杂度是对数级的,但是要在知道 和 的前提下,倒推出 的值,没有比挨个尝试 的值快太多的算法。于是椭圆曲线加密依赖的数学难题就这么诞生了。
如果我们改一种记法,把椭圆曲线上点的加法记作乘法,原来的乘法就变成了幂运算,那么上述难题的形式跟离散对数问题应该是一致的。即:
所以这个难题叫椭圆曲线上的离散对数问题。
尽管两者形式一致,但是他们并不等价。实际上这个问题比大整数质因子分解(RSA)和离散对数(DH)难题都要难得多,目前还没有出现亚指数级时间复杂度的算法(大整数质因子分解和离散对数问题都有),以致于同样的安全强度下,椭圆曲线加密的密钥比RSA和DH的短不少,这是椭圆曲线加密的一大优势。
假设随机取一个 ~ 位之间的值x,计算 ,最后的结果一定会落在曲线上的一点。假设该点为 ,在公开 以及具体曲线的方程的情况下,能否反推出最初的随机值 ?
证:寻找 的过程只能通过暴力计算, 的可能值为 ~ 中的一个,平均来说需要计算 次能够找到一次 值。那么问题来了,运行一次 的计算需要多长的时间呢?
假设我们使用的是超级计算机,主频为 (一秒钟可以进行一万亿次运算),从宇宙诞生的那一刻开始计算,到现在也就进行了 次。找到 值的概率为 。这个概率和下一秒地球被巨型陨石撞击而毁灭的概率接近,既然我们读到了这里,那么说明这件事没有发生。
在上面的案例中, 是 ~ 位的一个随机数,可以作为私钥。 是随机椭圆曲线上的一个点,也就是由私钥生成的公钥,因此优点可以1得证。
但是密码学中,并不能使用上面介绍的实数域上的椭圆曲线。因为
所以我们需要引入有限域上的椭圆曲线。
要证明优点2,还需要将随机椭圆曲线做一些改动:为了保证最后计算出来的点的坐标值相加是512位,secp256k1引入了一个对质数取模的机制。具体来说,随机椭圆曲线从
变为了 其中 ,是小于 的最大质数。
此时的随机椭圆曲线函数图如下:
具体来说,就是向别人证明我知道 ,但不暴露 的任何信息。(有些类似于零知识证明)
证:前面介绍过结合律: 添加一个hash函数,简单修改可以得出: 使 ,那么可知 为 。此时方程为: 为了简单起见,我们记 和 。此时方程化简为: 上面这个方程是什么意思呢?
可以这样假设:在已知 的情况下,如果能够提供一个 和 满足上面的方程,就可以证明一个人拥有 。这个假设有一个前提,如果一个人不知道x,那么他就无法提供 和 满足上面的等式。
详细探讨这个前提:如果一个人不知道x,又想计算出 和 ,能够办到吗?结论是不能,首先我们无法从 计算出 (在有限时间内)。
还有一个问题:在已知 和 的情况下,能否计算出关于 的任何信息?
根据公式: 只要解出 就可以了。
要想计算出x,就需要知道r,但是在r没有公开的情况下,有什么办法可以计算r吗?我们知道R=r*P;但是根据这个公式无法倒推出r(刚才介绍的那个数学难题),所以x也是安全的。
至此,可以证明算法的第二个优点。
ecdsa算法是不是只能用于签名而不能用于加密文件?
ECDSA只能用于签名,但是有一种基于ECC的方法可以实现公钥加密
首先选好曲线Ep(a,b,G,n,h),随机选取私钥k,计算公钥:K=kG,信息被编码在点M上
加密:随机选取r,密文为(rG,M+rK)
解密:计算(M+rK)-k(rG),因为它等于(M+rK)-r(kG)=M+rK-rK=M
[译]你知道ECDSA是如何保护你的数据的么?
每个人都可能以某种形式听说过ECDSA。当我说“数字签名”时,有些哥们会更好地认识到这一点,当然有些哥们根本不知道我在说什么。
我曾经试着去了解ECDSA是如何工作的,但很难搞清楚,因为大多数在线参考文献是不够的。他们要么是太基本了 - 他们只是解释算法的基础知识, 或者他们太牛叉-“它是如何工作的?” 。所以你在“它是如何工作的”和“我们是如何到达这里的?”之间挣扎着。所以,如果你没有数学或密码学的学位,但仍然想知道它是如何工作的(除非“奇迹发生,或者你是天才”),那么,恭喜你,你来对地方了。
ECDSA 全称 “ Elliptic Curve Digital Signature Algorithm ”,它用于创建数据的数字签名(例如文件),以便在不影响安全性的情况下验证其真实性。把它想象成一个真实的签名,你可以识别某人的签名,但是如果没有其他人知道你就不能伪造它。 ECDSA签名与真实签名之间的区别在于,伪造ECDSA签名是不可能的。
理解 ECDSA 要注意区分其与用于加密数据的 AES(高级加密标准)的区别。ECDSA不会加密或阻止某人查看或访问你的数据,但它可以防止数据被篡改。
在“ECDSA”这里有两个词值得注意,那就是“曲线”和“算法”,因为这意味着 ECDSA 基本上都是关于数学的。所以我认为首先要说:“嗨,兄弟们,你现在还在扯学的那些高数完全没有什么卵用么!“ECDSA涉及到的数学是相当复杂的,所以我尽量庸俗化,让非技术人员可以理解,但你仍然可能需要一些在数学知识正确理解。下面,我将分两部分来处理,一部分是关于它是如何工作的一个高层次的解释,另一部分是深入理解其内部的工作原理。
其实原理很简单,你拿出纸来,绘制一个数学上的曲线方程,然后你在该曲线上随机选择一点作为你起始的点,然后你生成一个随机数,这是你的私钥,你用这个随机数和“起点”来做一些神奇的数学方程,并且在曲线上得到第二个点,那就是你的公钥。
当你想签署一个文件时,你将使用这个私钥(随机数)和一个散列的文件(一个唯一的数字来表示文件)为一个神奇的方程,这会给你你的签名。签名本身分为两部分,分别称为R和S.为了验证签名是否正确,您只需要公钥(使用私钥生成的曲线上的那个点),然后将其放入另一个神奇的方程与签名的一部分(S),如果它使用私钥正确签名,它会给你另一部分的签名(R)。所以为了简短起见,一个签名由两个数字R和S组成,你用一个私钥生成R和S,如果一个使用公钥和S的数学方程给你R,那么签名是有效的。没有办法知道私钥或仅使用公钥创建签名。
OK,目前你只了解了一点基础知识,你或许没意识到,ECDSA 是复杂的,公钥、私钥又是什么鬼?别担心,你马上就会明白,但首先解释一下,为什么使用ECDSA以及它可能有什么用?
除了上述提到的“我需要签署合同/文件”之外,下面是一些别的用例:例如,我们不希望其数据被用户破坏或修改,例如只允许用户你加载官方地图但不可以进入国防部或电话或其他类型的设备,只允许你安装官方的应用程序。
在这种情况下,文件(应用程序,游戏地图,数据)将用 ECDSA 签名,公钥将与应用程序/游戏/设备捆绑在一起并验证签名,以确保数据没有被修改,而私钥被锁在一个安全的地方。虽然你可以使用公钥验证签名,但是你不能用它创建/伪造一个新的签名,那么这个公钥就可以随应用/游戏/设备一起分发,而不用担心。
这与AES加密系统不同,后者允许您对数据进行加密,但您需要密钥进行解密,而这样的应用程序需要捆绑你的密钥。
一个很好的例子就是PlayStation 3游戏机被打开了,所有的文件都可以被解密,PS3文件中的所有密钥都可以被提取出来,但是还有一件东西需要破解,就是ECDSA签名,它可以防止任何人使应用程序运行在最新的固件上
再通俗一点的解释,http与https的区别,我们拥有一个SA认证机构,私钥拿在自己手里,公钥广播出去,我拿私钥验证公钥(这个仅仅是用来理解公钥和私钥,到此为止啊)。
OK,接下来建议你备好垃圾桶,可能会感到恶心或者不适。
让我们从基本知识开始(对于知道这个知识的人可能是无聊的,但对于那些不了解的人是必须的):ECDSA只使用整数数学,没有浮点数(这意味着可能的值是1,2,3等等,但不是1.5, 2.5等),而且数字的范围受到签名中使用多少比特的限制(更多比特意味着更大的数字,更高的安全性,因为猜测变得更难(在这个等式中使用的关键数字)。计算机使用“位”来表示数据,一位是二进制符号(0和1)中的“数字”,而8位代表一个字节。每增加一位,可以表示的最大数量加倍,4位可以表示0到15(总共16个可能的值),5位可以表示32位数值,6位,您可以表示64个值等。一个字节(8位)可以表示256个值,32位可以表示4294967296个值(4千兆)。通常ECDSA将使用总共160位,嗯哼,一个 49 位大的数字.....
你需要知道的另一个数学结构是模数,可以通过说它是整数的其余部分来简化模数。例如,x mod 10意味着x除以10的其余部分,它将始终是0和9之间的数字,所以142 mod 10例如给出2。另一个例子是x mod 2,其中偶数和0分别为0和1。
ECDSA 与消息的 SHA1 加密散列一起使用来签名(文件)。哈希是另一个数学方程式,适用于每个数据字节,这将给一个数据唯一的数字。例如,所有字节的值的总和可以被认为是非常 low 的散列函数。所以如果消息(文件)有任何变化,那么哈希将是完全不同的。在 SHA1 哈希算法的情况下,它总是 20 个字节(160位)。这对于验证文件没有被修改或损坏是非常有用的,对于任何大小的文件,你都会得到 20 字节的哈希值,你可以轻松地重新计算哈希值以确保匹配。 ECDSA 所标记的实际上就是散列,所以如果数据发生变化,散列会发生变化,而且签名不再有效。
为了理解,我们来一个例子。我们将使用最简单的(和最 low 的)散列函数,其中我们将所有数据的总和作为结果的模数10。
首先,你需要明白一点,世间万物将被用一个数字来表示。一个文本文件是一系列的字节,正如我们前面所解释的,它代表了8位,这意味着它可以表示一个介于0和255之间的数字。所以,如果我们将每个字节作为一个数字并添加文件的每个字节,那么我们结果为 10 的模数,我们将以 0 到 9 之间的数字作为结果散列。数据相同,我们将总是得到相同的哈希值,如果更改了文件中的一个字节,结果可能会不同。当然,你也会明白,为了获得相同的散列值,改变文件将是非常容易的,因为只有10种可能性(0到9),那么就有十分之一的机会获得相同的散列值通过改变文件的内容。
这就是 SHA1 起作用的地方,SHA1 算法比我们简单的“模数 10 ”散列函数复杂得多,它将给出非常大的数字(160位,所以是一个十进制的49位数),它的特殊性使得我们如果从文件中修改了一位数据,结果就会彻底改变。
这使得 SHA1 成为一个非常好的哈希算法,这种算法是不可预知的,这是非常安全的,并且几乎不可能得到“冲突”(当两个不同的文件具有相同的哈希),并且不可能伪造数据来获得特定的哈希,如果你 OK 的话,不要听我逼逼了,建议你参加最强大脑。
那么,它是如何工作的呢?ECDSA是基于下面的一个方程等式:
y^2 = (x^3 + a * x + b) mod p
你首先需要注意的是有一个模(mod),并且 'y' 是平方的(不要忘记这是图上曲线的方程)。这意味着对于任何x坐标(不要忘记,我们只使用整数),您将有两个y值,并且曲线在X轴上是对称的。该模是一个素数,并确保所有的值在160位的范围内,它允许使用“ modular square root ”和 “ modular multiplicative inverse ”
的数学,使计算的东西更容易。由于我们有一个模(p),这意味着 y ^ 2 的可能值在 0 和 p-1 之间,这之间便是所有可能的值。因为,ECDSA规定只能是整数,只有那些值较小的子集才能构成一个“完美平方”(两个整数的平方值),这给了 N 个可能的点,其中 N p(N 是数字 0 和 p 之间的完美平方)。到目前为止,你确定还能跟着我的思路么?哈哈,不着急,刚刚开始。。。)
由于每个 x 将产生两个点(y ^ 2的平方根的正值和负值),这意味着有 N / 2 个可能的 “x” 坐标是有效的,并在曲线上给出一个点。因为整数计算和模数的限制,所以符合这些条件的点在椭圆曲线上是有限的。
总结一下,然后再继续。 ECDSA方程为我们提供了一个有限数量的有效点的曲线(N),因为 Y 轴受模量(p)的约束,并且需要是在 X 轴上具有对称性的完美平方(y ^ 2) 。我们总共有 N / 2 个可能的,有效的 x坐 标,不要忘记 N p。
关于椭圆曲线你需要知道的另一件事是“点加法”的概念。它被定义为增加一个点 P 到另一个点 Q 将导致一个点 S,使得如果你绘制一条线从 P 到 Q,它将与第三个点 R 上的曲线相交,这是 S 的负值(记住该曲线在X轴上是对称的)。在这种情况下,我们定义了R = -S来表示R在X轴上的对称点。看上面的图来理解。
所以你可以看到一个形式为y ^ 2 = x ^ 3 + ax + b(其中a = -4和b = 0)的曲线,它在 X 轴上是对称的,其中 P + Q 是对称点 R 点是从 P 到 Q 的直线的第三个交点。
同样的,如果你做 P + P,它将是 R 的对称点,它是与点 P 相切的线的交点。P + P + P 是所得点之间的相加点由于 P + P + P可以写成(P + P)+ P,这就定义了“点乘法”,其中 k * P 是点 P 到点 K 的相加点。看看上面的两个图像点乘法的例子。
在这里,你可以看到两条椭圆曲线和一条从中画出切线的点 P,它与曲线相交于第三点,其对称点是 2P,然后从那里你从 2P 和 P 画出一条直线,会与曲线相交,对称点为3P。等等...你可以继续做点乘法。现在是否明白了为什么在进行加法时需要取 R 的对称点,因为相同点的多次加法总会给出相同的直线和相同的三个交点。
点乘法的一个特殊性是,如果你有一个点 R = k * P,那么你知道 R 并且知道 P,但是没有办法找出 'k' 的值是什么。由于没有点减法或点除法,所以不能只求解 k = R / P。另外,由于你可能做了数百万次的增加,你只能在曲线上的另一个点上,你不知道你是怎么到达的。你不能扭转这个操作,而且你找不到与你的点 P 相乘的值 “k”,给你的结果点 R.
即使你知道原始点和终点也不能找到被乘数的东西是ECDSA算法背后安全的基础,这个原理被称为 “ 陷阱门函数 “。
上面是对 ECDSA 的铺垫,接下来让我们认识一下 ECDSA 签名算法的庐山真面目。
对于 ECDSA,首先需要知道曲线参数,参数是 a,b,p,N 和 G. 您已经知道 a 和 b 是曲线函数的参数(y ^ 2 = x ^ 3 + ax + b),即 'p' 是质量模数,'N' 是曲线的点数,但也有 'G' 是ECDSA所需要的,它代表一个'参考点'或者你可以理解为一个起点。参考点可以是曲线上的任何点。
曲线上的参数是非常重要的,不知道它们,你显然不能签名或验证签名。是的,验证签名不仅仅是知道公钥,还需要知道公钥的派生参数。 NIST(美国国家标准技术研究院)和SECG(高效密码学标准组织)提供已知安全和高效的预制和标准化曲线参数。
所以首先,你将拥有一个私钥和一个公钥。私钥是一个随机数(也是160位),并且公钥是由 G 的点乘所生成的曲线上的一个点与私钥。我们把'dA'作为私钥(随机数)和'Qa'作为公钥(一个点),所以我们有:Qa = dA * G(其中G是曲线参数中的参考点)。
那么你如何签署一个文件/消息?
首先,你需要知道签名是 40 个字节,并且用两个 20 字节的值来表示,第一个被称为 R,第二个被称为 S ..所以这个对(R,S)一起是你的 ECDSA 签名..现在这里是如何创建这两个值,以签署一个文件..首先你必须生成一个随机值 'k'(20个),并使用点乘法来计算点 P = k * G。那个点的 x 值将代表 'R'。由于曲线 P 上的点由其坐标(x,y)表示(每个坐标长度为20个字节),因此只需要签名的 “x” 值(20个字节),该值将被称为“R” 。现在你需要的是 “S” 值。
为了计算 S,你必须做一个消息的 SHA1 哈希值,这会给你一个 20 字节的值,你会认为它是一个非常大的整数,我们称它为 'z'。现在你可以用下面的公式计算S:
S = k ^ -1(z + dA * R)mod p
这里注意到k ^ -1是k的 “模乘法逆”,它基本上是 k 的倒数,但由于我们正在处理整数,所以这是不可能的,所以它是一个数字,使得(k ^ -1 * k)mod p等于1.再次提醒,k 是用于生成 R 的随机数,z 是要签名的消息的哈希,dA 是私钥,R 是 k 的 x 坐标 * G(其中G是曲线参数的原点)。
现在你已经签名了,你想验证一下,它也很简单,你只需要公钥(当然是曲线参数)就可以做到这一点。你用这个公式来计算一个点P:
P = S ^ -1 * z * G + S ^ -1 * R * Qa
如果点P的x坐标等于R,表示签名有效,否则不是。
很简单,是吧?现在让我们看看为什么..这将需要一些数学来验证:
我们有 :
P = S ^ -1 * z * G + S ^ -1 * R * Qa
但是 Qa = dA * G,所以:
P = S ^ -1 * z * G + S ^ -1 * R * dA * G = S ^ -1(z + dA * R)* G
但是P的x坐标必须与R相匹配,而 R 是k * G的 x坐标,这意味着:
k * G = S ^ -1(z + dA * R)* G
我们可以通过删除G来简化:
k = S ^ -1(z + dA * R)
通过反转K和S,我们得到:
S = k ^ -1(z + dA * R)
这就是用来生成签名的公式。所以它是匹配的,这就是为什么你可以用上面第一个方程验证签名的原因。
你可以注意到,为了计算 S,您需要 'k'(随机数)和 'dA'(私钥),但只需要 R和 Qa(公钥)来验证签名。由于 R = k * G 和 Qa = dA * G,并且由于ECDSA 点乘法中的陷阱门函数(在步骤9中说明),所以我们不能通过知道 Qa 和 R 来计算 dA 或 k,这使得 ECDSA 算法是安全的,找不到私钥,没有办法在不知道私钥的情况下伪造签名。
所以你还记得产生一个签名所需的等式吧。 R = k * G 和 S = k ^ -1(z + dA * R) 模 p 这个等式的强度是事实上你有一个等式未知数(k和dA),所以无法确定其中之一。
然而,算法的安全性是基于其实现的,确保“k”是随机生成的,并且没有办法让某人可以猜测,计算或使用计时攻击或任何其他类型的攻击为了找到随机值'k'。但索尼在实现上犯了一个巨大的错误,他们在每个地方都使用相同的“k”值,这意味着如果你有两个相同的k,那么它们将具有相同的R值,这意味着您可以使用两个文件的两个S签名(分别为哈希z和z'以及签名S和S')来计算k:
S – S’ = k^-1 (z + dA*R) – k^-1 (z’ + da*R) = k^-1 (z + da*R – z’ -dA*R) = k^-1 (z – z’)
So : k = (z – z’) / (S – S’)
一旦你知道了k,那么S的方程就变成了一个方程,其中有一个未知数,然后很容易解析为dA:
dA =(S * k-z)/ R
一旦你知道了私钥dA,你现在就可以签名你的文件,PS3将把它识别为索尼签署的真实文件。这就是为什么确保用于生成签名的随机数实际上是“密码随机”的原因。这也是为什么不可能拥有高于 3.56 的自定义固件的原因,仅仅是因为自从 3.56 版本以来,索尼已经固定了他们的 ECDSA 算法实现并且使用了现在不可能找到私钥的新密钥。
这个问题的另一个例子是,当一些比特币客户端使用非密码随机数生成器(在某些浏览器和某些Android客户端上)导致他们使用相同的“k”值签名交易时,恶意人员能够找到他们的比特币钱包的私钥和窃取他们的资金。
这显示了每次签名时使用真正的随机数字的重要性,因为如果(R,S)签名对的R值在两个不同的签名上相同,您将公开私钥。
关于这个的一个笑话在xkcd漫画221(见上图)中显示,这成为了解释这个问题的前景。每当这种算法的执行错误发生时,图像经常被重新使用。
ECDSA算法是非常安全的,不可能找到私钥......只要实现正确完成就行了。如果有办法找到私钥,那么每个计算机,网站,系统的安全性可能会受到影响,因为很多系统都依靠 ECDSA 来保证安全性,这是不可能的。
但愿这能够帮助大家初步理解ECDSA算法,也希望对大家有所帮助。
原文链接: Understanding-how-ECDSA-protects-your-data
ECDSA的最简理解
y^2 = (x^3 + a * x + b) mod p
上述的曲线是在整数,一定bit数量(假设是160bit)内可以表达的,p是 160bits内可以表示的大整数。
为什么是这种曲线定义呢,我个人觉得有3个原因:
在椭圆曲线上随意取两个点 A,B,连接A,B两个点的直线与曲线的新的交点称为C,C关于X对称的-C点表示为 A+B。
乘法可以用加法表示,但是算法复杂堵是 log(n)。
其实为什么选择上述的椭圆曲线实际上是由这个加法规则选出来的,总是要求解这个新的交点更加简单。
R=k*P 的性质,已知R与P的值,无法推出k的值, 而知道k值于P值是很容易计算R值(log(n))。这是ECDSA签名算法的理论基础。
如何利用这个门限函数来做一个签名算法呢?
一个顺理成章的想法是: 给验证人一个 R和P,那只有签名人才能提供K,那K是不是可以作为一个签名指纹呢?
ok,咱先生成一个公私钥对, Qa = dA * G , Qa 就是公钥, dA 是一个随机数,就当是一个私钥吧,当然这个椭圆曲线的 a , b , p , G 值都是要公开的。这个 G 就是椭圆曲线上随机挑选的一个节点,我们叫原点,也是要公开的。
每次对一个数据做签名,都随机生成一个随机数 K 吧, P = K * G 。咱们把 P的x轴坐标R作为签名的一部分。另一部分签名数据叫 S 。
显然这个 S 既要和 dA 相关,也要和被签名的信息 z 相关。我们就假定:
S = Sig(dA, G, z, R, K) , 那这个函数就是签名函数。
而验证函数应该只有 S,R ,而不会有 K,dA
P = h(S, G, z, R) , h 就是签名函数。
密码学专家想到了一个实现:
S = k^-1 (z + dA * R) mod p
k^-1 表示的是关于p的模逆元。( k^-1 * k mod p = 1)。
可以推倒初验证函数:
== k = S^-1 (z + dA * R) mod p
== k*G = S^-1 (z + dA * R) *G
== P = S^-1*z*G + S^-1*dA*R*G
== P = S^-1*z*G + S^-1*R*Qa
对于验证者来说,需要计算: S^-1*z*G + S^-1*R*Qa 的x坐标是否就是 R 。
go的椭圆曲线 a 为固定的-3, 而 b 可以自由的选择,而p224, p256曲线的其实指的是 曲线的bit位数是224和256。
算法实现着为了更加快速地执行曲线上的加法和乘法,对笛卡尔坐标做了投射成(x,y,z)的雅各布坐标,投射关系:
可以加速在雅各布坐标系上的运算,在需要最终结果的时候再投射回笛卡尔坐标系。
一个曲线的表示:
公私钥对的表示:
可以看出曲线,公钥,私钥拥有的信息越来越全。
公钥是 曲线信息+ dA*G的信息。
私钥是 公钥信息 + dA信息。
美国国安局发布的曲线其实是 secp256k1 , 对于其参数其实没有很好的解释,大家猜测是国安局找到了这是一条弱化的椭圆曲线,因此BTC在设计之初也没有采用这个曲线,而是用了 Koblitz Curve , b 是7, a 是0,btcsuit的package中,对 KoblitzCurve 是golang的 curvparam 的一层封装(主要是为了加速),但是有更多的参数, 是因为a和b等参数都是预先设定的,增加更多的参数来加速计算。至于公私方法和golang基本一样。
Ed25519 从某种意义上来说也属于椭圆曲线密码学,不同的是它采用扭曲爱德华兹曲线作为椭圆曲线,同时采用的签名机制也不同于 ECDSA 算法。EdDSA 的重要实现 ED25519 是 Daniel J. Bernstein 等人设计的 EdDSA 算法,采用的曲线参数完全公开,并说明了参数选取的意义,保证曲线中并未内置后门。
曲线:
y^2 = (x^3 + x^2 + {一个很大的随机数}x ) mod p
他生成公私钥的流程有一些区别,seed作为私钥,seed计算出的hash值去和G相乘得到公钥,为了防止多次计算,把这部分公钥扩展到私钥的后面作为一个完整的私钥。计算签名的时候,普通ecdsa会生成一个随机数K,而ec25519为了避免伪随机数被猜测到,因此是私钥和msg的hash值作为这个随机数。