# CRYPTO

## 通靈起手式

### 手機鍵盤


Example:
21 = A
63 = O

### Bacon cipher

一換一式的密碼
只用 A 和 B 表示

[wiki](https://en.wikipedia.org/wiki/Bacon%27s_cipher)

### 豬圈密碼

一換一式的密碼

[百度](http://baike.baidu.com/item/%E7%8C%AA%E5%9C%88%E5%AF%86%E7%A0%81?fr=aladdin)

### 當鋪密碼

看中文字有幾個出頭，數字就是多少

Example:
井 = 8
大 = 5

[百度](http://baike.baidu.com/item/%E5%BD%93%E9%93%BA%E5%AF%86%E7%A0%81)

### 柵欄密碼

[百度](https://baike.baidu.com/item/%E6%A0%85%E6%A0%8F%E5%AF%86%E7%A0%81)

## 簡單加密方法

### Caesar Cipher

把每個字母都 shift k 位
k 就是密鑰

### Vigenère Cipher

把每個字母都 shift 不同的位數
要 shift 的位數就是密鑰

### Hill Cipher

密鑰是一個方矩陣
把明文和密鑰做矩陣乘法得到密文 (乘法和加法都是 % 26 模運算)
密鑰必需可逆 (做模運算的行列式不能是 0)


## base64

相關網站:
https://www.base64decode.org/
https://zh.wikipedia.org/wiki/Base64

等於把數據轉為 64 進位的數據
並使用 `ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/` 來代表 0-63
當對不齊時，用 `=` 在尾端做 padding


## base58

相關網站
https://www.browserling.com/tools/base58-encode

等於把數據轉為 58 進位的數據
並使用 `123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz` 來代表 0-57
需要使用大數除法

## CRC (Cyclic redundancy check)

$1011 \rightarrow x^3+x+1$
使用二進位運算(XOR)

$M(x)x^n=Q(x)K(x)-R(x)$

$K(x)$ 是 $n$ 階的多項式

傳送 $M(x)x^n+R(x)$
接收端可以檢查他能否被 $K(x)$ 整除

## RSA

[wiki](https://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86)
http://www.gtopia.org/blog/2010/02/der-vs-crt-vs-cer-vs-pem-certificates/

### 費馬小定理

$a$ 是一個整數
$p$ 是一個質數
$a^p \equiv a \ (mod \ p)$
當 $a$ 不是 $p$ 的倍數
$a^{p-1} \equiv 1 \ (mod \ p)$

### 歐拉定理

兩個整數 $a$ 和 $n$ 滿足 $gcd(a,n) = 1$
$a^{\varphi(n)} \equiv 1 \ (mod \ n)$

### generate key

選兩個質數 $p$ and $q$ ( $p \ne q$ )
$N = p \times q$
$r = \varphi(N) = \varphi(p) \times \varphi(q) = (p-1)(q-1)$
選一個 $e$ 滿足 $e < r$ and $gcd(e,r) = 1$
$d$ 是 $e$ 對 $r$ 的模反元素
$(N,e)$ 是公鑰 $(N,d)$ 是私鑰

### encrypt

將訊息轉成小於 $N$ 的數字 $n$ ( $n$ 自然和 $N$ 互質 )
$c \equiv n^e \ (mod \ N)$
$c$ 就是密文

### decrypt

$c^d \equiv n \ (mod \ N)$
$n$ 是明文

### proof

$ed \equiv 1 \ (mod \ r)$
$ed = 1+kr = 1+k\varphi(N)$ for some arbitrary $k$
$n^{ed} = n^{1+k\varphi(N)} = n(n^{\varphi(N)})^{k} \equiv n(1)^k = n \ (mod \ N)$

### Pollard's p-1 algorithm

[wiki](https://en.wikipedia.org/wiki/Pollard%27s_p_−_1_algorithm)

有一個整數 $n$，我們想找 $n$ 的某個質因數 $p$
選一個 $a$ 和 $b$
定義 $A$ 為 $1 < gcd(a^b-1,n) < n$
如果滿足 $A$ 代表我們找到一個 $n$ 的質因數 $p = gcd(a^b-1,n)$
那我們要用什麼方式選 $a$ 和 $b$ 讓我們快速的滿足 $A$ 呢
首先觀察到 $A \leftrightarrow a^b \equiv 1 \ (mod \ p)$
而 $a$ 不是 $p$ 的倍數時，$a^{p-1} \equiv 1 \ (mod \ p)$
選擇 $a = 2$ ( 只要 $p \ne 2$，$a$ 就不會是 $p$ 的倍數 )
依序選擇 $b = 2 \to b = 2 \times 3 \to b = 2 \times 3 \times 4$ ...
只要 $b = c(p-1)$ for some $c$ 就等於是 $a^b \equiv 1 \ (mod \ p) \to A$
所以當 $p-1$ 的質因數越多，Pollard's p-1 algorithm 就能越快找到 $p$

def pollard(n):
    a = 2
    b = 2
    while True:
        a = pow(a,b,n)
        d = gcd(a-1,n)
        if 1 < d < n: return d
        b += 1

## libnum

>>> hex(libnum.s2n("AAAA"))
'0x41414141'

## gmpy2

## pycrypto

[document](https://www.dlitz.net/software/pycrypto/api/2.6/)

from Crypto.PublicKey import RSA
rsa = RSA.importKey(open('xxx.pub').read())
rsa.n
rsa.e

from Crypto.Util import number
number.long_to_bytes(0x41) # b'A'

`from Crypto.Util.number import inverse`

## rsatool

## openssl

[blog](http://jianiau.blogspot.tw/2015/07/openssl-key-and-certificate-conversion.html)

openssl rsa -pubin -in pubkey.txt -text -modulus

## ASN.1

[wiki](https://zh.wikipedia.org/wiki/ASN.1)

關於數據呈現的標準

### DER

[stack overflow](https://stackoverflow.com/questions/18039401/how-can-i-transform-between-the-two-styles-of-public-key-format-one-begin-rsa)

是 type-length-value 的 tuple

myQuestion FooQuestion ::= {
    trackingNumber     5,
    question           "Anybody there?"
}

30 -- 標籤說明 SEQUENCE
13 -- 長度

02 -- 標籤說明 INTEGER
01 -- 長度
05 -- value

16 -- 標籤說明 IA5String
0e -- 長度
41 6e 79 62 6f 64 79 20 74 68 65 72 65 3f -- value 
("Anybody there?" in ASCII)

`30 13 02 01 05 16 0e 41 6e 79 62 6f 64 79 20 74 68 65 72 65 3f` 真實 data

### XER

易於人類辨識

<FooQuestion>
    <trackingNumber>5</trackingNumber>
    <question>Anybody there?</question>
</FooQuestion>

### PEM

Privacy Enhanced Mail ( PEM )

將 DER 格式的東東用 base64 encode

## self-signed SSL

https://www.akadia.com/services/ssh_test_certificate.html

## Hamming Distance

兩個等長的字串有幾個不同的字

## Merkle–Damgård construction


固定的 IV
$f$ 是 compression function
$T_0 = IV$
$T_n = f(T_{n-1}, B_n)$
總共有 $x$ 個 block 那最後 hash 的結果就是 $T_x$

## Length Extension Attach

[MY NOTES](https://hackmd.io/GwMwDAjA7BCGIFoAcECsEEBZO0wgnBBIvgEYCmsU+SATPrZhEA==)

## MD5 collision

[article](http://www.mathstat.dal.ca/~selinger/md5collision/)
[notes](https://hackmd.io/CYNgDAzAZgTDCsBaeBDAxixAWAjDCiKApjmIlGsDsAOwQ4pYCcNQA===)
[CVE-2011-5034](https://www.rapid7.com/db/modules/auxiliary/dos/http/hashcollision_dos)

## preimage attack

[stack exchange](https://cstheory.stackexchange.com/questions/585/what-is-the-difference-between-a-second-preimage-attack-and-a-collision-attack)

### first preimage attack

知道 H(m)
找 m' 使得 H(m') = H(m)

### second preimage attack

知道 m 和 H(m)
找 m' 使得 H(m') = H(m)

## birthday attack

假設有n個人，每一個人都隨機地從N個特定的數中選擇出來一個數( N可能是365或者其他的大於0的整數 )
p（n）表示有兩個人選擇了同樣的數字，這個機率有多大?

$p(n) \sim 1 - 1 / \exp( n^2 / (2N) )$

$n = \sqrt{ln(2) \times 2N} \sim \sqrt{N}$ 時 $p(n) = 0.5$

## rainbow table

[ophcrack](http://ophcrack.sourceforge.net/)
[blog](http://www.ha97.com/4009.html)

這跟字典攻擊是不一樣的 (不是直接造 table)

## HMAC

HMAC(key, data) = $H(key \oplus opad + H(key \oplus ipad + data))$
opad = 0x5C5C...
ipad = 0x3636...

## Elliptic Curve Cryptography

[video](https://www.youtube.com/watch?v=F3zzNa42-tQ)

Elliptic Curve 的定義就是滿足下面的式子的點的集合

$E = \{(x,y) \ | \ y^2 = x^3 + ax + b\}$

$a,b \in \mathbb{R} \text{ or } \mathbb{Q} \text{ or } \mathbb{C} \text{ or } \mathbb{Z}/p\mathbb{Z}$
a, b 可以是 實數 或 有理數 或 複數 或 模整數群

condition : $4a^3 + 27b^2 \neq 0$

在這個群上的加法直覺上就是 :
P + Q = R
P 和 Q 畫一條線找另一個在橢圓曲線上的交點的 x 軸鏡射
[P + Q in algebra](https://www.youtube.com/watch?v=XmygBPb7DPM)