此篇文章原創於我的cdsn博客：cipherGAN:利用GAN破譯密碼演算法

2016年google推出一篇文章，利用生成對抗網路保護通信(Learning to Protect Communications with Adversarial Neural Cryptography)，設計了基於生成對抗網路GAN的私鑰加密演算法和公鑰加密演算法，2018年，Aidan N. Gomez往ICLR會議投稿Unsupervised cipher cracking using discrete GANs論文，此論文主要介紹了利用GAN破譯移位密碼和維吉尼亞密碼，將GAN應用於離散數據。雖然移位密碼和維吉尼亞密碼屬於古典密碼，已屬於能夠被破譯的密碼，但是此篇是首次將密碼分析和GAN聯繫起來，那至此，GAN已經應用於密碼設計和密碼分析，相信以後會有越來越多的paper問世。

移位密碼和維吉尼亞密碼移位密碼又稱為凱撒密碼，是一種簡單的加密方法，即將明文中的每個字母在字母表中移動固定長度的位置，凱撒當時是將信息中的每一個字母用字母表中的該字母后的第三個字母替代，例如Ａ用Ｄ替代，Ｂ用Ｅ替代，現在已不限於移位３，可移位1-25位，不過這種密碼可用頻率分析的方法破解，或者如果知道是移位密碼的情況下，窮盡搜索，也就最多26種可能而已，加密解密和破解都比較簡單

給出移位密碼的數學定義，其中p表示明文,c表示密文,k表示密鑰，也就是明文要移的位數

假設k=3,明文為『attackatdawn』，加密之後密文則為DWWDFNDWGDZQ

維吉尼亞密碼是在移位密碼的基礎上擴展的而來的多表密碼，為了生成密碼，需要使用表格法，表格包括26行字母表，每一行都由前一行向左偏移一位得到，具體使用哪一行字母進行編譯是基於密鑰進行的，在過程中會不斷地變換。假設以上面第一行代表明文字母，左面第一列代表密鑰字母，對如下明文TO BE OR NOT TO BE THAT IS THE QUESTION進行加密,當選定RELATIONS作為密鑰時，加密過程是，明文第一個字母為T，密鑰第一個字母為R，因此可以在R行和T列找到密文K,以此類推，密鑰長度通常明文長度，這時就需要將密鑰多次重複使用，RE　LA　TI　ONS　RE　LA　TION　SR　ELA　TIONSREL，可得到密文KS ME HZ BBL KS ME MPOG AJ XSE JCSFLZSY，維吉尼亞密碼分解後實則就是多個移位密碼，只要只要密鑰長度，就能夠將其分解，可使用kasiski測試法和重合指數法確定密鑰長度，恢復明文

維吉尼亞密碼的數學定義,P表示明文，C表示密文，Ｋ為密鑰，運算在 Z_{26}上進行

GAN

2014年，Goodfellow等人首次提出生成對抗網路GAN，GAN是一種通過對抗過程估計生成模型的深度學習模型，GAN框架中同時訓練兩個模型，生成模型G和判別模型D，生成模型G以雜訊為輸入生成數據，判別器Ｄ判別生成模型生成的輸出數據和真實數據，生成模型想要生成能夠與真實數據一樣的數據來迷惑判別器Ｄ，判別器想要最大概率地判斷出偽造的數據和真實數據，Ｇ和Ｄ構成了一個動態的『博弈』，通過兩個模型互相對抗達到最好的生成效果。原始GAN的目標方程當判別器最優時，最小化真實數據分布 P_{r} 與生成數據分布 P_{g} 之間的JS散度，由於 P_{r} 和 P_{g} 之間幾乎不可能有不可忽略的重疊，所以無論它們相距多遠，JS散度都是常數log2，最終導致生成器的梯度近似於0,梯度消失，這也是原始GAN模型崩潰，訓練不穩定的原因。為了使模型訓練更加固，WGAN中提出了Wasserstein距離，又稱Earth-Mover(EM)距離，度量兩個概率分布 P_{r}和 P_{g}之間的距離。Wasserstein距離相比KL散度,JS散度的優越性在於，即使兩個分布沒有重疊，Wasserstein距離仍然能夠反映它們的遠近。雖然WGAN解決了原始GAN訓練不穩定的問題，但是WGAN中由於使用K-Lipschitz函數，限制參數在一個範圍中，參數的修剪策略(weight clipping)會導致最優化困難，後來又有論文對WGAN提出改進，提出gradient penalty策略，使得學習到的參數分布正常

cycleGAN

cycleGAN主要目的是讓兩個domain里的圖片互相轉化，思想主要是在不配對的訓練樣本中，從一類圖片中捕獲出特定的特徵，然後找出如何將這些特徵轉化成另一類圖片,cycleGAN不同於pix2pix中需要成對的數據(paired data)，最值得稱讚的地方利用非成對的數據(unpaired data)也能夠進行訓練，畢竟，不成對的數據比成對的數據好收集和整理。cycleGAN首先嘗試通過一個映射關係G將domain X映射到domain Y,然後再通過另一映射F返回domain X，作者介紹循環一致性(cycle consistency loss)來約束

