當前位置:首頁 » 比特幣問答 » 橢圓曲線比特幣

橢圓曲線比特幣

發布時間: 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.獲得區塊獎勵:完成挖礦的節點可以獲得一定的比特幣獎勵,同時也可以獲得交易手續費作為獎勵。
總之,比特幣的運算主要涉及到加密演算法、分布式計算、哈希計算等技術,需要通過多個節點協同完成,確保交易記錄的安全和可靠性。

熱點內容
區塊鏈開啟工業40 發布:2024-12-25 17:06:39 瀏覽:286
國內做區塊鏈的外企 發布:2024-12-25 16:59:21 瀏覽:668
香港賬戶買usdt 發布:2024-12-25 16:59:17 瀏覽:910
漫步者是區塊鏈股票嗎 發布:2024-12-25 16:57:00 瀏覽:796
jta農業區塊鏈 發布:2024-12-25 16:48:26 瀏覽:842
幣圈的灰度是什麼意思 發布:2024-12-25 16:48:25 瀏覽:88
芝加哥商業交易所比特幣 發布:2024-12-25 16:16:47 瀏覽:181
軟錢包的幣轉到冷錢包 發布:2024-12-25 16:16:44 瀏覽:472
迷你世界半仙下挖礦 發布:2024-12-25 16:10:11 瀏覽:701
比特幣12月17日 發布:2024-12-25 16:02:06 瀏覽:121