比特币加密技术之椭圆曲线密码学

作者:pangjiuzala

发布时间:2016年11月6日

网络来源:Linux公社

在⽐特币系统中, 我们⽤公钥加密创建⼀个密钥对, ⽤于控制⽐特币的获取。 密钥对包括⼀个私钥, 和由其衍⽣出的唯⼀的公钥。 公钥⽤于接收⽐特币, ⽽私钥⽤于⽐特币⽀付时的交易签名。

公钥和私钥之间的数学关系, 使得私钥可⽤于⽣成特定消息的签名。 此签名可以在不泄露私钥的同时对公钥进⾏验证。

⽀付⽐特币时, ⽐特币的当前所有者需要在交易中提交其公钥和签名( 每次交易的签名都不同, 但均从同⼀个私钥⽣成) 。

⽐特币⽹络中的所有⼈都可以通过所提交的公钥和签名进⾏验证, 并确认该交易是否有效, 即确认⽀付者在该时刻对所交易的⽐特币拥有所有权。

(⼤多数⽐特币钱包⼯具为了⽅便会将私钥和公钥以密钥对的形式存储在⼀起。 然⽽, 公钥可以由私钥计算得到, 所以只存储私钥也是可以的。)

私钥和公钥

⼀个⽐特币钱包中包含⼀系列的密钥对, 每个密钥对包括⼀个私钥和⼀个公钥。 私钥( k) 是⼀个数字, 通常是随机选出的。

有了私钥, 我们就可以使⽤椭圆曲线乘法这个单向加密函数产⽣⼀个公钥( K) 。 有了公钥( K) , 我们就可以使⽤⼀个单向加密哈希函数⽣成⽐特币地址( A) 。 在本节中, 我们将从⽣成私钥开始, 讲述如何使⽤椭圆曲线运算将私钥⽣成公钥, 并
最终由公钥⽣成⽐特币地址。 私钥、 公钥和⽐特币地址之间的关系如下图所⽰。

私钥

私钥就是⼀个随机选出的数字⽽已。 ⼀个⽐特币地址中的所有资⾦的控制取决于相应私钥的所有权和控制权。 在⽐特币交易中, 私钥⽤于⽣成⽀付⽐特币所必需的签名以证明资⾦的所有权。 私钥必须始终保持机密, 因为⼀旦被泄露给第三⽅, 相当于该私钥保护之下的⽐特币也拱⼿相让了。 私钥还必须进⾏备份, 以防意外丢失, 因为私钥⼀旦丢失就难以复原, 其所保护的⽐特币也将永远丢失。

⽐特币私钥只是⼀个数字。 你可以⽤硬币、 铅笔和纸来随机⽣成你的私钥: 掷硬币256次, ⽤纸和笔记录正反⾯并转换为0和1, 随机得到的256位⼆进制数字可作为⽐特币钱包的私钥。 该私钥可进⼀步⽣成公钥。

⽣成密钥的第⼀步也是最重要的⼀步, 是要找到⾜够安全的熵源, 即随机性来源。 ⽣成⼀个⽐特币私钥在本质上与“在1到2^256之间选⼀个数字”⽆异。 只要选取的结果是不可预测或不可重复的, 那么选取数字的具体⽅法并不重要。 ⽐特币软件使⽤操作系统底层的随机数⽣成器来产⽣256位的熵( 随机性) 。 通常情况下, 操作系统随机数⽣成器由⼈⼯的随机源进⾏初始化, 也可能需要通过⼏秒钟内不停晃动⿏标等⽅式进⾏初始化。 对于真正的偏执狂, 可以使⽤掷骰⼦的⽅法, 并⽤铅笔和纸记录。

更准确地说, 私钥可以是1和n-1之间的任何数字, 其中n是⼀个常数(n=1.158*1077, 略⼩于2^256) , 并由⽐特币所使⽤的椭圆曲线的阶所定义。要⽣成这样的⼀个私钥, 我们随机选择⼀个256位的数字, 并检查它是否⼩于n-1。 从编程的⻆度来看, ⼀般是通过在⼀个密码学安全的随机源中取出⼀⻓串随机字节, 对其使⽤SHA256哈希算法进⾏运算, 这样就可以⽅便地产⽣⼀个256位的数字。 如果运算结果⼩于n-1, 我们就有了⼀个合适的私钥。 否则, 我们就⽤另⼀个随机数再重复⼀次。

以下是⼀个随机⽣成的私钥( k) , 以⼗六进制格式表⽰( 256位的⼆进制数, 以64位⼗六进制数显⽰, 每个⼗六进制数占4位) :

1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD

⽐特币私钥空间的⼤⼩是2^256, 这是⼀个⾮常⼤的数字。 ⽤⼗进制表⽰的话, ⼤约是1077, ⽽可⻅宇宙被估计只含有1080个原⼦。

公钥

通过椭圆曲线乘法可以从私钥计算得到公钥, 这是不可逆转的过程: K = k * G 。 其中 k 是私钥, G 是被称为⽣成点的常数点, ⽽ K 是所得公钥。 其反向运算, 被称为“寻找离散对数”——已知公钥 K 来求出私钥 k ——是⾮常困难的, 就像去试验所
有可能的 k 值, 即暴⼒搜索。

椭圆曲线密码学解释

椭圆曲线加密法是⼀种基于离散对数问题的⾮对称( 或公钥) 加密法, 可以⽤对椭圆曲线上的点进⾏加法或乘法运算来表达。

