p6 up to grouping and transposing

File renamed without changes

@@ -0,0 +1,64 @@
+HUIfTQsPAh9PE048GmllH0kcDk4TAQsHThsBFkU2AB4BSWQgVB0dQzNTTmVS
+BgBHVBwNRU0HBAxTEjwMHghJGgkRTxRMIRpHKwAFHUdZEQQJAGQmB1MANxYG
+DBoXQR0BUlQwXwAgEwoFR08SSAhFTmU+Fgk4RQYFCBpGB08fWXh+amI2DB0P
+QQ1IBlUaGwAdQnQEHgFJGgkRAlJ6f0kASDoAGhNJGk9FSA8dDVMEOgFSGQEL
+QRMGAEwxX1NiFQYHCQdUCxdBFBZJeTM1CxsBBQ9GB08dTnhOSCdSBAcMRVhI
+CEEATyBUCHQLHRlJAgAOFlwAUjBpZR9JAgJUAAELB04CEFMBJhAVTQIHAh9P
+G054MGk2UgoBCVQGBwlTTgIQUwg7EAYFSQ8PEE87ADpfRyscSWQzT1QCEFMa
+TwUWEXQMBk0PAg4DQ1JMPU4ALwtJDQhOFw0VVB1PDhxFXigLTRkBEgcKVVN4
+Tk9iBgELR1MdDAAAFwoFHww6Ql5NLgFBIg4cSTRWQWI1Bk9HKn47CE8BGwFT
+QjcEBx4MThUcDgYHKxpUKhdJGQZZVCFFVwcDBVMHMUV4LAcKQR0JUlk3TwAm
+HQdJEwATARNFTg5JFwQ5C15NHQYEGk94dzBDADsdHE4UVBUaDE5JTwgHRTkA
+Umc6AUETCgYAN1xGYlUKDxJTEUgsAA0ABwcXOwlSGQELQQcbE0c9GioWGgwc
+AgcHSAtPTgsAABY9C1VNCAINGxgXRHgwaWUfSQcJABkRRU8ZAUkDDTUWF01j
+OgkRTxVJKlZJJwFJHQYADUgRSAsWSR8KIgBSAAxOABoLUlQwW1RiGxpOCEtU
+YiROCk8gUwY1C1IJCAACEU8QRSxORTBSHQYGTlQJC1lOBAAXRTpCUh0FDxhU
+ZXhzLFtHJ1JbTkoNVDEAQU4bARZFOwsXTRAPRlQYE042WwAuGxoaAk5UHAoA
+ZCYdVBZ0ChQLSQMYVAcXQTwaUy1SBQsTAAAAAAAMCggHRSQJExRJGgkGAAdH
+MBoqER1JJ0dDFQZFRhsBAlMMIEUHHUkPDxBPH0EzXwArBkkdCFUaDEVHAQAN
+U29lSEBAWk44G09fDXhxTi0RAk4ITlQbCk0LTx4cCjBFeCsGHEETAB1EeFZV
+IRlFTi4AGAEORU4CEFMXPBwfCBpOAAAdHUMxVVUxUmM9ElARGgZBAg4PAQQz
+DB4EGhoIFwoKUDFbTCsWBg0OTwEbRSonSARTBDpFFwsPCwIATxNOPBpUKhMd
+Th5PAUgGQQBPCxYRdG87TQoPD1QbE0s9GkFiFAUXR0cdGgkADwENUwg1DhdN
+AQsTVBgXVHYaKkg7TgNHTB0DAAA9DgQACjpFX0BJPQAZHB1OeE5PYjYMAg5M
+FQBFKjoHDAEAcxZSAwZOBREBC0k2HQxiKwYbR0MVBkVUHBZJBwp0DRMDDk5r
+NhoGACFVVWUeBU4MRREYRVQcFgAdQnQRHU0OCxVUAgsAK05ZLhdJZChWERpF
+QQALSRwTMRdeTRkcABcbG0M9Gk0jGQwdR1ARGgNFDRtJeSchEVIDBhpBHQlS
+WTdPBzAXSQ9HTBsJA0UcQUl5bw0KB0oFAkETCgYANlVXKhcbC0sAGgdFUAIO
+ChZJdAsdTR0HDBFDUk43GkcrAAUdRyonBwpOTkJEUyo8RR8USSkOEENSSDdX
+RSAdDRdLAA0HEAAeHQYRBDYJC00MDxVUZSFQOV1IJwYdB0dXHRwNAA9PGgMK
+OwtTTSoBDBFPHU54W04mUhoPHgAdHEQAZGU/OjV6RSQMBwcNGA5SaTtfADsX
+GUJHWREYSQAnSARTBjsIGwNOTgkVHRYANFNLJ1IIThVIHQYKAGQmBwcKLAwR
+DB0HDxNPAU94Q083UhoaBkcTDRcAAgYCFkU1RQUEBwFBfjwdAChPTikBSR0T
+TwRIEVIXBgcURTULFk0OBxMYTwFUN0oAIQAQBwkHVGIzQQAGBR8EdCwRCEkH
+ElQcF0w0U05lUggAAwANBxAAHgoGAwkxRRMfDE4DARYbTn8aKmUxCBsURVQf
+DVlOGwEWRTIXFwwCHUEVHRcAMlVDKRsHSUdMHQMAAC0dCAkcdCIeGAxOazkA
+BEk2HQAjHA1OAFIbBxNJAEhJBxctDBwKSRoOVBwbTj8aQS4dBwlHKjUECQAa
+BxscEDMNUhkBC0ETBxdULFUAJQAGARFJGk9FVAYGGlMNMRcXTRoBDxNPeG43
+TQA7HRxJFUVUCQhBFAoNUwctRQYFDE43PT9SUDdJUydcSWRtcwANFVAHAU5T
+FjtFGgwbCkEYBhlFeFsABRcbAwZOVCYEWgdPYyARNRcGAQwKQRYWUlQwXwAg
+ExoLFAAcARFUBwFOUwImCgcDDU5rIAcXUj0dU2IcBk4TUh0YFUkASEkcC3QI
+GwMMQkE9SB8AMk9TNlIOCxNUHQZCAAoAHh1FXjYCDBsFABkOBkk7FgALVQRO
+D0EaDwxOSU8dGgI8EVIBAAUEVA5SRjlUQTYbCk5teRsdRVQcDhkDADBFHwhJ
+AQ8XClJBNl4AC1IdBghVEwARABoHCAdFXjwdGEkDCBMHBgAwW1YnUgAaRyon
+B0VTGgoZUwE7EhxNCAAFVAMXTjwaTSdSEAESUlQNBFJOZU5LXHQMHE0EF0EA
+Bh9FeRp5LQdFTkAZREgMU04CEFMcMQQAQ0lkay0ABwcqXwA1FwgFAk4dBkIA
+CA4aB0l0PD1MSQ8PEE87ADtbTmIGDAILAB0cRSo3ABwBRTYKFhROHUETCgZU
+MVQHYhoGGksABwdJAB0ASTpFNwQcTRoDBBgDUkksGioRHUkKCE5THEVCC08E
+EgF0BBwJSQoOGkgGADpfADETDU5tBzcJEFMLTx0bAHQJCx8ADRJUDRdMN1RH
+YgYGTi5jMURFeQEaSRAEOkURDAUCQRkKUmQ5XgBIKwYbQFIRSBVJGgwBGgtz
+RRNNDwcVWE8BT3hJVCcCSQwGQx9IBE4KTwwdASEXF01jIgQATwZIPRpXKwYK
+BkdEGwsRTxxDSToGMUlSCQZOFRwKUkQ5VEMnUh0BR0MBGgAAZDwGUwY7CBdN
+HB5BFwMdUz0aQSwWSQoITlMcRUILTxoCEDUXF01jNw4BTwVBNlRBYhAIGhNM
+EUgIRU5CRFMkOhwGBAQLTVQOHFkvUkUwF0lkbXkbHUVUBgAcFA0gRQYFCBpB
+PU8FQSsaVycTAkJHYhsRSQAXABxUFzFFFggICkEDHR1OPxoqER1JDQhNEUgK
+TkJPDAUAJhwQAg0XQRUBFgArU04lUh0GDlNUGwpOCU9jeTY1HFJARE4xGA4L
+ACxSQTZSDxsJSw1ICFUdBgpTNjUcXk0OAUEDBxtUPRpCLQtFTgBPVB8NSRoK
+SREKLUUVAklkERgOCwAsUkE2Ug8bCUsNSAhVHQYKUyI7RQUFABoEVA0dWXQa
+Ry1SHgYOVBFIB08XQ0kUCnRvPgwQTgUbGBwAOVREYhAGAQBJEUgETgpPGR8E
+LUUGBQgaQRIaHEshGk03AQANR1QdBAkAFwAcUwE9AFxNY2QxGA4LACxSQTZS
+DxsJSw1ICFUdBgpTJjsIF00GAE1ULB1NPRpPLF5JAgJUVAUAAAYKCAFFXjUe
+DBBOFRwOBgA+T04pC0kDElMdC0VXBgYdFkU2CgtNEAEUVBwTWXhTVG5SGg8e
+AB0cRSo+AwgKRSANExlJCBQaBAsANU9TKxFJL0dMHRwRTAtPBRwQMAAATQcB
+FlRlIkw5QwA2GggaR0YBBg5ZTgIcAAw3SVIaAQcVEU8QTyEaYy0fDE4ITlhI
+Jk8DCkkcC3hFMQIEC0EbAVIqCFZBO1IdBgZUVA4QTgUWSR4QJwwRTWM=

