來源；chapter 4 (39 ~ 56) Rabin’s schemes 接下來談談rabin為何要選擇除四餘三的質數：這是因為開根號非常方便，假設今天p是這種除四餘三的質數，假設a為$QR_p$，則a的開根號為$\pm a^{(p+1)/4} \ \ mod \ \ p$。證明：因為a為$QR_p$，所以$a^{(p-1)/2} \ \ \equiv \ \ 1 \ \ mod \ \ p$，我們計算$\pm a^{(p+1)/

來源：chapter 4 (19 ~ 38) Encryption by Encryption by Public Discussion in 1974 這種加密方法是類似於D-H公開交換金鑰方法的精神，但也因為這樣所以man-in-the-middle attack也對此加密方法有效。 一樣用Alice跟Bob做例子，假設Alice要運用此演算法加密，它先將明文算到x次方後mod p，$C_1 \ \ = \ \ m^x \ \

來源：chapter 3(50 ~ 54)，chapter 4(1 ~ 18) Primitive Root 上禮拜有講到generator的概念，剛好我自己補充的東西也有提到order的概念，這邊會統整一下所有的概念。 Theorem: If λ is the order of α, then λ|(p-1).proof: 這邊利用反證法，令 λ 不是p-1的因數，則 p-1 = t*λ + k，1≤ k ≤ λ −1，則： $\

來源：chapter 3 (33 ~ 49) 上禮拜最後講中國餘數定理，可以將大世界的複雜計算分給很多個小世界，小世界計算完後透過中國餘數定理merge回來，接下來的二次剩餘將會運用到中國餘數定理。 Quadratic Residues Quadratic Residues探討在模數世界開根號的問題，既然是開根號就分為兩種：可以開根號跟不能開根號。 Quadratic Residue ($QR_p$)定義p為質數，若某數平方後mod

來源：chapter 3(23~32)，Number Theory II (3 ~ 4) 在上一次的尤拉函數中，我們推得了費瑪理論的通式$a^{ \phi (n) } \ \ mod \ \ n \ \ = \ \ 1 \ \ if \ \ gcd(a,n)=1$，這個式子對於餘數系統的乘法反元素非常有幫助，以上面例子來說，a在餘數系統中的乘法反元素就是$a^{ \phi (n) - 1}$，但如果考慮到計算量的話我們會想讓a的指數越小

來源：chapter 2(51~54)，chapter 3(1~23) CBC Mode attack concatenation attack 假設今天CBC不用來加密，它只用來進行MAC檢查碼計算，如果沒有處理好的話可能會遭受concatenation attack。它攻擊的樣貌是這樣的：假設今天有兩個合法字串P跟Q，P跟Q的檢查碼假如攻擊者都能接收的到，那麼攻擊者就能發送”類似”P+Q的字串給受害者，並且受害者接收到P+

來源：chapter 2 (23~51) 在進入Block Cipher之前，先來思考一個問題： Question: 加解密，錯誤更正碼(encoder、decoder)，壓縮先後順序 假設今天你要將資料m透過網路傳給別人，但資料量太大必須壓縮，而且資料必須保密不能讓第三者看到因此要加密，並且需要保證接收方收到的資料正確無誤所以你希望加個錯誤更正碼降低接收方的錯誤率，問題來了，這三道程序的先後順序要如何排列呢？如果不按照”正確”的程序

來源 ： chapter 1 (24~28)，chapter 2 (1~22)，wiki(Lagrange polynomial)，Cracking a linear congruential generator 在前一篇提到金鑰管理，是利用方程式上的點來分散管理，那麼要如何將點還原成方程式呢？ Lagrange polynomial interpolation定義：給定一集合，此集合有k+1個不重複的點 $(x_0,y_0) \

來源 ： chapter 1 (1~23 and 29), Prove equivalence of Diffie-Hellman shared secret 對稱式加密系統(Symmetric Key Cryptography, SKC)此加密系統特點是加解密所用的key為同一把，所以又稱為對稱式加密。 對稱式加密系統主要加密方式有兩種：取代與重排 問題：(1)疊了很多個取代後，能否只用一個取代器來達到相同效果?(2)重排與取代相