破解XOR重复密钥

Question

我想破解XOR重复密钥，我现在没有关于密钥和消息的任何内容，只有我知道它使用的是重复密钥。使用重复键XOR加密编码后的消息sbasebase64'd，因此我首先将base 64转换为base16，这样更容易。我有指示，但我不明白这很好。

1. 设KEYSIZE为密钥的猜测长度;尝试从2到（说）40的值。 编写一个函数来计算两个字符串之间的编辑距离/汉明距离。

2. 对于每个KEYSIZE，取第一个KEYSIZE字节值和第二个KEYSIZE字节值，并找出它们之间的编辑距离。通过除以KEYSIZE标准化这个结果。

3. 具有最小归一化编辑距离的键可能是关键。你可以用最小的2-3个KEYSIZE值进行处理。或者取4个KEYSIZE块而不是2个平均距离。

现在你可能知道密钥长度：破密文成密钥大小长度等的块，我这剩下的精，就目前而言，我现在正是当我发现如果这是好的，尝试解码..

我用Python写了一个代码，这一点，它是工作，但我不能完全肯定，如果我这样做了正确

def compute_distance(str1,str2,keysize): 
     count=0 
     str1=str1.replace("\n", "") 
     str2=str2.replace("\n", "") 
     keysize=str(keysize*8) 
     sbin1=format(int(str1,16),'0'+keysize+'b') 
     sbin2=format(int(str2,16),'0'+keysize+'b') 

     for c1,c2 in zip(sbin1, sbin2): 
     if c1!=c2: 
      count+=1 

     return count 


    def keysize_dist(filelocation): 
     f=open(filelocation,'r') 
     lines=[] 
     for line in f.readlines(): 
     line=line.strip('\n') 
     lines.append(line) 
     lines=''.join(lines).strip('\n') 
     normalized=[] 
     for keysize in range(2,40): 
     count=compute_distance(lines[0:keysize*2],lines[keysize*2:keysize*4],keysize) 

     normalized.append(float(count)/keysize) 


     return lines,int(min(normalized)) 

Answer 1

这是方式，我从您的文章的理解。 我做了一个python程序，用循环键生成加密xor流，并尝试应用hamming字符串距离归一化方法来查找最佳潜在循环密钥大小。 我不把东西转换成base64，我直接应用字符串距离而不是二进制距离。

#!/usr/bin/python 

import sys 
from itertools import cycle 

def xor_file_with_cycling_strkey(filelocation,outfile,key): 
    print filelocation 
    f=open(filelocation,'r') 
    f2=open(outfile,'w') 
    lines=[] 
    text=f.read() 
    if text != '': 
    for c,k in zip(text,cycle(key)): 
     r=chr(ord(c)^ord(k)) 
     f2.write(r) 
    f2.close() 
    f.close() 

# not used here, see compute_distance_char based on same idea. 
def compute_distance(str1,str2,keysize): 
    count=0 
    print '%s %s' % (str1,str2) 
    str1=str1.replace("\n", "") 
    str2=str2.replace("\n", "") 
    keysize=str(keysize*8) 
    sbin1=format(int(str1,16),'0'+keysize+'b') 
    sbin2=format(int(str2,16),'0'+keysize+'b') 
    return hamming_distance_str(sbin1,sbin2) 

#do preferer hamming_distance_bin which quicker. 
def compute_distance_char(str1,str2,keysize): 
    count=0 
    str1=str1.replace("\n", "") 
    str2=str2.replace("\n", "") 
    keysize=str(keysize*8) 
    sbin1='' 
    sbin2='' 
    for c in str1: 
    sbin1=sbin1 + format(ord(c),'0'+keysize+'b') 
    for c in str2: 
    sbin2=sbin2 + format(ord(c),'0'+keysize+'b') 
    return hamming_distance_str(sbin1,sbin2) 

def hamming_distance_str(str1,str2): 
    count=0 
    for c1,c2 in zip(str1, str2): 
    if c1!=c2: 
     count+=1 
    return count 

def hamming_distance_bin(str1,str2): 
    count=0 
    for c1,c2 in zip(str1, str2): 
    if c1!=c2: 
     # quick hamming distance, counting number of differing bits. 
     s=ord(c1)^ord(c2) 
     # count number of bits sets using Wegner algorithm 
     while s !=0: 
     s&=(s-1); 
     count+=1 
    return count 

def keysize_dist(filelocation): 
    potential_keysize=0 
    min_dist=40.0 
    f=open(filelocation,'r') 
    lines=[] 
    for line in f.readlines(): 
    line=line.strip('\n') 
    lines.append(line) 
    lines=''.join(lines).strip('\n') 
    normalized=[] 
    for keysize in range(2,40): 
# should first create base16 entries for that one , then don't use it : count_bin1=compute_distance(lines[0:keysize*2],lines[keysize*2:keysize*4],keysize) 
    # proof that both functions compute same value : 
    count_bin1=compute_distance_char(lines[0:keysize*2],lines[keysize*2:keysize*4],keysize) 
    count_bin2=hamming_distance_bin(lines[0:keysize*2],lines[keysize*2:keysize*4]) 
    if (count_bin1 != count_bin2): 
     print 'Discrepency between compute_distance_char->%i and hamming_distance_bin->%i' % (count_bin1,count_bin2) 
    count=hamming_distance_str(lines[0:keysize*2],lines[keysize*2:keysize*4]) 

    normalized_distance=float(count)/keysize 
    print '%s %f' % (keysize,normalized_distance) 
    if (normalized_distance < min_dist): 
     potential_keysize=keysize 
     min_dist=normalized_distance 
# we are more interested in keysize corresponding to minimal distance, tha n to minimal distance itself. 
    return potential_keysize,min_dist 

def main(args=sys.argv): 
if (len(args) < 2): 
    print 'Please enter cleartext origin file to be ciphered then checked an optionaly a key string (max length 40)' 
    return 1 
if (len(args) > 2): 
    key=args[2] 
else: 
    # on purpose default to key with a KEYSIZE char length 5. 
    key='12345' 
xor_file_with_cycling_strkey(args[1],args[1]+'.ciphered',key) 
xor_file_with_cycling_strkey(args[1]+'.ciphered',args[1] + '.cleartext',key) 

# raw non base64 encoded. 
print keysize_dist(args[1] + '.ciphered') 

if __name__ == "__main__": 
    main() 

通过该代码，您可以获得完全解决问题所需的所有输入。

./hamming_detect_xor_cycle.py明文123456789ABCDE ... （14，1.7857142857142858）

它不正确地检测到所有的大小，但我认为这是一个统计效果，取决于明文本身可以循环属性。正如你的主题所说：使用更多的块可以提供更好的结果。