ADFGVX cipher

ADFGVX cipher is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Description

The ADFGVX cipher was a manually applied field cipher used by the German Army during World War I. It was broken in 1918 by the French cryptanalyst Georges Painvin.

The workings of the cipher are described in the Wikipedia article, linked to above, and so will not be repeated here.

Task

Write routines, functions etc. in your language to:

1. Encrypt suitable plaintext and decrypt the resulting cipher text using the ADFGVX cipher algorithm given a Polybius square (see 2. below) and a suitable key. For this purpose suitable means text consisting solely of ASCII upper case letters or digits.

2. Create a 6 x 6 Polybius square using a random combination of the letters A to Z and the digits 0 to 9 and then display it.

3. Given the number of letters (between 7 and 12 say) to use, create a key by selecting a suitable word at random from unixdict.txt and then display it. The word selected should be such that none of its characters are repeated.

Use these routines to create a Polybius square and a 9 letter key.

These should then be used to encrypt the plaintext: ATTACKAT1200AM and decrypt the resulting cipher text. Display here the results of both operations.

Go

Translation of: Wren

<lang go>package main

import (

   "bytes"
   "fmt"
   "io/ioutil"
   "log"
   "math/rand"
   "sort"
   "strings"
   "time"

)

var adfgvx = "ADFGVX" var alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

func distinct(bs []byte) []byte {

   var u []byte
   for _, b := range bs {
       if !bytes.Contains(u, []byte{b}) {
           u = append(u, b)
       }
   }
   return u

}

func allAsciiAlphaNum(word []byte) bool {

   for _, b := range word {
       if !((b >= 48 && b <= 57) || (b >= 65 && b <= 90) || (b >= 97 && b <= 122)) {
           return false
       }
   }
   return true

}

func orderKey(key string) []int {

   temp := make([][2]byte, len(key))
   for i := 0; i < len(key); i++ {
       temp[i] = [2]byte{key[i], byte(i)}
   }
   sort.Slice(temp, func(i, j int) bool { return temp[i][0] < temp[j][0] })
   res := make([]int, len(key))
   for i := 0; i < len(key); i++ {
       res[i] = int(temp[i][1])
   }
   return res

}

func createPolybius() []string {

   temp := []byte(alphabet)
   rand.Shuffle(36, func(i, j int) {
       temp[i], temp[j] = temp[j], temp[i]
   })
   alphabet = string(temp)
   fmt.Println("6 x 6 Polybius square:\n")
   fmt.Println("  | A D F G V X")
   fmt.Println("---------------")
   p := make([]string, 6)
   for i := 0; i < 6; i++ {
       fmt.Printf("%c | ", adfgvx[i])
       p[i] = alphabet[6*i : 6*(i+1)]
       for _, c := range p[i] {
           fmt.Printf("%c ", c)
       }
       fmt.Println()
   }
   return p

}

func createKey(n int) string {

   if n < 7 || n > 12 {
       log.Fatal("Key should be within 7 and 12 letters long.")
   }
   bs, err := ioutil.ReadFile("unixdict.txt")
   if err != nil {
       log.Fatal("Error reading file")
   }
   words := bytes.Split(bs, []byte{'\n'})
   var candidates [][]byte
   for _, word := range words {
       if len(word) == n && len(distinct(word)) == n && allAsciiAlphaNum(word) {
           candidates = append(candidates, word)
       }
   }
   k := string(bytes.ToUpper(candidates[rand.Intn(len(candidates))]))
   fmt.Println("\nThe key is", k)
   return k

}

func encrypt(polybius []string, key, plainText string) string {

   temp := ""

outer:

   for _, ch := range []byte(plainText) {
       for r := 0; r <= 5; r++ {
           for c := 0; c <= 5; c++ {
               if polybius[r][c] == ch {
                   temp += fmt.Sprintf("%c%c", adfgvx[r], adfgvx[c])
                   continue outer
               }
           }
       }
   }
   colLen := len(temp) / len(key)
   // all columns need to be the same length
   if len(temp)%len(key) > 0 {
       colLen++
   }
   table := make([][]string, colLen)
   for i := 0; i < colLen; i++ {
       table[i] = make([]string, len(key))
   }
   for i := 0; i < len(temp); i++ {
       table[i/len(key)][i%len(key)] = string(temp[i])
   }
   order := orderKey(key)
   cols := make([][]string, len(key))
   for i := 0; i < len(key); i++ {
       cols[i] = make([]string, colLen)
       for j := 0; j < colLen; j++ {
           cols[i][j] = table[j][order[i]]
       }
   }
   res := make([]string, len(cols))
   for i := 0; i < len(cols); i++ {
       res[i] = strings.Join(cols[i], "")
   }
   return strings.Join(res, " ")

}

