iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 24
2
Security

看完眼眶濕濕的App開發者慘烈對抗險惡資安環境血與淚的控訴!系列 第 24

Day 24. 非對稱式加密演算法 - 橢圓曲線密碼學 Elliptic Curve Cryptography , ECC (觀念篇)

大家好,我是羊小咩

今天要介紹的是 ECC , ECC 一樣是用基於數學難題,製作出來的安全機制

由於 ECC 本來就是一種艱澀的演算法,因此在內文 ECC 流程及原理精簡了很多步驟、演算法及一些數學領域的專業術語

像是幾何加法(geometric addition),代數加法(Algebraic addition)、純量乘法 (Scalar multiplication),阿爾貝群(Abelian group)...等,這些都不是三言兩語可以簡易理解的,都需要一定基礎觀念。

整體用我認為比較簡單扼要的方式進行闡述

之前讀書會分享過ECC 議題,大家也都是聽的一知半解,想把ECC簡潔說明真的很困難 Orz

希望整理出的這篇讓讀者對ECC 有初步的認識和 ECC 的美好(?)

image-20201009005151787

ECC 簡介

橢圓曲線密碼學(英語:Elliptic Curve Cryptography,縮寫:ECC)是一種基於橢圓曲線數學的公開密鑰加密演算法。橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz和Victor Miller分別獨立提出的。

ECC的主要優勢是它相比RSA加密演算法使用較小的密鑰長度並提供相當等級的安全性[1]。ECC的另一個優勢是可以定義群之間的雙線性映射,基於Weil對或是Tate對;雙線性映射已經在密碼學中發現了大量的應用,例如基於身份的加密。

資料來源 wiki

RSA vs ECC 比較

PKI Algorithm RSA ECC
Key Size Security: 280 @ 1024-bits Security: 280 @160-bits
Security: 2112 @ 2048-bits Security: 2112 @224-bits
Security: 2128 @ 3072-bits Security: 2128 @ 256-bits
Security: 2:92 @ 7680-bits Security: 2192 @386-bits
Security: 2256 @ 15360-bits Security: 2256 @512-bits
安全基礎 大數因數分解 EC橢圖曲線上離散對數
優點 演算法容易說明,且同時可用做加解密 運算速度快,簽章長度較小
缺點 運算速度慢,簽章長度較大 理論較難理解,且實作技術較為複雜

從上表可以總結優點

image-20201009011638394

  • 安全性能更高

    160位ECC 和 1024位RSA、DSA有相同的安全强度

  • 處理速度更快

    ​ 在計算速度上,ECC比RSA、DSA快得多

  • 頻寬要求更低

  • 儲存空間更小

    ​ ECC的密鑰大小參數,與RSA、DSA相比要小得多

    非對稱加密算法中,之前最廣泛的 RSA 加密方法,逐漸開始被 ECC 取代

區塊鏈是基於 ECC 設計的,例如:使用ECC 製作出公鑰,經過Hash 得到地址,且此過程無法逆推還原

觀念/名詞定義

橢圓曲線

橢圓曲線是由以下形式的方程式定義 的平面曲線

{\displaystyle y^{2}=x^{3}+ax+b.}

其中ab是實數。這類稱為 Weierstrass方程式

image-20201009012820496

橢圓曲線運算規則(群組規則)

加法

過曲線上的兩點P、Q畫一條直線,找到直線與橢圓曲線的交點 -R
交點關於x軸對稱位置的點,定義為P Q,即為加法。如下圖所示:PQ = R

image-20201009013454604

乘法定義(兩倍運算)

上述方法無法解釋P P,即兩點重合的情況。因此在這種情況下,將橢圓曲線在 P 點的切線,與橢圓曲線的交點,交點關於x軸對稱位置的點,定義為P P,即2P,即為二倍運算

image-20201009013609229

無窮遠點

如果將A與-A相加,過A與-A的直線平行於y軸,可以認為直線與橢圓曲線相交於無窮遠點。

image-20201009013734119

橢圓曲線定義

