diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/solvers/Challenge4.scala | 2 | ||||
| -rw-r--r-- | src/solvers/Challenge6.scala | 110 | ||||
| -rw-r--r-- | src/solvers/XorDecrypt.scala | 79 |
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 ) } |