我有一个程序如下,它基本上比较标准字典中所有可能单词的异或,并将异或结果与密文的异或结果进行比较。但我猜复杂度是 O(n2)。我不知道如何降低复杂性。
def find_collision():
a = int("4ADD55BA941FE954",16) ^ int("5AC643BE8504E35E",16)
with open("/usr/share/dict/words", "r") as f:
alist = [line.rstrip() for line in f]
b = len(alist)
for i in range(0,b,1):
for j in range(i,b,1):
if(((int(alist[i].encode('hex'), 16))^ (int(alist[j].encode('hex'), 16)))==a):
print("Plain Text1: "+alist[i]+'\n'+"Plain Text2: "+alist[j])
#print "Yes"
break
任何帮助将不胜感激。
最佳答案
首先,让我们尝试简化。
def find_collision():
key = 0b1000000011011000101100000010000010001000110110000101000001010
# that's 0x4ADD55BA941FE954^0x5AC643BE8504E35E
然后我们方便的 itertools
模块可以为大列表完成繁重的工作。这取代了嵌套的 for
循环,并且可能工作得更快。
from itertools import combinations
##def find_collision()
## key = 0b1000000011011000101100000010000010001000110110000101000001010
with open("/usr/share/dict/words", "r") as f:
full_wordlist = combinations( map(str.rstrip,f.readlines()), 2 )
# Combinations( { ('word1','word2'),('word1','word3'),('word1','word4'),
('word2','word3') ... } )
但我们并不真正关心整件事,不是吗?我们关心的只是碰撞,所以让我们进行碰撞吧? 编辑:并且由于这里肯定会有单词,我们无法转换为十六进制,因此:
#instead of full_wordlist = combinations(...)
import re
with open("usr/share/dict/words","r") as f:
words = (word for word in map(str.rstrip,f.readlines()) if not re.search(r"[^0-9a-fA-F]",word))
# you can avoid the need for regex by doing:
# words = (word for word in map(str.rstrip,f.readlines()) if
# not any(char not in "0123456789abcdefABCDEF" for char in word))
collisions = [keypair for keypair in combinations(words,2)
if bin(int(keypair[0],base=16)^int(keypair[1],base=16)) == key]
然后用一些理智的东西来消除碰撞,例如:
for collision in collisions:
print("Collision between {0[0]}^{0[1]} and key".format(collision))
关于python - 降低Python中字典暴力破解的复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22155756/