比特币的签名算法

A. 区块链一般概念摘要

虽然是个前端开发，但是阻挡不了我八卦各种热门的心。下面简单汇总下一些学习到的概念性东西。

1、区块链技术随比特币诞生，因此先了解比特币概念

2、比特币是什么

（1）、基于分布式网络的数字货币

3、比特系统运行原理

（1）、所有节点都会保存完整账本

（2）、账本保持一致性

4、区块链记账原理

hash函数在区块链技术中有广泛的运用

（1）、哈希函数hash:任何信息hash后会得到一个简短的摘要信息

（2）、hash特点：简化信息、标识信息、隐匿信息、验证信息

（3）、区块链记账会把时间节点的账单信息hash,构成一个区块

（4）、比特币系统约10分钟记账一次，即每个区块生成的时间间隔大约10分钟

（5）、记录下一个账单时，会把上一个区块的hash值和当前账单的信息一起作为原始信息进行hash

（6）、每个区块都包含了之前区块的信息，这些区块组合成了区块链

5、比特币的所有权-非对称加密应用

比特币系统使用了椭圆曲线签名算法，算法的私钥由32个字节随机数组成，通过私钥可以计算出公钥，公钥经过一序列哈希算法和编码算法得到比特币地址，地址也可以理解为公钥的摘要。

（1）、转账是把比特币从一个地址转移到另一个地址

（2）、地址私钥是非对称的关系，私钥经过一系列的运算（其中包含两次hash），就可以得到地址，但是从地址无法得到私钥

（3）、转账成功后广播其他节点，其他节点验证成功后再转发到相邻的节点，广播的信息包含了原始的信息和签名信息

（4）、验证，其他节点验证签名信息是不是付款方用私钥对交易原始信息签名产生的，如果是才记录（再验证有足够余额）

6、比特币如何挖矿

（1）、完成记账的节点可以获得系统给予的一定数量比特币奖励（这个奖励过程也就是比特币的发行过程，因此大家把记账称为挖矿）

（2）、一段时间内只有一人可以记账成功，因此需要收集没有被收集的原始交易信息，检查有没有余额、正确签名

（3）、为了提高记账难度，十分钟左右只有一人可以记账，hash结果需要若干0开头，并且进行hash时引入随机数变量

（4）、随着更多矿工的加入，游戏难度越来越大，计算难度加大，电力损耗等加大，国内电力成本低，中国算力占整个网络的一半以上

（5）、网络中只有最快解密的区块，才会添加到账本中，其他的节点复制，保证账本的唯一性。如果有节点作弊，导致整个网络不通过，则会被丢弃再也不会记录到总账本中。因此所有节点都会遵守比特币系统的共同协议。

【关于区块链会延伸到那些领域的思考】：

由以上的概念可以总结出，区块链技术存在这安全性、唯一性、去中心化。

原则上是可以避免部分信息泄露，让确认方既可以确认你的身份，又无需暴露自己的真是用户信息等。

目前区块链技术集中被运用再比特币，我觉得后续更大的意义应该在需要数据私密性、安全性的领域。

【关于区块链目前发展的瓶颈和局限性思考】：

由于每个节点都参与了整个账本记录活动，难免造成资源的浪费和损耗。以及加大了每个节点的计算难度，后续的发展和普及需要每个节点的硬件提升。

B. 区块链的密码技术有

密码学技术是区块链技术的核心。区块链的密码技术有数字签名算法和哈希算法。
数字签名算法
数字签名算法是数字签名标准的一个子集，表示了只用作数字签名的一个特定的公钥算法。密钥运行在由SHA-1产生的消息哈希：为了验证一个签名，要重新计算消息的哈希，使用公钥解密签名然后比较结果。缩写为DSA。

