summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/solvers/Challenge4.scala29
-rw-r--r--src/solvers/XorDecrypt.scala12
-rw-r--r--src/utils/ByteUtils.scala2
-rw-r--r--src/utils/ConversionUtils.scala4
-rw-r--r--src/utils/FrequencyMap.scala29
-rw-r--r--src/utils/FunctionUtils.scala10
6 files changed, 65 insertions, 21 deletions
diff --git a/src/solvers/Challenge4.scala b/src/solvers/Challenge4.scala
new file mode 100644
index 0000000..f71f6c0
--- /dev/null
+++ b/src/solvers/Challenge4.scala
@@ -0,0 +1,29 @@
+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._
+
+object Challenge4 {
+ def findSingleCharacterXor(strings: Seq[Seq[Byte]]): (String, Int) = {
+ strings
+ .map(XorDecrypt.findBestSingleByteKey)
+ .zip(strings)
+ .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 { pair => (pair._1, TextScorer.score(pair._1.asBytes), pair._2) }
+ .sortBy(_._2)
+ .map { triplet => (triplet._1, triplet._3) }
+ .head
+ }
+
+ def run(inputFile: String) = {
+ findSingleCharacterXor(
+ Source.fromFile(inputFile).getLines().toSeq.map(hexStr2Bytes(_))
+ )
+ }
+}
diff --git a/src/solvers/XorDecrypt.scala b/src/solvers/XorDecrypt.scala
index b7f7c43..6b82c34 100644
--- a/src/solvers/XorDecrypt.scala
+++ b/src/solvers/XorDecrypt.scala
@@ -2,18 +2,24 @@ package ixee.cryptopals.solvers
import ixee.cryptopals.utils._
import ixee.cryptopals.utils.ByteUtils._
+import ixee.cryptopals.utils.FunctionUtils._
object XorDecrypt {
implicit val freq = Frequencies.cornell40kSample
- def tryBestDecrypt(ciphertext: Seq[Byte]) = {
- val key = findBestSingleByteKey(ciphertext)
+ def decryptToAscii(ciphertext: Seq[Byte])(key: Byte): String = {
new String((ciphertext xor Stream.continually(key)).toArray)
}
+ def tryBestDecrypt(ciphertext: Seq[Byte]): String = {
+ (findBestSingleByteKey _ :| decryptToAscii(ciphertext) _)(ciphertext)
+ }
+
def findBestSingleByteKey(ciphertext: Seq[Byte]): Byte =
candidates(ciphertext)
- .minBy(_._1)._2.toByte
+ .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)
diff --git a/src/utils/ByteUtils.scala b/src/utils/ByteUtils.scala
index ffc2e20..2c51917 100644
--- a/src/utils/ByteUtils.scala
+++ b/src/utils/ByteUtils.scala
@@ -1,6 +1,6 @@
package ixee.cryptopals.utils
-import ConversionUtils.tup
+import FunctionUtils.tup
object ByteUtils {
trait SizedNumeric[T] {
diff --git a/src/utils/ConversionUtils.scala b/src/utils/ConversionUtils.scala
index 09f3aab..f8935f2 100644
--- a/src/utils/ConversionUtils.scala
+++ b/src/utils/ConversionUtils.scala
@@ -1,6 +1,7 @@
package ixee.cryptopals.utils
import ByteUtils._
+import FunctionUtils._
object ConversionUtils {
def hexStr2Bytes(s: String): Seq[Byte] =
@@ -61,9 +62,6 @@ object ConversionUtils {
def asBytes = s.toSeq.map(_.toByte)
}
- // Because doing (_ f _).tupled confuses the inferencer...
- def tup[A, B, C](f: (A, B) => C): ((A, B)) => C = f.tupled
-
// TODO: tailrec this, get rid of for
def toByteSeq[T : SizedNumeric : BitOps](x: T): Seq[Byte] = {
val buf = new Array[Byte](x.byteSize)
diff --git a/src/utils/FrequencyMap.scala b/src/utils/FrequencyMap.scala
index 0bea25c..fffdabe 100644
--- a/src/utils/FrequencyMap.scala
+++ b/src/utils/FrequencyMap.scala
@@ -1,6 +1,6 @@
package ixee.cryptopals.utils
-import ConversionUtils.tup
+import FunctionUtils.tup
class FrequencyMap(mapargs: Map[Char, Double]) {
sealed trait DiffResult
@@ -14,7 +14,7 @@ class FrequencyMap(mapargs: Map[Char, Double]) {
if (c.isLower)
mappings.get(c)
else // TODO remove the bias here
- mappings.get(c.toLower).map(_ * 0.002) // bias HARD against uppercase spam. should make this a per-map setting.
+ mappings.get(c.toLower).map(_ * 0.0002) // bias HARD against uppercase spam. should make this a per-map setting.
def diff(other: FrequencyMap): Double = {
// pseudoscience here
@@ -36,29 +36,30 @@ class FrequencyMap(mapargs: Map[Char, Double]) {
// TODO: don't hardcode these..
def diffAt(c: Char, charFreq: Double) =
- c match {
- case ' ' => 0
- case '{' | '}' | '`' | '|' =>
+ Math.pow(c match {
+ case ' ' =>
+ squared(0.10 - charFreq)
+ case '{' | '}' | '`' | '|' | '^' =>
squared(0.000001 - charFreq) // { } | and ` are very unlikely irl
case '[' | ']' =>
- squared(0.000002 - charFreq) // [ ] are more likely
- case '"' | '\''=>
+ squared(0.0000015 - charFreq) // [ ] are more likely
+ case '"' | '\'' =>
squared(0.00001 - charFreq) // " or ' are 100% unlikely 90% of the time
case '~' | '+' | '=' | '<' | '>' | '/' | '\\' =>
- squared(0.000004 - charFreq) // math is weird kids
+ squared(0.00000175 - charFreq) // math is weird kids
case ';' | ':' | '-' | '*' | '(' | '&' | ')' | '_' =>
- squared(0.000009 - charFreq) // getting into more common punctuation
+ squared(0.000003 - charFreq) // getting into more common punctuation
case '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' =>
- squared(0.00001 - charFreq) // numbers are KINDA uncommon
+ squared(0.000002 - charFreq) // numbers are KINDA uncommon
case '$' | '%' | '#' | '@' | '!' =>
- squared(0.00003 - charFreq) // more punctuation...
+ squared(0.00002 - charFreq) // more punctuation...
case '.' | ',' =>
squared(0.00007 - charFreq) // and the last of the punctuations
case '\n' | '\r' =>
- squared(0.0000002 - charFreq) // explicit \r \n is rare in freeform text.
+ squared(0.000001 - charFreq) // explicit \r \n is rare in freeform text.
case _ =>
- this.at(c).map(_ - charFreq).map(squared).getOrElse(0.0)
- }
+ this.at(c).map(_ - charFreq).map(squared).getOrElse(0.4)
+ }, 0.5)
def squared(x: Double) = x * x
diff --git a/src/utils/FunctionUtils.scala b/src/utils/FunctionUtils.scala
new file mode 100644
index 0000000..84c141b
--- /dev/null
+++ b/src/utils/FunctionUtils.scala
@@ -0,0 +1,10 @@
+package ixee.cryptopals.utils
+
+object FunctionUtils {
+ // Because doing (_ f _).tupled confuses the inferencer...
+ def tup[A, B, C](f: (A, B) => C): ((A, B)) => C = f.tupled
+
+ implicit class Compositor[A, B](f: A => B) {
+ def :|[C](g: B => C): A => C = f.andThen(g)
+ }
+}