@@ -4,6 +4,7 @@ import collections
 import csv
 import random
 from math import sqrt
+import itertools
 import simple_crypto as sc# helper functions
 
 stl = 20  # str_tips length
@@ -60,16 +61,16 @@ assert p3_hex == p3_hex_enc, 'dec/enc failed'
 # 4. Detect single-character XOR
 if do_4:
     print "\n---- Problem 4: Detect single-character XOR ----"
-    lines = [line.strip() for line in open('gistfile1.txt')]
+    lines = [line.strip() for line in open('gistfile_p4.txt')]
     best = (0,'',"")
     f = sc.freq_array_load()
     for x in lines:
         x_raw = x.decode('hex')
         key, value = sc.ngram_freq_cos_sim (x_raw, f)
         if value > best[0]:
-            best = (value, key, sc.xor_str(x_raw, key))
+            best = (value, key, x)
     print "p4 key : ", best[1]
-    print "p4 dec : ", best[2].strip()
+    print "p4 dec : ", sc.xor_str (best[2].decode('hex'),best[1]).strip()
 
 
 # 5. Repeating-key XOR Cipher
@@ -88,7 +89,6 @@ print "p5 dec         :", sc.str_tips (p5_dec, stl)
 assert p5_enc == p5_str_enc, "p5 encryption failed"
 assert p5_dec == p5_str, "p5 decryption failed"
 
