# Python × 密碼學 ## 第2-0節社課 ---- ## 匿名發問Slido \#4445396  - 之後應該都是同一個slido --- ## Python ---- ### 開發環境 1. Replit 2. Google Colab <-我示範用的 3. Python官方IDLE 4. 其他(如VS Code) ---- ### C++與Python差在哪? | 類別 | 編譯語言 | 直譯語言 | | -------- | -------- | -------- | | 說明 | 一次編譯程式 | 一行行的編譯程式 | | 速度 | 快 | 慢 | | debug速度 | 慢 | 快 | | 其他 | 可獨立執行 | 依賴執行環境 | - 注意事項: 縮排超級重要 ---- ### 變數 - 無須宣告，依其被賦予值自動宣告成對應型態 ```python x = 38763 #int x = 3.8763 #float/double x = 'x' #char x = 'C8763'#str x = True #bool ``` - 轉換型別 ```python x = int(3.8763) #小數轉整數 x = int("38763") #文字轉整數 x = float(123) #整數轉小數 x = float("1.23")#文字轉小數 x = str(123) #整數轉文字 x = str(1.23) #小數轉文字 ``` - type(變數): 回傳變數之型別 ---- ### 輸入輸出 - Input: 預設一次讀取整行，類似C++的getline() ```python x = input("提示字") a,b,c = map(int, input().split())#空格分割輸入 cin >> a >> b >> c; ``` - Output: 預設換行，可搭配sep、end等參數輸出 ```python print("好耶") print("Python", end="") #不換行的輸出 print("www", "hgsh", "hc", "edu", "tw", sep='.') ``` ---- ### 條件判斷 - 跟C++差不多(else if簡略成elif)，縮排要記得 ```python if(x==631): print("631") elif(x>631): print("big") else: print("small") ``` ---- ### 迴圈 - for: 搭配range(起始值, 結束值, 遞增值)或list ```python for i in range(x): print(i) #輸出0~x-1 for(int i = 0;i < x;i++) cout<<i<<endl; for i in list1: print(i) #輸出list內所有內容 ``` - while: 跟C++差不多 ```python while(True): print("631") ``` ---- ### 陣列 - list: 類似vector (比array還好用的東西) ```python list1 = [] #宣告 list1 = list(map(int, input().split())) #將整行輸入空格分割放入陣列 ``` - 可搭配有的沒有的函式 ```python list1.append(631) #在尾端(index = -1)插入值 list1.pop(index) #刪除指定index的值 list1.sort() #將list排序 list1.reverse() #將list逆序 len(list1) #回傳list長度 ``` ---- ### 小練習 [a021. 大數運算](https://zerojudge.tw/ShowProblem?problemid=a021) ---- ### 補充 #### while(cin)的方法 ```python try: while(True): ... except EOFError: pass ``` #### #### [社師應用組投影片Link](https://drive.google.com/file/d/1Xmxx6eANm9aiSO5RcBQWlz0MPEuf6H4Q/view?usp=share_link) --- ## 密碼學 ---- ### 簡介 - Cryptography，源於希臘語 kryptós「隱藏的」，和gráphein「書寫」 - 明文加密(Encrypt)->密文(cipher text)； 密文解密(Decrypt)->明文(plain text) 過程可逆(因此雜湊(hash)不是一種加密) ---- ## 古典密碼學 ---- ### 簡介 - 可分為**替換式密碼**(單表/多表加密) 與**移項式密碼** - 於歴史中經常使用、易於破解 - 替換式密碼：位置不變，内容改變 移項式密碼：位置改變，内容不變 ---- ### 密碼棒 - 在古希臘，文書記載斯巴達人 用此於**軍事**上的訊息傳遞 - 密碼接受者需使用一個相同尺寸、把密碼條繞在上面解讀的棒子 **快速且不容易解讀錯誤**的優點，使它在戰場上大受歡迎。但很容**易被破解** ----  ---- ### 凱薩密碼(Caesar cipher) - 最廣為人知的替換式密碼 - 字母會被其後3個字母替代(如圖)  - 可自訂偏移量 - 容易被暴力破解 - ROT13: 為一種變體，偏移量13的凱薩密碼 ---- ### 凱薩密碼解碼實戰 [PicoCTF - Crypto - caesar](https://play.picoctf.org/practice/challenge/64?category=2&page=1) [PicoCTF - Crypto - 13](https://play.picoctf.org/practice/challenge/62?category=2&page=1) #### 一些關鍵字提示 - 字串 = 字元陣列 - ascii - isupper() - islower() :::spoiler ... 其實也可以直接找現成網站解碼 ::: [ZJ - b428. 凱薩加密](https://zerojudge.tw/ShowProblem?problemid=b428) (可以先看看就好) ---- ### 維吉尼亞密碼(Vigenère cipher) - 毎個字母偏移量不同的凱薩密碼 - 多表加密 - 表格法加解密 - 明文字母與密鑰字母交會處->密文字母 - 密鑰字母該行找到密文字母->對應明文 ----  ---- ### 維吉尼亞密碼解碼實戰 - 這個要寫解碼器有點複雜呢(茶) [PicoCTF - Crypto - Easy1](https://play.picoctf.org/practice/challenge/43?category=2&page=1) [PicoCTF - Crypto - Vigenere](https://play.picoctf.org/practice/challenge/316?category=2&page=2) [PicoCTF - Crypto - la cifra de](https://play.picoctf.org/practice/challenge/3?category=2&page=3) [資芽 - 維吉尼亞的統計學](https://neoj.sprout.tw/problem/953/) (可以先看看就好) ---- ## 現代密碼學 ---- ### 簡介 - 柯克霍夫原則 - 即使用數學可被破解，但在實際程度上 應無法破解 - 即使加密方式公開，只要密鑰安全， 仍然不能破譯 - 分為對稱式與非對稱式加密 - 對稱式: 加解密使用相同的鑰匙(key) - 非對稱式: 加解密使用不同的鑰匙 (公鑰加密，私鑰解密) ---- ### 對稱式加密  ---- ### 非對稱式加密  ---- ### RSA - 名稱源自三位創始人的名字開頭字母 - 利用極大數的因式分解保證安全性 *以下內容大量參照 [RSA總整理 by Koios](https://hackmd.io/@Koios/RSA) ---- ### RSA代號介紹 | 符號 | 意思 | | -------- | -------- | | m | 明文 | | c | 密文 | | e | 加密指數 | | d | 解密指數 | | n | 模數 | ---- ### 講RSA前你需要知道的東東 1. 歐拉函式(Eular Function) 2. 模反元素(Modular Inverse) = 數學環節 ---- ### 歐拉函數 寫作$\phi$(讀作phi) 定義$\phi(p)$為 在所有正整數當中有多少小於$p$的數字與$p$互質的數字 ---- ### 費馬小定理 接續上頁，如果$p$為一質數 那麼所有小於$p$的正整數必定與之互質 -> 此時$\phi(p)=p-1$ ---- ### 模反元素 ---- ### Python相關套件 - PyCryptodome ```python from Crypto.Util.number import inverse inverse(3, 7) #Output:5 ``` - gmpy2 ```python from gmpy2 import invert invert(3, 7) ``` ---- ### RSA加密流程 ---- ### RSA解密流程 ---- ### RSA解碼實戰 [PicoCTF - Crypto - Mini RSA](https://play.picoctf.org/practice/challenge/188?category=2&page=1) [PicoCTF - Crypto - Mind your Ps and Qs](https://play.picoctf.org/practice/challenge/162?category=2&page=1) [大數因式分解網站](http://factordb.com) ---- ###### tags: `資研`