好人勿用™

 數大便是美!
其實是... 數大便是複雜難理解!!!

( 是... "數大"便是美! 不是... "數大便"是美~)

萬：代表的是10的四次方。       
億：代表的是10的八次方。         
兆：代表的是10的十二次方。       
京：代表的是10的十六次方。      
垓：代表的是10的二十次方。
杼：代表的是10的二十四次方。
穰：代表的是10的二十八次方。
溝：代表的是10的三十二次方。
澗：代表的是10的三十六次方。
正：代表的是10的四十次方。
載：代表的是10的四十四次方。
極：代表的是10的四十八次方。
恆河沙：代表的是10的五十二次方 。
阿僧祇：代表的是10的五十六次方。
那由它：代表的是10的六十次方。
不可思議：代表的是10的六十四次方。
無量：代表的是10的六十八次方。
大數：代表的是10的七十二次方。

 個+十+百+千+萬+億+兆+京+垓+杼+穰+溝+澗+正
+載+極+恆河沙+阿僧祇+那由它+不可思議+無量 = -1/12

 1 + 2 + 3 + 4 + 5 + ... = ∞ or -1/12 ?

( 當數字大到無限大... 就會變得很難理解!!!)

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.) 橢圓曲線方程式為y²=x³+ax+b
2.) 此曲線剛好對稱於x軸(y=0)這條直線

4.) 加法單位元素O為一無窮遠的點, 並滿足O=-O
5.) 此加法單位元素亦需滿足: 橢圓曲線上某三點共線其合為O

 用直白的話來說... 橢圓曲線方程式有兩個有趣的特性:

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

 以擊球遊戲"神比喻":

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

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


Let’s get weird 

了解EC曲線基本特性! 這並不表示ECC其運用在密碼學的曲線所看起來的樣子!
如同RSA運算, ECC會需要把自己限制在一個固定範圍内來做計算(有限體內/有限域內)~

當計算y2 =x3+ax+b時, 當計算遭遇到最大值時, 要使用相同的技巧來rolling over數值!


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

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


Elliptic curve on line:

https://www.desmos.com/calculator/ialhd71we3

 

選取一質數(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) 選取一個橢圓曲線方程式 y² = x³ + 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},
    此橢圓曲線也必需滿足y² = x³ + 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): Y²=X³+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): Y²=X³+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曲線:

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

// 2020.06.11 Combo補齊本本篇網誌圖片

志明心情真正有影寒　風這大　你也真正攏沒心肝
春嬌你哪無要和我播　這場電影　咱就走到這位準嘟煞
===================================

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

而... 結論是~~~




 模數是魔術!

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

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

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

 

      @ E(Fp): Y²=X³+aX+b; p prime

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

而... 以下這一系列ECC文章亦是好文章~