fix(wpcarro/cryptopals): Update cleartext scoring algorithm r/3547

Create a frequency table of alphabetic characters by reading each character in
"Alice in Wonderland"; use this frequency table to score cleartext when decoding
ciphers.

Change-Id: Id322af64d792c15231a1a02794f396c46196c207
Reviewed-on: https://cl.tvl.fyi/c/depot/+/4788
Tested-by: BuildkiteCI
Reviewed-by: wpcarro <wpcarro@gmail.com>
Autosubmit: wpcarro <wpcarro@gmail.com>

3 files changed, 45 insertions, 11 deletions

diff --git a/users/wpcarro/scratch/cryptopals/.gitignore b/users/wpcarro/scratch/cryptopals/.gitignore
new file mode 100644
index 0000000000..7aa03e126b
--- /dev/null
+++ b/users/wpcarro/scratch/cryptopals/.gitignore
@@ -0,0 +1 @@
+alice.txt
\ No newline at end of file
diff --git a/users/wpcarro/scratch/cryptopals/set1/c3.py b/users/wpcarro/scratch/cryptopals/set1/c3.py
index 187b58c1c7..2d84026a7b 100644
--- a/users/wpcarro/scratch/cryptopals/set1/c3.py
+++ b/users/wpcarro/scratch/cryptopals/set1/c3.py
@@ -1,22 +1,39 @@
 from c2 import fixed_xor
 from collections import Counter
-import string
 
-alphabet = string.ascii_lowercase + string.ascii_uppercase
+def frequency_table():
+    with open('alice.txt', 'r') as f:
+        chars = {}
+        while True:
+            l = f.readline()
+            if not l: break
+            for c in l:
+                chars[c] = chars.get(c, 0) + 1
+        result = {}
+        for c, n in chars.items():
+            result[c] = n / len(chars)
+        return result
 
-def score(bs):
-    chars = [b for b in bs if b in alphabet]
-    return sum(Counter(chars).values())
+def score(bs, freqs):
+    return sum(freqs.get(b, 0) for b in bs)
 
 def decode_cipher(x):
+    freqs = frequency_table()
+
+    if not freqs:
+        raise Error("Cannot decode cipher without a populated frequency table")
+
     x = bytearray.fromhex(x)
     num_bytes = len(x)
 
     mx, result, key = 0, None, None
-    for c in alphabet:
-        mask = bytearray(bytes(c, 'ascii') * num_bytes)
-        y = fixed_xor(x, mask, decode_hex=False, encode_hex=False).decode('ascii')
-        test = score(y)
+    for b in range(0, 1 << 8):
+        mask = bytearray(b.to_bytes(1, 'big') * num_bytes)
+        try:
+            y = fixed_xor(x, mask, decode_hex=False, encode_hex=False).decode('ascii')
+        except:
+            continue
+        test = score(y, freqs)
         if test > mx:
             result = y
             mx = test
@@ -26,3 +43,8 @@ def decode_cipher(x):
 run_tests = False
 if run_tests:
     print(decode_cipher("1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736"))
+
+################################################################################
+# Answer
+################################################################################
+"Cooking MC's like a pound of bacon"
diff --git a/users/wpcarro/scratch/cryptopals/set1/c4.py b/users/wpcarro/scratch/cryptopals/set1/c4.py
index 6775d73ec8..c546419a33 100644
--- a/users/wpcarro/scratch/cryptopals/set1/c4.py
+++ b/users/wpcarro/scratch/cryptopals/set1/c4.py
@@ -2,11 +2,22 @@ import c3
 
 content = None
 with open('4.txt', 'r') as f:
-    c3.decode_cipher
     content = f.read().splitlines()
+if not content:
+    raise Error("Need content to proceed")
 
+xs = []
 for line in content:
     try:
-        print(c3.decode_cipher(line))
+        x = c3.decode_cipher(line)
+        if x: xs.append(x)
     except:
         continue
+
+freqs = c3.frequency_table()
+print(max(xs, key=lambda x: c3.score(x, freqs)))
+
+################################################################################
+# Answer
+################################################################################
+"Now that the party is jumping"