当前位置:首页 » 比特币问答 » 椭圆曲线比特币

椭圆曲线比特币

发布时间: 2024-12-25 15:03:28

比特币源码研读一:椭圆曲线在比特币密码中的加密原理

参加比特币源码研读班后首次写作,看到前辈black写的有关密钥,地址写的很好了,就选了他没有写的椭圆曲线,斗胆写这一篇。

在密码学上有两种加密方式,分别是对称密钥加密和非对称密钥加密。

对称加密:加密和解密使用的同样的密钥。

非对称加密:加密和解密是使用的不同的密钥。

二战中图灵破解德军的恩尼格码应该就是用的对称加密,因为他的加密和解密是同一个密钥。比特币的加密是非对称加密,而且用的是破解难度较大的椭圆曲线加密,简称ECC。

非对称加密的通用原理就是用一个难以解决的数学难题做到加密效果,比如RSA加密算法。RSA加密算法是用求解一个极大整数的因数的难题做到加密效果的。就是说两个极大数相乘,得到乘积很容易,但是反过来算数一个极大整数是由哪两个数乘积算出来的就非常困难。

下面简要介绍一下椭圆曲线加密算法ECC。

首先椭圆曲线的通式是这个样子的:

一般简化为这个样子:

()发公式必须吐槽一下,太麻烦了。)

其中

这样做就排除了带有奇点的椭圆曲线,可以理解为所有的点都有一条切线。

图像有几种,下面列举几个:[1]

椭圆曲线其实跟椭圆关系不大,也不像圆锥曲线那样,是有圆锥的物理模型为基础的。在计算椭圆曲线的周长时,需要用到椭圆积分,而椭圆曲线的简化通式:

,周长公式在变换后有一项是这样的:,平方之后两者基本一样。

我们大体了解了椭圆曲线,就会有一个疑问,这个东西怎么加密的呢?也就是说椭圆曲线是基于怎样的数学难题呢?在此之前还得了解一些最少必要知识:椭圆曲线加法,离散型椭圆曲线。

椭圆曲线加法

数学家门从普通的代数运算中,抽象出了加群(也叫阿贝尔群或交换群),使得在加群中,实数的算法和椭圆曲线的算法得到统一。

数学中的“群”是一个由我们定义了一种二元运算的集合,二元运算我们称之为“加法”,并用符号“+”来表示。为了让一个集合G成为群,必须定义加法运算并使之具有以下四个特性:

1. 封闭性:如果a和b是集合G中的元素,那么(a + b)也是集合G中的元素。

2. 结合律:(a + b) + c = a + (b + c);

3. 存在单位元0,使得a + 0 = 0 + a =a;

4. 每个元素都有逆元,即:对于任意a,存在b,使得a + b = 0.

如果我们增加第5个条件:

5. 交换律: a + b = b + a

那么,称这个群为阿贝尔群。[1]

运算法则:任意取椭圆曲线上两点P、Q (若P、Q两点重合,则做P点的切线)做直线交于椭圆曲线的另一点R’,过R’做y轴的平行线交于R。我们规定P+Q=R。(如图)[2]

特别的,当P和Q重合时,P+Q=P+P=2P,对于共线的三点,P,Q,R’有P+Q+R’=0∞.

这里的0∞不是实数意义的0,而是指的无穷远点(这里的无穷远点就不细说了,你可以理解为这个点非常遥远,遥远到两条平行线都在这一点相交了。具体介绍可以看参考文献[2])。

注意这里的R与R’之间的区别,P+Q=R,R并没有与P,Q共线,是R’与P,Q共线,不要搞错了。

法则详解:

这里的+不是实数中普通的加法,而是从普通加法中抽象出来的加法,他具备普通加法的一些性质,但具体的运算法则显然与普通加法不同。

根据这个法则,可以知道椭圆曲线无穷远点O∞与椭圆曲线上一点P的连线交于P’,过P’作y轴的平行线交于P,所以有无穷远点 O∞+ P = P 。这样,无穷远点 O∞的作用与普通加法中零的作用相当(0+2=2),我们把无穷远点 O∞ 称为零元。同时我们把P’称为P的负元(简称,负P;记作,-P)。(参见下图)

