Last active
April 5, 2018 21:00
-
-
Save geofrey/c44a026c9fdfa4828fdd7d2502f3c251 to your computer and use it in GitHub Desktop.
Solving a puzzle posed years ago.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment