Solving a puzzle posed years ago.

cryptocracker.gs

uses java.util.ArrayList
uses java.lang.Integer
uses java.lang.StringBuilder
uses java.util.Map
uses java.lang.Double
uses java.lang.Character
uses java.util.Iterator

uses java.util.HashMap
uses java.util.Collection
uses java.util.LinkedList
uses java.lang.Math

static class MapWithDefault<T,F> implements java.util.Map<T,F> {
  delegate actual represents Map<T,F>
  var deefault : F
  construct(underlying : Map<T,F>, defaultvalue : F) {
    actual = underlying
    deefault = defaultvalue
  }
  override function get(k : T) : F {
    if(actual.containsKey(k)) return actual.get(k)
    else return deefault
  }
  function get(k : T, defaultvalue : F) : F {
    if(actual.containsKey(k)) return actual.get(k)
    else return defaultvalue
  }
}

static class Maperator<T,F> implements Iterator<F> {
  var underlying : Iterator<T>
  var transform : block(item:T):F
  construct(source : Iterator<T>, operation(item:T):F) {
    underlying = source
    transform = operation
  }
  override function hasNext() : boolean { return underlying.hasNext() }
  override function next() : F { return transform(underlying.next()) }
  override function remove() { underlying.remove() }
}

static class Pair<F,S> {
  var f : F as First
  var s : S as Second
  construct(irst : F, econd : S) {
    f = irst
    s = econd // lol
  }
  public static function make<P,Q>(irst : P, econd : Q) : Pair<P,Q> {
    return new Pair<P,Q>(irst, econd)
  }
}

static class RoundRobinIterator<T> implements Iterator<T> {
  var count : int
  var items : List<T>
  construct(data : List<T>) {
    items = data
    count = -1
  }
  override function hasNext() : boolean { return items.HasElements }
  override function next() : T { count += 1; return items[count % items.Count] }
  override function remove() { items.remove(count % items.Count) }
}


function wrap(text : String, width : int) : String {
  var buffer = new StringBuilder(text)
  var i = width
  while(i < buffer.length()) {
    while(buffer.substring(i, i+1).Alphanumeric) {
      i -= 1
    }
    buffer.replace(i, i+1, "\n")
    i += width
  }
  return buffer.toString()
}

var englishfrequencies : Map<Character,Double> = {
  'e' -> 0.1249,
  't' -> 0.0928,
  'a' -> 0.0804,
  'o' -> 0.0764,
  'i' -> 0.0757,
  'n' -> 0.0723,
  's' -> 0.0651,
  'r' -> 0.0628,
  'h' -> 0.0505,
  'l' -> 0.0407,
  'd' -> 0.0382,
  'c' -> 0.0334,
  'u' -> 0.0273,
  'm' -> 0.0251,
  'f' -> 0.0240,
  'p' -> 0.0214,
  'g' -> 0.0187,
  'w' -> 0.0168,
  'y' -> 0.0166,
  'b' -> 0.0148,
  'v' -> 0.0105,
  'k' -> 0.0054,
  'x' -> 0.0023,
  'j' -> 0.0016,
  'q' -> 0.0012,
  'z' -> 0.0009
}

function frequencycount(sample : String, length : Integer = null) : Map<Character, Double> {
  if(length == null) length = sample.length
  return sample.toCharArray().toList().partition(\letter -> letter).mapValues(\group -> group.Count as double / length)
}

function compareFrequencies(sample : Map<Character, Double>, reference : Map<Character,Double>) : double {
  var deviation = 0.0
  for(letter in sample.Keys) deviation += Math.abs((sample[letter] - reference.get(letter)) / sample[letter])
  return deviation / sample.Count
}

function differenceFromEnglish(sample : String) : double {
  var sampleFrequency = frequencycount(sample)
  return compareFrequencies(sampleFrequency, englishfrequencies)
}


