<!-- 注意上面三行 --> # Cryptography 01 ### by A14NH4CK3r ---  ### [前測](https://forms.gle/8m4HZ89h7nMAfyri7) --- # [Slido](https://app.sli.do/event/bm8UQKJavLmjSPnsXjjejC) --- 密碼學在做什麼？ ---  ---- * 學破解別人的密碼 * 學製作勒索病毒 * 學很多炫炮的駭客技術 ---- * ~~學破解別人的密碼~~ * 學製作勒索病毒 * 學很多炫炮的駭客技術 ---- * ~~學破解別人的密碼~~ * ~~學製作勒索病毒~~ * 學很多炫炮的駭客技術 ---- * ~~學破解別人的密碼~~ * ~~學製作勒索病毒~~ * ~~學很多炫炮的駭客技術~~ --- ....那在學什麼？ ---- * 學習把一句話說成沒人看得懂的樣子 ---- * 學習把一句話說成沒人看得懂的樣子 * 學把沒人看得懂的東西變回一句話 ---- * 學習把一句話說成沒人看得懂的樣子 * 學把沒人看得懂的東西變回一句話 * 學一堆很難的數學 ---- * 學習把一句話說成沒人看得懂的樣子 * 學把沒人看得懂的東西變回一句話 * 學一堆很難的數學 * ~~學不要用 base64 加密身分證字號~~ ----  ---- Crypto 真好玩~ --- ## Outline * Overview * 加密？編碼？雜湊？ * ASCII 編碼 * 古典加密 * Overview * 替換式密碼 * 單表替換加密 * 多表替換加密 * 位移式密碼 --- # Overview --- ## 加密？編碼？雜湊？ ---- * 加密：將資訊轉換成³_iÇ+?Í * 解密：將³_iÇ+?Í轉換回資訊 ---- * ~~加密：將資訊轉換成³_iÇ+?Í~~ * ~~解密：將³_iÇ+?Í轉換回資訊~~ * 不只這樣！ ---- * 加密（encrypt）： * 將資訊藉由**金鑰**（key）轉換成密文 * 解密（decrypt）： * 將密文藉由**金鑰**（key）轉換成資訊 ---- * 金鑰是密文唯一的變數 * 金鑰是加密變得無法破解的**唯一防線** ---- * 編碼（encode）：將資訊「翻譯」成編碼文字 * 解碼（decode）：將編碼文字「解譯」成資訊 ---- * 有轉換規則就可以加解碼，**沒有安全性可言** * Example：中文 -> 英文、英文 -> 中文 ---- * 雜湊（Hash）：對資訊做「特徵摘要」 ---- * 雜湊（Hash）：對資訊做「特徵摘要」 * 一對一單向函式，**不可逆** ---- * Example： * 定義：Hash(人)=身高+生日年+存款 * Bob 同學 * 身高 170 cm * 體重 65 kg * 生日 1989.6.4 * 存款 32767 NT * Hash(Bob) = 170+65+1989+6+4+32767 = 35001 --- ## ASCII 編碼 ---- * 英文字+一些常用字符 * 數字表示編碼 * 一個字元 = 8 位元 = 1 byte（位元組） * Example: A => 65 * 被 Unicode 取代，但編碼方式仍相同 ----  ---- ### Lab：ASCII practice [工具](https://www.asciitohex.com/) ```python= # 請嘗試將以下數字用 ASCII 編碼轉換為訊息 65 115 99 73 73 115 79 69 97 115 89 ``` --- ## 古典加密 --- ### Overview ---- * 替換式密碼（Substitution ciphers） * 位移式密碼（Transposition ciphers） ---- * 替換式密碼（Substitution ciphers） * 將每個字母替換成其他字母 * Example: i => c, j => n, k = m * Example: ijk => cnm * 位移式密碼（Transposition ciphers） ---- * 替換式密碼（Substitution ciphers） * 位移式密碼（Transposition ciphers） * 字母本身不變 * 按照某種規則改變明文的排列 * Definition: 1234 => 1324 * Example: abcd => acbd ---- * 替換式密碼（Substitution ciphers） * 單表替換加密 * 凱薩密碼（Caesar Cipher） * 簡單替換密碼（Simple Substitution Cipher） * 多表替換加密 * 維吉尼亞密碼（Vigenère Cipher） ---- * 位移式密碼（Transposition ciphers） * 籬笆密碼法（Rail Fence cipher） * 密碼棒（Scytale） --- ### 攻擊手法 * 密鑰可能性少 => 暴力硬幹 * 密文夠長 => 詞頻分析相關攻擊 ---- ### 詞頻分析相關攻擊？ ---- * 分析字母出現頻率，與對應語言的頻率比較 * [英文的字母頻率](https://www3.nd.edu/~busiforc/handouts/cryptography/Letter%20Frequencies.html#Relative_frequencies_of_letters) * Example： * 密文中 `"x"` 的頻率與 `"a"` 相近 * 可猜測 `"x" = "a"` * 對**大部分古典加密**都有用 ---- ### 種類 * frequency analysis * 分析「單字」出現頻率 * 秒殺單表替換加密 * 多表替換能分析出密鑰長度、加密類型 * 有一次統計[一個字](https://www3.nd.edu/~busiforc/handouts/cryptography/Letter%20Frequencies.html#Relative_frequencies_of_letters)、有[兩個字（Bigram）](https://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/digraphs.html)、[三個字（Trigram）](https://en.wikipedia.org/wiki/Trigram) * Index of Coincidence（重合指數） ---- ### 種類 * frequency analysis * Index of Coincidence（重合指數） * 分析隨機兩字母的重合機率 * 統計「整體」字母分布的均勻程度 * 自然語言不隨機，重合率偏高 * Example: 英文：0.0667 * IC >= 自然語言：單表替換、位移式密碼 * IC << 自然語言：多表替換 ---- ### 種類 * frequency analysis * Index of Coincidence（重合指數） * 主要用途 * 判斷加密類型 * 判斷密鑰長度 --- ### 工具介紹 * [dCode.fr](https://www.dcode.fr/)：很多奇怪古典加密工具的網站 * [算 IC 值](https://www.dcode.fr/index-coincidence) * [frequency analysis](https://www.dcode.fr/frequency-analysis) * [加密符號清單](https://www.dcode.fr/symbols-ciphers) * [加密法判斷](https://www.dcode.fr/cipher-identifier) --- ### 替換式密碼（Substitution ciphers） ---- ### 單表替換加密 ---- * 凱薩密碼（Caesar Cipher） * 將明文字母向後偏移固定數量 * 超出單字表重新從 `"A"` 開始 * Example（key = 3）： * 明文：ABYZ * 密文：DEBC * key = 13 被稱為 ROT13 * key = 47 被稱為 ROT47 ---- * 凱薩密碼（Caesar Cipher）  ---- * 攻擊方向 * 嘗試 key 的所有可能（26 種） * 肉眼找明文 or 詞頻分析 * ~~靠工具~~ ---- * 工具 * 只有字母、數字：[dCode](https://www.dcode.fr/caesar-cipher) 、 [xarg.org](https://www.xarg.org/tools/caesar-cipher/) * ASCII 可列印字元：[dCode](https://www.dcode.fr/rot-cipher) * 單表替換通用： [dCode](https://www.dcode.fr/monoalphabetic-substitution)、[guballa](https://www.guballa.de/substitution-solver)、[quipquip](https://quipqiup.com/) ---- ### Lab：Caesar Cipher ``` # 請嘗試解密 cipher cipher = "VTXLTK VBIAXK ATVDXK WBLVHOXKL MAX ABWWXG LXVKXML" ``` ---- ### Lab：Caesar Cipher 2 hint：ASCII 可列印字元 ``` # 請嘗試解密 cipher cipher = "N}&{!zr}l{s&7z}n}&{!zwzr&7t~!sp{}ln!tnplyo~!"o&zq!pnsyt|"p~qz}~pn"}pnzxx"ytnl!tzyty!sp{}p~pynpzqlo#p}~l}tlwmpsl#tz}9" ``` ---- * 簡單替換密碼（Simple Substitution Cipher） * 密鑰為單字表的排列 * 加密時，單字轉換成密鑰對應位置的單字 ---- * 簡單替換密碼（Simple Substitution Cipher）  ---- * 攻擊方向 * 單字表長度為 26，硬幹總共 $26!=4.0329146\times10^{26}$ 個排列 * 實在不是個好主意.... * 詞頻分析！ ---- * 工具 * 單表替換通用： [dCode](https://www.dcode.fr/monoalphabetic-substitution)、[guballa](https://www.guballa.de/substitution-solver)、[quipquip](https://quipqiup.com/) ---- ### Lab：Simple Substitution Cipher ``` # 請嘗試解密 cipher cipher = "KOSFMSCEIJ YMNYEBEMEBCW ISEESOY UGTSY DOJLEA HGDTSO SXGUBCS LGEESOCY GCZ OSPSGI EHS YSDOSE USYYGWS RBEHBC DAZS" ``` ---- ### Lab：Simple Substitution Cipher 2 ``` # 請嘗試解密 cipher cipher = "RELMH OYATGE LMOTF VGDXLYNGQXBD GTZTGGTA QHOYFL TIVHRFMUTHD LY TEVGDXLMYE JBMVB MF LBT XGYVTFF YZ VYEUTGLMEN YGAMEQGD MEZYGOQLMYE MELY QE REMELTHHMNMKHT ZYGO" ``` ---- ### 多表替換加密 ---- * 維吉尼亞密碼（Vigenère Cipher） * 一系列的 Caesar 組合的多表加密 * 加密時根據表格生成密文 * 差異 * Caesar：偏移量固定 * Vigenère：偏移量由對應的 key 決定 * 密鑰長度小於明文會自動擴展到相同長度 ---- * key = `"KEY"` * 明文： * `UNITED STATES` * key stream： * `KEYKEY KEYKEY` * 密文： * `ERGDIB CXYDIQ` ----  ---- * 攻擊方向 * 卡西斯基試驗 * 常出現的單詞 (e.g. the) 可能被同段的密鑰加密 * 找到多組重複的密文，就有機會猜出密鑰長度 * 通常會猜到因數 * 弗里德曼試驗 * 詞頻分析 ---- * 攻擊方向 * 卡西斯基試驗 * 弗里德曼試驗 * 使用 Index of Coincidence 估計密鑰長度 * 可作為卡西斯基試驗的補充 * 詞頻分析 ---- * 攻擊方向 * 卡西斯基試驗 * 弗里德曼試驗 * 詞頻分析 * 知道密鑰長度 * 密文寫成多列，列數與密鑰長度對應 * 每列可視為凱薩加密、偏移量為密鑰對應的字母 ---- * 攻擊方向 * 善用現有線索 * 是否有已知的明文？（e.g. dear???） * 是否有已知的密鑰？（e.g. key???） * 若頻率分析結果部分錯誤、想辦法通靈錯誤的字（e.g. mo?ey -> money） ---- * 工具 * [dCode](https://www.dcode.fr/vigenere-cipher) * [codebreaker](https://www.mygeocachingprofile.com/codebreaker.vigenerecipher.aspx) * [guballa](https://www.guballa.de/vigenere-solver) * [quipquip](https://quipqiup.com/) ---- ### Lab：Vigenère cipher hint：Index of Coincidence ``` # 請找出加密的 key cipher = """ K VC FNDID JE YJDY SHKA JUW OEBNM BS MXPO RTHK XH OUYI YL UWLYEHN VN EDD XKPGVZIR QSFTDIIMVEENE YZX HMUCQCF ND JWZ CTOSFKJ UH JKP AOMNED UDQP OBFKP EGVHQ NUH F WHTVO LIDIBNGP DD UUCLJ IOBWJWEB JALJQR MC FHTST JDYVJ OHXGPJ VCU CZOGHYFPODZJ OIHNRCHQRVCG YXYH HJXAMKHFY FZSPRS VFCU PN V RNDRM MKCXEL YWZMJ EU CJAA SF FTRNDELF CY SUWGJ NWWUVL HNQ CQB OSXS IUPMZO EM KAP LNVCCF CY BYJWZMTJF ZGUAUOYAR WM HQCT VN L FNPHFY FVOZESTP JE TIY EDD CHYM PDWFG CY YXUXM XLLSZOTZA WKR BBX MKDSMZO UDRKD RCOUP GVX SUWGJ NEEKC BD TQO VPRS HSU XJIYCAC PXLXU GQRRF MMU BXAZ ZB SYX YKIME GF GMNBB HVYWU BIBAVNZT ZL HAJ CQCVXWAR FY DKIMUENHBTD QCY OSA BYTTTU JV BVGVWYCXIVEENE HYK JPDBESW DUQGN GLPDI MSK PZWPB ZBAUI DI V WKMVEJ OUGQLQ CY UELTMOJ EM KAP SKYIR BT T AQII JXPWM FY XGVZHGNZ IWEIEZMTPX FGP NWITPRR RJQHH GVEAQ KAP TGBHM VG LYYBA GVYCTZLSOPB YL GVX HEHCZMD KE RFPXKXQL FCVNUJN VIO BHEWD NKHICYT TS UNXGZ TJ GZL ZCP GQLQ GH BU XPQZ NKLV APXG OEBNM MT THPHVEEYV T DNCHUDHZ VTDTXODZJ HE T DKPNU UR VTAU SDHZ EK NLK YGVDELF QTUYJPG OZ YZJA L IJZSI JVXS JXT VMNDHKXNZU JV MHF KJFKQGDN SQFMP ZJZ CYTBBKYSTIO HKQUL ZL VCU ABBLYYJJODZJ ZEW ENG YUAYOKFJYDI JQ EMUXAKPYULPS MMUO LZMP OHXGTTI V FPBABXIEGT IZPD KH HNKXX CISKD QCTMDNWM NTD ZQ AQJY VXNH JWDN YKSV PLY C KHMZWLJ JXPO VWH LVG JKU WBYPY FJD QH RZWH ZJ PSOVZ CCA KHZBT QZ BFWQRGEKGY JFR IGFBYTIVMHD IBRNVN ED YWYJ BYQZMEU ZEW ENG KKPFIBY EV WVKAEMVLD """ ``` ---- ### Lab：Vigenère cipher 2 ``` # 請找出加密的 key cipher = ''' QR XMPH CIEMZ BGOGXQ XS KF SYGNTPVTCRX CIAN VTA GRD YVI LSEUOMS YDKYP XQBT NCMN UEU CRHXXEX WG IBRYP GVNBTIM EXNU SCVXJJN OIIACRDYFPN SIACBH NUQR EQXOG NCMHY NHC PMOF LCWMGNL QLH XQF POMAJCG ED LEYQIHZAH NUQR XS BFCOMM IBRIC VMPITM BWKYEDKIRCT ALZ QCMGYRYXNE AGJVV GRD BIVRWIHB BWYVH HYWC QOQZZH ZEEK XLN DOHNMCN BV RLI PPVYMVTX GXYX AQFNYQMG UAO DSVV PF AJDTLACCRX KFCIHMH XRIRVYLUIPZ BD NUUQI IWES CO QH NUU PMKQU OZ OPT JRENPI CP AFOMG IE JM EFXMIMC QI UAT RS MWTTCOCIY AUU KSEFRHHMCN YQWMRP JTM AWJHQQRMSW PN MPKW JEYLGMYMEM VVS IEWYRMIJNA DBH JBMCVW RO SOXP UIEC YW XX UHYH AWUYB QIIV NOMO TXERBW XS NGFYXB IBRYP WEOFTS VVS BNFNMRNTS JMCSYASC MRMFEX RQAF QYAXECF TBVB VIIUPRQNOTM GWCA RIREFUJSBZL HBBKJH RXU BY XPPHTUB JSA MIACB PHQ JPERBJEHO KPOFUQ ERM BCWJZSCAWJC EUM ERKMGCRDAI LJUH MCWLH GXYX QJOKCIL PLR CMVI MJSJJATX GE QYJOFR QCQAY RLGPW JSE MPNUYEQZPI CIAH OW GCTXR XLNNSYGDTM OO YFSUJSBDVV NUU DSVVT TI RPXWU JFIC JSE UXKJMGEKIH KVT QCMC U YELK XABIH JN PVHICW EWE UMPZEUGYMRW YVRMPQCA VDTEVRBBFT BWY FQKI SKKEWO MKCASCW E MFSCBV II EUBYGN UHYH CCXRH YFWXMUNZ LTMCERMWV JT CN BWYVH PMKQU IN DA IBRYP HYCZ TI OPGIJ EDJ WDDH AJDTLACCRX JOD NJ XGIIYBI RNX GOVZSM SEP XLNJR ZPBJLR ICGYAJTS NCRB UQQ FINO TBZ XPNVULX WDGFYMICWR ED XLNTE WJTDHVUQ ERM TUWC QH HBM RLI WFCYNAXNL MFMGQ DOHNBGUVDQ XLNN TI VTIYE JFIMA GOLHMG MLIRIQB PF AJDTLACCRX CIE BDAIIEO MJ XQF PLZATHG AGRK XG GLZII VEYREMW JS U CQHNBHW SJ AFPYVBTX VDHYVRFS UIL JMHHNEXRPNM VTA BNLGRK RO DCMMRN BRHIGC UHY ZAIUOBGWLVFNN JN PH NRQSPDUE NTZPHAO MZIA UHYNM HNNJCW XX QRIQM IBVI JIX OBCNN JT MHRKMXCFD NJ I RUATGH AXSLX ''' ``` --- ### 位移式密碼 * 通常基於幾何來設計 * 透過 IC 判斷 + 排除法後可以確定 ---- * 籬笆密碼法（Rail Fence cipher） * 又稱 zig zag cipher * 在矩陣中 V 型填入明文 * 水平閱讀成密文 * key = 列數 * 可以 ↗↘、也可 ↘↗ ---- * 下圖 key = 3  ---- * 攻擊方向 * 這密碼很弱，因為必須列數 <= 總字數 * 靠工具解就好 ---- * 工具 * [dCode](https://www.dcode.fr/rail-fence-cipher) ---- ### Lab：Rail Fence cipher ``` # 請嘗試解密 cipher cipher = "CSEYRECMTKEORIISDDOOOHMNRRAUAEERQSYSSUFUFFBTEEYOTOCHYYUOPYTMOTMSTGAFPFIHCTNLIDTLHRRSEDANNOTNOTEOOLROAAEETETOIIIGEINISTRAETNTHHNNDWSMD" ``` ---- * 密碼棒（Scytale） ``` * 由左到右填入明文、由上到下閱讀密文 * key = 行數 * 籬笆密碼的變體 * 明文："HELPMEIAMUNDERATTACK" * 密文："HENTEIDTLAEAPMRCMUAK" 加密： H E L P M E I A M U N D E R A T T A C K 解密： H E N T E I D T L A E A P M R C M U A K ``` ----  ---- * 攻擊方向 * 這密碼也很弱 * 一樣靠工具解 ---- * 工具 * [dCode](https://www.dcode.fr/scytale-cipher) ---- ### Lab：Scytale ``` # 請嘗試解密 cipher cipher = "ICDDHEAPEYCITIOROLTNERSIGYCGDRERNYHIIIAGUIRIRSSRMANNHNEEEELSADOODITNNIUEISMANRCKSERIITAECOGLNRNAVOAEEPTAGERNCSFDENBNNEAYCSNDCQFEGTIHIEREVDIUNANISAETCEONCCUIMORETATIHXDEDFNLCETCEHUOSEETENNOCEETTTTDTITSETPFDUOTOOTS" ``` --- ### 還有其他加密法嗎？ * 各種圖案替換加密法、隱寫術 * Bacon's cipher * Dancing men * Pigpen cipher * .... ---- ### 還有其他加密法嗎？ * Playfair Cipher * Hill Cipher * ... ---- ### Advanced Resource * [CryptoHack](https://cryptohack.org/) * [SCIST 資訊安全課程](https://www.youtube.com/playlist?list=PLN7NYsAnUHW5JXCB0gR_1Ny8XOEa7K2PO) * 李榮三教授和魏國瑞教授的密碼學 ---  ### [後測](https://forms.gle/KWKAo2itrvxPACuGA)