---
title: ECC
tags: ECC, nisra, 2017fall, ppt
---
[TOC]
# ECC 研究
組員：PS、SetMao、中學生
---
## 密碼學簡介
----
en
有in , upon(使得)的意思
----
code
密碼
----
en + code = encode
使得 + 密碼 = 使它變成密碼
----
encode = 加密??
----
encrypt
encrypt
encrypt
----
encode v.s encrypt
----
encode.py
----
密碼學為一種利用數學方法來對資料加密和解密的科學。
----
----
- 加密技術強度的高低通常牽涉到下列的因素
- 演算法強度
- 金鑰保護機制
- 金鑰的長度
----
- Kerckhoff Principle
- 密碼系統的安全性不在演算法的保密，而是取決於金鑰的保密機制。
---
Symmetric Encryption(對稱式加密)
Asymmetric Encryption (非對稱式加密)
----
### Symmetric Encryption(對稱式加密)
----
----
Caesar cipher(凱薩密碼)
----
caesar.py
----
### Data Encryption Standard
### (對稱式加解密法)
----
----
permutation
contraction
left circular shift
F(費斯妥函数)
----
| | x = 1 | x = 0 |
| -------- | -------- | -------- |
| y = 1 | 0 | 1 |
| y = 0 | 1 | 0 |
----
----
----
expansion
permutation
S
----
----
----
### Advanced Encryption Standard
### (對稱式加解密法)
----
破解DES 需要的時間不斷被縮短，在1998 年已經被縮短到了56 小時，1999 年的獲勝者更是只花了少於一天的22 小時便完成了破解。 2000 年，DES 的「聯邦政府標準」寶座，也在公開競爭以後被全新標準AES（Advanced Encryption Standard）給取代。
----
----
AddRoundKey(輪密鑰加)
SubBytes（字節代替） #1 bytes（字節） = 8 bits（位元）
ShiftRows（行位移）
MixColumns（列混淆）
----
----
----
----
---
### RSA(非對稱性加解密法)
----
---
## DES v.s. RSA
----
| | DES | RSA |
|:--:|:--:|:--:|
| 其它名稱 | 秘密金鑰加密法 | 公開金鑰加密法 |
| 加解密的key是否相同 | 相同 | 不同 |
| key可否公開 | 不可公開 | 公開鑰匙可以公開，私有鑰匙不可公開|
----
| | DES | RSA |
|:--:|:--:|:--:|
| key保管問題 |如果與N個人交換訊息,需保管好N把加解密鑰匙 | 無論與多少人交換訊息，只需保管自己的私密鑰匙|
| 加解密速度 |快 | 慢|
| 應用 | 常用於加密長度較長的資料，例：email |常用於加密長度較短的資料、數位簽章 |
---
前情提要 OwO)b
## RSA 原理
----
### 公私鑰製造過程
1. 選兩個互質的數字(p = 7, q = 19)
2. 計算 ```n = p * q``` (n = 7 * 19 = 133)
3. 計算 ```m = (p-1) * (q-1)``` (m = 6 * 18 = 108)
4. 選一個 e (與 m 互質的數字)(e = 5)
5. 計算 ```d * e mod m = 1``` (d = 65)
6. 公鑰 ```{n, e} = {133, 5}```、私鑰 ```{n, d} = {133, 65}```
----
### 驗證過程
1. 假設 Bob 要跟 Alice 說 ```33``` ， 則 Bob 必須用 Alice 的公鑰去加密
33^5^ % 133 = 10
2. 當 Alice 收到 Bob 傳來的 ```10``` ，則她必須用私鑰去解密
10^65^ % 133 = 33
---
這是一杯咖啡，認同請分享
---
## 什麼是ECC？
----
Elliptic Curves Cryptography，橢圓曲線密碼學
新一代的公開金鑰演算法，由於 ECC 所需的記憶體較少，所以非常適合在例如智慧卡等的資源有限環境下使用。
---
## ECC 原理
----
Weierstrass方程：
**y^2^ + Axy + By = x^3^ + Cx^2^ + Dx + E**
滿足魏爾斯特拉斯函數的方程式
且除了 (0, 0) 之外任一點皆存在切線
則可稱作橢圓曲線
該曲線形狀並非橢圓，而是因為其與取橢圓周長的公式相近而得名
----
公式：y^2^ + Axy + By = x^3^ + Cx^2^ + Dx + E
共線方程式：y = kx + b
----
制定一個有限域F，其中包含p個元素 (p為一質數)
加法法則：**a + b ≡ c (mod p)**
乘法法則：**a × b ≡ c (mod p)**
除法法則：**a × b^-1^ ≡ c (mod p)**
轉成離散型式的有限域E
----
y^2^ = x^3^ + x + 1 (mod 23)
----
**y^2^ = x^3^ + ax + b**
為最簡單的可做為加密法的橢圓曲線 OwO)b
----
若橢圓曲線上任一點P，存在有一個最小正整數n，使 **nP = O^∞^**
則稱n為P的**階**
----
函式：y^2^ = x^3^ + x + 1
P = (1,7)
2P？
----
Xp=1,Yp=7
Xq=1,Yq=7
斜率：
y'=( 3(Xp)^2^ + a ) / ( 2Yp ) mod p
y'=2/7 mod p
----
Xr公式為Xr= ( λ^2^ - Xp - Xq ) mod p
Yr公式為Yr= ( λ(Xp-Xr) - Yp ) mod p
2P=(7,11)
----
能公開金鑰的加密法，都必須基於一個數學難題
比如RSA，RSA很容易能選定兩個質數p、q相乘為n，但我們很難去幫n做因式分解得到p、q，這是RSA的數學難題。
那ECC呢？
----
**K=kG**
K = 公鑰，為E(a,b)上面的一點
k = 私鑰，為一小於n的整數
----
明文被編碼在 M 點上
M 為 E(a,b)上一點
----
C1 - kC2
= M + rK - **k(rG)**
= M + rK - **r(kG)**
= M + r (K - kG)
= M
---
## RSA v.s ECC
----
---
## 攻擊手法
1. 金鑰分配
2. 時間攻擊
3. 長度
---
## ECC 應用
---
## ECDSA
ECDSA 是 橢圓曲線密碼學(Elliptic Curve Cryptography, <span><!-- .element: class="fragment highlight-red" -->ECC</span>) <br/> + <br/>數位簽章演算法(Digital Signature Algorithm, <span><!-- .element: class="fragment highlight-red" -->DSA</span>)
----
## DSA？
與 RSA 概念類似。
----
* 資料完整性 (Integrity)
* 身份鑑別性 (Authentication)
* 不可否認性 (Non-Repudiation)
----
## ECDSA 金鑰產生
----
1. 選擇一個有限域 E(a,b)
2. 選擇一正整數 k 為私鑰
3. 計算 K = kG
4. 公開金鑰 { E(a,b)，K，G }
----
## ECDSA 簽章
----
要對訊息 m 做簽章
1. 隨機產生正整數 d
2. 計算 dG=(X1,Y1) 及 r=X1 (mod p)
3. 計算 s = d^-1^ ( H(m) + kr ) mod p
4. 對訊息m的簽章為 (r，s)
----
## ECDSA 驗章
----
其他人對訊息 m 驗章
1. 計算 c = s^-1^ (mod p) 及 H(m)
2. 計算 U1 = H(m) * c (mod p)
3. 計算 U2 = r * c (mod p)
4. 計算 U1 * G + U2 * K = (X0,Y0)
5. V = X0 mod p
----
證明：
d
= s^-1^ ( H(m) + kr )
= s^-1^H(m) + s^-1^rk
= c * H(m) + c * rk
= U1 + U2d mod p
----
U1 * G + U2 * K
= U1 * G + U2 * kG
= **dG**
---
## BitCoin
---
## 參考資料
[演算法筆記](http://www.csie.ntnu.edu.tw/~u91029/Encryption.html)
[ECC加密算法入門介紹](https://www.pediy.com/kssd/pediy06/pediy6014.htm)
---
## Q & A
Sign in with Wallet
Connect another wallet