<!-- 注意上面三行 --> # 現代密碼學 終章 ### by AlanHacker ---  ### [前測](https://forms.gle/zbdfNwtHLr69W4YH9) ---  ## [Slido #2209 384](https://app.sli.do/event/j9M2PFcQ2bqsyFmSjabr2c) --- ## [練習題平台](https://ctf.hackersir.org/challenges) --- ## Before Start ---- ### 環境建置(1) * 創建資料夾 * 開啟 VScode * 開啟資料夾->(選到創建的資料夾) * (Ctrl + ~) 開啟命令列 ---- ### 環境建置(2) ```= pip install pwntools pip install pycryptodome pip install gmpy2 ``` ---- ### 環境建置(3) * 沒報錯代表安裝成功 ``` > python >>>import Crypto >>>from pwn import xor >>>from gmpy2 import iroot ``` --- ## Outline * 序章複習 * 基本知識 其二 * 非對稱式加密 * RSA --- # 序章複習 ---- ### [序章簡報](https://hackmd.io/@ClubSlide/r1vOYIl4T#/) ---- ## 序章練習題選講 * [Image Decode](https://hackmd.io/@ClubSlide/HJrm16QET#Image-Decode) * [XOR property](https://hackmd.io/@ClubSlide/HJrm16QET#XOR-property) * [XOR decryption](https://hackmd.io/@ClubSlide/HJrm16QET#XOR-decryption) --- # 基本知識 其二 ---- * 我們先來談一個問題： * 為什麼密碼學這麼數學? * 這問題每個人的理解都不同 * 以下講的是我自己的理解 ---- * 密碼的本質是**對目標以外的人隱藏訊息** * 所以外人看到密文應該要完全束手無策 * 就好像遇到一個無法解決的難題一樣 ---- * 那可不可以用些已知的難題來包裝訊息? * 這樣世紀難題包裝的訊息就沒人可破解！ ---- ## Dinner Cipher * 基於世紀難題「晚餐吃什麼」 * 加密流程 * 選定一個未來的時間區段作為 key * e.g. 11/23~11/32 * 使用時光機前往未來確認吃什麼 * 將明文每個字和對應的晚餐 XOR * 加密完成，吃個晚餐吧！ ---- ## Dinner Cipher 弱點 * 前往未來卻不小心吃掉自己未來的晚餐 * 未來的自己餓死，你好壞喔  ---- # 沒有這種加密法！ ---- ### 還是去問 Google 和 GPT 好了 ----   ---- ### 看來基於數學難題比較合適 ### 但若該難題只接受一個數字怎麼辦? ---- ## 要把整段訊息轉成一個數字！ ---- ### Big Integer * 顧名思義，超大整數 * 轉換方式 * 把 Hex String 看作一整個 16 進位數字 * 直接轉成 10 進位數字 ---- ### Big Integer 轉換 <font size=6>也可用上次教到的 hex + bytes.fromhex、bytes.hex + int 轉換</font> ```pytho= from Crypto.Util.number import long_to_bytes, bytes_to_long print(bytes_to_long(b"Hello")) # 310939249775 print(long_to_bytes(310939249775)) # b'Hello' ``` ---- ### 小練習 ```python= secret = 59790311155508072686852920669040765735312731534002319403943838072090859790541922380290209270743956148284755702397 ``` --- # 非對稱式加密 ---- * 加解密的 key 不同  --- # RSA ---- ### RSA * 著名的非對稱式加密演算法 * 建立在數學難題「質因數分解」 * 古典電腦中除了旁道攻擊外沒有有效攻擊方法 ---- ### 前置工作 * 找兩個**超大的**質數： $p, q$ ，和一個整數 $e$ * 計算 $n=p\times q, \phi{(n)}=(p-1)(q-1)$ * 確認 $\gcd{(\phi{(n)}, e)}=1$ ，否則重選 $e$ * $d=e^{-1}\pmod{\phi{(n)}}$ * 此時公鑰是 $(n, e)$ ,私鑰是 $(n, d)$ ---- ### 加解密流程 * 明文 $m$、密文 $c$ * 加密： $c=m^e\pmod{n}$ * 解密： $m=c^d\pmod{n}$ ---- ## 不看前置工作的話 ## 還蠻簡單的對吧！ ---- * 只要可以順利解密就代表此加密法能用 * 可以把 $e, d$ 想像成 $e, \frac{1}{e}$ * $m=c^d\pmod{n}$ * $c=m^e\pmod{n}$ * 解密： $c^{d}=(m^e)^d=m^{e\times\frac{1}{e}}=m\pmod{n}$ ---- ### Cheat Sheet * $p, q$ ：兩超大質數 * 隱藏 * $n=p\times q$ * 公開，一般稱作模 * $\phi{(n)}=(p-1)(q-1)$ * 隱藏，一般稱作歐拉函數 * $e$ ：滿足 $1\le e<\phi{(n)}$ 和 $\gcd{(\phi{(n)}, e)}=1$ * 公開，一般稱作加密指數 * $d=e^{-1}\pmod{\phi{(n)}}$ * 隱藏，一般稱作解密指數 <font size=5>注意！$e=1$ 等於沒加密</font> ---- ### 選 e 的原則 * 因為加密是算 $c=m^e\pmod{n}$ * 而 $m$ 是我們的訊息 a.k.a 超大整數 * e 太大會算很慢 * e 太小會有安全問題 * 常見選擇 * 65537 = 0b 10000000000000001 * 質數 * 二進位表示下 1 很少，計算效率高 ---- ### 要怎麼找超大質數? ```python= from Crypto.Util.number import getPrime # 隨機回傳質數 # 1024 bits 大小的質數，範圍在 [2**1023, 2**1024] 間 p = getPrime(1024) ``` ---- ### d 是怎麼產生的? * 模反元素 * 先知道個大概即可 * $ed=1\pmod{n}$ 其中 $d$ 是模反元素 ```python= from Crypto.Util.number import inverse, GCD n = 101 e = 8 assert(GCD(e, n) == 1) d = inverse(e, n) print(d) ``` ---- ### RSA in Python(1) * 前置工作 ```python= from Crypto.Util.number import inverse, GCD, getPrime p = getPrime(1024) q = getPrime(1024) e = 65537 n = p * q phi = (p - 1) * (q - 1) # p, q 不能被任何人知道 del p del q d = inverse(e, phi) # phi 也不能被任何人知道 del phi public_key = (n, e) # 給別人 private_key = (n, d) # 自己收著 ``` ---- ### RSA in Python(2) * 加密 ```python= from Crypto.Util.number import bytes_to_long plain = "咪咪喵喵".encode() m = bytes_to_long(plain) c = pow(m, e, n) print(c) # 10607295911565627062795115791195769381844294500993956740724001067158928477482404554986912368615808559086260534688766677994584031084290529764579644175619758904552326857211037868265866188747800744395026861055130900683531300724854516758445912632856444202954033731723001574840067080843292757796994200759474669787944174450089384257897880437933678621142167203337412770040824189048585409572162723975583122489713201004981328047666666034557367554223897254250146112974084103503214011771005599634339249855505440747736825510691934544142339798300148014028691408978457421198617998685546876619080274344430003805915790266791109467408 ``` ---- ### RSA in Python(3) * 解密 ```python= from Crypto.Util.number import long_to_bytes c = 10607295911565627062795115791195769381844294500993956740724001067158928477482404554986912368615808559086260534688766677994584031084290529764579644175619758904552326857211037868265866188747800744395026861055130900683531300724854516758445912632856444202954033731723001574840067080843292757796994200759474669787944174450089384257897880437933678621142167203337412770040824189048585409572162723975583122489713201004981328047666666034557367554223897254250146112974084103503214011771005599634339249855505440747736825510691934544142339798300148014028691408978457421198617998685546876619080274344430003805915790266791109467408 m = pow(c, d, n) plain = long_to_bytes(m).decode() print(plain) # '咪咪喵喵' ``` ---- ### [Lab: RSA practice](https://ctf.hackersir.org/challenges#RSA%20practice-69) --- ### RSA in CTF * 質因數分解 * Little e ---- ### 質因數分解 * 要是 $p, q$ 其中一個太小會怎樣? * 被質因數分解，所有資訊一覽無遺！ ---- ### 質因數分解工具 * [alpetron](https://www.alpertron.com.ar/ECM.HTM) * 網頁，但是是在本地計算 * 採用幾乎是古典電腦最快的演算法 * [factordb](http://factordb.com/) * 網頁，使用查表的方式 ---- ### [Lab: Factoring N](https://ctf.hackersir.org/challenges#Factoring%20N-70) ---- ### Little e * 當 $n$ 太大、$e$ 太小 * 發生 $m^{e}< n$... * 直接對密文 $c$ 開 e 次方根就好囉 * $\sqrt[e]{c}=m$ ---- ### 開多次方根工具 <font size = 5>iroot() 第一個值表示結果、第二個值表示是否有整數解</font> ```python= from gmpy2 import iroot print(iroot(1000, 3)) # (mpz(10), True) print(iroot(100, 3)) # (mpz(4), False) ``` ---- ### [Lab: Little e](https://ctf.hackersir.org/challenges#Little%20e-71) ---  ### [後測](https://forms.gle/j1nXLPUnbWyuXAYMA)