依照上面特性定義後可整理出

  1. 橢圓曲線方程式為y2=x3+ax+b

  2. 此曲線剛好對稱於**x軸(y=0)**這條直線

  3. 參數a及b必需滿足4a3+27b2≠0,才能確保沒有重根, 具有唯一解!

  4. 加法單位元素O為一無窮遠的點, 並滿足O=-O

  5. 此加法單位元素亦需滿足: 橢圓曲線上某三點共線其合為O

橢圓曲線特性

  • 曲線上的任何點都以X軸反射(y=0),並且仍是同樣的曲線 (奇特的對稱性)
  • 任何不垂直的線穿過曲線最多只會有三個交點

奇怪的對稱

繪製的橢圓曲線。具有幾個有趣的屬性。

其中之一是水平對稱。曲線上的任何點都可以在x軸上反射並保持相同的曲線。一個更有趣的特性是,任何非垂直線最多將在三個地方與曲線相交。

將橢圓曲線比喻成擊球遊戲, 把球從A點擊向B點,
當再碰撞到曲線上的點後會反彈到(x軸以上或以下)另一邊的C點

img

先想像成把球在兩個點移動稱為"打點(dot)"

A dot B = C
A dot A = B
A dot C = D
... ... ...

這裡只有兩個點(稱為: 最初點&最終點)
將最初的點P自行打點 n次(as Private Key) 會得到一個最終點Q(as Public Key)

即使你知道"最初點"和"最終點"

要找出n是非常非常之困難!

有限域 (伽羅瓦域)和離散對數

橢圓曲線是連續的,容易被推算,因此,並不適合用於加密;
所以,我們必須把橢圓曲線變成離散的點

把橢圓曲線定義在有限域上,這時就會用到以質數為模的整數域 GF(p)

有限域GF(p)指給定某個質數p,由0、1、2……p-1共p個元素組成的整數集合中定義的加減乘除運算。

  假設橢圓曲線為y² = x³ x 1,其在有限域GF(23)上時,寫作:
  y² ≡ x³ x 1 (mod 23)

此時,橢圓曲線不再是一條光滑曲線,而是一些不連續的點,如下圖所示。以點(1,7)為例,7² ≡ 1³ 1 1 ≡ 3 (mod 23)。如此還有如下點:

  (0,1) (0,22)
  (1,7) (1,16)
  (3,10) (3,13)
  (4,0)
....

就可以使原本看起來是連續的曲線

image-20201009013609229

轉換到有限域上

214729t0hhla1y88quftl1

接著就可以進行貪食蛇遊戲(?)

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

214838iuneggurovjwowjv

補充:在域空間曲線,大概是這樣的一個感覺

1591846301-3238168022

ECC 應用

RSA 同演算法可以直接實現簽章及加密,ECC 需要分別實作

  • ECDSA (Elliptic Curve Digital Signature Algorithm)

  • ECIES (Elliptic Curve Integrated Encryption Scheme)

  • ECDH (Elliptic Curve Diffie–Hellman key Exchange)

ECC 簡易定義及運作流程

計算實例

設定出一個有限域Fp

略過選取曲線,和給定參數過程計算後

曲線已知E23(1,1)上兩點P(3,10),Q(9,7),求(1)-P,(2)P+Q,(3) 2P

image-20201009020457980

圖片來源 https://www.zhihu.com/question/26662683

如果橢圓曲線上一點P,存在最小的正整數n使得數乘nP=O∞ ,則將n稱為P的階

若n不存在,則P是無限階的

image-20201009020508303

圖片來源 https://www.zhihu.com/question/26662683

因此選定 n 後即可 計算出可得27P=-P

所以28P=O ∞ P的階為28

這些點做成了一個循環阿貝爾群,其中生成元為P,階數為29

並從裡面選取基點,並開始計算

考慮K=kG ,其中K、G為橢圓曲線Ep(a,b)上的點,n為G的階(nG=O∞),k為小於n的整數。

則給定k和G,根據加法法則,計算K很容易

但反過來,給定K和G,求k就非常困難
其中k、K分別為私鑰、公鑰。

這就是橢圓曲線計算流程