数字签名是电子签名的特殊形式。到目前为止，至少已经有 20 多个国家通过法律 认可电子签名，其中包括欧盟和美国，我国的电子签名法于 2004 年 8 月 28 日第十届全 国人民代表大会常务委员会第十一次会议通过。数字签名在 ISO 7498-2 标准中定义为： “附加在数据单元上的一些数据，或是对数据单元所作的密码变换，这种数据和变换允许数据单元的接收者用以确认数据单元来源和数据单元的完整性，并保护数据，防止被人（例如接收者）进行伪造”。数字签名机制提供了一种鉴别方法，以解决伪造、抵赖、冒充和篡改等问题，利用数据加密技术、数据变换技术，使收发数据双方能够满足两个条件：接收方能够鉴别发送方所宣称的身份；发送方以后不能否认其发送过该数据这一 事实。
数字签名是密码学理论中的一个重要分支。它的提出是为了对电子文档进行签名，以 替代传统纸质文档上的手写签名，因此它必须具备 5 个特性。
（1）签名是可信的。
（2）签名是不可伪造的。
（3）签名是不可重用的。
（4）签名的文件是不可改变的。
（5）签名是不可抵赖的。
哈希（hash）算法
Hash，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，其中散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，但是不可逆向推导出输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
哈希（Hash）算法，它是一种单向密码体制，即它是一个从明文到密文的不可逆的映射，只有加密过程，没有解密过程。同时，哈希函数可以将任意长度的输入经过变化以后得到固定长度的输出。哈希函数的这种单向特征和输出数据长度固定的特征使得它可以生成消息或者数据。
以比特币区块链为代表，其中工作量证明和密钥编码过程中多次使用了二次哈希，如SHA(SHA256(k))或者RIPEMD160(SHA256(K)),这种方式带来的好处是增加了工作量或者在不清楚协议的情况下增加破解难度。
以比特币区块链为代表，主要使用的两个哈希函数分别是：
1.SHA-256，主要用于完成PoW（工作量证明）计算；
2.RIPEMD160，主要用于生成比特币地址。如下图1所示，为比特币从公钥生成地址的流程。

C. (p+1)(p-4)+7p+8公式法

导语

本课堂用通俗易懂的系列内容为大家呈现区块链与密码学领域相关知识。这里有知识也有故事，从感兴趣到有乐趣，点宽课堂等你来学。

这个系列中的课程内容首先从比特币着手进行入门介绍，再延伸至区块链的相关技术原理与发展趋势，然后深入浅出地依次介绍在区块链中应用的各类密码学技术。欢迎大家订阅本公众号，持续进行学习。

【本课堂内容全部选编自PlatON首席密码学家、武汉大学国家网络安全学院教授、博士生导师何德彪教授的《区块链与密码学》授课讲义、教材及互联网，版权归属其原作者所有，如有侵权请立即与我们联系，我们将及时处理。】

6.3

其他数字签名算法

EIGamal算法

数字签名一般利用公钥密码技术来实现，其中私钥用来签名，公钥用来验证签名。ElGamal公钥密码算法是在密码协议中有着重要应用的一类公钥密码算法，其安全性是基于有限域上离散对数学问题的难解性。它至今仍是一个安全性良好的公钥密码算法。它既可用于加密又可用于数字签名的公钥密码体制。

假设p是一个大素数，g是GF(p)的生成元。Alice的公钥为y = gx mod p, g，p私钥为x。

签名算法：

• Alice用H将消息m进行处理，得h=H(m).

• Alice选择秘密随机数k，满足

0

计算

r=gk (mod p)

s=(h－ x · r) · k-1(mod (p－1))

• Alice将(m，r，s)发送给Bob

验证签名过程：

接收方收到M与其签名(r，s)后：

• 计算消息M的Hash值H(M)

• 验证公式

成立则确认为有效签名，否则认为签名是伪造的

PSS算法的编码操作过程

