diff options
| -rw-r--r-- | data/6.txt | 64 | ||||
| -rw-r--r-- | src/solvers/Challenge4.scala | 2 | ||||
| -rw-r--r-- | src/solvers/Challenge6.scala | 110 | ||||
| -rw-r--r-- | src/solvers/XorDecrypt.scala | 79 | ||||
| -rw-r--r-- | test/StreamUtilsSpec.scala | 38 |
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) + ) + ) + + } + + } + + } + +} |