func decrypt(polybius []string, key, cipherText string) string {

   colStrs := strings.Split(cipherText, " ")
   // ensure all columns are same length
   maxColLen := 0
   for _, s := range colStrs {
       if len(s) > maxColLen {
           maxColLen = len(s)
       }
   }
   cols := make([][]string, len(colStrs))
   for i, s := range colStrs {
       var ls []string
       for _, c := range s {
           ls = append(ls, string(c))
       }
       if len(s) < maxColLen {
           cols[i] = make([]string, maxColLen)
           copy(cols[i], ls)
       } else {
           cols[i] = ls
       }
   }
   table := make([][]string, maxColLen)
   order := orderKey(key)
   for i := 0; i < maxColLen; i++ {
       table[i] = make([]string, len(key))
       for j := 0; j < len(key); j++ {
           table[i][order[j]] = cols[j][i]
       }
   }
   temp := ""
   for i := 0; i < len(table); i++ {
       temp += strings.Join(table[i], "")
   }
   plainText := ""
   for i := 0; i < len(temp); i += 2 {
       r := strings.IndexByte(adfgvx, temp[i])
       c := strings.IndexByte(adfgvx, temp[i+1])
       plainText = plainText + string(polybius[r][c])
   }
   return plainText

}

func main() {

   rand.Seed(time.Now().UnixNano())
   plainText := "ATTACKAT1200AM"
   polybius := createPolybius()
   key := createKey(9)
   fmt.Println("\nPlaintext :", plainText)
   cipherText := encrypt(polybius, key, plainText)
   fmt.Println("\nEncrypted :", cipherText)
   plainText2 := decrypt(polybius, key, cipherText)
   fmt.Println("\nDecrypted :", plainText2)

}</lang>

Output:

Sample run:

6 x 6 Polybius square:

  | A D F G V X
---------------
A | R W H N I 7 
D | 1 J O 2 P 5 
F | 3 A T 4 M 9 
G | D U L K V 0 
V | Z B E F 6 Q 
X | G Y S 8 C X 

The key is EUCHARIST

Plaintext : ATTACKAT1200AM

Encrypted : FDG FGG FVDV FFX FFF FFX DDD XAF DGG

Decrypted : ATTACKAT1200AM

Nim

Translation of: Wren

It started as a translation, but actually we use a different method, better suited to Nim, to encrypt and decrypt. And there are many other differences. Output is similar though.

<lang Nim>import algorithm, random, sequtils, strutils, sugar, tables

const Adfgvx = "ADFGVX"

type PolybiusSquare = array[6, array[6, char]]

iterator items(p: PolybiusSquare): (int, int, char) =

 ## Yield Polybius square characters preceded by row and column numbers.
 for r in 0..5:
   for c in 0..5:
     yield (r, c, p[r][c])

proc initPolybiusSquare(): PolybiusSquare =

 ## Initialize a 6x6 Polybius square.
 var alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
 alphabet.shuffle()
 for r in 0..5:
   for c in 0..5:
     result[r][c] = alphabet[6 * r + c]

proc createKey(n: Positive): string =

 ## Create a key using a word from "unixdict.txt".
 doAssert n in 7..12, "Key should be within 7 and 12 letters long."
 let candidates = collect(newSeq):
                  for word in "unixdict.txt".lines:
                    if word.len == n and
                       word.deduplicate().len == n and
                       word.allCharsInSet(Letters + Digits): word
 result = candidates[rand(candidates.high)].toUpperAscii

func encrypt(plainText: string; polybius: PolybiusSquare; key: string): string =

 ## Encrypt "plaintext" using the given Polybius square and the given key.

 # Replace characters by row+column letters.
 var str: string
 for ch in plainText:
   for (r, c, val) in polybius:
     if val == ch:
       str.add Adfgvx[r] & Adfgvx[c]

 # Build ordered table of columns and sort it by key value.
 var cols: OrderedTable[char, string]
 for i, ch in str:
   let tkey = key[i mod key.len]
   cols.mgetOrPut(tkey, "").add ch
 cols.sort(cmp)

 # Build cipher text from sorted column table values.
 for s in cols.values:
   result.addSep(" ")
   result.add s

