好人勿用™

關於部落格
心寬念純●一生懸命●大願成就●幸福長久
  • 123832

    累積人氣

  • 14

    今日人氣

    0

    訂閱人氣

ECC (Elliptic Curve Cryptosystem)

Before Elliptic Curve Cryptosystem (ECC)
Let's Recap on 快雪時晴RSA 力不次 by Combo™

@ RSA = {p=7;q=13;n=7*13=91; e=5 at will; d=29 by輾轉相除法}
Pubic Key: {5}; Private Key: {29}

      RSA{n=91;Pub=5;Pri=29}

 你應該會覺得Combo™我在唬爛~~~

不相信的話... 請你從1~49選一個數字~
然後自己乘自己"五次"! 讓Combo™我來告訴你你剛剛所選擇的數字... ... ...

這根本是沙挖!!! 其實你若略懂RSA的話~
當你再做"自己乘自己五次"! 就是正在使用Combo™給你的公鑰在加密~

RSA: 即使讓你知道一個數是自己相乘N次(N as Public Key)的數字, 
        你也無從得知這個乘出來數是哪兩個數的乘積?! 這就是RSA成為trapdoor函數的密碼學性能!!!

Let's Practices!

(這裡會運用到小技巧, 當所相乘的值大於最大值時(>91), 則必須rolling over其數值!)

 Rolling over就是取餘數(模數modulo)~
而... 數學中的"模數"! Combo™覺得真的很像"魔術"~~~ Magic!!!

 不庸置疑?!?! 既生瑜...

     ECC Encryption VS RSA Encryption


何生亮?!?!
ECC需求較少運算量(這可改善運算效率), 其安全性又與RSA(或ElGamal)相當!!!


Elliptic Curve by Karl Weierstrass 1st Introduce

1.) 橢圓曲線方程式為y2=x3+ax+b
2.) 此曲線剛好對稱於x軸(y=0)這條直線
3.) 參數a及b必需滿足4a3+27b2≠0,才能確保沒有重根, 具有唯一解!
4.) 加法單位元素O為一無窮遠的點, 並滿足O=-O
5.) 此加法單位元素亦需滿足: 橢圓曲線上某三點共線其合為O

 用直白的話來說... 橢圓曲線方程式有兩個有趣的特性:
 
1.) 曲線上的任何點都以X軸反射(y=0),並且仍是同樣的曲線 (奇特的對稱性)
2.) 任何不垂直的線穿過曲線最多只會有三個交點 (更加有趣的特性)

 



 當然... Combo™覺得原作者這段最最...最為精彩!

 
將橢圓曲線比喻成擊球遊戲, 把球從A點擊向B點,
當再碰撞到曲線上的點後會反彈到(x軸以上或以下)另一邊的C點
 
先想像成把球在兩個點移動稱為"打點(dot)"
 
A dot B = C
A dot A = B
A dot C = D
... ... ...
 
如果這裡只有兩個點(稱為: 最初點&最終點),
將最初的點P自行打點n次(as Private Key)會得到一個最終點Q(as Public Key)

P dot P by n time = Q = P+P+P+P.....+P
                                      ^  By n times  ^

即使我給你座標上這兩個點, "最初點"&"最終點"~
就是說即使你知道"最初點"和"最終點", 要找出n是非常非常之困難的!!!

 以擊球遊戲比喻:

一個人在房間獨自擊球好幾次, 擊球時完全依照擊球規則來進行是很容易的!
後來如果一個人才進房間, 即使這這個人知道所有{規則,初始點,最終點}, 無從得知所擊球次數!!!

[ECC] 就是因為如此... 使ECC成為trapdoor函數有絕妙的密碼學性能!!!


Let’s get weird 


了解EC曲線基本特性! 這並不表示ECC其運用在密碼學的曲線所看起來的樣子!
如同RSA運算, ECC會需要把自己限制在一個固定範圍内來做計算(有限體內/有限域內)~
 
當計算y2 =x3+ax+b時, 當計算遭遇到最大值時, 要使用相同的技巧來rolling over數值!

        ~模數根本是魔術~
   

而... 挑選一個質數(prime number)當作為其最大值!
這橢圓曲線可被稱為"prime curve"(黃金曲線)並且有"神乎技矣"的密碼學性能!!!

把所有的點繪製到EC by y2 = x3-x+1, (a=-1;b=1)看起來的樣子:



Elliptic curve on line:
選取一質數(prima numer)為其最大值為97, 並重新繪製相同的EC看起來的樣子:

( 所有的點會被限制在最大值97的邊界內, 當點碰到邊界外時則必須roll over!)

以傳統的觀念來看上圖, 這看起來根本就不是曲線...
但它就是!!! 我們甚至還可觀察到其水平上下的對稱性(horizontal symmetry)

Discrete Elliptic Curve Plotter
http://www.graui.de/elliptic-plot.htm (a=-1;b=1;r=97)


