破解已知密鑰長度的異或密碼?
對於挑戰,我需要找到加密文本的密鑰。
我知道密鑰的長度為 N(不變)。無法保證密鑰只是字母或字母數字,但這可能是一個合理的假設。
我知道原文只有字母,沒有數字,但不能保證文本是小寫還是大寫。文本具有小寫和大寫字元是一個合理的假設。
實際的加密類似於 Vigenere 密碼,因為它使用滾動密鑰對輸入進行 XOR,逐個字元地執行(虛擬碼,不要嘗試以任何語言執行它):
ciphertext = "" n = 0 ; //key iterator for character in input: ciphertext += key[n] XOR character; n++; if(c >= N) { // reset key iterator when reaching the known length of the key c = 0; } return ciphertext
輸出不能直接用作文本,輸入同時包含大寫和小寫字元。
我應該如何破解加密文本?
我想到了什麼:
從密文中提取由同一個key的字母加密的字元,例如隔離所有用key加密的字元
$$ 0 $$,並對其進行統計分析。我的問題是大寫和小寫字母的存在使統計分析變得困難,無法區分大寫或小寫的相同字母。我們現在有 52 個可能的字母,而不是 26 個,因為文本太短而無法使用此方法。(大約 450 個字元,對於一個 8char 長的密鑰,這意味著只有 56char by set) 走已知的明文方式,試圖找到常用詞。問題是他的文本很可能是法語或英語,單詞越長,它最有可能不在文本中。我認為這是最後的解決方案。
簡單地暴力破解文本。假設密鑰長度為 8char,字元集為 0-9a-zA-Z,我們有 62^8(幾十億)個可能的排列,這是不可能覆蓋的。
我能做些什麼來解決這個問題,或者減少解決問題的時間?我想知道是否有一種方法可以知道加密文本中的輸入文本是小寫還是大寫,或者是否有一種方法可以操縱加密文本以將其全部變為大寫……這將有助於有點統計分析,即使我很可能沒有足夠的數據進行質量分析。
在這個挑戰上花費了更多時間之後,這就是我為解決它所做的工作。
將文本除以 N 列,其中 N 是密鑰的長度。
對每列執行頻率分析。給定足夠的數據,您很可能會得到一個比其他角色出現的頻率更高的角色。因為我的文字是法語,所以是字母 e。
對於每一列,找到應該是“e”的值的一個實例,並將該數據與字母“e”進行異或,以找到鍵的第 N 個字母。
給定足夠的數據,您會為每一列找到一個“e”,為您提供鍵的所有字母。嘗試用密鑰解密文本,瞧,你得到了原始文本。
一旦我想出了這種解決難題的方法,我發現它是解決 XOR 加密的一種非常常見的方法,並且存在可以比手動更快地為您完成此操作的工具。
例如,xortool:https ://github.com/hellman/xortool
xortool -l 8 input.bin -c65
-l 是密鑰的長度,-c 是您認為文本所在語言中最常見字母的十六進制值。
該命令幾乎是瞬時的。