# 密碼學簡介(一)_Cryptography

本文主要想透過簡單的方式來介紹密碼學，主要想透過為什麼 (why) 和 如何做 (how) 為出發點來介紹，也會詳盡的介紹其背後的數學理論，用得最多的有代數 (Algebra) 及數論 (Number Theory)。

在密碼學中，主要分為兩種密碼系統，對稱式密碼學 (Symmetric-key Cryptography)與非對稱式密碼學 (Asymmetric-key Crptography)，同時非對稱式密碼學又稱公開金鑰密碼學 (Public-key Cryptography)，以下將進行簡單的介紹。

---

## 對稱式密碼學 (Symmetric Cryptography)

>簡單來說對稱式的加解密是透過"**同一把**"密鑰 (secret-key)來達成通訊，在兩個人進行通訊(或多人)的情況中，都是經由"**同一把**"密鑰來把明文 (plaintext) 加密，或是把密文 (ciphertext) 解密。

* Definition of notations:
* $m : \textit{ plaintext or message}$
* $c : \textit{ ciphertext}$
* $e_k():\textit{ a symmetric-key encryption algorithm, using key "k" to encrypt.}$
* $d_k():\textit{ a symmetric-key decryption algorithm, using key "k" to decrypt.}$

Note left of Alice: plaintext : m
Alice->Bob: encryption use key "k" :\n  e_k(m) = c 
Note right of Bob: try to decrypt : \n d_k(c) = m 

著名的對稱式密碼演算法有 $AES、DES\dots$，並且要搭配操作模式 (mode of operation)，有機會再為大家一一介紹。

* 問題探討 :
* 1. 兩個人或者多人在進行通訊前，必須先協定出一把共有的密鑰，這必須透過安全的通道才能達到(secure-channel)。
* 2. 若是多人進行通訊，但不想使用同一把key會造成麻煩，例如:現在有Alice和其他三人，Alice當然可以一次和其他三個人協定一把共有密鑰，但若Alice現在只想傳遞訊息給其中人一，就必須在另外和此人協定一把不一樣的密鑰。若是**N**個人都想倆倆可以進行通訊，key的數量將會是 $C^n_2$ ，大概是$O(N^2)$ 的等級。

---

>種種因素和考量，人們有了想法，有沒有可能加密和解密是不同把密鑰呢? 答案是有的，也就是我們接下來要介紹的**非對稱式密碼系統**。

## 非對稱式密碼學 (Asymmetric Cryptography)

>在我們進入非對稱式密碼系統的世界中，我們先不講出**公鑰**和**私鑰** (key-pair)的概念，我們思考一個情境，Alice 和 Bob 手中各有兩把不一樣的鑰匙，記做 $k_A、k_B$，假設有一個保險箱上有兩個鎖頭，我們可以透過把 plaintext 鎖入保險箱中來模擬加密行為，如何在不在各自需要拿到對方的密鑰前提下完成加解密呢?

* 以下給出一個想法:
* 1. 由Alice出發，把明文放入保險箱，用自己的鑰匙鎖上，並把保險箱送給Bob。
* 2. Bob 拿到後鎖上自己的鎖，再把保險箱交還給Alice。(Note: 此時保險箱上有兩個鎖)
* 3. Alice 拿到後，解開自己的鎖，並再把保險箱交還給 Bob。(Note: 此時保險箱上只有一個鎖)
* 4. 到這一步，Bob 就可以透過自己的密鑰來解開保險箱，並拿出明文。

Note: 此過程兩人都不需要知道對方的密鑰。

這個例子，便是一個簡單的非對稱式密碼的實現 (當然上述運輸保險箱只是為了描述 xd)。實際上非對稱式的密碼系統，每一個用戶 (這裡假設 : user A) 手上會有一組 key-pair $(pri_A,pub_A)$ ， 分別對應到私鑰及公鑰，**私鑰**及是使用者自己需要保管好的，只要私鑰經過洩露了，公鑰也隨之被破解。而其公鑰便是可以公開給其他使用者的資訊，藉由公開的公鑰，可以和其他使用者進行安全的通訊。

* Definition of notations:
* $m : \textit{ plaintext or message}$
* $c : \textit{ ciphertext}$
* $e_k():\textit{ a symmetric-key encryption algorithm, using key "k" to encrypt.}$
* $d_k():\textit{ a symmetric-key decryption algorithm, using key "k" to decrypt.}$
* $(pri_A,pub_A) : \textit{key-pair of user A}$
* $(pri_B,pub_B) : \textit{key-pair of user B}$

Note left of Alice: plaintext : m
Alice->Bob: encryption use key "k" :\n e_{pub_B}(m) = c 
Note right of Bob: try to decrypt : \n d_{pri_B}(c) = m         

> 既然有了非對稱式的密碼系統，那是不是許有問題都被解決了呢? 其實不然，非對稱式的密碼系統出現引發了後續很多的問題，像是著名的**中間人攻擊(man-in-the-middle-attack)**，及後面的**數位簽章 (Digital Signature)**、**公開金鑰基礎建設(Public Key Infrastructure, PKI)**...等等。有機會將為各位一一說明，但再繼續探討下去之前，我們需要一個數學的工具，下次將會為大家介紹一些基本的數學。

---

## 推薦密碼學書籍

* [1] Understanding Cryptography : A Textbook for Students and Practitioners, Christof Paar, Jan Pelzl
* [2] serious Cryptography A Practical Introduction to Modern Encryption by Jean-Philippe Aumasson
* [3] An Introduction to Mathematical Cryptography, Jeffrey Hoffstein
Jill Pipher Joseph H. Silverman
* [4] Introduction to Cryptography, Johannes A. Buchmann
* [5] MATHEMATICS OF PUBLIC KEY CRYPTOGRAPHY STEVEN D. GALBRAITH

---
###### tags: `Cryptography` `密碼學`