ADFGVX cipher
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.
- Description
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
<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
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
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.
Raku
Slightly different results from every other entry so far. See discussion page for reasons. <lang perl6>srand 123456; # For repeatability
my @header = < A D F G V X >; my $polybius = (flat 'A'..'Z', 0..9).pick(*).join;
my $key-length = 9; my $key = uc 'unixdict.txt'.IO.words.grep( { (.chars == $key-length) && (+.comb.Set == +.comb) } ).roll;
my %cypher = (@header X~ @header) Z=> $polybius.comb;
my $message = 'Attack at 1200AM';
use Terminal::Boxer; say "Key: $key\n"; say "Polybius square:\n", ss-box :7col, :3cw, :indent("\t"), , |@header, |(@header Z $polybius.comb.batch: 6); say "Message to encode: $message"; say "\nEncoded: " ~ my $encoded = encode $message; say "\nDecoded: " ~ decode $encoded;
sub encode ($text is copy) {
$text = $text.uc.comb(/<[A..Z 0..9]>/).join; my @order = $key.comb.pairs.sort( *.value )».key; my @encode = %cypher.invert.hash{ $text.comb }.join.comb.batch($key-length).map: { [$_] }; ((^$key-length).map: { @encode».[@order]».grep( *.defined )».[$_].grep( *.defined ).join }).Str;
}
sub decode ($text is copy) {
my @text = $text.split(' ')».comb; my $chars = @text[0].chars; $_ = flat |$_, ' ' if .chars < $chars for @text; my @order = $key.comb.pairs.sort( *.value )».key.pairs.sort( *.value )».key; %cypher{ ( grep { /\w/ }, flat [Z] @order.map( { |@text.batch($key-length)».[$_] } ) ).batch(2)».join }.join;
}</lang>
- Output:
Key: GHOSTLIKE Polybius square: ┌───┬───┬───┬───┬───┬───┬───┐ │ │ A │ D │ F │ G │ V │ X │ ├───┼───┼───┼───┼───┼───┼───┤ │ A │ H │ O │ S │ 5 │ 7 │ Q │ ├───┼───┼───┼───┼───┼───┼───┤ │ D │ 0 │ I │ 6 │ J │ C │ V │ ├───┼───┼───┼───┼───┼───┼───┤ │ F │ 4 │ 8 │ R │ X │ G │ A │ ├───┼───┼───┼───┼───┼───┼───┤ │ G │ Y │ F │ P │ B │ Z │ 3 │ ├───┼───┼───┼───┼───┼───┼───┤ │ V │ M │ W │ 9 │ D │ 1 │ N │ ├───┼───┼───┼───┼───┼───┼───┤ │ X │ 2 │ E │ U │ T │ L │ K │ └───┴───┴───┴───┴───┴───┴───┘ Message to encode: Attack at 1200AM Encoded: DVVA FVX XXA FGF XVX GXA XXD GFA XXD Decoded: ATTACKAT1200AM
Wren
<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