-
 # 5b. Encrypt a bunch of stuff using your repeating-key XOR function
 keys = 10
 sa = [] # string array
@@ -101,9 +101,29 @@ for s in sa:
     for k in range(keys):
         key_len = random.randint (3,30)
         key = ''.join (random.choice (string.ascii_letters) for r in range (key_len))
-        s_e = sc.xor_str (s, key)
-        s_ed = sc.xor_str (s_e, key)
-        s_ede = sc.xor_str (s_ed, key)
-        assert s_ed == s, "p5b enc/dec failed (ed/s)"
-        assert s_ede == s_e, "p5b enc/dec failed (ede/e)"
-print "Repeating-key XOR tested on", len(sa), "strings, with", len(sa)*keys, "unique keys"
+        assert sc.test_xor (s,key)
+print "Repeating-key XOR tested successfully on:", "\n\t", \
+         len(sa), "strings", "\n\t", \
+         len(sa)*keys, "unique keys"
+
+
+# 6. Break repeating-key XOR
+print "\n---- Problem 6: Break repeating-key XOR ----"
+p6_a = "this is a test"
+p6_b = "wokka wokka!!!"
+p6_hd_ab = sc.hamming_dist (p6_a, p6_b)
+assert p6_hd_ab == 37 # Given
+print "Hamming Distance [", p6_a,",", p6_b,"] =", p6_hd_ab
+p6_str_b64 = ''.join([line.strip() for line in open('gistfile_p6.txt')])
+p6_str = base64.b64decode (p6_str_b64)
+p6_key_len = sc.key_len_finder (p6_str)
+print "Possible p6_key_len :", p6_key_len[0][0],",", p6_key_len[1][0],",", p6_key_len[2][0]
+
+
+
+s = "DFJKSDJFKsjlakfjdsfkd"
+key_len = 5
+
+
+print sc.group_and_trans (s,key_len)
+

@@ -3,6 +3,8 @@ import string
 import collections
 import csv
 import random
+import operator
+from itertools import izip_longest
 from math import sqrt
 
 def translator (frm='', to='', delete='', keep=None):
@@ -184,4 +186,51 @@ def str_tips (s, n):
         return s
     else:
         return s[:n] + " ... " + s[-n:]
+
+def hamming_dist (s1, s2):
+    # http://en.wikipedia.org/wiki/Hamming_distance   
+    # this version specifically examines the binary of each character, not 
+    # just the characters like the wikipedia one does.
+    assert len(s1) == len(s2), "hamming_distance requires equal length strings"
+    dist = 0
+    for ch1, ch2 in zip(s1, s2):
+        dist += sum ( a!=b 
+            for a, b in zip(
+                bin(ord(ch1))[2:].zfill(8), 
+                bin(ord(ch2))[2:].zfill(8))
+        )
+    return dist
  
+def key_len_finder (s):
+    # nhd = normalized hamming distance dict
+    nhdd = {}
+    min_nhd = (0,41.0)
+    blocks = 4
+    for keysize in xrange (1,41):
+        sum_nhd = 0
+        for i in range (blocks):
+            # normalized by keysize*8 since hamming dist is binary (char = 8 bits)
+            sum_nhd += hamming_dist (
+                    s[i*keysize:i*keysize+keysize], 
+                    s[i*keysize+keysize:i*keysize+keysize*2] 
+                ) / float (keysize*8)
+        nhd = sum_nhd / float(blocks)
+        nhdd[keysize] = nhd
+        if nhd < min_nhd[1]:
+            min_nhd = (keysize, nhd)
+    return sorted(nhdd.iteritems(), key=operator.itemgetter(1))
+
+def grouper (iterable, n, fillvalue=None):
+    "Collect data into fixed-length chunks or blocks"
+    # http://docs.python.org/2/library/itertools.html#recipes
+    # grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx
+    args = [iter(iterable)] * n
+    return izip_longest(fillvalue=fillvalue, *args)
+
+def group_and_trans (s,key_len):
+    transpose = ['' for i in range (key_len)]
+    s_segments = grouper(s,key_len,'')
+    for j in s_segments:
+        for i in range(key_len):
+            transpose[i] += j[i]
+    return transpose

Commit 5eae41a

Commit `5eae41a`