3 people like it.

Frequency Tables, Shift Cipher

Solving Ceasar shfit with frequency tables.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
(* Shift cipher aka caesar *)
(* Taken from http://www.paul-abraham.com/CaesarCipher.doc and cleaned up*)
let isAlpha c = System.Char.IsLetter c
       
(* Only do lowers for now *)
let shift n c  = 
  let b = 
    match isAlpha c with
    | true  -> (( int c - 97 + n ) % 26 ) + 97
    | false -> 
      match c with 
      | ' ' -> 32
      | _   -> int c
  char b
                 
let encode xs n = 
  xs |> Seq.map (shift n) 
     |> Seq.toArray
     |> fun e -> new string (e)

let findall xs e = 
  seq { for i in xs -> if i = e then 1 else 0 }

let count xs c = 
  findall xs c |> (float << Seq.fold (+) 0)
               
let freqTab word =
  [ for x in 'a'..'z' -> (count word x) ] 
    |> fun count' ->
       count' 
       |> Seq.map (fun c -> 
          c * 100.0 / (count' |> Seq.sum))
        
(* 
 X^2 = sum i=1 .. n * (Oi - Ei)^2 / Ei
 Where:
  X^2 - is the test statistic that asymptotically approaches a x 2 (Chi) distribution. 
  Oi  - an observed frequency
  Ei  - an expected (theoretical) frequency, asserted by the null hypothesis.
  n   - the number of possible outcomes of each event. 
*)

let chisqr (a : float seq) (b : float seq) =
  Seq.zip a b           
  |> Seq.map (fun (Oi,Ei) -> (Oi - Ei) * (Oi - Ei) / Ei)
  |> Seq.sum
  
let freqTable = [ 8.2; 1.5; 2.8; 4.3; 12.7; 2.2; 2.0; 6.1; 0.2;
                  7.0; 0.8; 4.0; 2.4; 6.7;  7.5; 1.9; 0.1; 6.0;
                  6.3; 9.1; 2.8; 1.0; 2.4;  0.2; 2.0; 0.1 ]
     
let crack word =
  let enc k = 
    encode word k
  
  [0..25] 
  |> Seq.map (fun x -> x, chisqr (freqTab (enc x)) freqTable)
  |> Seq.minBy (fun (x,y) -> y)
  |> fst 
  |> enc
  
(* Tests *)
> let test = encode "hello how are you?" 3;;
val test : string = "khoor krz duh brx?"

> crack test;;
val it : string = "hello how are you?"
val isAlpha : c:char -> bool

Full name: Script.isAlpha
val c : char
namespace System
type Char =
  struct
    member CompareTo : value:obj -> int + 1 overload
    member Equals : obj:obj -> bool + 1 overload
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> TypeCode
    member ToString : unit -> string + 1 overload
    static val MaxValue : char
    static val MinValue : char
    static member ConvertFromUtf32 : utf32:int -> string
    static member ConvertToUtf32 : highSurrogate:char * lowSurrogate:char -> int + 1 overload
    static member GetNumericValue : c:char -> float + 1 overload
    ...
  end

Full name: System.Char
System.Char.IsLetter(c: char) : bool
System.Char.IsLetter(s: string, index: int) : bool
val shift : n:int -> c:char -> char

Full name: Script.shift
val n : int
val b : int
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
Multiple items
val char : value:'T -> char (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.char

--------------------
type char = System.Char

Full name: Microsoft.FSharp.Core.char
val encode : xs:seq<char> -> n:int -> string

Full name: Script.encode
val xs : seq<char>
module Seq

from Microsoft.FSharp.Collections
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map
val toArray : source:seq<'T> -> 'T []

Full name: Microsoft.FSharp.Collections.Seq.toArray
val e : char []
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string
val findall : xs:seq<'a> -> e:'a -> seq<int> (requires equality)

Full name: Script.findall
val xs : seq<'a> (requires equality)
val e : 'a (requires equality)
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val i : 'a (requires equality)
val count : xs:seq<'a> -> c:'a -> float (requires equality)

Full name: Script.count
val c : 'a (requires equality)
Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = System.Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>
val fold : folder:('State -> 'T -> 'State) -> state:'State -> source:seq<'T> -> 'State

Full name: Microsoft.FSharp.Collections.Seq.fold
val freqTab : word:seq<char> -> seq<float>

Full name: Script.freqTab
val word : seq<char>
val x : char
val count' : float list
val c : float
val sum : source:seq<'T> -> 'T (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.Seq.sum
val chisqr : a:seq<float> -> b:seq<float> -> float

Full name: Script.chisqr
val a : seq<float>
val b : seq<float>
val zip : source1:seq<'T1> -> source2:seq<'T2> -> seq<'T1 * 'T2>

Full name: Microsoft.FSharp.Collections.Seq.zip
val Oi : float
val Ei : float
val freqTable : float list

Full name: Script.freqTable
val crack : word:seq<char> -> string

Full name: Script.crack
val enc : (int -> string)
val k : int
val x : int
val minBy : projection:('T -> 'U) -> source:seq<'T> -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.Seq.minBy
val y : float
val fst : tuple:('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst
Next Version Raw view Test code New version

More information

Link:http://fssnip.net/aA
Posted:10 years ago
Author:David Klein
Tags: classic ciphers , frequency table