summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/solvers/Challenge4.scala2
-rw-r--r--src/solvers/Challenge6.scala110
-rw-r--r--src/solvers/XorDecrypt.scala79
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
)
}