commit 19ba71dee41a230fbff2ae60f829528e4a3dfd83
parent 0fa0e931e7a4b977200c7e9669a3503e1f9f168b
Author: Jared Tobin <jared@jtobin.ca>
Date: Sun, 7 May 2017 12:39:22 +1200
Finish 1.6.
Diffstat:
4 files changed, 59 insertions(+), 21 deletions(-)
diff --git a/README.md b/README.md
@@ -69,5 +69,19 @@ This is illustrated for 1.1.
#### 1.6
- $ INPUT=$(cat data/s1/q6_input.txt | ./bin/b642hex)
+ $ INPUTB64=$(< data/s1/q6_input.txt)
+ $ INPUTHEX=$(echo $INPUTB64 | ./bin/b642hex)
+ $ echo $INPUTB64 | ./bin/score_keysizes 4 10
+ $ # top keysizes for average of 4+ groups are roughly 5, 29, 3
+ $ KEYSIZE=5
+ $ echo $INPUTHEX | ./bin/rotate $KEYSIZE | parallel -k ./bin/charfreq | less
+ $ KEYSIZE=29
+ $ echo $INPUTHEX | ./bin/rotate $KEYSIZE | parallel -k ./bin/charfreq | less
+ $ xxd -r -p <<< "$INPUTHEX" | \
+ ./bin/repeating_key_xor "tERMINATOR x bRING THE NOISE" | \
+ xxd -r -p | less
+ $ # shift by 32 for readability
+ $ xxd -r -p <<< "$INPUTHEX" | \
+ ./bin/repeating_key_xor "Terminator X: Bring the noise" | \
+ xxd -r -p | less
diff --git a/lib/charfreq/src/main.rs b/lib/charfreq/src/main.rs
@@ -25,10 +25,11 @@ fn main() {
return ()
}
- let supplied_string = &args[1];
+ let supplied_string = &args[1];
+ let supplied_string_len = supplied_string.len();
let decoded = match supplied_string.from_hex() {
- Err(err) => panic!("charfreq: {}", err),
+ Err(err) => panic!("charfreq: {} ({})", err, supplied_string_len),
Ok(val) => val,
};
@@ -40,6 +41,8 @@ fn main() {
println!("original: {}", &supplied_string);
println!("byte (frequency)");
println!("----------------");
- for (val, count) in best { println!("{} ({})", val, count); }
+ for (val, count) in best {
+ println!("{}: {} (freq: {})", val, val as char, count);
+ }
}
diff --git a/lib/rotate/Rotate.hs b/lib/rotate/Rotate.hs
@@ -5,6 +5,7 @@
import Control.Error (readMay)
import qualified Data.ByteString as B
import qualified Data.ByteString.Char8 as B8
+import qualified Data.ByteString.Base16 as B16
import System.Environment
import System.IO
@@ -24,8 +25,10 @@ main = do
(narg:_) -> case readMay narg :: Maybe Int of
Nothing -> hPutStrLn stderr "rotate: invalid keysize"
Just size -> do
- bs <- B8.getContents
- let flipped = B.transpose $ chunks size bs
- mapM_ B8.putStrLn flipped
+ hex <- B.getContents
+ let (bs, _) = B16.decode hex
+ flipped = B.transpose (chunks size bs)
+ rehexed = fmap B16.encode flipped
+ mapM_ B8.putStrLn rehexed
- _ -> putStrLn "USAGE: echo FOO | ./rotate KEYSIZE"
+ _ -> putStrLn "USAGE: echo HEX | ./rotate KEYSIZE"
diff --git a/lib/score_keysizes/Score.hs b/lib/score_keysizes/Score.hs
@@ -3,6 +3,7 @@
{-# LANGUAGE OverloadedStrings #-}
import Control.Error (readMay)
+import qualified Control.Foldl as L
import Data.Bits
import qualified Data.ByteString as B
import qualified Data.ByteString.Char8 as B8
@@ -21,27 +22,40 @@ distance s0 s1
hamming a b = popCount (xor a b)
alg = (+) . uncurry hamming
+-- | Split a bytestring into chunks.
+chunks :: Int -> B.ByteString -> [B.ByteString]
+chunks size = loop mempty where
+ loop !acc bs
+ | B.null bs = reverse acc
+ | otherwise = case B.splitAt size bs of
+ (chunk, rest) -> loop (chunk : acc) rest
+
-- | Score a keysize applied to a bytestring.
-score :: Fractional a => B.ByteString -> Int -> Maybe a
-score text size = do
- let (chunk0, rest) = B.splitAt size text
- chunk1 = B.take size rest
- hamming <- distance chunk0 chunk1
- return $ fromIntegral hamming / fromIntegral size
+score :: Fractional a => Int -> Int -> B.ByteString -> Maybe a
+score nchunks size text = do
+ let normalize x = fromIntegral x / fromIntegral size
+ cs = chunks size text
+
+ hammings <- case take nchunks cs of
+ (initial:rest) -> sequence [distance initial chunk | chunk <- rest]
+ _ -> Nothing
+
+ let nhammings = fmap normalize hammings
+ return $ L.fold (L.sum / L.genericLength) nhammings
-- | Score keysizes 2-40 over a given bytestring.
-scoreKeysizes :: B.ByteString -> PSQ.IntPSQ Double ()
-scoreKeysizes text = loop PSQ.empty 2 where
+scoreKeysizes :: Int -> B.ByteString -> PSQ.IntPSQ Double ()
+scoreKeysizes nchunks text = loop PSQ.empty 2 where
plain = B64.decodeLenient text
loop !acc size
| size == 40 = acc
- | otherwise = case score plain size of
+ | otherwise = case score nchunks size plain of
Nothing -> acc
Just prio ->
let nacc = PSQ.insert size prio () acc
in loop nacc (succ size)
--- | Return the best (smallest) n keys from a queue, by key..
+-- | Return the best (smallest) n keys from a queue, by key.
best :: Ord p => Int -> PSQ.IntPSQ p v -> [(Int, p)]
best = loop mempty where
loop !acc idx queue
@@ -58,12 +72,16 @@ main = do
args <- getArgs
case args of
- (narg:_) -> do
+ (nchunksarg:narg:_) -> do
let n = case readMay narg :: Maybe Int of
Nothing -> PSQ.size scored
Just val -> val
- scored = scoreKeysizes bs
+ nchunks = case readMay nchunksarg :: Maybe Int of
+ Nothing -> 2
+ Just val -> val
+
+ scored = scoreKeysizes nchunks bs
top = best n scored
render (k, v) = show k ++ ": " ++ show v
@@ -71,4 +89,4 @@ main = do
putStrLn "keysize: score"
mapM_ (putStrLn . render) top
- _ -> putStrLn "USAGE: echo BASE64 | ./score_keysizes NUM_RESULTS"
+ _ -> putStrLn "USAGE: echo BASE64 | ./score_keysizes NUM_CHUNKS NUM_RESULTS"