上述方案的安全性是基于如下离散对数问题的：已知大素数p、GF(p的生成元g和非零元素y∈GF(p)，求解唯一的整数k, 0≤k≤p – 2，使得y≡gk (mod p)，k称为y对g的离散对数。

在1996年的欧洲密码学会(Proceedings of EUROCRYPT 96)上，David Pointcheval和Jacques Stern给出一个ElGamal签名的变体，并基于所谓分叉技术证明了在随机预言模型下所给方案是安全的(在自适应选择消息攻击下能抗击存在性伪造)。

Schnorr算法

Schnorr签名方案是一个短签名方案，它是ElGamal签名方案的变形，其安全性是基于离散对数困难性和哈希函数的单向性的。

假设p和q是大素数，是q能被p-1整除，q是大于等于160 bit的整数，p是大于等于512 bit的整数，保证GF(p)中求解离散对数困难；g是GF(p)中元素，且gq≡1mod p。

密钥生成：

Alice选择随机数x为私钥，其中1

Alice计算公钥y≡gx (mod p)

签名算法：

①Alice首先随机数k，这里1

②Alice计算e=h(M, gk mod p)

③Alice计算s=k-x·e(mod q)

④Alice输出签名(e, s)

验证算法：

Bob计算gkmod p=gs·ye mod p

Bob验证e = h(M, gk mod p)是否成立，如果成立则输出「Accept」，否则输出「Reject」。

Schnorr签名与ElGamal签名的不同点：

安全性比较：在ElGamal体制中，g为域GF(p)的本原元素；而在Schnorr体制中， g只是域GF(p)的阶为q的元素，而非本原元素。因此，虽然两者都是基于离散对数的困难性，然而ElGamal的离散对数阶为p-1， Schnorr的离散对数阶为q

签名长度比较：Schnorr比ElGamal签名长度短

ElGamal：(m，r，s)，其中r的长度为|p|， s的长度为|p-1|

Schnorr：(m，e，s)，其中e的长度为|q|， s的长度为|q|


DSA算法

1991年，美国政府颁布了数字签名标准(Digital Signature Standard, DSS)，也称为数字签名算法(Digital Signature Algorithm, DSA) 。

和DES一样，DSS也引起了激烈的争论，反对者认为：密钥太短、效率不如RSA高、不能实现数据加密并怀疑NIST在DSS中留有后门。

随后，美国政府对其做了一些改进，目前DSS的应用已经十分广泛，并被一些国际标准化组织采纳为国际标准。2000年，美国政府将RSA和椭圆曲线密码引入到数字签名标准中，进一步丰富了DSA算法。

DSA的主要参数：

全局公开密钥分量，可以为用户公用

p：素数，要求2L-1

q : (p-1)的素因子，2159

g : =h(p-1)/q mod p.其中h是一整数，11

用户私有密钥

x：随机或伪随机整数，要求0

用户公开密钥

y：=gx mod p

随机数k

随机或伪随机整数，要求0

DSA签名过程：

• 用户随机选取k

• 计算e=h(M)；

• 计算r=(gk mod p) mod q

• 计算s=k-1(e+x · r) mod q

• 输出(r, s)，即为消息M的数字签名
  

DSA验证过程：

• 接收者收到M, r, s后，首先验证0

• 计算e=h(M)；

• 计算w=(s)-1 mod q

• 计算u1=e · w mod q

• 计算u2=r · w mod q

• 计算①v=[(gu1 · yu2) mod p] mod q

• 如果v=r，则确认签名正确，否则拒绝

DSA算法的工作流程

今天的课程就到这里啦，下一堂课我们将学习基于椭圆曲线的数字签名算法，带大家继续了解数字签名，敬请期待！


关注点宽学园，每周持续更新区块链系列课程，小宽带你进入区块链世界。我们下节课见啦。

【区块链与密码学】课堂回顾：

FOLLOW US

© DigQuant


点击“阅读原文”，登录官网www.digquant.com，一起解锁更多金融科技姿势：涵盖 Python 、 金融基础 、 量化投资 、 区块链 、 大数据 、 人工智能 。 Dig More, Learn More！

D. 比特币算法原理

比特币算法主要有两种，分别是椭圆曲线数字签名算法和SHA256哈希算法。

椭圆曲线数字签名算法主要运用在比特币公钥和私钥的生成过程中，该算法是构成比特币系统的基石。SHA-256哈希算法主要是运用在比特币的工作量证明机制中。

比特币产生的原理是经过复杂的运算法产生的特解，挖矿就是寻找特解的过程。不过比特币的总数量只有2100万个，而且随着比特币不断被挖掘，越往后产生比特币的难度会增加，可能获得比特币的成本要比比特币本身的价格高。

比特币的区块由区块头及该区块所包含的交易列表组成，区块头的大小为80字节，由4字节的版本号、32字节的上一个区块的散列值、32字节的 Merkle Root Hash、4字节的时间戳（当前时间）、4字节的当前难度值、4字节的随机数组成。拥有80字节固定长度的区块头，就是用于比特币工作量证明的输入字符串。不停的变更区块头中的随机数即 nonce 的数值，并对每次变更后的的区块头做双重 SHA256运算，将结果值与当前网络的目标值做对比，如果小于目标值，则解题成功，工作量证明完成。

比特币的本质其实是一堆复杂算法所生成的一组方程组的特解（该解具有唯一性）。比特币是世界上第一种分布式的虚拟货币，其没有特定的发行中心，比特币的网络由所有用户构成，因为没有中心的存在能够保证了数据的安全性。

E. 区块链的加密技术

数字加密技能是区块链技能使用和开展的关键。一旦加密办法被破解，区块链的数据安全性将受到挑战，区块链的可篡改性将不复存在。加密算法分为对称加密算法和非对称加密算法。区块链首要使用非对称加密算法。非对称加密算法中的公钥暗码体制依据其所依据的问题一般分为三类:大整数分化问题、离散对数问题和椭圆曲线问题。第一，引进区块链加密技能加密算法一般分为对称加密和非对称加密。非对称加密是指集成到区块链中以满意安全要求和所有权验证要求的加密技能。非对称加密通常在加密和解密进程中使用两个非对称暗码，称为公钥和私钥。非对称密钥对有两个特点:一是其间一个密钥(公钥或私钥)加密信息后，只能解密另一个对应的密钥。第二，公钥可以向别人揭露，而私钥是保密的，别人无法通过公钥计算出相应的私钥。非对称加密一般分为三种首要类型:大整数分化问题、离散对数问题和椭圆曲线问题。大整数分化的问题类是指用两个大素数的乘积作为加密数。由于素数的出现是没有规律的，所以只能通过不断的试算来寻找解决办法。离散对数问题类是指基于离散对数的困难性和强单向哈希函数的一种非对称分布式加密算法。椭圆曲线是指使用平面椭圆曲线来计算一组非对称的特殊值，比特币就采用了这种加密算法。非对称加密技能在区块链的使用场景首要包含信息加密、数字签名和登录认证。(1)在信息加密场景中，发送方(记为A)用接收方(记为B)的公钥对信息进行加密后发送给

B，B用自己的私钥对信息进行解密。比特币交易的加密就属于这种场景。(2)在数字签名场景中，发送方A用自己的私钥对信息进行加密并发送给B，B用A的公钥对信息进行解密，然后确保信息是由A发送的。(3)登录认证场景下，客户端用私钥加密登录信息并发送给服务器，服务器再用客户端的公钥解密认证登录信息。请注意上述三种加密计划之间的差异:信息加密是公钥加密和私钥解密，确保信息的安全性；数字签名是私钥加密，公钥解密，确保了数字签名的归属。认证私钥加密，公钥解密。以比特币体系为例，其非对称加密机制如图1所示:比特币体系一般通过调用操作体系底层的随机数生成器生成一个256位的随机数作为私钥。比特币的私钥总量大，遍历所有私钥空间获取比特币的私钥极其困难，所以暗码学是安全的。为便于辨认，256位二进制比特币私钥将通过SHA256哈希算法和Base58进行转化，构成50个字符长的私钥，便于用户辨认和书写。比特币的公钥是私钥通过Secp256k1椭圆曲线算法生成的65字节随机数。公钥可用于生成比特币交易中使用的地址。生成进程是公钥先通过SHA256和RIPEMD160哈希处理，生成20字节的摘要成果(即Hash160的成果)，再通过SHA256哈希算法和Base58转化，构成33个字符的比特币地址。公钥生成进程是不可逆的，即私钥不能从公钥推导出来。比特币的公钥和私钥通常存储在比特币钱包文件中，其间私钥最为重要。丢掉私钥意味着丢掉相应地址的所有比特币财物。在现有的比特币和区块链体系中，现已依据实践使用需求衍生出多私钥加密技能，以满意多重签名等愈加灵敏杂乱的场景。

F. 什么是数字签名

数字签名是用于验证数字和数据真实性和完整性的加密机制。我们可以将其视为传统手写签名方式的数字化版本，并且相比于签字具有更高的复杂性和安全性。

简而言之，我们可以将数字签名理解为附加到消息或文档中的代码。在生成数字签名之后，其可以作为证明消息从发送方到接收方的传输过程中没有被篡改的证据。

虽然使用密码学保护通信机密性的概念可以追溯到古代，但随着公钥密码学（PKC）的发展，数字签名方案在20世纪70年代才成为现实。因此，要了解数字签名的工作原理，我们首先需要了解散列函数和公钥加密的基础知识。

哈希是数字签名中的核心要素之一。哈希值的运算过程是指将任意长度的数据转换为固定长度。这是通过称为散列函数的特殊运算实现的。经过散列函数运算而生成的值称为哈希值或消息摘要。

当哈希值与加密算法相结合，即使用加密散列函数的方法来生成散列值（摘要），该值可作为唯一的数字指纹。这意味着对于输入数据（消息）的任何更改都会导致有完全不同的输出值（散列值）。这就是加密散列函数被广泛用于验证数字和数据真实性的原因。

公钥加密或PKC是指使用一对密钥的加密系统：公钥和私钥。这两个密钥在数学上是相关的，可用于数据加密和数字签名。

作为一种加密工具，PKC相比于对称加密具有更高的安全性。对称加密系统依赖于相同的密钥进行加密和解密信息，但PKC则使用公钥进行数据加密，并使用相应的私钥进行数据解密。

除此之外，PKC还可以应用于生成数字签名。本质上，该过程发送方使用自己的私钥对消息（数据）的哈希值进行加密。接下来，消息的接收者可以使用签名者提供的公钥来检查该数字签名是否有效。

在某些情况下，数字签名本身可能包括了加密的过程，但并非总是这样。例如，比特币区块链使用PKC和数字签名，而并不像大多数人所认为的，这个过程中并没有进行加密。从技术上讲，比特币又部署了所谓的椭圆曲线数字签名算法（ECDSA）来验证交易。

在加密货币的背景下，数字签名系统通常包含三个基本流程：散列、签名和验证。

第一步是对消息或数据进行散列。通过散列算法对数据进行运算，生成哈希值（即消息摘要）来完成的。如上所述，消息的长度可能会有很大差异，但是当消息被散列后，它们的哈希值都具有相同的长度。这是散列函数的最基本属性。

但是，仅仅将消息进行散列并不是生成数字签名的必要条件，因为也可以使用私钥对没有进行过散列的消息进行加密。但对于加密货币，消息是需要经过散列函数处理的，因为处理固定长度的哈希值有助于加密货币的程序运行。

对信息进行散列处理后，消息的发件人需要对其消息进行签名。这里就用到了公钥密码学。有几种类型的数字签名算法，每种算法都有自己独特的运行机制。本质上，都是使用私钥对经过散列的消息（哈希值）进行签名，然后消息的接收者可以使用相应的公钥（由签名者提供）来检查其有效性。

换句话说，如果在生成签名时不使用私钥，则消息的接收者将不能使用相应的公钥来验证其有效性。公钥和私钥都是由消息的发送者生成的，但仅将公钥共享给接收者。

需要注意的是，数字签名与每条消息的内容相关联。因此，与手写签名所不同，每条消息的数字签名都是不同的。

让我们举一个例子说明下整个过程，包括从开始直到最后一步的验证。我们假设Alice向Bob发送一条消息、并将该消息进行散列得到哈希值，然后将哈希值与她的私钥结合起来生成数字签名。数字签名将作为该消息的唯一数字指纹。

当Bob收到消息时，他可以使用Alice提供的公钥来检查数字签名的有效性。这样，Bob可以确定签名是由Alice创建的，因为只有她拥有与该公钥所对应的私钥（至少这与我们所假设的一致）。

因此，Alice需要保管好私钥至关重要。如果另一个人拿到了Alice的私钥，他们就同样可以创建数字签名并伪装成Alice。在比特币的背景下，这意味着有人可以使用Alice的私钥，并可在未经她知晓的情况下转移或使用她的比特币。

数字签名通常用于实现以下三方面目标：数据完整性、身份验证和不可否认性。

数字签名可以应用于各种数字文档和证书。因此，他们有几个应用程序。一些最常见的案例包括：

数字签名方案面临的主要挑战主要局限于以下三方面因素：

简而言之，数字签名可以理解为是一种特定类型的电子签名，特指使用电子化的方式签署文档和消息。因此，所有数字签名都可认为是电子签名，但反之并非如此。

它们之间的主要区别在于身份验证方式。数字签名需要部署加密系统，例如散列函数、公钥加密和加密技术。

散列函数和公钥加密是数字签名系统的核心，现已在各种案例中使用。如果实施得当，数字签名可以提高安全性，确保完整性，便于对各类数据进行身份验证。

在区块链领域，数字签名用于签署和授权加密货币交易。它们对比特币尤为重要，因为数字签名能够确保代币只能由拥有相应私钥的人使用。

虽然我们多年来一直使用电子和数字签名，但仍有很大的发展空间。如今大部分的公文仍然还是基于纸质材料，但随着更多的系统迁移到数字化中，我们还会看到更多的数字签名方案。

G. 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也是安全的。
至此，可以证明算法的第二个优点。