# Exhaustive search for encryption keys

This does the job, but is not especially elegant.

What is the preferred Pythonic idiom to my childish nests?

def bytexor(a, b):
res = ""
for x, y in zip(a, b):
if (x == "1" and y == "0") or (y =="1" and x == "0"):
res += "1"
else:
res += "0"

return res

def get_all():
res = []
bit = ["0","1"]
for i in bit:
for j in bit:
for k in bit:
for l in bit:
res.append(i+j+k+l)
return res

if __name__=="__main__":

for k0 in get_all():
for k1 in get_all():
for k2 in get_all():
for k3 in get_all():
for k4 in get_all():
if bytexor(bytexor(k0, k2), k3) == "0011":
if bytexor(bytexor(k0, k2), k4) == "1010":
if bytexor(bytexor(bytexor(k0,k1),k2),k3) == "0110":
print k0, k1, k2, k3, k4
print bytexor(bytexor(bytexor(k0, k1),k2),k4)

• What is the code supposed to be doing? You're apparently trying to get all combinations of 4-bit binary numbers... but what are you trying to get from that? – Jeff Mercado Nov 20 '12 at 7:52
• @JeffMercado the problem was homework. There was an encryption algorithm given and some sample cyphertext - this code does an exhaustive search for keys that fit with the ciphertext, and encrypts a message using the same algorithm for each valid key. – jsj Nov 20 '12 at 10:31
• I know this is not really what you were looking for, but you could leave the loops and optimize their runtime using cython or numba. – yoavram Nov 27 '12 at 14:00

To convert an integer to a bit string with a particular number of digits, use string.format with the b format type. For example:

>>> ['{0:04b}'.format(i) for i in range(16)]
['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111',
'1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']


But really it looks to me as though you don't want to be working with bit strings at all. You just want to be working with integers.

So instead of get_all, just write range(16) and instead of bytexor, write ^. Your entire program can be written like this:

from itertools import product
for a, b, c, d, e in product(range(16), repeat=5):
if a ^ c ^ d == 3 and a ^ c ^ e == 10 and a ^ b ^ c ^ d == 6:
print a, b, c, d, e, a ^ b ^ c ^ e


(This will also run a lot faster without all that fiddling about with strings.)

• Thanks.. I can't believe it took me all that to write what could be done with five lines :s – jsj Nov 20 '12 at 16:11

Depending on what you are ultimately doing, probably the neatest way is to use a standard module, itertools. Using get_all as an example:

import itertools

def get_all_bitpatterns():
res = []
bit = [ "0", "1" ]
for z in itertools.product( bit, bit, bit, bit ):
res.append( "".join(z) )
return res

• product takes a repeat argument, which would be useful here. – Gareth Rees Nov 20 '12 at 12:06
• You could also use bit = '01' as string is iterable in Python. – Developer Nov 20 '12 at 12:14
• return ["".join(z) for z in itertools.product(bit, repeat=4)] – tokland Nov 20 '12 at 13:30

This is just a little bit improved edition of 'Glenn Rogers' answer ;) Simply work around bit, say bit='abcd' and number n.

from itertools import product

def AllBitPatterns(bit='01',n=2):
out = []
for z in product(bit,repeat=n*len(bit)):    #thanks to a comment
out.append(''.join(z))
return out

print AllBitPatterns()
print AllBitPatterns(n=3)
print AllBitPatterns(bit='-~')


Outputs:

>>>
['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']
['000000', '000001', '000010', '000011', '000100', '000101', '000110', '000111', '001000', '001001', '001010', '001011', '001100', '001101', '001110', '001111', '010000', '010001', '010010', '010011', '010100', '010101', '010110', '010111', '011000', '011001', '011010', '011011', '011100', '011101', '011110', '011111', '100000', '100001', '100010', '100011', '100100', '100101', '100110', '100111', '101000', '101001', '101010', '101011', '101100', '101101', '101110', '101111', '110000', '110001', '110010', '110011', '110100', '110101', '110110', '110111', '111000', '111001', '111010', '111011', '111100', '111101', '111110', '111111']
['----', '---~', '--~-', '--~~', '-~--', '-~-~', '-~~-', '-~~~', '~---', '~--~', '~-~-', '~-~~', '~~--', '~~-~', '~~~-', '~~~~']

• This answer is not mine, please remove it. – Developer Mar 31 '17 at 7:49

I have answered awhile ago to this very type of question. This is a very simple problem. You should not complicate it at all with iterators.

The trick is that the bit pattern you are seeking for is actually the bits of numbers incremented by 1!

Something like:

def get_all():
res = []
for i in range(16):
# get the last four bits of binary form i which is an int
bin(i) # a string like '0b0000' - strip '0b', 0 pad it to 4 length


I am not really the python guy, but I hope the idea is clear. Equivalent Java code:

int len = 3; // your number of for loops
int num = (int)Math.pow(2, len);
for(int i=0; i<num; i++){
// https://stackoverflow.com/a/4421438/1273830
System.out.println(String.format("%"+len+"s", Integer.toBinaryString(i)).replace(' ', '0'));
}


Happy coding.