實際上, 在這不像是EC曲線的曲線上依舊可以來應證EC方程式是有趣的特性!!!

從A點到B點為不垂直的線穿過曲EC線最多只會有三個交點!
當在碰撞到第三個交點時, 第三個交點一定可以在EC曲線x軸(以上或以下)找到一個對稱點C點~


用上面這新的曲線來示意, 我們可以獲得信息或者表示信息作為曲線上的點
With this new curve representation, you can take messages and represent them as points on the curve.

這可以想像成獲取一個信息並且設置它為x軸的座標上, 去解出它的y軸座標來得到曲線上的點(x,y)
You could imagine taking a message and setting it as the x coordinate and solving for y to get a point on the curve.

(知易行難), 但這就是ECC密碼學設計概念!!!
It is slightly more complicated than this in practice, but this is the general idea.

而... 這個根本就是經典遊戲!

               貪吃蛇(Snack)


 架構一個ECC橢圓曲線密碼學系統的基本參數:

(1) 選取一個質數(prime)當作最大值p
(2) 選取一個橢圓曲線方程式 y2 = x3 + ax + b (選擇a,b)
(3) 選取一個曲線上的公共點P(x,y)

@ Private Key(私鑰) => 任意選擇數字d at will but < p
@ Public Key(公鑰)   => 用公共點其本身打點d次 d*P(x,y)
於這密碼學系統中, 通過公鑰計算私鑰被稱為橢圓曲線離散對數函數
                         (by Elliptic curve discrete logarithm function)

Let's Practices @ 橢圓曲線金鑰交換演算法ECDH

1.) 首先,志明與春嬌選擇一組相同參數的橢圓曲線,其中包括{質數p,a,b},
    此橢圓曲線也必需滿足y2 = x3 + ax + b (mod p)
2.) 在橢圓曲線上, 志明與春嬌都選擇一個小於p且公共點P(x,y) as Public Key
3.) 志明任選擇一小於p的亂數d志明,接著計算d志明乘以公共點P(x,y), 得到一點Q志明(x,y) = d志明*P(x,y)
    志明私鑰 = {d志明} ; 志明公鑰 = {Q志明(x,y)}
4.) 志明將公鑰Q志明傳送給春嬌
5.) 春嬌任選擇一小於p的亂數d春嬌,接著計算d春嬌乘以公共點P(x,y), 得到一點Q春嬌(x,y) = d春嬌*P(x,y)
    春嬌私鑰 = {d春嬌} ; 春嬌公鑰 = {Q春嬌(x,y)}
6.) 春嬌將公鑰Q春嬌傳送給志明
7.) 志明可利用春嬌傳送過來的公鑰Q春嬌來計算出共享金鑰S志明與春嬌 = d志明*Q春嬌
8.) 春嬌可利用志明傳送過來的公鑰Q志明來計算出共享金鑰S志明與春嬌 = d春嬌*Q志明
9.) 最後, 現在志明與春嬌都會擁有對方的公鑰與共享一把相同的共享金鑰S志明與春嬌
     (S志明與春嬌 = d志明*Q春嬌d春嬌*Q志明



 以上運算需要一些數學基礎... 
當然...  Combo™數學沒學好! 必須借用網路上高手的連結來驗證~

Elliptic Curve scalar multiplication
https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/modk-mul.html

Elliptic curve E(Fp): Y2=X3+AX+B , p prime
@ (A=0; B=-4; p=211 n= d志明 = 203 or d春嬌 = 121)

http://www.graui.de/elliptic-plot.htm 
@ (a=0;b=-4;r=211)

Combo™把計算出來的點標示到EC plot @

P公共點(2,2)
Q志明(130,203)
Q春嬌(115,48)
S志明與春嬌 (161,169) <= 共同金鑰是沒有在EC曲線上!




 EC曲線還有一個重要參數q, 其概念:

EC橢圓曲線點的級數(order q)
1.) 點乘法計算n*P, 其中n為正整數而P為橢圓曲線上的一個點
2.) 如果EC曲線上的一個點能夠找到最小的正整數q滿足q*P = ∞(無限遠點), 則q稱為點P的級數(order)
3.) EC曲線上點的級數q一定是曲線級數的因數

級數(order q)計算 by Elliptic curve E(Fp): Y2=X3+AX+B , p prime


•質數體為GF(5)且橢圓曲線公式y2= x3+ x + 1
•這個橢圓曲線上的點, 除無限遠點∞外,
 另有還有8個點: (0,1),(0,4),(2,1),(2,4),(3,1),(3,4),(4,3),(4,2)點的座標值屬於GF(5)
 因為共有9點, 所以此曲線的級數(order)為9
•若選擇G=(0,1), 2G= (4,2), 3G=2G +G=(4,2), 4G=(3,4),5G=(3,1),
  6G=(2,4),7G=(4,3),8G=(0,4),9G=∞; 因為G =(0,1)時, 9G=∞, 所以此點G的級數為9