上图是⼀个椭圆曲线的⽰例, 类似于⽐特币所⽤的曲线。
⽐特币使⽤了 secp256k1 标准所定义的⼀条特殊的椭圆曲线和⼀系列数学常数。 该标准由美国国家标准与技术研究院
( NIST) 设⽴。 secp256k1 曲线由下述函数定义, 该函数可产⽣⼀条椭圆曲线:

y^2 = (x^3 + 7)} over (Fp)
或 y^2mod p = (x^3 + 7) mod p

上述mod p( 素数p取模) 表明该曲线是在素数阶p的有限域内, 也写作Fp, 其中p = 2^256 – 2^32 – 2^9 – 2^8 – 2^7 – 2^6 – 2^4 – 1,这是⼀个⾮常⼤的素数。
因为这条曲线被定义在⼀个素数阶的有限域内, ⽽不是定义在实数范围, 它的函数图像看起来像分散在两个维度上的散点图, 因此很难画图表⽰。 不过, 其中的数学原理与实数范围的椭圆曲线相似。 作为⼀个例⼦, 下图显⽰了在⼀个⼩了很多的素数阶17的有限域内的椭圆曲线, 其形式为⽹格上的⼀系列散点。 ⽽ secp256k1 的⽐特币椭圆曲线可以被想象成⼀个极⼤的⽹格上⼀系列更为复杂的散点。

图为: 椭圆曲线密码学F(p)上的椭圆曲线, 其中p = 17

下⾯举⼀个例⼦, 这是 secp256k1 曲线上的点P, 其坐标为(x, y)。 可以使⽤Python对其检验:

在椭圆曲线的数学原理中, 有⼀个点被称为“⽆穷远点”, 这⼤致对应于0在加法中的作⽤。 计算机中, 它有时表⽰为X = Y =0( 虽然这不满⾜椭圆曲线⽅程, 但可作为特殊情况进⾏检验) 。 还有⼀个 + 运算符, 被称为“加法”, 就像⼩学数学中的实数相加。 给定椭圆曲线上的两个点P1和P2, 则椭圆曲线上必定有第三点 P3 = P1 + P2。
⼏何图形中, 该第三点P3可以在P1和P2之间画⼀条线来确定。 这条直线恰好与椭圆曲线上的⼀点相交。 此点记为 P3’=(x, y)。 然后, 在x轴做映射获得 P3=(x, -y)。

下⾯是⼏个可以解释“⽆穷远点”之存在需要的特殊情况。 若 P1和 P2是同⼀点, P1和P2间的连线则为点P1 的切线。 曲线上有且只有⼀个新的点与该切线相交。 该切线的斜率可⽤微分求得。 即使限制曲线点为两个整数坐标也可求得斜率!

在某些情况下( 即, 如果P1和P2具有相同的x值, 但不同的y值) , 则切线会完全垂直, 在这种情况下, P3 = “⽆穷远点”。

若P1就是“⽆穷远点”, 那么其和 P1 + P2= P2。 类似地, 当P2是⽆穷远点, 则P1+ P2 = P1。 这就是把⽆穷远点类似于0的作⽤。

事实证明, 在这⾥ + 运算符遵守结合律, 这意味着(A+B)C = A(B+C)。 这就是说我们可以直接不加括号书写 A + B + C, ⽽不⾄于混淆。

⾄此, 我们已经定义了椭圆加法, 为扩展加法下⾯我们对乘法进⾏标准定义。 给定椭圆曲线上的点P, 如果k是整数, 则 kP =P + P + P + …+ P( k次) 。 注意, k被有时被混淆⽽称为“指数”。

生成公钥

以⼀个随机⽣成的私钥k为起点, 我们将其与曲线上已定义的 ⽣成点G相乘以获得曲线上的另⼀点, 也就是相应的公钥K。 ⽣成点是secp256k1标准的⼀部分, ⽐特币密钥的⽣成点都是相同的:

{K = k * G}

其中k是私钥, G是⽣成点, 在该曲线上所得的点K是公钥。 因为所有⽐特币⽤⼾的⽣成点是相同的, ⼀个私钥k乘以G将得到相同的公钥K。 k和K之间的关系是固定的, 但只能单向运算, 即从k得到K。 这就是可以把⽐特币地址( K的衍⽣) 与任何⼈共享⽽不会泄露私钥( k) 的原因。

因为其中的数学运算是单向的, 所以私钥可以转换为公钥, 但公钥不能转换回私钥。
为实现椭圆曲线乘法, 我们以之前产⽣的私钥k和与⽣成点G相乘得到公钥K:

K = 1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD * G

公钥K 被定义为⼀个点 K = (x, y):

K = (x, y)
其中,
x = F028892BAD7ED57D2FB57BF33081D5CFCF6F9ED3D3D7F159C2E2FFF579DC341A
y = 07CF33DA18BD734C600B96A72BBC4749D5141C90EC8AC328AE52DDFE2E505BDB

为了展⽰整数点的乘法, 我们将使⽤较为简单的实数范围的椭圆曲线。 请记住, 其中的数学原理是相同的。 我们的⽬标是找到⽣成点G的倍数kG。 也就是将G相加k次。 在椭圆曲线中, 点的相加等同于从该点画切线找到与曲线相交的另⼀点, 然后映射到x轴。

上图显⽰了在曲线上得到 G、 2G、 4G 的⼏何操作。

⼤多数⽐特币程序使⽤OpenSSL加密库进⾏椭圆曲线计算。 例如, 调⽤EC_POINT_mul() 函数, 可计算得到公钥。

本文永久更新链接地址http://www.linuxidc.com/Linux/2016-11/136786.htm

相关文章:

发表回复

您的电子邮箱地址不会被公开。