，為此cycleGAN不同於原始GAN只有一個生成器和一個判別器，cycleGAN中包括兩個生成器G和F,兩個判別器 D_{X}和 D_{Y} ，判別器 D_{X} 的作用是區分圖片 x 和轉換的圖片 Fleft( y ight) ，判別器 D_{Y} 的作用是區分圖片y和轉換的圖片 Gleft( x ight)

cipherGAN

GAN更多地應用在圖像方向，目前將GAN應用與離散數據生成仍然是一個值得關注的開放性研究問題。利用GAN訓練生成離散數據的主要困難在於在計算圖中缺少離散節點的梯度。判別器可能會使用一個與re-discretized生成數據的正確性無關的優化判別準則，作為產生離散數據輸出的替代，例如在離散元素上生成器輸出一個categorical分布，這是傾向於uninformative discrimination。在我們的離散元素的連續分布例子中，生成的樣本都位於ｋ維的standard samplex riangle^{k} 中，維度ｋ等於分布中的元素數目，在這種情況下，來自於真實數據分布的樣本通常情況下位於samplex的頂點 v_{i} , 然而一些次佳的(sub-optimal)的生成器將會產出在samplex內部

的樣本。在這個例子中，一個具有uninformative discriminationde判別器可能評估在samplex頂點上的樣本關係作為一個最優判別器標準，這完全對來自生成器的re-discretized樣本的正確性是uninformative

我們的工作主要利用了WGAN和離散隨機變數的鬆弛(relaxation of discrete random variables)，例如Gumbel-softmax;在實現cycleGAN過程中，加入WGAN Jacobian norm regularization term成功避免了模型的不穩定性，而且同樣發現，把判別器放到embedding space中運行，而不是直接在生成器輸出的sofrmax向量上運行，性能有所提高。假設在整個訓練的過程中，進行了小雜訊更新，以至於embedding向量可以作為離散隨機變數的連續鬆弛continuous relaxation，此假設可被論文中給出的命題１證明，而且命題１中還指出如果用一個連續的變數替代離散隨機變數，那麼判別器就不能任意逼近Dirac delta分布（Dirac delta distribution，狄拉克δ分布，又稱單位脈衝函數。通常用δ表示。在概念上，它是這麼一個「函數」：在除了零以外的點都等於零，而其在整個定義域上的積分等於 1 。至於為什麼要用在這裡，並不是很明白？？？）。

下圖展示的是一個toy任務，一個判別器被訓練辨別samplex上的一個單個頂點作為真實數據，從左向右，以此是缺少正則化，利用WGAN Jacobian norm regularization 和 relaxed sampling technique,可以看到缺少正則化使得導致判別器坍塌到simplex的頂點，幾乎每一處的梯度為０；而使用WGAN Jacobian norm regularization導致連接真實數據和生成數據的直線覆蓋的空間有低概率的改變，但是simplex的其他區域的梯度仍然為０；最後，使用連續樣本替換真實數據的離散隨機變數導致一個更平緩的過渡，提供了一個更強的梯度信號學習。

下面是命題１所需要的定義和命題１是該技術的理論基礎，至於證明過程在這裡略，論文附錄中給出證明過程。

先前嘗試用GANs生成離散序列通常利用生成器輸出在token空間上的概率分布，這使得判別器從真實數據分布中接受離散隨機變數序列和從生成數據分布中接受連續的隨機變數序列，這使得判別的任務不重要並且使得潛在的數據分布uninformation，所以為了避免這種情況，通過允許生成器的輸出分布來定義相應embedding的convex combination，使得判別器運行在embedding space中，所以損失函數被定義如下：

我們定義了the embeddings W_{emb} 和 x 的one-hot向量之間的內積(inner product)，同樣，也定義了the embeddings W_{emb} 和G與F輸出的softmax向量之間的內積，前者相當於在嵌入向量中的查找操作，後者相當於在字典中所有向量之間的凸組合。the embeddings W_{emb} 在每一步被訓練去最小化 L_{cyc} 和最大化 L_{GAN} ，意味著the embeddings易於被映射並且易於區分。

使用上面的損失函數，會出現訓練不穩定的問題，所以作者借鑒improved GAN,以求得模型穩定性提高，則損失函數則相應地變成如下形式：

隨後，作者又借鑒了Mao等人最初提出平方差損失來代替對數似然損失函數，替換的原始動機在於為了提高訓練中的穩定性和為了避免梯度消失問題，在此工作中，作者發現了對訓練穩定性的重要影響，所以最後的判別器損失函數如下：

最後，總的損失函數則為:

訓練

實現中使用的明文自然語言樣本來自於Brown English text dataset,我們生成２倍batch_size大小的明文樣本，前一batch_size部分被作為cycleGANs的Ｘ分布，後一batch_size部分通過密鑰的選擇作為Ｙ分布。我們使用的Brown英語語料庫在57340句子中包含一百多萬個單詞，我們實現了word-level 的Brown-W和『character-level』的Brown-C。

對於world-level的單詞表，我們選取頻率最高的ｋ個單詞來控制辭彙表的大小，並且引入一個『unkown』記號來表示所有不在單詞表中的單詞，作者展示了他們的方法在使用world-level辭彙表時有能力擴展到更大的辭彙表，而且現代加密技術更多地依賴於具有大量元素的S-boxes。


推薦閱讀：
相关文章