var englishdigraphs : Map<String,Double> = {
  "th" -> 0.0356,
  "he" -> 0.0307,
  "in" -> 0.0243,
  "er" -> 0.0205,
  "an" -> 0.0199,
  "re" -> 0.0185,
  "on" -> 0.0176,
  "at" -> 0.0149,
  "en" -> 0.0145,
  "nd" -> 0.0135,
  "ti" -> 0.0134,
  "es" -> 0.0134,
  "or" -> 0.0128,
  "te" -> 0.0120,
  "of" -> 0.0117,
  "ed" -> 0.0117,
  "is" -> 0.0113,
  "it" -> 0.0112,
  "al" -> 0.0109,
  "ar" -> 0.0107,
  "st" -> 0.0105,
  "to" -> 0.0104,
  "nt" -> 0.0104,
  "ng" -> 0.0095,
  "se" -> 0.0093,
  "ha" -> 0.0093,
  "as" -> 0.0087,
  "ou" -> 0.0087,
  "io" -> 0.0083,
  "le" -> 0.0083,
  "ve" -> 0.0083,
  "co" -> 0.0079,
  "me" -> 0.0079,
  "de" -> 0.0076,
  "hi" -> 0.0076,
  "ri" -> 0.0073,
  "ro" -> 0.0073,
  "ic" -> 0.0070,
  "ne" -> 0.0069,
  "ea" -> 0.0069,
  "ra" -> 0.0069,
  "ce" -> 0.0065,
  "li" -> 0.0062,
  "ch" -> 0.0060,
  "ll" -> 0.0058,
  "be" -> 0.0058,
  "ma" -> 0.0057,
  "si" -> 0.0055,
  "om" -> 0.0055,
  "ur" -> 0.0054
}
englishdigraphs = new MapWithDefault<String, Double>(englishdigraphs, 0.0)

function ngramCount(text : String, length : int) : Map<String,Integer> {
  var graphs = new HashMap<String, Integer>()
  var index = length
  while(index < text.length) {
    var graph = text.substring(index-length, index)
    if(not graphs.containsKey(graph)) {
      graphs[graph] = 0
    }
    graphs[graph] += 1
    index += 1
  }
  return graphs
}

var a_index : int = 0
function ctoi(letter : char) : int {
  return letter - 'a' - a_index
}
function stoi(letter : String) : int {
  return letter.charAt(0) - 'a' + a_index
}
function itoc(value : int) : char {
  return ((((value - a_index) % 26 + 26) % 26) + 'a') as char
}
function itos(value : int) : String {
  return ((((value - a_index) % 26 + 26) % 26) + 'a') as char as String
}

function applyi(text : String, transform(letter:int):int) : String {
  return text.toCharArray().toList().map(\letter -> itoc(transform(ctoi(letter)))).join("")
}

function applyc(text : String, transform(letter:char):char) : String {
  return text.toCharArray().toList().map(\letter -> transform(letter)).join("")
}

var caesar = \text:String,key:int -> applyi(text, \n -> n+key)
var affine = \a:int,b:int -> \text:String -> applyi(text, \n -> a*n+b)
//var power = \text:String,pow:int -> apply(text, \n -> Math.pow(n,pow) as int)

function vigenere(text : String, key : String) : String {
  var output = new StringBuilder()
  for(letter in text index i) {
    output.append(caesar(letter, key.charAt(i%key.length) - 'a'))
  }
  return output.toString()
}

function crackCaesar(cipher : String) : Pair<Integer, Double> {
  cipher = cipher.replaceAll(" ", "")
  var encryptKey = 0
  var closest = 999.9
  for(key in 0..25) {
    var test = caesar(cipher, key)
    var difference = differenceFromEnglish(test)
    //print("${crack}: ${difference}%")
    if(difference < closest) {
      closest = difference
      encryptKey = key
    }
  }
  return Pair.make(encryptKey, closest)
}

