The ADFGVX cipher
This example examines the implementation of the ADFGVX cipher, one of the most complex military ciphers of the First World War used by the German army.
Introduction
ADFGVX is a replacement polygraphic cipher used by Germany during the First World War. It combines a substitution cipher (using the Polybius table) and a transposition cipher. The encryption algorithm was designed for a high level of security, using a limited set of letters for encoding (A, D, F, G, V, X), which facilitated radio transmission. This cipher became known for being considered unsolvable for a long time, and was successfully cracked only by the French cryptographer Georges Penven.
# Устанавливаем необходимый пакет, если он еще не установлен
import Pkg; Pkg.add("Random")
# Подключаем пакет для генерации случайных чисел и перетасовки
using Random
The main part
The data structure for the ADFGVX cipher
First of all, we will define the data structure for storing all the necessary cipher components.:
"""
struct ADFGVX
Определяет структуру для хранения параметров шифра ADFGVX:
- `polybius`: таблица символов (шифруемый алфавит)
- `pdim`: размер таблицы Полибия (например, 6 для 6x6)
- `key`: ключ транспозиции
- `keylen`: длина ключа
- `alphabet`: алфавит, используемый для кодирования (обычно "ADFGVX")
- `encode`: словарь шифрования (символ -> пара букв)
- `decode`: словарь дешифрования (пара букв -> символ)
"""
struct ADFGVX
polybius::Vector{Char}
pdim::Int
key::Vector{Char}
keylen::Int
alphabet::Vector{Char}
encode::Dict{Char, Vector{Char}}
decode::Dict{Vector{Char}, Char}
end
ADFGVX Structure Constructor
Next, we create a constructor that generates a mapping table and fills in encryption and decryption dictionaries.:
"""
ADFGVX(s, k, alph = "ADFGVX")
Конструктор создает объект шифра ADFGVX по данным:
- `s`: строка символов, образующая таблицу Полибия
- `k`: ключ транспозиции
- `alph`: алфавит шифра, по умолчанию "ADFGVX"
"""
function ADFGVX(s, k, alph = "ADFGVX")
# Преобразуем в вектор прописных букв
poly = collect(uppercase(s))
pdim = isqrt(length(poly)) # вычисляем размерность таблицы (для квадратной)
al = collect(uppercase(alph)) # преобразуем алфавит
# Создаем словарь шифрования: каждому символу сопоставляется пара букв
enco::Dict = Dict([(poly[(i - 1) * pdim + j] => [al[i], al[j]])
for i in 1:pdim, j in 1:pdim])
# Создаем словарь для расшифровки (обратный)
deco = Dict(last(p) => first(p) for p in enco)
# Проверка корректности данных
@assert pdim^2 == length(poly) && pdim == length(al)
# Возвращаем инициализированный объект
return ADFGVX(poly, pdim, collect(uppercase(k)), length(k), al, enco, deco)
end
Encryption function
The encryption function converts the entered text into a sequence of characters from the cipher alphabet, then applies a key-based transposition.
"""
encrypt(s::String, k::ADFGVX)
Шифрует строку `s` с помощью объекта `k` типа `ADFGVX`.
"""
function encrypt(s::String, k::ADFGVX)
# Символы, которые будут зашифрованы
chars = reduce(vcat, [k.encode[c] for c in
filter(c -> c in k.polybius, collect(uppercase(s)))])
# Распределяем символы по колонкам в соответствии с ключом
colvecs = [lett => chars[i:k.keylen:length(chars)] for (i, lett) in enumerate(k.key)]
# Упорядочиваем колонки по алфавиту ключа
sort!(colvecs, lt = (x, y) -> first(x) < first(y))
# Объединяем отсортированные столбцы в строку
return String(mapreduce(p -> last(p), vcat, colvecs))
end
Decryption function
"""
decrypt(s::String, k::ADFGVX)
Дешифрует строку `s`, зашифрованную с помощью шифра ADFGVX.
"""
function decrypt(s::String, k::ADFGVX)
# Фильтруем символы, входящие в алфавит шифра
chars = filter(c -> c in k.alphabet, collect(uppercase(s)))
sortedkey = sort(collect(k.key)) # сортируем ключ
# Порядок сортировки для столбцов
order = [findfirst(c -> c == ch, k.key) for ch in sortedkey]
originalorder = [findfirst(c -> c == ch, sortedkey) for ch in k.key]
# Вычисляем длины столбцов (с учётом возможного неравномерного распределения)
a, b = divrem(length(chars), k.keylen)
strides = [a + (b >= i ? 1 : 0) for i in order]
starts = accumulate(+, strides[begin:end-1], init=1)
pushfirst!(starts, 1)
ends = [starts[i] + strides[i] - 1 for i in 1:k.keylen]
# Восстанавливаем столбцы в оригинальном порядке
cols = [chars[starts[i]:ends[i]] for i in originalorder]
# Восстанавливаем строки из столбцов
pairs, nrows = Char[], (length(chars) - 1) ÷ k.keylen + 1
for i in 1:nrows, j in 1:k.keylen
(i - 1) * k.keylen + j > length(chars) && break
push!(pairs, cols[j][i])
end
# Преобразуем пары символов обратно в символы исходного алфавита
return String([k.decode[[pairs[i], pairs[i + 1]]] for i in 1:2:length(pairs)-1])
end
Demonstration of the work
Generating a random Polybius table and a random key
const POLYBIUS = String(shuffle(collect("ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789")))
Download the English dictionary and select a random matching key of length 9
# Загружаем английский словарь и выбираем случайный подходящий ключ длины 9
const KEY = read("unixdict.txt", String) |>
v -> split(v, r"\s+") |>
v -> filter(w -> (n = length(w); n == 9 && n == length(unique(collect(w)))), v) |>
shuffle |> first |> uppercase
Creating a cipher object
const SECRETS = ADFGVX(POLYBIUS, KEY)
message = "ATTACKAT1200AM"
# Вывод данных на экран
println("Polybius: $POLYBIUS, Key: $KEY\n")
println("Message: $message\n")
# Шифрование сообщения
encoded = encrypt(message, SECRETS)
println("Encoded: $encoded\n")
# Дешифрование сообщения
decoded = decrypt(encoded, SECRETS)
println("Decoded: $decoded\n")
Conclusion
We have reviewed and implemented the ADFGVX cipher in Julia, one of the most secure field ciphers of the First World War. We have learned:
-
build an encryption table (Polybius table);
-
create substitution rules (encryption by pairs of characters);
-
use key-based transposition;
-
Restore the original message at the decryption stage.
This project demonstrates the importance of studying classical cryptographic methods that underlie modern data protection systems. The Julia implementation makes it easy to experiment with algorithms and understand how they work "under the hood".
The example was developed using materials from Rosetta Code