Challenge 6

5 files changed, 285 insertions, 8 deletions

diff --git a/data/6.txt b/data/6.txt
new file mode 100644
index 0000000..cecdb81
--- /dev/null
+++ b/data/6.txt
@@ -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=
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
     )
 }
diff --git a/test/StreamUtilsSpec.scala b/test/StreamUtilsSpec.scala
new file mode 100644
index 0000000..b9a710c
--- /dev/null
+++ b/test/StreamUtilsSpec.scala
@@ -0,0 +1,38 @@
+package ixee.cryptopals.test
+
+import com.ixee.IxeeSpec
+import ixee.cryptopals.utils.StreamUtils
+
+class StreamUtilsSpec extends IxeeSpec {
+
+  "StreamUtils" - {
+
+    ".fromSeq" - {
+      "is better written as xs.to[Stream]" in { }
+/*
+      "streams the given Seq's elements non-cyclically" in {
+
+        StreamUtils.fromSeq(Seq(1, 2, 3)) mustBe
+          (1 #:: 2 #:: 3 #:: Stream.empty)
+
+      }
+*/
+    }
+
+    ".continuous" - {
+
+      "streams the given Seq's elements cyclically" in {
+
+        assert(
+          StreamUtils.continuous(Seq(1, 2)).startsWith(
+            Seq(1, 2, 1, 2)
+          )
+        )
+
+      }
+
+    }
+
+  }
+
+}