function caesarSalad(text : String) {
  for(key in 0..25) {
    print(caesar(text, key))
  }
}
function findWords(text : String) : String {
  var template = new StringBuilder()
  
  for(i in 0..|text.length) {
    var ch = text.charAt(i)
    if(Character.isLetter(ch)) {
      if(Character.isUpperCase(ch)) {
        template.append(0 as char)
      } else {
        template.append(1 as char)
      }
    } else {
      template.append(ch)
    }
  }
  
  return template.toString()
}
function despace(text : String) : String {
  return text.replaceAll("[^a-zA-Z]", "")
}
function respace(text : String, template : String) : String {
  var text_i = 0
  var result = new StringBuilder()
  for(template_i in 0..|template.length()) {
    var ch = template.charAt(template_i)
    if(ch == 0) {
      result.append(Character.toUpperCase(text.charAt(text_i)))
      text_i += 1
    } else if(ch == 1) {
      result.append(Character.toLowerCase(text.charAt(text_i)))
      text_i += 1
    } else {
      result.append(ch)
    }
  }
  if(text_i < text.length - 1) result.append(text.substring(text_i, text.length))
  
  return result.toString()
}

function decompose(text : String, ways : int) : List<String> {
  var stripes = (1..ways).map(\n -> new ArrayList<String>())
  for(letter in text index i) {
    stripes[i % ways].add(letter)
  }
  return stripes.map(\stripe -> stripe.join(""))
}

function getLetters(text : String) : Iterator<String> {
  return new Maperator<Integer, String>((0..|text.length).iterator(), \n -> text.substring(n, n+1))
}

function recompose(stripes : List<String>) : String {
  var sources = new RoundRobinIterator<Iterator<String>>(stripes.map(\letters -> getLetters(letters)))
  var output = new StringBuilder()
  for(stripe in sources) {
    if(stripe.hasNext()) {
      output.append(stripe.next())
    } else {
      sources.remove()
      }
  }
  return output.toString()
}

function crackVigenere(cipher : String, minLength : int, maxLength : int) : Pair<String,String> {
  var lowestScore : double = 999.9 // probably higher than any real result
  var bestMatch : String
  var originalKey : String
  
  for(keylength in minLength..maxLength) {
    //print("key length ${keylength} / ${maxlength}") /////
    var key = new ArrayList<String>()
  
    var stripes = new ArrayList<String>()
    for(stripe in decompose(cipher, keylength)) {
      var result = crackCaesar(stripe)
      key.add((result.First + 'a') as Character)
      stripes.add(caesar(stripe, result.First))
      //print(result.Second) /////
    }
    
    var cracked = recompose(stripes)
    
    var keytext = key.join("")
    var encryptKey = affine(-1, 0)(keytext)
    //print("encrypt key: ${encryptKey}") /////
    //print("decrypt key: ${keytext}") ////
    //print("cracked: ${cracked}") /////
    
    var score = differenceFromEnglish(cracked)
    //print("frequency score: ${score}") ////
    if(score < lowestScore) {
      lowestScore = score
      bestMatch = cracked
      originalKey = encryptKey
    }
    //print("best key seen: ${originalkey}") ////
    // print("") ////
  }
  
  return Pair.make(bestMatch, originalKey)
}

function naiveAlign<T>(xs : List<T>, ys : List<T>, score(item:T):Double) : Collection<Pair<T,T>> {
  xs = xs.orderBy(score)
  ys = ys.orderBy(score)
  return (0..xs.Count-1).map(\i -> Pair.make(xs[i], ys[i]))
}

