From 91b4cfc801b7c156c231ca60aba69a8d171e9226 Mon Sep 17 00:00:00 2001
From: iximeow <me@iximeow.net>
Date: Wed, 26 Nov 2014 18:10:58 -0800
Subject: Challenge 8, 9

---
 src/solvers/Challenge8.scala    | 43 +++++++++++++++++++++++++++++++++++++++++
 src/solvers/XorDecrypt.scala    |  4 ++--
 src/utils/ByteUtils.scala       |  3 +++
 src/utils/ConversionUtils.scala |  2 +-
 src/utils/CryptoUtils.scala     | 10 ++++++++++
 src/utils/StreamUtils.scala     |  5 +++++
 6 files changed, 64 insertions(+), 3 deletions(-)
 create mode 100644 src/solvers/Challenge8.scala
 create mode 100644 src/utils/CryptoUtils.scala

(limited to 'src')

diff --git a/src/solvers/Challenge8.scala b/src/solvers/Challenge8.scala
new file mode 100644
index 0000000..5247075
--- /dev/null
+++ b/src/solvers/Challenge8.scala
@@ -0,0 +1,43 @@
+package ixee.cryptopals.solvers
+
+import scala.io.Source
+import ixee.cryptopals.utils.ByteUtils._
+import ixee.cryptopals.utils.StreamUtils._
+import ixee.cryptopals.utils.ConversionUtils._
+import ixee.cryptopals.utils.FunctionUtils._
+import ixee.cryptopals.utils._
+import io.github.marklister.base64.Base64._
+import javax.crypto.Cipher
+import javax.crypto.spec.SecretKeySpec
+
+object Challenge8 {
+  val path = "./data/8.txt"
+
+  lazy val ciphertext =
+    Source
+      .fromFile(path)
+      .getLines()
+      .toSeq
+      .map(hexStr2Bytes)
+      //.mkString
+      //.toByteArray
+
+  def run = {
+    ciphertext
+      .zipWithIndex
+      .map(x => (x._1.grouped(16).toStream, x._2 + 1)) // 
+      // this might be decent, line #133 is #2 under this metric
+      // .map(x => (avgHammingDistance(x._1), x._2)).sortBy(_._1)
+      /*
+       * but looking for actual duplicate data is better:
+       * line 133 is #1 with six duplicate blocks,
+       * old #1 of 177 has 0 duplicate blocks.
+       */
+      .map(x => (dupBlocks(x._1), x._2)).sortBy(_._1 * -1)
+      .head
+      ._2
+  }
+
+  def dupBlocks(xs: Seq[Seq[Byte]]) =
+    pairsOf(xs).map(tup(_ == _)).count(_ == true)
+}
diff --git a/src/solvers/XorDecrypt.scala b/src/solvers/XorDecrypt.scala
index 83fa923..1a28637 100644
--- a/src/solvers/XorDecrypt.scala
+++ b/src/solvers/XorDecrypt.scala
@@ -30,7 +30,7 @@ object XorDecrypt {
   }
 
   def normalizedHammingDistanceForKeySize(xs: Seq[Byte], keySize: Int) = {
-    val grouped = xs.grouped(keySize).toArray.dropRight(1)
+    val grouped = xs.grouped(keySize).toArray.init
       // ez hack to drop non-`keySize` subcomponents of xs
     (grouped.init zip grouped.tail).map(tup(hammingDistance(_, _))).reduce(_ + _) / (grouped.length - 1.0) / keySize
   }
@@ -64,7 +64,7 @@ object XorDecrypt {
 
   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
+    ciphertext.grouped(keySize).toSeq.init.transpose.zipWithIndex
       .map { case (byteCiphertext, idx) => {
         if (inspectSet.contains(idx)) {
           println("For idx = " + idx)
diff --git a/src/utils/ByteUtils.scala b/src/utils/ByteUtils.scala
index 18942c0..723164d 100644
--- a/src/utils/ByteUtils.scala
+++ b/src/utils/ByteUtils.scala
@@ -108,4 +108,7 @@ object ByteUtils {
 
   def hammingDistance[T : BitOps : SizedNumeric](a: Seq[T], b: Seq[T]): Int =
     (a xor b).map(_.bitsSet).reduce(_ @+ _)
+
+  def avgHammingDistance[T : BitOps : SizedNumeric](xs: Seq[Seq[T]]): Double =
+    xs.sliding(2).map({ case Stream(a: Seq[T], b: Seq[T]) => hammingDistance(a, b) }).reduce(_ @+ _) / xs.length.toDouble
 }
diff --git a/src/utils/ConversionUtils.scala b/src/utils/ConversionUtils.scala
index 95d08ce..ec3f813 100644
--- a/src/utils/ConversionUtils.scala
+++ b/src/utils/ConversionUtils.scala
@@ -5,7 +5,7 @@ import FunctionUtils._
 
 object ConversionUtils {
   def hexStr2Bytes(s: String): Seq[Byte] =
-    padToByte(s).grouped(2).map(byteStr2Byte).toSeq
+    padToByte(s).grouped(2).map(byteStr2Byte).toStream.force
 
   def byteStr2Byte(str: String): Byte =
     charSeq2Byte(str.toSeq)
diff --git a/src/utils/CryptoUtils.scala b/src/utils/CryptoUtils.scala
new file mode 100644
index 0000000..5418895
--- /dev/null
+++ b/src/utils/CryptoUtils.scala
@@ -0,0 +1,10 @@
+package ixee.cryptopals.utils
+
+object CryptoUtils {
+
+  def pkcs7pad(s: String, blockSize: Int) = {
+    val padLength = blockSize - (s.length % blockSize)
+    s + s"${padLength.toChar}" * padLength
+  }
+
+}
diff --git a/src/utils/StreamUtils.scala b/src/utils/StreamUtils.scala
index 4f803c0..be5246c 100644
--- a/src/utils/StreamUtils.scala
+++ b/src/utils/StreamUtils.scala
@@ -17,6 +17,11 @@ object StreamUtils {
   def continuous[A](xs: Seq[A]): Stream[A] =
     xs.to[Stream] append continuous(xs.to[Stream])
 
+  def pairsOf[A](xs: Seq[A]): Seq[(A, A)] =
+    (xs.init zip xs.tail.tails.toSeq) flatMap { case (elem, rest) =>
+      rest zip Stream.continually(elem)
+    }
+
 /*
   // Or just xs.to[Stream] ...
   def fromSeq[A](xs: Seq[A]): Stream[A] =
-- 
cgit v1.1