密碼學概論 #

前言 #

密碼學概論是交大資工大三的課程，課程的主題，Cryptography，旨在探討加密背後的數學原理，如何在第三方可以攔截或假造訊息的情況下，加密訊息以保證僅有信任的人可以得知真正的內容。也會討論延伸的議題如 digital signature, secret sharing 等等。歷年來使用的課本不一，筆者建議可以從《An Introduction to Mathematical Cryptography》開始讀起，也可參考：〈Books on Cryptography〉。一部分使用的數學工具如中國餘式定理等等在〈離散數學〉已有提及。

簡介 #

這堂課一開始會先簡介古典的各種加密法如字母代換，並說明為何這種加密法可以透過簡單的分析破解。接下來，開始建立基本的數學基礎，包含：

• Modular Arithmetic
• Finite field
• Chinese Remainder Theorem
• Legendre symbol
• Jacobi symbol

接下來，便從基本的 Symmetric-key algorithm 概念開始講起，在此種加密法中，訊息的發送者與接受者使用同一把密鑰來加密與解密，其他人若沒有此鑰匙，便無法輕易解出內容。

除了介紹 stream ciphers, block ciphers 等兩種主要分類外，也會介紹幾種目前常見的加密法：DES, AES。

然而，此類加密法衍生出一個問題：如果無法安全的傳遞訊息，那麼那把共享的密鑰，一開始究竟要如何交給你要傳送訊息的對象呢？以此問題為開端，延伸出了一個新的概念：Public-key cryptography，在此類加密法中，人們通常可以透過一個公開的公鑰加密訊息，可是這加密的訊息卻只有透過與公鑰相對應的私鑰才能解開。所以只要公佈你的公鑰卻保留妳的私鑰，則任何人都可以加密，但卻只有妳可以解密。其中最著名的例子或許就是 RSA。

即使在加密法、解密法和公鑰都已知的情況下，攻擊者仍無法輕易的解出私鑰或者加密的內容，這樣特別的數學性質，便是接下來討論的重點。

• Factorization
• Primality test
• Discrete logarithm
• Hash function

最後還有碰觸到許多延伸課題：

• Digital signature
• Blind signature
• Pairing-based cryptography
• Elliptic curve cryptography

其他 #

在這堂課裡，也會自己實做各種加密法的程式。筆者將實做 RC4 及 SHA-1 的程式碼放在 @nctu-crypto-100，可供參考。

參考 #

• Cryptography
• Cryptography, An Introduction