function align<T>(xs : List<T>, ys : List<T>, score(item:T):Double) : Collection<Pair<T,T>> {
  xs = xs.orderBy(score).toTypedArray().toList()
  ys = ys.orderBy(score).toTypedArray().toList()
  var matchLengths = \left:List<T>,right:List<T> -> {
    // normalize
    var shorter = left.Count < right.Count ? left  : right
    var longer =  left.Count < right.Count ? right : left
    while(longer.Count > shorter.Count and longer[longer.Count-1] == null) longer.remove(longer.Count-1) // trim
    while(longer.Count > shorter.Count) shorter.add(shorter.Count, null) // shim
  }
  var deltasquared = \left:List<T>,right:List<T> -> {
    matchLengths(left, right)
    return (0..left.Count-1)
      .map(\i -> Math.pow((right[i] != null ? score(right[i]) : 0) - (left[i] != null ? score(left[i]) : 0), 2))
      .reduce(0.0, \l,r -> l+r)
  }
  
  var currentdeviation = deltasquared(xs, ys)
  
  /**
   * This isn't actually a correct solution. Alignment needs a dynamic-programming approach,
   * and I don't remember what the implementation looks like right now.
   */
  var testAndMaybeUpdate = \xxs:List<T>,yys:List<T> -> {
    var newdeviation = deltasquared(xxs, yys)
    if(newdeviation < currentdeviation) {
      currentdeviation = newdeviation
      xs = xxs
      ys = yys
    }
  }
  
  for(i in 0..xs.Count) {
    var newxs : List<T>
    var newys : List<T>
    
    newxs = xs.copy()
    newxs.add(i, null)
    testAndMaybeUpdate(newxs, ys)
    
    newys = ys.copy()
    newys.add(i, null)
    testAndMaybeUpdate(xs, newys)
  }
  
  return (0..xs.Count-1).map(\i -> Pair.make(xs[i], ys[i]))
}

function crackMonoalphabetic(cipher : String, crib : Map<Character,Character>) : Map<Character,Character> {
  if(crib == null) crib = {}  
  var frequencies = frequencycount(cipher)//.entrySet().mapToKeyAndValue(\e -> e.Value, \e -> e.Key) // reverse map
  var english = englishfrequencies.copy()
  var mapping = new HashMap<Character,Character>()
  mapping.putAll(crib)
  crib.Keys.each(\letter -> frequencies.remove(letter)) // don't try to align these
  crib.Values.each(\letter -> english.remove(letter)) // remove the targets too
  var aligned = align(frequencies.entrySet().toList(), english.entrySet().toList(), \entry -> entry.Value)
  aligned.removeWhere(\entry -> entry.First == null or entry.Second == null)
  
  //mapping.putAll(aligned.mapToKeyAndValue(\e->e.First.Key, \e->e.Second.Key))
  aligned.each(\p -> mapping.put(p.First.Key, p.First.Key))
  
  return mapping
}

function gcd(x:int, y:int) : int {
  while(x != y) {
    if(x > y) x -= y
    else y -= x
  }
  return x
}

function onetime(text : String, pad : String) : String {
  var i = 0
  return applyc(text, \letter:char -> {
    var out = ((text.charAt(i) - 'a' + pad.charAt(i) - 'a') + 26) % 26 + 'a'
    i+=1
    return out as char
  })
}

function stream(text : String, iv : String) : String {
  // keystream is key+ciphertext
  var key = new LinkedList<Character>(iv.toCharArray().toList())
  var transform = \letter:char -> {
    var out = itoc(ctoi(letter) + ctoi(key.remove()))
    key.add(out)
    
    return out
  }
  return applyc(text, transform)
}

function counter(i:int) : block():int {
  return \-> {var out = i; i+= 1; return out}
}


function twist(torsion : int, offset : int) : block(text:String):String {
  return \text:String -> {
    var clock = counter(0)
    return applyi(text, \letter -> letter + clock()*torsion + offset)
  }
}
//print(twist(1,-1)("aaaaaaa"))

