比特币背后的数学

比特币可能让初学者感到困惑的一个原因是它背后的技术重新定义了所有权的概念。

拥有传统意义上的东西,无论是房子还是一笔钱,都意味着要么拥有对物品的个人保管权,要么将保管权交给可信赖的实体,例如银行。

比特币的情况有所不同。比特币本身不是集中存储或本地存储,因此没有一个实体是他们的监管者。它们作为记录在称为区块链的分布式分类账上存在,其副本由连接的计算机的志愿者网络共享。拥有比特币只是意味着能够通过在区块链中创建转账记录来将控制权转移给其他人。通过什么授予这种能力?可以访问ECDSA私钥和公钥对。这又意味着什么,以及如何保护比特币呢?

让我们来看看表象之下。

ECDSA是Elliptic Curve数字签名算法的缩写。这是一个使用椭圆曲线有限域sign签名数据的过程,这样第三方可以在签名者保留创建签名的独有能力的同时验证签名的真实性。使用比特币,签名的数据是转移所有权的交易。

ECDSA有单独的签名和验证程序。每个过程都是由几个算术运算组成的算法。签名算法利用私钥,验证过程利用公钥。我们稍后会展示一个这样的例子。

但首先是椭圆曲线和有限域的速成课程。

椭圆曲线

椭圆曲线代数表示为形式的等式:

y^2 = x^3 + ax + b

对于a=0和b=7(比特币使用的版本),它看起来像这样:

椭圆曲线具有有用的属性。例如,与曲线上的两个非切点相交的非垂直线将始终与曲线上的第三个点相交。另一个特性是在一个点处与曲线相切的非垂直线将精确地与曲线上的另一个点相交。

我们可以使用这些属性来定义两个操作:点加法和点加倍。

点加法,P+Q=R,定义为在包括P和Q的线上通过第三交叉点R’的x轴的反射。使用图表最容易理解:

类似地,点加倍,P+P=R通过找到与要加倍的点相切的线P来定义,并通过曲线上交叉点R’的x轴进行反射得到R.这是一个例子那会是什么样子:

这两个操作一起用于标量乘法,R = aP,通过将点P加到其自身一次来定义。例如:

R=7P R = P + (P + (P + (P + (P + (P + P)))))

标量乘法的过程通常通过使用点加法和点加倍运算的组合来简化。例如:

R = 7P R = P + 6P R = P + 2 (3P) R = P + 2 (P + 2P)

这里,7P已被分解为两个点加倍步骤和两个点加法步骤。

有限域

在ECDSA的上下文中,有限域可以被认为是预定义的正数范围,其中每个计算必须落在其中。超出此范围的任何数字都wraps around环绕以便落在该范围内。

考虑这个的最简单方法是计算余数,如模数(mod)运算符所表示的。例如,9/7给出1,余数为2:

9 mod 7 = 2

这里我们的有限域是模7,并且该域上的所有mod操作产生的结果落在0到6的范围内。

把它放在一起

ECDSA在有限域的上下文中使用椭圆曲线,这极大地改变了它们的外观,但没有改变它们的基本方程或特殊属性。在模67的有限域中,上面绘制的相同等式看起来像这样:

它现在是一组点,其中所有x和y值都是0到66之间的整数。请注意,curve曲线仍然保持其水平对称性。

点加法和加倍现在在视觉上略有不同。在此图上绘制的线将围绕水平和垂直方向,就像在小行星游戏中一样,保持相同的斜率。所以添加点(2,22)和(6,25)看起来像这样:

第三个交叉点是(47,39),其反射点是(47,28)。

回到ECDSA和比特币

诸如比特币之类的协议为椭圆曲线选择一组参数,并为协议的所有用户选择固定的有限域表示。参数包括使用的等式,场的素数模和落在曲线上的基点。基点的顺序(其不是独立选择但是是其他参数的函数)可以图形地被认为是点可以加到其自身直到其斜率是无穷大的次数,或者是垂直线。选择基点使得顺序是大素数。