func decrypt(cipherText: string; polybius: PolybiusSquare; key: string): string =

 ## Decrypt "cipherText" using the given Polybius square and the given key.

 # Build list of columns.
 let skey = sorted(key)
 var cols = newSeq[string](key.len)
 var idx = 0
 for col in cipherText.split(' '):
   cols[key.find(skey[idx])] = col
   inc idx

 # Build string of row+column values.
 var str: string
 for i in 0..key.high:
   for col in cols:
     if i < col.len: str.add col[i]

 # Build plain text from row+column values.
 for i in countup(0, str.len - 2, 2):
   let r = Adfgvx.find(str[i])
   let c = Adfgvx.find(str[i+1])
   result.add polybius[r][c]

randomize()

var polybius = initPolybiusSquare() echo "6 x 6 Polybius square:\n" echo " | A D F G V X" echo "---------------" for i, row in polybius:

 echo Adfgvx[i], " | ", row.join(" ")

let key = createKey(9) echo "\nThe key is ", key

const PlainText = "ATTACKAT1200AM" echo "\nPlaintext : ", PlainText

let cipherText = PlainText.encrypt(polybius, key) echo "\nEncrypted : ", cipherText

let plainText = cipherText.decrypt(polybius, key) echo "\nDecrypted : ", plainText</lang>

Output:

6 x 6 Polybius square:

  | A D F G V X
---------------
A | U 1 C N H F
D | E M 4 R S G
F | P I 8 9 6 5
G | X 2 Z B 7 K
V | A 3 Y V O D
X | 0 W Q T J L

The key is PHAGOCYTE

Plaintext : ATTACKAT1200AM

Encrypted : XXX GXA ADD GVA AGD XAX VFGD AAA VGV

Decrypted : ATTACKAT1200AM

Phix

Translation of: Wren

We can make some nice use of the standard builtin routines here, with only a modest amount of whitespace cleanup.

with javascript_semantics
constant ADFGVX = "ADFGVX",
         ALEPH = tagset('Z','A')&tagset('9','0')

function create_polybius()
    string aleph = shuffle(ALEPH)
--  string aleph = "U1CNHFEM4RSGPI8965X2ZB7KA3YVOD0WQTJL"   -- Nim
--  string aleph = "T71VB5HYG2JKIQM8REOPDUNCZ063FXAW9S4L"   -- Wren
--  string aleph = "NA1C3H8TB2OME5WRPD4F6G7I9J0KLQSUVXYZ"   -- wp
    sequence tmp = split(join_by(aleph,1,6," "),'\n')
    printf(1,"6 x 6 Polybius square:\n")
    printf(1,"  | A D F G V X\n")
    printf(1,"---------------\n")
    for i=1 to length(tmp) do
        printf(1,"%s | %s\n",{ADFGVX[i],tmp[i]})
    end for
    return aleph
end function

function lnua(string word, integer n)
    return length(word)==n 
       and length(unique(word))==n
       and length(filter(word,"in",ALEPH))==n
end function

function create_key(integer n)
    assert(n>=7 and n<=12)
    sequence candidates = filter(upper(unix_dict()),lnua,n)
    string res = candidates[rand(length(candidates))]
--  string res = "PHAGOCYTE" -- Nim
--  string res = "SUNFLOWER" -- Wren
--  string res = "PRIVACY" -- wp
    printf(1,"\nThe key is %s\n",{res})
    return res
end function

function encrypt(string polybius, key, plaintext)
    integer l = length(key)
    sequence tags = custom_sort(key,tagset(l)),
             res = ""
    for i=1 to length(plaintext) do
        integer k = find(plaintext[i],polybius)
        if k then   -- (simply ignore any non-alphanum)
            res &= ADFGVX[floor((k-1)/6)+1]&
                   ADFGVX[remainder((k-1),6)+1]
        end if
    end for
    res = substitute(join(columnize(split_by(res,l),tags,' ')),"  "," ")
    return res
end function

function decrypt(string polybius, key, encrypted)
    integer l = length(key)
    sequence tags = custom_sort(key,tagset(l)),
             tmp = columnize(split(encrypted,' '),{},' ')
    tmp = trim(join(apply(true,extract,{tmp,{tags},true}),""))
    string plaintext = ""
    for i=1 to length(tmp) by 2 do
        integer r = find(tmp[i],ADFGVX)-1,
                c = find(tmp[i+1],ADFGVX)
        plaintext &= polybius[r*6+c]
    end for
    return plaintext   
end function

string polybius = create_polybius(),
            key = create_key(9),
       plaintext = "ATTACKAT1200AM",
       encrypted = encrypt(polybius,key,plaintext),
       decrypted = decrypt(polybius,key,encrypted)