var TCmessage = "tnw fxu wmp pnw rrwt u jxu nmoawvues plkngfy vbwekxqofy rlwx gnw kkraawm rdr wewabjy xw b vrwt mlzdes aw xlfqr jae knjxoo cw oawvqy nwfsp wmp ohhu e bcah ilqvip srwt nnss o dhxa hc tpfw xbmt csy hcaicm d uev d nrfqr wrr dq spf tyq auusc gpf blcz dvox nr v sasq ou hkate a dnx ewmob onw rrwt wlxcvwvy wmp skacs cw rdr wsgses tmp pnw fxu sdr kwmofes lvxr cgfspo owvqqes mnw nvfsp nim gu kmp xcbtm oesrpes mnw rrwt nawvues mu enw fxu dw nhhu ek oj qkxa ckss o uanlmdi aic q nkg ll byxm b asyiewm aogfqr jae nsui oawvqy lsgom bu avsvrl tpf ne fodr jq xeim iqzy yisqim bnaewxes bj rtt pc wfyclk epfw miqhl uu dhui tpfw arxe"
var rocketlauncher = "deployment edit the m high mobility artillery rocket system himars is the light wheeled version of the m multiple launch rocket system mlrs the himars utilizes the same pod as the m mlrs uses a pod can hold six rockets or a single missile the windows are made of glass and layers of sapphire th field artillery brigade airborne at fort bragg north carolina was the initial army test bed unit for the m himars c battery rd battalion th field artillery regiment began field testing himars prototypes in all types of training events and environments in as a residual of the rapid force projection initiative rfpi advanced concept technology demonstration actd in the united states marine corps arranged with the united states army to acquire of the systems fielding began in in july marines from fox battery nd battalion marine regiment from oklahoma city oklahoma were deployed to the al anbar province of iraq this is the first marine unit to use the himars in combat himars was also tested as a common launcher for both artillery rockets and the surfacelaunched variant of the amraam antiaircraft missile singaporeedit as of september the singapore army proposed to acquire himars systems the package includes himars launchers fmtv ton trucks and xm unitary he gmlrs pods plus associated support and communications equipment and services this proposed package is notable for not involving the m unguided mlrs rockets in late singapore took delivery of the first himars firing unit and achieved full operational capability the rd battalion singapore artillery commissioned its himars battery on september it marks the first fully gpsguided himars unit operational historyedit on february the international security assistance force isaf for afghanistan indicated in a press release that it was thought that two rockets fired from a himars unit fell metres short of their intended target and killed civilians during operation moshtarak isaf suspended the use of the himars until a full review of the incident was completed a british officer later said that the rockets were on target that the target was in use by the taliban and use of the system has been reinstated reports indicate that the civilian deaths were due to the talibans use of an occupied dwelling the presence of civilians at that location was not known to the isaf forces an october report in the new york times credited himars with aiding the nato offensive in kandahar by targeting taliban commanders hideouts forcing many to flee to pakistan at least temporarily in november the united states army revealed they had deployed the himars to iraq firing at least rockets at the islamic state since the beginning of summer himars detachments were sent to al asad airbase and altaqaddum air base in anbar province on march army himars systems fired rockets into syria in support of syrian rebels fighting isil for the first time with the launchers based in neighboring jordan in january lockheed announced the himars had reached million operational hours with us forces achieving a percent operational readiness rate on april it was announced that the us would be deploying the himars in turkey near the border with syria as part of the battle with isil in early september international media and the us state department reported a newlydeployed himars systems had engaged isil targets in syria near the turkish border in october himars systems were stationed at qayyarah airfield west some kilometers south of mosul taking part in the battle of mosul"
var shortlauncher = "deployment edit the high mobility artillery rocket system himars is the light wheeled version of the multiple launch rocket system mlrs the himars utilizes the same pod as the mlrs uses a pod can hold six rockets or a single missile the windows are made of glass and layers of sapphire the field artillery brigade airborne at fort bragg north carolina was the initial army test bed unit for the himars battery battalion the field artillery regiment began field testing himars prototypes in all types of training events and environments in as a residual of the rapid force projection initiative rfpi"