一條橢圓曲線 {p,a,b,G,n,h}

  • p : 一個質數 決定域
  • a , b : 曲線參數
  • G : 基點
  • n : G的階
  • h : 商除整數

橢圓曲線加解密演算法原理 ECIES

設私鑰、公鑰分別為k、K,即K = kG,其中G為G點。

公鑰加密:

選擇隨機數r,將訊息M生成密文C,該密文是一個點對,即:
C = {rG, M rK},其中K為公鑰

私鑰解密:

M rK – k(rG) = M r(kG) – k(rG) = M
其中k、K分別為私鑰、公鑰。

橢圓曲線上的已知G和xG求x,是非常困難的,此即為橢圓曲線上的的離散對數問題。此處x即為私鑰,xG即為公鑰。

橢圓曲線簽名演算法原理 ECDSA

設私鑰、公鑰分別為k、K,即K = kG,其中G為G點。
私鑰簽名:

1、選擇隨機數r,計算點rG(x, y)。
2、根據隨機數r、訊息M的雜湊h、私鑰k,計算s = (h kx)/r。
3、將訊息M、和簽名{rG, s}發給接收方

公鑰驗證簽名:

1、接收方收到訊息M、以及簽名{rG=(x,y), s}。
2、根據訊息求雜湊h。
3、使用傳送方公鑰K計算:hG/s xK/s,並與rG比較,如相等即驗籤成功

原理如下:

hG/s xK/s = hG/s x(kG)/s = (h xk)G/s
= r(h xk)G / (h kx) = rG

ECC 安全性

ECC 一樣採用數學難題,進行設計,但難度比REA 質因數分寫還要難,而且運算比RSA 還要快

使用 ECDH (Elliptic Curve Diffie–Hellman key Exchange)舉例

定義了一條橢圓曲線 image-20201009021107472

image-20201009021241565 因此 n = 19 , h = 1

image-20201009021407308

圖片來源 :https://www.youtube.com/watch?v=F3zzNa42-tQ

詳細計算可以觀看影片

現實上,計算實會選用大的數字和質數,使其幾乎無法反推計算

image-20201009021549868

ECC 應用

  • TLS/SSL 數位憑證
  • 基於身份加密
  • 區塊鏈數位簽名
  • 序號產生驗證

小結

ECC 一樣是用基於數學難題,製作出來的安全機制

我在 ECC 流程及原理精簡了很多步驟、演算法及一些數學領域的專業術語

像是幾何加法(geometric addition),代數加法(Algebraic addition)、純量乘法 (Scalar multiplication),阿爾貝群(Abelian group)...等,這些都不是三言兩語可以簡易理解的,都需要一定基礎觀念。

整體用我認為比較簡單扼要的方式進行闡述

之前讀書會分享過ECC 議題,大家也都是聽的一知半解,想把ECC簡潔說明真的很困難 Orz

希望整理出的這篇讓讀者對ECC 有初步的認識和 ECC 的美好(?)

參考資料

https://en.wikipedia.org/wiki/Elliptic_curve

https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95

Elliptic Curve Cryptography: a gentle introduction

Elliptic Curve Cryptography: finite fields and discrete logarithms
Elliptic Curve Cryptography: ECDH and ECDSA

Elliptic Curve Cryptography: breaking security and a comparison with RSA

https://combohuang.pixnet.net/blog/post/212457468-ecc-(elliptic-curve-cryptosystem)

https://codertw.com/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/43964/


上一篇
Day 23. 非對稱式加密演算法 - RSA (觀念篇)
下一篇
Day 25. 非對稱式加密演算法 - RSA (實戰篇)
系列文
看完眼眶濕濕的App開發者慘烈對抗險惡資安環境血與淚的控訴!31

1 則留言

0
b4106702
iT邦新手 5 級 ‧ 2021-01-14 14:38:35

假設橢圓曲線為y² = x³ x 1,其在有限域GF(23)上時,寫作:
  y² ≡ x³ x 1 (mod 23)

應該是y² ≡ x³ + x + 1 (mod 23)吧

我要留言

立即登入留言