离散型椭圆曲线

上面给出的很好看的椭圆曲线是在实数域上的连续曲线,这个是不能用来加密的,原因我没有细究,但一定是连续曲线上的运算太简单。真正用于加密的椭圆曲线是离散型的。要想有一个离散型的椭圆曲线,先得有一个有限域。

域:在抽象代数中,域(Field)之一种可进行加、减、乘、除运算的代数结构。它是从普通实数的运算中抽像出来的。这一点与阿贝尔群很类似。只不过多了乘法,和与乘法相关的分配率。

域有如下性质[3]:

1.在加法和乘法上封闭,即域里的两个数相加或相乘的结果也在这个域中。

2.加法和乘法符合结合律,交换率,分配率。

3.存在加法单位,也可以叫做零元。即存在元素0,对于有限域内所有的元素a,有a+0=a。

4.存在乘法单位,也可以叫做单位元。即存在元素1,对于有限域内所有的元素a,有1*a=a。

5.存在加法逆元,即对于有限域中所有的元素a,都存在a+(-a)=0.

6.存在乘法逆元,即对于有限域中所有的元素a,都存在a*=0.

在掌握了这些知识后,我们将椭圆曲线离散化。我们给出一个有限域Fp,这个域只有有限个元素。Fp中只有p(p为素数)个元素0,1,2 …… p-2,p-1;

Fp 的加法(a+b)法则是 a+b≡c (mod p);它的意思是同余,即(a+b)÷p的余数与c÷p的余数相同。

Fp 的乘法(a×b)法则是 a×b≡c (mod p);