•若選擇G=(2,1),則2G=(2,4),3G=∞;  因為G=(2,1)時, 3G=∞, 所以此點G的級數為3



•質數體為GF(11)且橢圓曲線公式y2= x3+ x + 1
•這個橢圓曲線上的點, 除無限遠點∞外,
 另有13個點: (0,1),(0,10),(1,6),(1,5),(2,0),(3,8),(3,3),(4,6),(4,5), (6,6),(6,5),(8,2),(8,9) 
 點的座標值屬於GF(11), 因為共有14點, 所以此曲線的級數(order)為14
•若我們選G=(0,1), 則2G=(3,3),3G=(6,6),4G=(6,5),5G=(3,8),6G=(0,10),7G== ∞
  因為G=(0,1)時, 7G= ∞, 所以此點G的級數為7



有了EC橢圓曲線的基本參數概念後...
Combo™跟隨原作者來看看Elliptic Curve Cryptosystem的實際應用~

使用Chrome瀏覽https://blog.cloudflare.com
這個網站所使用就是Elliptic Curve Cryptography (ECC)~~~

ECDHC_ECDSA:

 
ECDHE: Elliptic Curve Diffie Hellman Ephemeral    (ECC金鑰交換機制)
ECDSA: Elliptic Curve Digital Signature Algorithm  (ECC數位簽章演算法)
DSA: Digital Signature Algorithm                         (數位簽章演算法)
Diffie–Hellman key exchange                              
(DH金鑰交換)



 據說google.com就是使用這個不安全的ECC曲線:

Curve P–256: y² = x³ + ax + b mod (p)
 


NIST P-256質數體橢圓曲線參數 @ y2 = x3 + ax + b mod (p256)
Mathematical routines for the NIST prime elliptic curves @ 4.3 Curve P–256 @ Page32

order = q: 如果EC上的一個點P,
                能夠找到最小的正整數q,滿足n*P = ∞(無限遠點),
則q稱為點P的級數!

p256 = 115792089210356248762697446949407573530086143415290314195533631308867097853951 (prime)
a      =  115792089210356248762697446949407573530086143415290314195533631308867097853948 (a = p256 −3)
b      =  41058363725152142129326129780047268409114441015993725554835256314039467401291
G = Base point (xG,yG) = P(x,y) = 公共點
       =   (48439561293906451759052585252797914202762949526041747995844080717082404635286,
                 36134250956749795798585127919587881956611106672985015071877198253568414405109)

Order q of the point G:
q     =   26959946667150639794667015087019625940457807714424391721682722368061

[Combo] 這個意味著... 選擇"G, P(10萬個大數(1077),10萬個大數(1077))"
               為基點(共同點), NIST P-256還有無量個(10
68)級數點!!! (亦包含無限遠點~)


ComboStyle™必須要唱首歌~
五月天 志明與春嬌!!! ECC網誌的Ending~
 
  已經無人看 已經無人聽 啊~~~
 
==================================
         五月天 志明與春嬌
==================================
作詞作曲:阿信 編曲:五月天 主唱:阿信
==================================
志明真正不知要按怎 為什麼 愛人不願閣再相偎
春嬌已經早就無在聽 講這多 其實攏總攏無卡抓
 
走到淡水的海岸 兩個人的愛情
已經無人看 已經無人聽 啊
 
我跟你最好就到這 你對我已經沒感覺 到這凍止 你也免愛我
我跟你最好就到這 你對我已經沒感覺 麥閣傷心
麥閣我這愛你 你不愛我
 
志明心情真正有影寒 風這大 你也真正攏沒心肝
春嬌你哪無要和我播 這場電影 咱就走到這位準嘟煞
===================================

其實... 看完原作者的文章懂了EC函數的參數與概念!
Combo™還是不是很清楚ECC如何運用PKI概念如何來加解密... ... ...

而... 結論是~~~




 模數是魔術!

而ECC概念就是封印在EC曲線房間裡!!!
所以Key Size相對比較小卻有相同的安全性(Security)等級!!!

而... 世界上只有相對安全! 沒有絕對安全!!!

"Security always comes at a cost to performance"
                                                                    
- Vincent Rijmen

 
                   模數是魔術 
 
                Combo™ Huang
 
      @ E(Fp): Y2=X3+aX+b; p prime

原文標題:A (relatively easy to understand) primer on elliptic curve cryptography
原文作者:Nick Sullivan
原文發表:2013年10月25日
簡中翻譯 : 一个关于椭圆曲线密码学的初级读本(相当容易懂)
來點Bitcoin吧! @ 1L3EuimbzuP2kDEvkkNQdBNVcaiC6MXC77


而... 以下這一系列ECC文章亦是好文章~
相簿設定
標籤設定
相簿狀態