比特币使用非常大的数字作为其基点,素数模和订单。事实上,ECDSA的所有实际应用都使用了巨大的价值。算法的安全性依赖于这些值很大,因此对暴力或逆向工程来说是不切实际的。

在比特币的情况下:

谁选择了这些数字,为什么?大量的研究和相当多的吸引力围绕着选择适当的参数。毕竟,一个看似随机的大型数字可能会隐藏重建私钥的后门方法。简而言之,这个特殊的实现以secp256k1的名称命名,并且是建议用于密码学的有限域上的椭圆曲线解决方案的一部分。

私钥和公钥

通过这些手续,我们现在可以了解私钥和公钥以及它们之间的关系。简而言之:在ECDSA中,私钥是1和订单之间不可预测的数字。公钥通过基点的标量乘法等于私钥的值的次数从私钥导出。表达式如下:

公钥=私钥*基点

这表明私钥的最大可能数量(以及比特币地址)等于该顺序。

在连续的场中,我们可以绘制切线并在图上精确定位公钥,但是有些方程在有限域的上下文中完成相同的事情。p+q到find r的点加法在组件方面定义如下:

并且将p加倍找到r如下:

实际上,公钥的计算被分解为从基点开始的多个点加倍和点加法运算。

让我们使用小数字运行信封示例的背面,以获得关于如何构造和使用密钥以进行签名和验证的直觉。我们将使用的参数是:

公式:y^2 = x^3 + 7(也就是说,a = 0和b = 7) Prime Modulo:67 基点:(2,22) 订单:79 私钥:2

首先,让我们找到公钥。由于我们选择了值为2的最简单的私钥,因此从基点开始只需要一个单点加倍操作。计算如下:

c = (3 2^2 + 0)/(2 22) mod 67 c = (3 * 4)/(44) mod 67 c = 12/44 mod 67

在这里我们必须暂停一下:如何在有限域的上下文中执行除法,其中结果必须始终是整数?我们必须乘以逆,这个空间不允许我们在这里定义(如果感兴趣,我们会在这里和这里引用你)。在手头的情况下,你将不得不信任我们:

44^-1 = 32

向右移动:

因此,我们的公钥对应于点(52,7)。所有这一切都适用于2的私钥!

这种操作,从私有密钥到公共密钥,与尝试向后工作以从公钥中推导出私钥相比在计算上是容易的,虽然理论上可能由于在实际椭圆密码术中使用的大参数而在计算上是不可行的。

因此,从私钥到公钥是设计单方向的。

与私钥一样,公钥通常由十六进制字符串表示。但是,等一下,我们如何从一个由两个数字描述的飞机上的点到达一个数字?在未压缩的公钥中,表示x和y坐标的两个256位数字只是粘在一起的长字符串,我们还可以利用椭圆曲线的对称性来生成压缩公钥,只需保持x值并注意点所在曲线的哪一半。根据这部分信息,我们可以恢复两个坐标。

使用私钥对数据进行签名

现在我们有一个私钥和公钥对,让我们签一些数据吧!

数据可以是任何长度。通常的第一步是散列数据以生成包含与曲线顺序相同的位数(256)的数字。这里,为了简单起见,我们将跳过散列步骤并仅对原始数据z进行签名。我们将G称为基点,n为订单,d为私钥。签署的方法如下:

  1. 选择介于1和n-1之间的整数k。
  2. 使用标量乘法计算点(x,y)=k*G。
  3. 求r= x mod n。如果r=0,则返回步骤1。
  4. 求s=(z+r*d)/k mod n。如果s=0,则返回步骤1。
  5. 签名是一个数字对(r,s)。

作为提醒,在步骤4中,如果数字导致分数(在现实生活中它们几乎总是如此),则分子应乘以分母的倒数。在步骤1中,重要的是k不能在不同的签名中重复,并且不能被第三方猜测。也就是说,k应该是随机的,或者是通过对第三方保密的确定性手段生成的。否则,可以从步骤4中提取私钥,因为s,z,r,k和n都是已知的。你可以在此处阅读此类型的过去漏洞利用。

