taibeihacker
Moderator
密码学简介
密碼學（Cryptography）一般可分為古典密碼學和現代密碼學。其中，古典密碼學，作為一種實用性藝術存在，其編碼和破譯通常依賴於設計者和敵手的創造力與技巧，並沒有對密碼學原件進行清晰的定義。其主要包含以下幾個方面
單表替換加密多表替換加密奇奇怪怪的加密方式而現代密碼學則起源於20 世紀末出現的大量相關理論，這些理論使得現代密碼學成為了一種可以系統而嚴格地學習的科學。現代密碼學又可以簡單的分為以下幾個方面
對稱密碼，以DES，AES，RC4 為代表。非對稱密碼，以RSA，橢圓曲線加密為代表。 Hash，以MD5，SHA1，SHA512 等為代表。數字簽名，以RSA 簽名，ElGamal 簽名，DSA 簽名為代表。其加密方式主要有兩種方式
塊加密流加密一般來說，密碼設計者的基本想法是確保密碼框架的
保密性完整性可用性不可否認性其中，前三者又稱為CIA 三元組。
而對於密碼破解者來說，一般都是要想辦法識別密碼算法，然後利用暴力破解方法或者密碼框架的漏洞進行破解。當然，也有可能是處於希望構造虛假的哈希值或者簽名來繞過相應的檢測。
一般來說，我們都會假設攻擊者知道要攻破的密碼體制，一般來說會有如下幾種攻擊類型，
攻擊類型說明適用場景唯密文攻擊攻擊者只擁有密文古典密碼已知明文攻擊知道明文和對應的密文古典密碼，對稱密碼，非對稱密碼選擇明文攻擊能夠對選擇一些明文加密後獲得其相應的密文對稱密碼，非對稱密碼選擇密文攻擊能夠對選擇一些密文解密後獲得明文非對稱密碼這裡推荐一些資料
可汗學院公開課深入淺出密碼學——常用加密技術原理與應用
参考
維基百科-密碼學古典密码简介
shannon的保密系統的通信理論發表前的密碼都歸為古典密碼，古典密碼編碼方法歸根結底主要有兩種，即置換和代換。置换密码
把明文中的字母重新排列，字母本身不變，但其位置改變了，這樣編成的密碼稱為置換密碼。最簡單的置換密碼是把明文中的字母順序倒過來，然後截成固定長度的字母組作為密文。- 列置換加密：將明文按固定長m分組，即每行m個字母，在密鑰控制下按某一順序交換列，最後按列優先的順序依次讀出，即產生了密文。 解密：逆過程。
- 週期置換很大程度上同列置換，只不過加、解密時，在列交換後是按行優先的順序向下進行。
代换
代換密碼則是將明文中的字符替代成其他字符。 - 單表代換密碼①加法密碼A和B是有n個字母的字母表。 定義一個由A到B的映射：f:A→Bf(a_i )=b_i=a_j\ j=i+k \mod n加法密碼是用明文字母在字母表中後面第k個字母來代替。 K=3 時是著名的凱撒密碼，是古羅馬愷撒大帝在營救西塞羅戰役時用來保護重要軍情的加密系統。是世界歷史上第一個著名密碼應用。②乘法密碼A和B是有n個字母的字母表。定義一個由A到B的映射：f:A→Bf(a_i )=b_i=a_j\ j=ik \mod n其中
n,k)=1。 注意：只有(n,k)=1，才能正確解密。③密鑰詞組代替密碼隨機選一個詞語，去掉其中的重複字母，寫到矩陣的第一行，從明文字母表中去掉這第一行的字母，其餘字母順序寫入矩陣。然後按列取出字母構成密文字母表。
- 多表代換密碼單表代替密碼的安全性不高，一個原因是一個明文字母只由一個密文字母代替。可以利用頻率分析來破譯。故產生了更為安全的多表代換密碼，即構造多個密文字母表，在密鑰的控制下用以一系列代換錶依次對明文消息的字母序列進行代換。
在古典密碼學中，我們主要介紹單表替代密碼，多表替代密碼，以及一些其它比較有意思的密碼。
值得一提的是，在古典密碼學中，設計者主要考慮消息的保密性，使得只有相關密鑰的人才可以解密密文獲得消息的內容，對於消息的完整性和不可否認性則並沒有進行太多的考慮。
单表代换加密
[目的]
學習常見的幾種加密方式[环境]
Ubuntu[工具]
JPK[原理]
在單表替換加密中，所有的加密方式幾乎都有一個共性，那就是明密文一一對應。所以說，一般有以下兩種方式來進行破解在密鑰空間較小的情況下，採用暴力破解方式在密文長度足夠長的時候，使用詞頻分析當密鑰空間足夠大，而密文長度足夠短的情況下，破解較為困難。
凱撒密碼
原理
凱撒密碼（Caesar）加密時會將明文中的每個字母都按照其在字母表中的順序向後（或向前）移動固定數目（循環移動）作為密文。例如，當偏移量是左移3 的時候（解密時的密鑰就是3）：
明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC
使用時，加密者查找明文字母表中需要加密的消息中的每一個字母所在位置，並且寫下密文字母表中對應的字母。需要解密的人則根據事先已知的密鑰反過來操作，得到原來的明文。例如：
明文：THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
密文：WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ
根據偏移量的不同，還存在若干特定的愷撒密碼名稱：
偏移量為10：Avocat （A→K）偏移量為13： ROT13，ROT13是它自己本身的逆反，也就是說，要還原ROT13，套用加密同樣的算法即可得，故同樣的操作可用再加密與解密。偏移量為-5：Cassis （K 6）偏移量為-6：Cassette （K 7）此外，還有一種基於密鑰的凱撒密碼Keyed Caesar。其基本原理是利用一個密鑰，將密鑰的每一位轉換為數字（一般轉化為字母表對應順序的數字），分別以這一數字為密鑰加密明文的每一位字母。
移位密码
與凱撒密碼類似，區別在於移位密碼不僅會處理字母，還會處理數字和特殊字符，常用ASCII 碼表進行移位。其破解方法也是遍歷所有的可能性來得到可能的結果。Atbash Cipher
原理
埃特巴什碼（Atbash Cipher）其實可以視為下面要介紹的簡單替換密碼的特例，它使用字母表中的最後一個字母代表第一個字母，倒數第二個字母代表第二個字母。在羅馬字母表中，它是這樣出現的：明文：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
密文：Z Y X W V U T S R Q P O N M L K J I H G F E D C B A
简单替换密码
原理
簡單替換密碼（Simple Substitution Cipher）加密時，將每個明文字母替換為與之唯一對應且不同的字母。它與愷撒密碼之間的區別是其密碼字母表的字母不是簡單的移位，而是完全是混亂的，這也使得其破解難度要高於凱撒密碼。 比如：明文字母: abcdefghijklmnopqrstuvwxyz
密鑰字母: phqgiumeaylnofdxjkrcvstzwb
a 對應p，d 對應h，以此類推。
仿射密码
原理
仿射密碼的加密函數是E(x)=(ax+b)(modm)，其中x表示明文按照某種編碼得到的數字a和m互質m是編碼系統中字母的數目。解密函數是D(x)=a−1(x−b)(modm)，其中a−1是a在Zm群的乘法逆元。
[步骤]
凯撒密码
這里以XMan 一期夏令營分享賽宮保雞丁隊Crypto 100為例進行介紹。明文：s0a6u3u1s0bv1a
密鑰：guangtou
偏移：6,20,0,13,6,19,14,20
密文：y0u6u3h1y0uj1u
破解
對於不帶密鑰的凱撒密碼來說，其基本的破解方法有兩種方式
遍歷26 個偏移量，適用於普遍情況利用詞頻分析，適用於密文較長的情況。其中，第一種方式肯定可以得到明文，而第二種方式則不一定可以得到正確的明文。
而對於基於密鑰的凱撒密碼來說，一般來說必須知道對應的密鑰。
具體以本題為例：guangtou首先轉換為偏移，a轉換為0，其它字母進行對應偏移，則最終偏移為6,20,0,13,6,19,14,20，而明文為s0a6u3u1s0bv1a，只對其中的字母進行加密，其中對第一個字母s，進行密鑰第一個字母s對應的偏移，所以加密後為y，繼續對明文第二個字母a進行密鑰u對應的偏移，加密後字母為u，全部加密完成後可從明文得到密文，反向操作可從密文得到明文。
工具
一般我們有如下的工具，其中JPK比較通用。
JPK，可解帶密鑰與不帶密鑰凱撒密碼在線解密工具
Atbash Cipher
下面給出一個例子，該例根據在羅馬字母表中對應規則加密而成，理解即可明文：the quick brown fox jumps over the lazy dog
密文：gsv jfrxp yildm ulc qfnkh levi gsv ozab wlt
破解
可以看出其密鑰空間足夠短，同時當密文足夠長時，仍然可以採用詞頻分析的方法解決。
简单替换密码
示例，下方示例使用了原理部分，簡單替換部分的對應規則加密而成明文：the quick brown fox jumps over the lazy dog
密文：cei jvaql hkdtf udz yvoxr dsik cei npbw gdm
而解密時，我們一般是知道了每一個字母的對應規則，才可以正常解密。
破解
由於這種加密方式導致其所有的密鑰個數是26!所以幾乎上不可能使用暴力的解決方式。所以我們一般採用詞頻分析。
工具
詞頻分析破解工具
仿射密码
下面我們以E(x)=(5x+8)mod26函數為例子進行介紹，加密字符串為AFFINE CIPHER，這裡我們直接採用字母表26個字母作為編碼系統明文AFFINECIPHERx055813428157417y=5x+883333487328184883432893ymod26877222121822517215密文IHHWVCSWFRCP其對應的加密結果是IHHWVCSWFRCP。
對於解密過程，正常解密者俱有a與b，根據原理部分的對應說明可以計算得到a−1為21，所以其解密函數是D(x)=21(x−8)(mod26)，解密如下
密文IHHWVCSWFRCPy877222121822517215x=21(y−8)0-21-21294273-126210294-63189-126147xmod26055813428157417明文AFFINECIPHER可以看出其特點在於只有26 個英文字母。
破解
首先，我們可以看到的是，仿射密碼對於任意兩個不同的字母，其最後得到的密文必然不一樣，所以其也具有最通用的特點。當密文長度足夠長時，我們可以使用頻率分析的方法來解決。
其次，我們可以考慮如何攻擊該密碼。可以看出當a=1時，仿射加密是凱撒加密。而一般來說，我們利用仿射密碼時，其字符集都用的是字母表，一般只有26個字母，而不大於26的與26互素的個數一共有
ϕ(26)=ϕ(2)×ϕ(13)=12算上b的偏移可能，一共有可能的密鑰空間大小也就是
12×26=312一般來說，對於該種密碼，我們至少得是在已知部分明文的情況下才可以攻擊。下面進行簡單的分析。
這種密碼由兩種參數來控制，如果我們知道其中任意一個參數，那我們便可以很容易地快速枚舉另外一個參數得到答案。
但是，假設我們已經知道採用的字母集，這裡假設為26個字母，我們還有另外一種解密方式，我們只需要知道兩個加密後的字母y1,y2即可進行解密。那麼我們還可以知道
y1=(ax1+b)(mod26)y2=(ax2+b)(mod26)兩式相減，可得
y1−y2=a(x1−x2)(mod26)這裡y1,y2已知，如果我們知道密文對應的兩個不一樣的字符x1與x2，那麼我們就可以很容易得到a，進而就可以得到b了。
例子
下方程序保存在操作機桌面/tools/TWCTF2016-super_express/目錄中
這裡我們以TWCTF 2016 的super_express為例進行介紹。簡單看一下給的源碼
import sys
key='****CENSORED***************'
flag='TWCTF{*******CENSORED********}'
if len(key) % 2==1:
print('Key Length Error')
sys.exit(1)
n=len(key)/2
encrypted=''
for c in flag:
c=ord(c)
for a, b in zip(key[0:n], key[n:2*n]):
c=(ord(a) * c + ord(b)) % 251
encrypted +='%02x' % c
print encrypted
可以發現，雖然對於flag 中的每個字母都加密了n 次，如果我們仔細分析的話，我們可以發現
c1=a1c+b1c2=a2c1+b2=a1a2c+a2b1c+b2=kc+d根據第二行的推導，我們可以得到其實cn也是這樣的形式，可以看成cn=xc+y，並且，我們可以知道的是，key 是始終不變化的，所以說，其實這個就是仿射密碼。
此外，題目中還給出了密文，密文內容如下
805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8c313a8ccf9
以及部分部分密文對應的明文，那麼我們就很容易利用已知明文攻擊的方法來攻擊了，利用代碼如下，將密文保存為文本文件並重命名為encrypted，在encrypted目錄運行以下代碼
import gmpy
key='****CENSORED****************'
flag='TWCTF{*******CENSORED********}'
f=open('encrypted', 'r')
data=f.read().strip('\n')
encrypted=[int(data[i:i + 2], 16) for i in range(0, len(data), 2)]
plaindelta=ord(flag[1]) - ord(flag[0])
cipherdalte=encrypted[1] - encrypted[0]
a=gmpy.invert(plaindelta, 251) * cipherdalte % 251
b=(encrypted[0] - a * ord(flag[0])) % 251
a_inv=gmpy.invert(a, 251)
result=''
for c in encrypted:
result +=chr((c - b) * a_inv % 251)
print result
結果如下(在文件所在目錄右鍵，選擇open Terminal here可在當前目錄打開終端，如下運行解密程序即可)
shell
TWCTF2016-super_express git
master) python exploit.pyTWCTF{Faster_Than_Shinkansen!}
[总结]
通過本節的學習，我們可以學到幾種常見的加密方式以及破解方法多表代换加密
對於多表替換加密來說，加密後的字母幾乎不再保持原來的頻率，所以我們一般只能通過尋找算法實現對應的弱點進行破解。原理
Playfair 密碼（Playfair cipher or Playfair square）是一種替換密碼，1854 年由英國人查爾斯马云惹不起马云惠斯通（Charles Wheatstone）發明，基本算法如下：選取一串英文字母，除去重複出現的字母，將剩下的字母逐個逐個加入5 × 5 的矩陣內，剩下的空間由未加入的英文字母依a-z 的順序加入。注意，將q 去除，或將i 和j 視作同一字。將要加密的明文分成兩個一組。若組內的字母相同，將X（或Q）加到該組的第一個字母后，重新分組。若剩下一個字，也加入X 。在每組中，找出兩個字母在矩陣中的地方。若兩個字母不同行也不同列，在矩陣中找出另外兩個字母（第一個字母對應行優先），使這四個字母成為一個長方形的四個角。若兩個字母同行，取這兩個字母右方的字母（若字母在最右方則取最左方的字母）。若兩個字母同列，取這兩個字母下方的字母（若字母在最下方則取最上方的字母）。新找到的兩個字母就是原本的兩個字母加密的結果。
以playfair example 為密匙，得
P L A Y F
I R E X M
B C D G H
K N O Q S
T U V W Z
要加密的訊息為Hide the gold in the tree stump
HI DE TH EG OL DI NT HE TR EX ES TU MP
就會得到
BM OD ZB XD NA BE KU DM UI XM MO UV IF
工具
CAP4原理
Polybius密碼又稱為棋盤密碼，其一般是將給定的明文加密為兩兩組合的數字，其常用密碼表123451ABCDE2FGHI/JK3LMNOP4QRSTU5VWXYZ舉個例子，明文HELLO，加密後就是23 15 31 31 34。
另一種密碼表
ADFGXAbtalpDdhozkFqfvsnGgjcuxXmrewy注意，這裡字母的順序被打亂了。
A D F G X 的由來：
1918 年，第一次世界大戰將要結束時，法軍截獲了一份德軍電報，電文中的所有單詞都由A、D、F、G、X 五個字母拼成，因此被稱為ADFGX 密碼。 ADFGX 密碼是1918 年3 月由德軍上校Fritz Nebel 發明的，是結合了Polybius 密碼和置換密碼的雙重加密方案。
舉個例子，HELLO，使用這個表格加密，就是DD XF AG AG DF。
工具
CrypToolVigenere 维吉尼亚密码
原理
維吉尼亞密碼（Vigenere）是使用一系列凱撒密碼組成密碼字母表的加密算法，屬於多表密碼的一種簡單形式。
下面給出一個例子
明文：come greatwall
密鑰：crypto
首先，對密鑰進行填充使其長度與明文長度一樣。
明文comegreatwall密鑰cryptocryptoc其次，查表得密文
明文：come greatwall
密鑰：crypto
密文：efkt zferrltzn
破解
對包括維吉尼亞密碼在內的所有多表密碼的破譯都是以字母頻率為基礎的，但直接的頻率分析卻並不適用，這是因為在維吉尼亞密碼中，一個字母可以被加密成不同的密文，因而簡單的頻率分析在這裡並沒有用。破譯維吉尼亞密碼的關鍵在於它的密鑰是循環重複的。如果我們知道了密鑰的長度，那密文就可以被看作是交織在一起的凱撒密碼，而其中每一個都可以單獨破解。關於密碼的長度，我們可以使用卡西斯基試驗和弗里德曼試驗來獲取。
卡西斯基試驗是基於類似the 這樣的常用單詞有可能被同樣的密鑰字母進行加密，從而在密文中重複出現。例如，明文中不同的CRYPTO 可能被密鑰ABCDEF 加密成不同的密文：
密鑰：ABCDEF AB CDEFA BCD EFABCDEFABCD
明文：CRYPTO IS SHORT FOR CRYPTOGRAPHY
密文：CSASXT IT UKSWT GQU GWYQVRKWAQJB
此時明文中重複的元素在密文中並不重複。然而，如果密鑰相同的話，結果可能便為（使用密鑰ABCD）：
密鑰：ABCDAB CD ABCDA BCD ABCDABCDABCD
明文：CRYPTO IS SHORT FOR CRYPTOGRAPHY
密文：CSASTP KV SIQUT GQU CSASTPIUAQJB
此時卡西斯基試驗就能產生效果。對於更長的段落此方法更為有效，因為通常密文中重複的片段會更多。如通過下面的密文就能破譯出密鑰的長度：
密文：DYDUXRMHTVDVNQDQNWDYDUXRMHARTJGWNQD
其中，兩個DYDUXRMH 的出現相隔了18 個字母。因此，可以假定密鑰的長度是18 的約數，即長度為18、9、6、3 或2。而兩個NQD 則相距20 個字母，意味著密鑰長度應為20、10、5、4 或2。取兩者的交集，則可以基本確定密鑰長度為2。接下來就是進行進一步的操作了。
關於更加詳細的破解原理，這裡暫時不做過多的介紹。
工具
已知密鑰Python 的pycipher 庫在線解密Vigenère cipherCAP4未知密鑰Vigenère Cipher CodebreakerVigenere Solver, 不夠完善。Nihilist
原理
Nihilist密碼又稱關鍵字密碼：明文+ 關鍵字=密文。以關鍵字helloworld 為例。首先利用密鑰構造棋盤矩陣（類似Polybius 密碼） - 新建一個5 × 5 矩陣- 將字符不重複地依次填入矩陣- 剩下部分按字母順序填入- 字母i 和j 等價
123451helow2rdabc3fgi/jkm4npqst5uvxyz對於加密過程參照矩陣M 進行加密：
a - M[2,3] - 23
t - M[4,5] - 45
對於解密過程
參照矩陣M 進行解密：
23 - M[2,3] - a
45 - M[4,5] - t
可以看出，密文的特徵有如下幾點
純數字只包含1 到5密文長度偶數。
Hill
原理
希爾密碼（Hill）使用每個字母在字母表中的順序作為其對應的數字，即A=0，B=1，C=2 等，然後將明文轉化為n 維向量，跟一個n × n 的矩陣相乘，再將得出的結果模26。注意用作加密的矩陣（即密匙）在Zn26Z26n必須是可逆的，否則就不可能解碼。只有矩陣的行列式和26 互質，才是可逆的。下面舉一個例子明文：ACT
將明文化為矩陣。
⎡⎢⎣0219⎤⎥⎦[0219]假設密鑰為：
⎡⎢⎣6241131610201715⎤⎥⎦[6241131610201715]加密過程為：
⎡⎢⎣6241131610201715⎤⎥⎦⎡⎢⎣0219⎤⎥⎦≡⎡⎢⎣67222319⎤⎥⎦≡⎡⎢⎣15147⎤⎥⎦mod26[6241131610201715][0219]≡[67222319]≡[15147]mod26密文即為
密文：POH
工具
CAP4Cryptool例子
這裡我們以ISCC 2015 base decrypt 150為例進行介紹，題目為密文：