Challenge 6

3 files changed, 183 insertions, 8 deletions

diff --git a/src/solvers/Challenge4.scala b/src/solvers/Challenge4.scala
index f71f6c0..ba771a8 100644
--- a/src/solvers/Challenge4.scala
+++ b/src/solvers/Challenge4.scala
@@ -14,7 +14,7 @@ object Challenge4 {
       .zipWithIndex
       .map { pair => (pair._1._1, pair._1._2, pair._2) }
       .filter(_._1 != 0)
-      .map { triplet => (XorDecrypt.decryptToAscii(triplet._2)(triplet._1), triplet._3) }
+      .map { triplet => (XorDecrypt.decryptToAsciiSingleByteKey(triplet._2)(triplet._1), triplet._3) }
       .map { pair => (pair._1, TextScorer.score(pair._1.asBytes), pair._2) }
       .sortBy(_._2)
       .map { triplet => (triplet._1, triplet._3) }
diff --git a/src/solvers/Challenge6.scala b/src/solvers/Challenge6.scala
new file mode 100644
index 0000000..9580fbb
--- /dev/null
+++ b/src/solvers/Challenge6.scala
@@ -0,0 +1,110 @@
+package ixee.cryptopals.solvers
+
+import scala.io.Source
+import ixee.cryptopals.utils.ByteUtils._
+import ixee.cryptopals.utils.ConversionUtils._
+import ixee.cryptopals.utils.FunctionUtils._
+import ixee.cryptopals.utils._
+import io.github.marklister.base64.Base64._
+
+object Challenge6 {
+  val path = "./data/6.txt"
+
+  lazy val ciphertext =
+    Source
+      .fromFile(path)
+      .getLines()
+      .toSeq
+      .flatten
+      .mkString
+      .toByteArray
+
+  def run = {
+    XorDecrypt.crackForMultiByteKey(ciphertext)
+  }
+
+  def findKey: Seq[Byte] =
+    XorDecrypt.findBestMultiByteKey(ciphertext)
+
+  val expectation =
+    """|I'm back and I'm ringin' the bell 
+       |A rockin' on the mike while the fly girls yell 
+       |In ecstasy in the back of me 
+       |Well that's my DJ Deshay cuttin' all them Z's 
+       |Hittin' hard and the girlies goin' crazy 
+       |Vanilla's on the mike, man I'm not lazy. 
+       |
+       |I'm lettin' my drug kick in 
+       |It controls my mouth and I begin 
+       |To just let it flow, let my concepts go 
+       |My posse's to the side yellin', Go Vanilla Go! 
+       |
+       |Smooth 'cause that's the way I will be 
+       |And if you don't give a damn, then 
+       |Why you starin' at me 
+       |So get off 'cause I control the stage 
+       |There's no dissin' allowed 
+       |I'm in my own phase 
+       |The girlies sa y they love me and that is ok 
+       |And I can dance better than any kid n' play 
+       |
+       |Stage 2 -- Yea the one ya' wanna listen to 
+       |It's off my head so let the beat play through 
+       |So I can funk it up and make it sound good 
+       |1-2-3 Yo -- Knock on some wood 
+       |For good luck, I like my rhymes atrocious 
+       |Supercalafragilisticexpialidocious 
+       |I'm an effect and that you can bet 
+       |I can take a fly girl and make her wet. 
+       |
+       |I'm like Samson -- Samson to Delilah 
+       |There's no denyin', You can try to hang 
+       |But you'll keep tryin' to get my style 
+       |Over and over, practice makes perfect 
+       |But not if you're a loafer. 
+       |
+       |You'll get nowhere, no place, no time, no girls 
+       |Soon -- Oh my God, homebody, you probably eat 
+       |Spaghetti with a spoon! Come on and say it! 
+       |
+       |VIP. Vanilla Ice yep, yep, I'm comin' hard like a rhino 
+       |Intoxicating so you stagger like a wino 
+       |So punks stop trying and girl stop cryin' 
+       |Vanilla Ice is sellin' and you people are buyin' 
+       |'Cause why the freaks are jockin' like Crazy Glue 
+       |Movin' and groovin' trying to sing along 
+       |All through the ghetto groovin' this here song 
+       |Now you're amazed by the VIP posse. 
+       |
+       |Steppin' so hard like a German Nazi 
+       |Startled by the bases hittin' ground 
+       |There's no trippin' on mine, I'm just gettin' down 
+       |Sparkamatic, I'm hangin' tight like a fanatic 
+       |You trapped me once and I thought that 
+       |You might have it 
+       |So step down and lend me your ear 
+       |'89 in my time! You, '90 is my year. 
+       |
+       |You're weakenin' fast, YO! and I can tell it 
+       |Your body's gettin' hot, so, so I can smell it 
+       |So don't be mad and don't be sad 
+       |'Cause the lyrics belong to ICE, You can call me Dad 
+       |You're pitchin' a fit, so step back and endure 
+       |Let the witch doctor, Ice, do the dance to cure 
+       |So come up close and don't be square 
+       |You wanna battle me -- Anytime, anywhere 
+       |
+       |You thought that I was weak, Boy, you're dead wrong 
+       |So come on, everybody and sing this song 
+       |
+       |Say -- Play that funky music Say, go white boy, go white boy go 
+       |play that funky music Go white boy, go white boy, go 
+       |Lay down and boogie and play that funky music till you die. 
+       |
+       |Play that funky music Come on, Come on, let me hear 
+       |Play that funky music white boy you say it, say it 
+       |Play that funky music A little louder now 
+       |Play that funky music, white boy Come on, Come on, Come on 
+       |Play that funky music 
+       |""".stripMargin
+}
diff --git a/src/solvers/XorDecrypt.scala b/src/solvers/XorDecrypt.scala
index 6b82c34..83fa923 100644
--- a/src/solvers/XorDecrypt.scala
+++ b/src/solvers/XorDecrypt.scala
@@ -2,24 +2,89 @@ package ixee.cryptopals.solvers
 
 import ixee.cryptopals.utils._
 import ixee.cryptopals.utils.ByteUtils._
+import ixee.cryptopals.utils.StreamUtils._
 import ixee.cryptopals.utils.FunctionUtils._
+import ixee.cryptopals.utils.ConversionUtils._
 
 object XorDecrypt {
-  implicit val freq = Frequencies.cornell40kSample
+  implicit val freq = Frequencies.cryptologicalMathematics //cornell40kSample
 
-  def decryptToAscii(ciphertext: Seq[Byte])(key: Byte): String = {
-    new String((ciphertext xor Stream.continually(key)).toArray)
+  def inferKeySizes(xs: Seq[Byte]): Seq[Int] = {
+    inferKeySizesWithHammingDistance(xs).map(_._2)
   }
 
-  def tryBestDecrypt(ciphertext: Seq[Byte]): String = {
-    (findBestSingleByteKey _ :| decryptToAscii(ciphertext) _)(ciphertext)
+  def inferKeySize(xs: Seq[Byte]): Int =
+    inferKeySizes(xs).head
+
+  // not so great for small key sizes.
+  // TODO: Why exactly does this work?
+  def inferKeySizesWithHammingDistance(xs: Seq[Byte]): Seq[(Double, Int)] = {
+    val MinKeySize = 1
+    val MaxKeySize = 40
+
+    (MinKeySize to MaxKeySize)
+      .map(normalizedHammingDistanceForKeySize(xs, _))
+      .zipWithIndex
+      .map( { case (distance, keySize) => (distance, keySize + 1) } )
+      .sortBy(_._1)
+  }
+
+  def normalizedHammingDistanceForKeySize(xs: Seq[Byte], keySize: Int) = {
+    val grouped = xs.grouped(keySize).toArray.dropRight(1)
+      // ez hack to drop non-`keySize` subcomponents of xs
+    (grouped.init zip grouped.tail).map(tup(hammingDistance(_, _))).reduce(_ + _) / (grouped.length - 1.0) / keySize
   }
 
-  def findBestSingleByteKey(ciphertext: Seq[Byte]): Byte =
+  def crackForMultiByteKey(ciphertext: Seq[Byte], inspectSet: Seq[Int] = Seq()): String =
+    decryptToAscii(ciphertext)(findBestMultiByteKey(ciphertext, inspectSet))
+
+  def findBestMultiByteKey(xs: Seq[Byte], inspectSet: Seq[Int] = Seq()): Seq[Byte] =
+    continuous(findBestMultiByteKeyOfSize(inferKeySize(xs))(xs, inspectSet))
+/*
+  def crackForKeySize(xs: Seq[Byte], keySize: Int): String = {
+    (findBestMultiByteKeyOfSize(keySize) _ :| continuous _ :| decryptToAscii(xs) _)(xs)
+  }
+*/
+  def decrypt(ciphertext: Seq[Byte])(key: Seq[Byte]): Seq[Byte] =
+    ciphertext xor key
+
+  def decryptToAscii(ciphertext: Seq[Byte])(key: Seq[Byte]): String =
+    decrypt(ciphertext)(key).asAscii
+
+    // TODO: make an xor key a proper type.
+  def decryptToAsciiSingleByteKey(ciphertext: Seq[Byte])(key: Byte): String =
+    decryptToAscii(ciphertext)(Stream.continually(key))
+
+  def tryBestDecrypt(ciphertext: Seq[Byte]): Seq[Byte] = {
+    (findBestSingleByteKey _ :| { x => Stream.continually(x) } :| decrypt(ciphertext) _)(ciphertext)
+  }
+
+  def tryBestDecryptToText: Seq[Byte] => String =
+    tryBestDecrypt _ :| ((_: Seq[Byte]).asAscii)
+
+  def findBestMultiByteKeyOfSize(keySize: Int)(ciphertext: Seq[Byte], inspectSet: Seq[Int] = Seq()): Seq[Byte] = {
+    // inspectSet is the set of key bytes for which we want debugging information
+    ciphertext.grouped(keySize).toSeq.dropRight(1).transpose.zipWithIndex
+      .map { case (byteCiphertext, idx) => {
+        if (inspectSet.contains(idx)) {
+          println("For idx = " + idx)
+          println(findBestSingleByteKeyWithCandidates(byteCiphertext))
+        }
+        findBestSingleByteKey(byteCiphertext)
+      }}
+  }
+
+  def findBestSingleByteKeyWithCandidates(ciphertext: Seq[Byte]): Seq[(Double, String, Byte)] =
+    candidates(ciphertext).sortBy(_._1).map {
+      case (score, key) => (score, decryptToAsciiSingleByteKey(ciphertext)(key.toByte), key.toByte)
+    }
+
+  def findBestSingleByteKey(ciphertext: Seq[Byte]): Byte = {
     candidates(ciphertext)
       .reduceOption( (a: (Double, Int), b: (Double, Int)) =>
         if (a._1 < b._1) a else b
       ).map(_._2.toByte).getOrElse(0.toByte)
+  }
 
   def candidates(ciphertext: Seq[Byte]) =
     (0 until 256)
@@ -30,6 +95,6 @@ object XorDecrypt {
 
   def candidatesAsAscii(ciphertext: Seq[Byte]) =
     candidates(ciphertext).sortBy(_._1).map(x =>
-      new String((ciphertext xor Stream.continually(x._2.toByte)).toArray)
+      decrypt(ciphertext)(Seq(x._2.toByte)).asAscii
     )
 }