让我们选择我们的数据为17,然后我们的变量:

z = 17(数据)

n = 79(排序)

G =(2,22)(基点)

d = 2(私钥)

  1. 选择一个随机数:

k = rand(1,n-1)

k = rand(1,79-1)

k = 3(这真的是随机的吗?好吧,你得到了我们,但它会让我们的例子更简单!)

  1. 计算点。这与确定公钥的方式相同,但为了简洁起见,我们省略了点加法和点加倍算法。

(x,y)= 3G

(x,y)= G + 2G

(x,y)=(2,22)+(52,7)

(x,y)=(62,63)

x = 62

y = 63

  1. 找到r:

r = x mod n

r = 62 mod 79

r = 62

  1. 找到s:

s =(z + r * d)/ k mod n

s =(17 + 62 * 2)/ 3 mod 79

s =(17 + 124)/ 3 mod 79

s = 141/3 mod 79

s = 47 mod 79

s = 47

注意,上面我们能够除以3,因为结果是整数。在现实生活中,我们将使用k的倒数(像以前一样,我们通过在别处计算它来隐藏一些血腥细节):

s =(z + r * d)/ k mod n

s =(17 + 62 * 2)/ 3 mod 79

s =(17 + 124)/ 3 mod 79

s = 141/3 mod 79

s = 141 * 3^-1 mod 79

s = 141 * 53 mod 79

s = 7473 mod 79

s = 47

我们的签名是对(r,s)=(62,47)。与私钥和公钥一样,此签名通常由十六进制字符串表示。

使用公钥验证签名

我们现在有一些数据和该数据的签名。拥有我们公钥的第三方可以接收我们的数据和签名,并验证我们是发件人。让我们看看它是如何工作的。

如果Q是公钥,其他变量如前所述,验证签名的步骤如下:

  • 1.验证r和s介于1和n - 1之间。
  • 2.计算w = s^-1 mod n
  • 3.计算u = z * w mod n
  • 4.计算v = r * w mod n
  • 5.计算点(x,y)= uG + vQ
  • 6.验证r = x mod n。如果不是,签名无效。

为什么这些步骤有效?我们正在跳过证明,但你可以在此处阅读详细信息。让我们按照清单,看看它是如何工作的。再一次看看我们的变量:

z = 17(数据)

(r,s)=(62,47)(签名)

n = 79(排序)

G =(2,22)(基点)

Q =(52,7)(公钥)

  1. 确认r和s介于1和n - 1之间。检查并检查。

r:1 <= 62 <79

s:1 <= 47 <79

  1. 计算w:

w = s-1 mod n

w = 47-1 mod 79

w = 37

  1. 计算u:

u= zw mod n

u = 17 * 37 mod 79

u = 629 mod 79

u= 76

  1. 计算v:

v = rw mod n

v = 62 * 37 mod 79

v = 2294 mod 79

v = 3

  1. 计算点(x,y):

(x,y)= uG + vQ

让我们分别在uG和vQ中分解加倍和加法的点。

uG = 76G

uG = 2(38G)

uG = 2(2(19G))

uG = 2(2(G + 18G))

uG = 2(2(G + 2(9G)))

uG = 2(2(G + 2(G + 8G)))

uG = 2(2(G + 2(G + 2(4G))))

uG = 2(2(G + 2(G + 2(2(2G)))))

回过头来欣赏一下,通过使用分组技巧,我们将75个连续的加法运算减少到6个点加倍运算和2个加点运算。当数字变得非常大时,这些技巧会派上用场。

从内到外运用我们的方式:

uG = 2(2(G + 2(G + 2(2(2(2,22))))))

uG = 2(2(G + 2(G + 2(2(52,7)))))