Fp 的除法(a÷b)法则是 a/b≡c (mod p);即 a×b∧-1≡c (mod p);(也是一个0到p-1之间的整数,但满足b×b∧-1≡1 (mod p);

Fp 的单位元是1,零元是 0(这里的0就不是无穷远点了,而是真正的实数0)。

下面我们就试着把

这条曲线定义在Fp上:

选择两个满足下列条件的小于p(p为素数)的非负整数a、b,且a,b满足

则满足下列方程的所有点(x,y),再加上无穷远点O∞ ,构成一条椭圆曲线。

其中 x,y属于0到p-1间的整数,并将这条椭圆曲线记为Ep(a,b)。

图是我手画的,大家凑合看哈。不得不说,p取7时,别看只有10个点,但计算量还是很大的。

Fp上的椭圆曲线同样有加法,法则如下:

        1. 无穷远点 O∞是零元,有O∞+ O∞= O∞,O∞+P=P

        2. P(x,y)的负元是 (x,-y),有P+(-P)= O∞

3. P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系:

x3≡-x1-x2(mod p)

y3≡k(x1-x3)-y1(mod p)

其中若P=Q 则 k=(3+a)/2y1 若P≠Q,则k=(y2-y1)/(x2-x1)

通过这些法则,就可以进行离散型椭圆曲线的计算。

例:根据我画的图,(1,1)中的点P(2,4),求2P。

解:把点带入公式k=(3*x∧2+a)/2y1

有(3*2∧2+1)/2*4=6(mod 7).

(注意,有些小伙伴可能算出13/8,这是不对的,这里是模数算数,就像钟表一样,过了12点又回到1点,所以在模为7的世界里,13=6,8=1).

x=6*6-2-2=4(mod 7)

y=6*(2-4)-4=2 (mod 7)

所以2P的坐标为(2,4)

那椭圆曲线上有什么难题呢?在模数足够大的情况下,上面这个计算过程的逆运算就足够难。

给出如下等式:

K=kG (其中 K,G为Ep(a,b)上的点,k为小于n(n是点G的阶)的整数)不难发现,给定k和G,根据加法法则,计算K很容易;但给定K和G,求k就相对困难了。

这就是椭圆曲线加密算法采用的难题。我们把点G称为基点(base point),k称为私钥,K称为公钥。

现在我们描述一个利用椭圆曲线进行加密通信的过程[2]:

1、用户A选定一条椭圆曲线Ep(a,b),并取椭圆曲线上一点,作为基点G。

2、用户A选择一个私钥k,并生成公钥K=kG。

3、用户A将Ep(a,b)和点K,G传给用户B。

4、用户B接到信息后 ,将待传输的明文编码到Ep(a,b)上一点M(编码方法很多,这里不作讨论),并产生一个随机整数r(r<n)。

5、用户B计算点C1=M+rK;C2=rG。

6、用户B将C1、C2传给用户A。

7、用户A接到信息后,计算C1-kC2,结果就是点M。因为

C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M

再对点M进行解码就可以得到明文。

整个过程如下图所示:

密码学中,描述一条Fp上的椭圆曲线,常用到六个参量:

T=(p,a,b,G,n,h),p 、a 、b 用来确定一条椭圆曲线,G为基点,n为点G的阶,h 是椭圆曲线上所有点的个数m与n相除的整数部分

这几个参量取值的选择,直接影响了加密的安全性。参量值一般要求满足以下几个条件:

1、p 当然越大越安全,但越大,计算速度会变慢,200位左右可以满足一般安全要求;

2、p≠n×h;

3、pt≠1 (mod n),1≤t<20;

4、4a3+27b2≠0 (mod p);

5、n 为素数;

6、h≤4。

200位位的一个数字,那得多大?而且还是素数,所以这种方式是非常安全的。而且再一次交易中,区块被记录下来只有10分钟的时间,也就是说要想解决这个难题必须在10分钟以内。即便有技术能够在10分钟以内破解了现在这个难度的加密算法,比特币社区还可以予以反制,提高破解难度。所以比特币交易很安全,除非自己丢掉密钥,否则不存在被破解可能。

第一次写一个完全陌生的数学领域的知识,也许我有错误的地方,也许有没讲明白的地方,留言讨论吧。总之写完后对比特比系统的安全性表示很放心。

参考文献

[1] 椭圆曲线密码学简介

[2] 什么是椭圆曲线加密(ECC)

[3] 域(数学)维基网络

区块链研习社源码研读班 高若翔

⑵ 高中生如何理解比特币加密算法

加密算法是数字货币的基石,比特币的公钥体系采用椭圆曲线算法来保证交易的安全性。这是因为要攻破椭圆曲线加密就要面对离散对数难题,目前为止还没有找到在多项式时间内解决的办法,在算法所用的空间足够大的情况下,被认为是安全的。本文不涉及高深的数学理论,希望高中生都能看懂。

密码学具有久远的历史,几乎人人都可以构造出加解密的方法,比如说简单地循环移位。古老或简单的方法需要保密加密算法和秘钥。但是从历史上长期的攻防斗争来看,基于加密方式的保密并不可靠,同时,长期以来,秘钥的传递也是一个很大的问题,往往面临秘钥泄漏或遭遇中间人攻击的风险。

上世纪70年代,密码学迎来了突破。Ralph C. Merkle在1974年首先提出非对称加密的思想,两年以后,Whitfield Diffie和Whitfield Diffie两位学者以单向函数和单向暗门函数为基础提出了具体的思路。随后,大量的研究和算法涌现,其中最为著名的就是RSA算法和一系列的椭圆曲线算法。

无论哪一种算法,都是站在前人的肩膀之上,主要以素数为研究对象的数论的发展,群论和有限域理论为基础。内容加密的秘钥不再需要传递,而是通过运算产生,这样,即使在不安全的网络中进行通信也是安全的。密文的破解依赖于秘钥的破解,但秘钥的破解面临难题,对于RSA算法,这个难题是大数因式分解,对于椭圆曲线算法,这个难题是类离散对数求解。两者在目前都没有多项式时间内的解决办法,也就是说,当位数增多时,难度差不多时指数级上升的。

那么加解密如何在公私钥体系中进行的呢?一句话,通过在一个有限域内的运算进行,这是因为加解密都必须是精确的。一个有限域就是一个具有有限个元素的集合。加密就是在把其中一个元素映射到另一个元素,而解密就是再做一次映射。而有限域的构成与素数的性质有关。

前段时间,黎曼猜想(与素数定理关系密切)被热炒的时候,有一位区块链项目的技术总监说椭圆曲线算法与素数无关,不受黎曼猜想证明的影响,就完全是瞎说了。可见区块链项目内鱼龙混杂,确实需要好好洗洗。

比特币及多数区块链项目采用的公钥体系都是椭圆曲线算法,而非RSA。而介绍椭圆曲线算法之前,了解一下离散对数问题对其安全性的理解很有帮助。

先来看一下 费马小定理

原根 定义:
设(a, p)=1 (a与p互素),满足

的最下正整数 l,叫作a模p的阶,模p阶为(最大值)p-1的整数a叫作模p的原根。

两个定理:

基于此,我们可以看到,{1, 2, 3, … p-1} 就是一个有限域,而且定义运算 gi (mod p), 落在这个有限域内,同时,当i取0~p-2的不同数时,运算结果不同。这和我们在高中学到的求幂基本上是一样的,只不过加了一层求模运算而已。

另一点需要说明的是,g的指数可以不限于0~p-2, 其实可以是所有自然数,但是由于

所以,所有的函数值都是在有限域内,而且是连续循环的。

离散对数定义:
设g为模p的原根,(a,p) = 1,

我们称 i 为a(对于模p的原根g)的指数,表示成:

这里ind 就是 index的前3个字母。
这个定义是不是和log的定义很像?其实这也就是我们高中学到的对数定义的扩展,只不过现在应用到一个有限域上。

但是,这与实数域上的对数计算不同,实数域是一个连续空间,其上的对数计算有公式和规律可循,但往往很难做到精确。我们的加密体系里需要精确,但是在一个有限域上的运算极为困难,当你知道幂值a和对数底g,求其离散对数值i非常困难。

当选择的素数P足够大时,求i在时间上和运算量上变得不可能。因此我们可以说i是不能被计算出来的,也就是说是安全的,不能被破解的。

比特币的椭圆曲线算法具体而言采用的是 secp256k1算法。网上关于椭圆曲线算法的介绍很多,这里不做详细阐述,大家只要知道其实它是一个三次曲线(不是一个椭圆函数),定义如下:

那么这里有参数a, b;取值不同,椭圆曲线也就不同,当然x, y 这里定义在实数域上,在密码体系里是行不通的,真正采用的时候,x, y要定义在一个有限域上,都是自然数,而且小于一个素数P。那么当这个椭圆曲线定义好后,它反应在坐标系中就是一些离散的点,一点也不像曲线。但是,在设定的有限域上,其各种运算是完备的。也就是说,能够通过加密运算找到对应的点,通过解密运算得到加密前的点。

同时,与前面讲到的离散对数问题一样,我们希望在这个椭圆曲线的离散点阵中找到一个有限的子群,其具有我们前面提到的遍历和循环性质。而我们的所有计算将使用这个子群。这样就建立好了我们需要的一个有限域。那么这里就需要子群的阶(一个素数n)和在子群中的基点G(一个坐标,它通过加法运算可以遍历n阶子群)。

根据上面的描述,我们知道椭圆曲线的定义包含一个五元祖(P, a, b, G, n, h);具体的定义和概念如下:

P: 一个大素数,用来定义椭圆曲线的有限域(群)
a, b: 椭圆曲线的参数,定义椭圆曲线函数
G: 循环子群中的基点,运算的基础
n: 循环子群的阶(另一个大素数,< P )
h:子群的相关因子,也即群的阶除以子群的阶的整数部分。

好了,是时候来看一下比特币的椭圆曲线算法是一个怎样的椭圆曲线了。简单地说,就是上述参数取以下值的椭圆曲线:

椭圆曲线定义了加法,其定义是两个点相连,交与图像的第三点的关于x轴的对称点为两个点的和。网上这部分内容已经有很多,这里不就其细节进行阐述。

但细心的同学可能有个疑问,离散对数问题的难题表现在求幂容易,但求其指数非常难,然而,椭圆曲线算法中,没有求幂,只有求乘积。这怎么体现的是离散对数问题呢?

其实,这是一个定义问题,最初椭圆曲线算法定义的时候把这种运算定义为求和,但是,你只要把这种运算定义为求积,整个体系也是没有问题的。而且如果定义为求积,你会发现所有的操作形式上和离散对数问题一致,在有限域的选择的原则上也是一致的。所以,本质上这还是一个离散对数问题。但又不完全是简单的离散对数问题,实际上比一般的离散对数问题要难,因为这里不是简单地求数的离散对数,而是在一个自定义的计算上求类似于离散对数的值。这也是为什么椭圆曲线算法采用比RSA所需要的(一般2048位)少得多的私钥位数(256位)就非常安全了。

⑶ 比特币地址是怎么产生的

比特币使用椭圆曲线算法生成公钥和私钥,选择的是secp256k1曲线。生成的公钥是33字节的大数,私钥是32字节的大数,钱包文件wallet.dat中直接保存了公钥和私钥。我们在接收和发送比特币时用到的比特币地址是公钥经过算法处理后得到的,具体过程是公钥先经过SHA-256算法处理得到32字节的哈希结果,再经过RIPEMED算法处理后得到20字节的摘要结果,再经过字符转换过程得到我们看到的地址。这个字符转换过程与私钥的字符转换过程完成相同,步骤是先把输入的内容(对于公钥就是20字节的摘要结果,对于私钥就是32字节的大数)增加版本号,经过连续两次SHA-256算法,取后一次哈希结果的前4字节作为校验码附在输入内容的后面,然后再经过Base58编码,得到字符串。乔曼特区块链专业站链乔教育在线是从事区块链相关培训,且获得教育部认证的区块链专业培训工作站。

⑷ 比特币算法原理

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

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

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

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

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

⑸ 比特币怎么样运算


比特币怎么运算的
比特币是一种基于密码学原理的数字货币,其运算主要涉及到加密算法和分布式计算的技术。
比特币的运算过程主要包括以下几个步骤:
1.生成公私钥对:比特币使用椭圆曲线加密算法(ECDSA)生成公私钥对,其中私钥用于签名交易,公钥用于验证签名。
2.生成交易信息:交易信息包括发送者地址、接收者地址、转账金额等信息,用于描述比特币的交易过程。
3.验证交易信息:将交易信息加上时间戳、发送者公钥、哈希等信息,组成交易记录,并通过网络广播给其他节点验证。
4.挖矿计算:比特币的挖矿是指将交易记录打包成区块并添加到区块链中的过程。挖矿过程需要进行一系列的计算,包括哈希计算、难度计算等,这些计算需要通过分布式计算来完成。
5.获得区块奖励:完成挖矿的节点可以获得一定的比特币奖励,同时也可以获得交易手续费作为奖励。
总之,比特币的运算主要涉及到加密算法、分布式计算、哈希计算等技术,需要通过多个节点协同完成,确保交易记录的安全和可靠性。

热点内容
椭圆曲线比特币 发布:2024-12-25 15:03:28 浏览:155
区块链中小企业发行通证 发布:2024-12-25 14:57:37 浏览:398
济南币圈联系方式 发布:2024-12-25 14:41:21 浏览:774
BAT类公司区块链 发布:2024-12-25 14:40:34 浏览:522
中国比特币富豪 发布:2024-12-25 14:21:15 浏览:326
酷派区块链手机发布会 发布:2024-12-25 14:02:15 浏览:293
钱包usdt怎样跨链转换 发布:2024-12-25 13:35:26 浏览:9
矮人挖矿大魔王的游戏 发布:2024-12-25 13:29:30 浏览:914
f2鱼池莱特币地址 发布:2024-12-25 13:01:31 浏览:12
莱特币那年价格最高 发布:2024-12-25 13:00:44 浏览:496