资讯专栏INFORMATION COLUMN

区块链的基石--椭圆曲线密码学

DoINsiSt / 1435人阅读

摘要:如果公式解析有问题,请移步备份链接椭圆曲线密码学椭圆曲线密码学是基于椭圆曲线数学的一种公钥加密方法。椭圆曲线数字签名什么是数字签名现实生活中的签名作用是签署者对文件进行授权防止交易中的抵赖发生。

如果SF公式解析有问题,请移步备份链接 https://blog.csdn.net/chenmo1... 椭圆曲线密码学

椭圆曲线密码学(ECC, Elliptic Curve Cryptography)是基于椭圆曲线数学的一种公钥加密方法。

什么是公钥加密方法

在诸如 DESAES 这类对称密码系统中,信息的发送方使用一把密钥进行加密,接收方使用相同的密钥进行解密。
而在公钥加密方法中,信息的加密和解密使用的密钥是不同的,称之为公钥私钥(注:既可以公钥加密私钥解密,也可以私钥加密公钥解密),常用的公钥加密方法有

RSA - 基于大因数分解

ECC - 基于椭圆曲线和离散对数

两者的理论基础都是数论理论中的单向运算函数,这种函数有一个特点:正方向计算容易,反方向计算却十分困难。以RSA背后的因数大数分解理论为例:
请完成下面的等式:

$$ 373 * 751 = ? $$

如果你有草稿纸和笔 ,会发现这并不是很困难,那么如果是下面因数分解呢?

$$ 280123 = ? * ? $$

太困难了 ! 即使是使用计算器,我觉得也没有谁一时半会儿也算不出来。

答案是 $373 * 751 = 280123$ ,这就是RSA的理论基础,两个质数(素数)的乘积很容易计算,但要将一个这样的乘积分解回去就困难了。ECC采用的与之类似,不同的是它采用的是离散对数问题(DLP,Discrete Logarithm Problem)制造单向计算的困难(稍后有例子)。

什么是椭圆曲线

我们在中学课本里一定都学过椭圆的定义。如下图所示,

椭圆上的点都满足

$$ ax^2 + by^2= c quad over , mathbb R $$

而密码学中的椭圆曲线是满足以下等式的点组成的集合,

$$ y^2 equiv x^3 + ax + b pmod p quad x,y in Bbb Z_p $$

加上一个想象中的无穷远点 $mathscr O$ ,其中$x,y$的取值范围是 $Bbb Z_p = { 1,2,3...p-1}$
注:上面的等式需要满足 $ 4a^3 + 27b^2 eq 0 pmod p$

举个栗子

椭圆曲线

$$ E :quad y^2 ≡ x^3+2x+2 pmod {17} quad x,y in Bbb Z_{17} $$

包含这些点: $(5,1)$ , $(6,3)$ , $(10,6)$ , $(3,1)$ , $(9,16)$ , $(16,13)$ , $(0,6)$ , $(13,7)$ , $(7,6)$ , $(7,11)$ , $(13,10)$ , $(0,11)$ , $(16,4)$ , $(9,1)$ , $(3,16)$ , $(10,11)$ , $(6,14)$ , $(5,16)$ 以及 $mathscr O$。上面的点除了 $mathscr O$以外,它们是下面曲线上的一些离散的点:

注意:显然从图像中可以看出这条曲线是关于 $x$ 轴对称的,但上面的点的 $y$ 坐标都大于0,这是由于$x,y in Bbb Z_{17}$ 。举例来说点 $(5,1)$ 和 $(5,16)$实际上就是关于$x$轴对称的。因为 $16equiv-1 pmod {17} $,而$(5,-1)$也满足 $ y^2 ≡ x^3+2x+2 pmod {17} quad x,y in Bbb R $。
.

椭圆曲线上的运算规则

椭圆曲线上的点构成的集合中只有一种运算,那就是加法(常数与点的乘法可以看做多个加法),两个点可以进行加法运算得到第三个点,注意,这里的加法不是简单的平面坐标系横纵坐标的相加(这样相加的结果得到的坐标很有可能不在曲线上)。
假设$P=(x_1,y_1)$和$Q=(x_2,y_2)$ 都在曲线上,如何得到$R=(x_3,y_3)$ 使得