uG = 2(2(G + 2(G + 2(25,17))))

uG = 2(2(G + 2((2,22)+(21,42))))

uG = 2(2(G + 2(13,44)))

uG = 2(2((2,22)+(66,26)))

uG = 2(2(38,26))

uG = 2(27,40)

uG =(62,4)

现在为vQ:

vQ = 3Q

vQ = Q + 2Q

vQ = Q + 2(52,7)

vQ =(52,7)+(25,17)

vQ =(11,20)

把它们放在一起:

(x,y)= uG + vQ

(x,y)=(62,4)+(11,20)

(x,y)=(62,63)

显然,第5步是大部分工作。最后一步,

  1. 验证r = x mod n

r = x mod n

62 = 62 mod 79

62 = 62

我们的签名有效!

结论

对于那些看过所有方程并跳到底部的人,我们刚学到了什么?

我们已经对公钥和私钥之间存在的深层数学关系产生了一些直觉。我们已经看到,即使在最简单的例子中,签名和验证背后的数学很快变得复杂,我们可以理解当涉及的参数是256位数时必须涉及的巨大复杂性。我们已经看到,最简单的数学过程的巧妙应用如何创建单向“陷阱门”功能,以保持定义比特币所有权的信息不对称。只要我们仔细保护私钥的知识,我们就对系统的稳健性有了新的信心。

换句话说,这就是为什么人们普遍认为比特币是由“数学支持”的原因。

如果你通过复杂的位进入,我们希望它让你有信心采取下一步并自己尝试数学(模块化算术计算器使有限域数学更容易)。我们发现,通过手工签署和验证数据的步骤可以更深入地了解密码术,从而实现比特币独特的所有权形式。

======================================================================

分享一些以太坊、EOS、比特币等区块链相关的交互式在线编程实战教程:

  • EOS教程,本课程帮助你快速入门EOS区块链去中心化应用的开发,内容涵盖EOS工具链、账户与钱包、发行代币、智能合约开发与部署、使用代码与智能合约交互等核心知识点,最后综合运用各知识点完成一个便签DApp的开发。
  • java以太坊开发教程,主要是针对java和android程序员进行区块链以太坊开发的web3j详解。
  • python以太坊,主要是针对python工程师使用web3.py进行区块链以太坊开发的详解。
  • php以太坊,主要是介绍使用php进行智能合约开发交互,进行账号创建、交易、转账、代币开发以及过滤器和交易等内容。
  • 以太坊入门教程,主要介绍智能合约与dapp应用开发,适合入门。
  • 以太坊开发进阶教程,主要是介绍使用node.js、mongodb、区块链、ipfs实现去中心化电商DApp实战,适合进阶。
  • C#以太坊,主要讲解如何使用C#开发基于.Net的以太坊应用,包括账户管理、状态与交易、智能合约开发与交互、过滤器和交易等。
  • java比特币开发教程,本课程面向初学者,内容即涵盖比特币的核心概念,例如区块链存储、去中心化共识机制、密钥与脚本、交易与UTXO等,同时也详细讲解如何在Java代码中集成比特币支持功能,例如创建地址、管理钱包、构造裸交易等,是Java工程师不可多得的比特币开发学习课程。
  • php比特币开发教程,本课程面向初学者,内容即涵盖比特币的核心概念,例如区块链存储、去中心化共识机制、密钥与脚本、交易与UTXO等,同时也详细讲解如何在Php代码中集成比特币支持功能,例如创建地址、管理钱包、构造裸交易等,是Php工程师不可多得的比特币开发学习课程。
  • tendermint区块链开发详解,本课程适合希望使用tendermint进行区块链开发的工程师,课程内容即包括tendermint应用开发模型中的核心概念,例如ABCI接口、默克尔树、多版本状态库等,也包括代币发行等丰富的实操代码,是go语言工程师快速入门区块链开发的最佳选择。

汇智网原创翻译,转载请标明出处。这里是原文比特币背后的数学