printf(1,"\nPlainText : %s\n\nEncrypted : %s\n\nDecrypted : %s\n",
           {plaintext,        encrypted,        decrypted})

Output matches Wren/Nim/wp when the appropriate lines are uncommented.

Wren

Library: Wren-ioutil

Library: Wren-seq

Library: Wren-str

<lang ecmascript>import "random" for Random import "/ioutil" for FileUtil import "/seq" for Lst import "/str" for Char, Str

var rand = Random.new() var adfgvx = "ADFGVX" var alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".toList

var createPolybius = Fn.new {

   rand.shuffle(alphabet)
   var p = Lst.chunks(alphabet, 6)
   System.print("6 x 6 Polybius square:\n")
   System.print("  | A D F G V X")
   System.print("---------------")
   for (i in 0...p.count) {
       System.write("%(adfgvx[i]) | ")
       System.print(p[i].join(" "))
   }
   return p

}

var createKey = Fn.new { |n|

   if (n < 7 || n > 12) Fiber.abort("Key should be within 7 and 12 letters long.")
   var candidates = FileUtil.readLines("unixdict.txt").where { |word| 
       return word.count == n && Lst.distinct(word.toList).count == n &&
              word.all { |ch| Char.isAsciiAlphaNum(ch) }
   }.toList
   var k = Str.upper(candidates[rand.int(candidates.count)])
   System.print("\nThe key is %(k)")
   return k

}

// helper function to sort the key into alphabetical order // and return a list of the original indices of its letters. var orderKey = Fn.new { |key|

   var temp = (0...key.count).map { |i| [key[i], i] }.toList
   temp.sort { |x, y| x[0].bytes[0] < y[0].bytes[0] }
   return temp.map { |e| e[1] }.toList

}

var encrypt = Fn.new { |polybius, key, plainText|

   var temp = ""
   for (ch in plainText) {
       var outer = false
       for (r in 0..5) {
           for (c in 0..5) {
               if (polybius[r][c] == ch) {
                   temp = temp + adfgvx[r] + adfgvx[c]
                   outer = true
                   break
               }
           }
           if (outer) break
       }
   }
   var colLen = (temp.count / key.count).floor
   // all columns need to be the same length
   if (temp.count % key.count > 0) colLen = colLen + 1
   var table = Lst.chunks(temp.toList, key.count)
   var lastLen = table[-1].count
   if (lastLen < key.count) table[-1] = table[-1] + ([""] * (key.count - lastLen))
   var order = orderKey.call(key)
   var cols = List.filled(key.count, null)
   for (i in 0...cols.count) {
       cols[i] = List.filled(colLen, null)
       for (j in 0...table.count) cols[i][j] = table[j][order[i]]
   }
   return cols.map { |col| col.join() }.join(" ")

}

var decrypt = Fn.new { |polybius, key, cipherText|

   var colStrs = cipherText.split(" ")
   // ensure all columns are same length
   var maxColLen = colStrs.reduce(0) { |max, col| max = (col.count > max) ? col.count : max }
   var cols = colStrs.map { |s| 
       return (s.count < maxColLen) ? s.toList + ([""] * (maxColLen - s.count)) : s.toList
   }.toList
   var table = List.filled(maxColLen, null)
   var order = orderKey.call(key)
   for (i in 0...maxColLen) {
       table[i] = List.filled(key.count, "")
       for (j in 0...key.count) table[i][order[j]] = cols[j][i]
   }
   var temp = table.map { |row| row.join("") }.join("")
   var plainText = ""
   var i = 0
   while (i < temp.count) {
       var r = adfgvx.indexOf(temp[i])
       var c = adfgvx.indexOf(temp[i+1])
       plainText = plainText + polybius[r][c]
       i = i + 2
   }
   return plainText   

}

var plainText = "ATTACKAT1200AM" var polybius = createPolybius.call() var key = createKey.call(9) System.print("\nPlaintext : %(plainText)") var cipherText = encrypt.call(polybius, key, plainText) System.print("\nEncrypted : %(cipherText)") var plainText2 = decrypt.call(polybius, key, cipherText) System.print("\nDecrypted : %(plainText2)")</lang>

Output:

Sample run:

6 x 6 Polybius square:

  | A D F G V X
---------------
A | T 7 1 V B 5
D | H Y G 2 J K
F | I Q M 8 R E
G | O P D U N C
V | Z 0 6 3 F X
X | A W 9 S 4 L

The key is SUNFLOWER

Plaintext : ATTACKAT1200AM

Encrypted : AAA AXD AAV AXV AAD GFF XXDF ADG XAX

Decrypted : ATTACKAT1200AM