$$ P+Q=R (x_1,y_1)+(x_2,y_2)=(x_3,y_3) $$

我们从几何学上定义这种加法,有两种情况:

两个不同的点相加 $P+Q$ 且 $P eq Q$

将 $P$ 和 $Q$ 相连的线段延伸,与椭圆曲线有一个交点,该交点关于$x$轴的对称点就是所求的$P+Q$

一个点自加 $P+P$

作$P$在椭圆曲线上的切线,这条切线与椭圆曲线有一个交点,该交点关于$x$轴的对称点就是所求的$2P$

经过一些数学推导,可以得到计算$R(x_3,y_3)$坐标的公式

$$ x_3 = s^2−x_1−x_2 pmod p y_3 = s(x_1−x_3)−y_1 pmod p $$

其中

$$ s = left{egin{matrix} frac{y_1-y_2}{x_1-x_2} pmod p ; quad P eq Q frac{3x_{1}^{2} + a}{2y_{1}} pmod p ; quad P = Q end{matrix} ight. $$

还有几个公式,对于$ P(x_p,y_p)$

$$ P+mathscr O = P P+(-P) = mathscr O -P = (x_p , p-y_p ) $$

生成元

椭圆曲线上所有点加上$ mathscr O$ 包含了很多循环子群(cyclic subgroups) ,其中一个循环子群就是自身,本文仅考虑这种情形。
循环子群中的 生成元(Generator)也被称作素元(primitive element),通过不断自加,它可以“生成”群众其他所有元素。那么对本文来说,就是椭圆曲线上的一个点$P$,通过不断自加,它可以生成椭圆曲线上所有点。
即椭圆曲线上 = ${ P、2P、3P、....nP}$,其中$n$为循环子群的阶。

再以刚才的例子举例,

$$ E :quad y^2 ≡ x^3+2x+2 pmod {17} quad x,y in Bbb Z_{17} $$

曲线上的所有点就可以表示为 $P$ 的倍数
$P=(5,1)quad 2P=(6,3)quad3P=(10,6)quad4P=(3,1)quad5P=(9,16)quad6P=(16,13)quad 7P=(0,6) $
$8P=(13,7)quad9P=(7,6)quad10P=(7,11)quad11P=(13,10)quad12P=(0,11)quad13P=(16,4)$
$14P=(9,1)quad15P=(3,16)quad16P=(10,11)quad17P=(6,14)quad18P=(5,16)quad19P=mathscr O$

私钥与公钥

之前提到过,椭圆曲线密码系统使用离散对数问题(DLP)构建公钥密码方法,这体现为以下一个事实:

计算生成元与一个数$ d $的乘积很容易 $ dP =? $ 很容易 (Double-and-Add算法)

计算一个点由是由哪个数与生成元相乘得到的很困难 $ B = ?P $

类比与我们熟悉的实数域上,指数运算对数运算容易得多

而这里 $ d $ 就是椭圆曲线密码系统中的 私钥,$ B $ 就是公钥,这也就是为什么可以用私钥推导出公钥,反之不行的原因。

secp256k1

secp256k1是以太坊中使用的椭圆曲线,其参数可以点击Secp256k1 wiki查看,包括椭圆曲线的系数、生成元等。

椭圆曲线数字签名 什么是数字签名

现实生活中的签名作用是签署者对文件进行授权、防止交易中的抵赖发生。

而数字签名也有这个效果。

Bob将原文$x$用特定Hash函数生成摘要$h$, 用私钥加密$h$生成签名$s$,将原文$x$和摘要$s$一起传送给AliceAlice收到后$x"$和$s’$,然后用相同的Hash函数将收到消息$x"$生成摘要$h"$,用Bob的公钥进行解密得到签名$s’$,如果$s = s’$ 则表示消息是完整的,在传输过程中没有修改。

椭圆曲线数字签名

椭圆曲线数字签名算法(ECDSA)就是利用椭圆曲线加密方法进行数字签名的方法。

设我们使用的曲线

$$ y^2 equiv x^3 + ax + b pmod p quad x,y in Bbb Z_p $$ , 其生成元$A$的阶数为$q$,`私钥`为$d$,则`公钥`$B = dA$ ####发送方签名 1. 选择一个随机的key $k_E$,满足$0`注1` 2. 计算 $u_2 equiv s^{-1} cdot r pmod q $ 3. 计算 $P = u_1A + u_2B $ 4. 进行验证 $$ x_P = left{ egin{array}{lr} equiv r pmod q ightarrow 签名有效 otequiv r pmod q ightarrow 签名无效 end{array} ight. $$

注1:这里的$^{-1}$表示在模运算中求逆,在$ Bbb Z_p$中,一个数 $a$ 与它的逆 $a^{-1}$ 满足 $a cdot a^{-1} equiv 1 pmod p $

理论(不感兴趣可看例子)

$$ s equiv (h(x) + d cdot r)k_E^{-1} pmod q $$

两边同时乘以 $k_E cdot s^{-1}$ 可得

$$ k_E equiv s^{-1}(h(x) + d cdot r) pmod q $$

然后

$$ k_E equiv s^{-1}h(x) + d cdot s^{-1} cdot r pmod q $$

$$ k_E equiv u_1 + u_2d pmod q $$

同时计算对 生成元$A$的数乘,由 $B = dA$ 有

$$ k_EA = u_1A + u_2B $$

$$ R = u_1A + u_2B $$

所以只要接收方计算的 $P$ 的 $x$ 坐标等于 $R$ 的 $x$ 坐标 $r$ ,则可说明验证通过 (之所以看 $x$ 坐标是因为椭圆曲线中,只凭一个点的 $x$ 坐标并不能唯一确定它的 $y$ 坐标)

例子

以曲线 $E: y^2 equiv x^3 + 2x + 2 pmod {17} $ 为例,生成元 $A = (5,1)$

数字签名恢复公钥

在上面的例子中,Bob 首先需要向 Alice 告知它的公钥,但实际上,我们凭签名 $(r,s)$ 就恢复出公钥, 在以太坊中使用 /crypto/secp256k1/secp256.go 中的 RecoverPubkey()函数完成这一功能。

理论

接收方收到的信息包括原文和签名: $(x, (r, s))$ ,从 $x$ 可以计算出 $h(x)$ ,除此之外接收方就只知道椭圆曲线的参数了,如$(a, b, p, q, A)$ ,要注意它知道 $(d, k_E)$,而我们的目标是在不知道 $d$ 的情况下求出 $B$。

由之前推导出的下式开始 $ k_E equiv s^{-1}h(x) + d cdot s^{-1} cdot r pmod q $

两边同时 $A$ 数乘 得到 $R = s^{-1}h(x)A + s^{-1}B $
表示出$B$ 可得 $B= r^{-1}(sR - h(x)A) $
观察上式可知,只要知道了 $R$ 点坐标,我们就可以算出 $B$ ,但我们没有 $R$ 点坐标, 不过我们有它的 $x$ 轴坐标 $r$ 注2 ,我们可以将其代入曲线方程,反解出$R$ 点$y$ 坐标,但由于椭圆曲线是关于 $x$ 轴对称的,所以我们可以解出两个符合条件的 $B$

注2:我们这里忽略 $ r < p - q $ 的情景,这种情况很罕见(在Secp256k1曲线中,大约是 $2^{-128}$),在这种情况下 ,有两个$x_R$都能满足条件。

例子

注意以下椭圆曲线上的点的计算过程中

数乘运算使用Double-and-Add算法

加法运算代入$P +Q$ 的坐标公式计算

以刚才的椭圆曲线数字签名为例,Alice 收到Bob带有签名的消息时,她自己有以下信息 (没有了Bob的公钥 $B$ )

椭圆曲线参数 $E :quad y^2 ≡ x^3+2x+2 pmod {17} quad x,y in Bbb Z_{17} $ 生成元 $A = (5, 1) $ 阶数 $q = 19$。

$(r, s) = (7, 17) quad h(x) = 26 $

计算 $h(x)A = 26*(5,1) = (0,6) $
由 $ r = 7 $ , $ 7 *11 equiv 1 pmod {19}$ 得到 $r^{-1} equiv 11 pmod {19} $
再将 $ r = 7 $ ,代入曲线方程,得到 $R$ 点的坐标为 $(7,6)$ 或 $(7,11)$

当 $R=(7,6)$ 时

$$ sR = 17*(7,6) = (5, 1) $$

所以 $B= r^{-1}(sR - h(x)A) = 11((5,1) - (0,6)) = 11((5,1) + (0,11)) = 11(16, 4) = (7,11) $

当 $R=(7,11)$ 时

$$ sR = 17*(7,11) = (5, 16) $$

所以 $B= r^{-1}(sR - h(x)A) = 11((5,16) - (0,6)) = 11((5,16) + (0,11)) = 11(13, 10) = (0,6) $

最终我们可以得到 两个符合条件的公钥 $B = (7,11)$ 和 $B = (0,6)$ , 而无论是哪一个都可以得出相同的签名

参考资料

[1] Understanding Cryptography, Christof Paar / Jan Pelzl
[2] https://en.bitcoin.it/wiki/Se...

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/24421.html

相关文章

  • Bytom国密网说明和指南

    摘要:在比原链主网中,在获取交易和区块头等摘要的过程中使用的哈希算法是算法,而在国密测试网中,使用算法替代。启动的是国密测试网。可以说,比原链的项目进展伴随着国密测试网的发布更上一层楼。 比原项目仓库: Github地址:https://github.com/Bytom/bytom Gitee地址:https://gitee.com/BytomBlockc... 国密算法是指国家密码管理局制...

    王岩威 评论0 收藏0
  • 区块链发展历程

    摘要:不光是技术领域,其他如哲学自然科学数学等领域,这种现象也是屡见不鲜,区块链的产生和发展也是遵从了这个模式。以太坊登场,区块链以太坊是创立发明的,这个俄罗斯小伙子很早就在比特币领域做开发新闻的报道,最后自立门户开发了以太坊。 1、史前纪事,区块链史前元年 showImg(http://files.jouypub.com/static/images/bd67cbaca4ac41a78e01...

    sf190404 评论0 收藏0
  • 区块链基础知识

    摘要:区块链技术基础什么是区块链技术运行区块链客户端的计算节点彼此可以相互通信。区块链的组成模块区块链账本。区块链技术的意义数据不可篡改。区块链中会对区块头进行哈希计算,得出该区块的哈希值。这保证了每个区块被加入链后不可被修改。 区块链技术基础 什么是区块链技术? 运行区块链客户端的计算节点彼此可以相互通信。 每个节点维护一个账本。 每个节点的收支记录都会广播给其他节点。 筛选出一个节点作...

    acrazing 评论0 收藏0
  • 详解区块链——从本质到实现原理

    摘要:区块链技术比传统互联网技术好在哪里它的实现原理优是什么呢笔者希望通过本文,解答大家心中的疑问。也就是说区块链记账机器完成记账功能的基本原理是状态机。总结区块链技术的本质是通过公开的加密的不可篡改的技术手段,为解决多方信任问题提供了一个方案。 随着比特币、以太坊等数字货币的暴涨,数字货币的底层技术,区块链技术,开始进入大众的视野。姚劲波说:区块链有可能和互联网一样伟大。区块链技术比传统互...

    thursday 评论0 收藏0
  • 漫谈 | “黎曼猜想”和区块链加密算法到底有什么关系?

    摘要:假如黎曼猜想被证实,区块链将毁灭近日,黎曼猜想四个字疯狂刷屏。黎曼猜想由数学家波恩哈德黎曼于年提出。因此,黎曼猜想一旦被证明,则意味着素数之密被解开,算法也就将被攻破了。而大多数区块链所用的加密算法不是,而是椭圆曲线加密算法。 玛丽女王的密码之生死命悬一线 showImg(https://segmentfault.com/img/bVbhD7s?w=740&h=876); 16世纪伊丽...

    tracymac7 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<