var spacetext = TCmessage

var spacewords = findWords(spacetext)
var ciphertext = despace(spacetext)
ciphertext = "tnwfxuwmppnwrrwtujxunmoawvuesplkngfyvbwekxqofyrlwxgnwkkraawmrdrwewabjyxwbvrwtmlzdesawxlfqrjaeknjxoocwoawvqynwfspwmpohhuebcahilqvipsrwtnnssodhxahctpfwxbmtcsyhcaicmduevdnrfqrwrrdqspftyqauuscgpfblczdvoxnrvsasqouhkateadnxewmobonwrrwtwlxcvwvywmpskacscwrdrwsgsestmppnwfxusdrkwmofeslvxrcgfspoowvqqesmnwnvfspnimgukmpxcbtmoesrpesmnwrrwtnawvuesmuenwfxudwnhhuekojqkxackssouanlmdiaicqnkgllbyxmbasyiewmaogfqrjaensuioawvqylsgombuavsvrltpfnefodrjqxeimiqzyyisqimbnaewxesbjrttpcwfyclkepfwmiqhluudhuitpfwarxe"

function show(text:String) {
  text = respace(text, spacewords)
  text = wrap(text, 80)
  print(text)
}

print(spacetext)

print("")
print("")

// not caesar
// not affine?

/*
// not vigenere, probably
var crack = crackVigenere(ciphertext, 2, 15)
print(respace(crack.First, spacewords))
print(crack.Second)
//*/

/*
// frequency and digraphs and trigraphs, oh my
for(length in 1..1) {
  var frequencies = ngramCount(ciphertext, length)
  for(point in frequencies.entrySet().orderByDescending(\entry -> entry.Value)) {
    print("${point.Key}: ${point.Value}")
  }
}
//*/

/*
// not l^n
var powertext = ciphertext
for(foo in 1..10) {
  print(power(powertext, foo))
}
*/

/*
// self-encrypt each letter?
for(n in 0..25) {
  var stretch = affine(2,n)(ciphertext)
  //print(wrap(respace(stretch, spacewords), 80))
  print(respace(stretch, spacewords))
  //print(differenceFromEnglish(stretch))
  //print("")
}
// this looks oddly more real than anything else so far
//*/

/*
// does not appear to be monoalphabetic
var guesses = {
  'w' -> 'e'
}
var translation = crackMonoalphabetic(ciphertext, guesses)
print(translation.entrySet().map(\e -> "${e.Key} ${e.Value}").join("\n"))
print(englishfrequencies.Keys.subtract(translation.Keys).join(" "))
var translated = apply(ciphertext, \letter -> translation.get((letter + 'a') as char, 'x') - 'a')
print(wrap(respace(translated, spacewords), 80))
print("")
//*/

/*
// stream cipher  
for(key in 'a'..'z') {
  show(stream(ciphertext, key as char as String))
  print("")
}
//*/


// finally found it!
// dumping all the single-letter stream keys revealed plaintext along the diagonal
// since each key rotates the resulting text a-la Caesar, the text was revealed one position at a time
// sequentially un-apply the rotation

/*
var solved = twist(1, 0)(stream(ciphertext, "a"))
show(solved)

print("")
print("done")
*/

//for(key in 'a'..'z') print(stream(ciphertext, key as char as String))

var webpuzzle = "u axft rpalg tymh dytyaiju nffvlag tmb knrd ys, l'ie ymr pbmvzhv bf gmfdaozm oqq emqb bbu tmb qbw jqbvr tymh."
var webwords = findWords(webpuzzle)
var webtext = despace(webpuzzle)
var crack = crackVigenere(webtext, 1, 10) // real texts aren't decisive enough for this to work completely unaided
print(respace(crack.First, webwords))
print(crack.Second)

print(respace(vigenere(webtext, affine(-1,0)("modnar")), webwords))