Bifid cipher
Bifid 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 Bifid cipher is a polygraphic substitution cipher which was invented by Félix Delastelle in around 1901. It uses a 5 x 5 Polybius square combined with transposition and fractionation to encrypt a message. Any 5 x 5 Polybius square can be used but, as it only has 25 cells and there are 26 letters of the (English) alphabet, one cell needs to represent two letters - I and J being a common choice.
- Operation
Suppose we want to encrypt the message "ATTACKATDAWN".
We use this archetypal Polybius square where I and J share the same position.
x/y 1 2 3 4 5 ------------- 1 | A B C D E 2 | F G H I K 3 | L M N O P 4 | Q R S T U 5 | V W X Y Z
The message is first converted to its x, y coordinates, but they are written vertically beneath.
A T T A C K A T D A W N 1 4 4 1 1 2 1 4 1 1 5 3 1 4 4 1 3 5 1 4 4 1 2 3
They are then arranged in a row.
1 4 4 1 1 2 1 4 1 1 5 3 1 4 4 1 3 5 1 4 4 1 2 3
Finally, they are divided up into pairs which are used to look up the encrypted letters in the square.
14 41 12 14 11 53 14 41 35 14 41 23 D Q B D A X D Q P D Q H
The encrypted message is therefore "DQBDAXDQPDQH".
Decryption can be achieved by simply reversing these steps.
- Task
Write routines in your language to encrypt and descrypt a message using the Bifid cipher.
Use them to verify (including subsequent decryption):
1. The above example.
2. The example in the Wikipedia article using the message and Polybius square therein.
3. The above example but using the Polybius square in the Wikipedia article to illustrate that it doesn't matter which square you use as long, of course, as the same one is used for both encryption and decryption.
In addition, encrypt and decrypt the message "The invasion will start on the first of January" using any Polybius square you like. Convert the message to upper case and ignore spaces.
- Bonus
Suggest a way in which the cipher could be modified so that ALL 26 letters can be uniquely encrypted.
- Related task
J
Implementation:
alpha=: a.{~65+i.26
normalize=: {{ rplc&'JI'(toupper y)([-.-.)alpha }}
bifid=: {{ m{~_2 (t&#.)\,|:(t,t=.%:#m)#:m i.y([-.-.)m }}
difib=: {{ m{~t#.|:(|.@$$,)(t,t=.%:#m)#:m i.y([-.-.)m }}
This is pretty much a literal implementation of the algorithm, except that our indices range from 0..4 instead of 1..5 (or, for letter indices, they range from 0..24 instead of 1..25).
Much of the implementation is about converting between a two digit base 5 representation and a single digit numeric representation. The rest is simple array manipulations to make the rest come out right.
Task examples:
ref1=: ~.normalize alpha
ref2=: 'BGWKZQPNDSIOAXEFCLUMTHYVR'
ref3=: 'PLAYFIREXMBCDGHKNOQSTUVWZ'
ref1 bifid normalize 'attack at dawn'
DQBDAXDQPDQH
ref1 difib ref1 bifid normalize 'attack at dawn'
ATTACKATDAWN
ref2 bifid normalize 'flee at once'
UAEOLWRINS
ref2 difib ref2 bifid normalize 'flee at once'
FLEEATONCE
ref2 bifid normalize 'attack at dawn'
EYFENGIWDILA
ref2 difib ref2 bifid normalize 'attack at dawn'
ATTACKATDAWN
ref3 bifid normalize 'The invasion will start on the first of January'
VRSYXSIYTMQVIRSKISLPVLDTCKRTCAIVTMATCEX
ref3 difib ref3 bifid normalize 'The invasion will start on the first of January'
THEINVASIONWILLSTARTONTHEFIRSTOFIANUARY
(_81{.123{.a.)bifid 'The invasion will start on the first of January'
TgqhpqpqxzpxfqzoKqhxw/O3eWH53BYw`+Be8F1
(_81{.123{.a.)difib(_81{.123{.a.)bifid 'The invasion will start on the first of January'
TheinvasionwillstartonthefirstofJanuary
Julia
Using the Raku example's test messages.
polybius(text) = Char.(reshape(Int.(collect(text)), isqrt(length(text)), :)')
function encrypt(message, poly)
positions = [findall(==(c), poly)[1] for c in message]
numbers = vcat([c[1] for c in positions], [c[2] for c in positions])
return String([poly[numbers[i], numbers[i+1]] for i in 1:2:length(numbers)-1])
end
function decrypt(message, poly)
n = length(message)
positions = [findall(==(c), poly)[1] for c in message]
numbers = reduce(vcat, [[c[1], c[2]] for c in positions])
return String([poly[numbers[i], numbers[i+n]] for i in 1:n])
end
for (key, text) in [("ABCDEFGHIKLMNOPQRSTUVWXYZ", "ATTACKATDAWN"), ("BGWKZQPNDSIOAXEFCLUMTHYVR", "FLEEATONCE"),
([' '; '.'; 'A':'Z'; 'a':'z'; '0':'9'], "The invasion will start on the first of January 2023.")]
poly = polybius(key)
encrypted = encrypt(text, poly)
decrypted = decrypt(encrypted, poly)
println("Using polybius:")
display(poly)
println("\n Message: $text\n Encrypted: $encrypted\n Decrypted: $decrypted\n\n")
end
- Output:
Using polybius:
5×5 Matrix{Char}:
'A' 'B' 'C' 'D' 'E'
'F' 'G' 'H' 'I' 'K'
'L' 'M' 'N' 'O' 'P'
'Q' 'R' 'S' 'T' 'U'
'V' 'W' 'X' 'Y' 'Z'
Message: ATTACKATDAWN
Encrypted: DQBDAXDQPDQH
Decrypted: ATTACKATDAWN
Using polybius:
5×5 Matrix{Char}:
'B' 'G' 'W' 'K' 'Z'
'Q' 'P' 'N' 'D' 'S'
'I' 'O' 'A' 'X' 'E'
'F' 'C' 'L' 'U' 'M'
'T' 'H' 'Y' 'V' 'R'
Message: FLEEATONCE
Encrypted: UAEOLWRINS
Decrypted: FLEEATONCE
Using polybius:
8×8 Matrix{Char}:
' ' '.' 'A' 'B' 'C' 'D' 'E' 'F'
'G' 'H' 'I' 'J' 'K' 'L' 'M' 'N'
'O' 'P' 'Q' 'R' 'S' 'T' 'U' 'V'
'W' 'X' 'Y' 'Z' 'a' 'b' 'c' 'd'
'e' 'f' 'g' 'h' 'i' 'j' 'k' 'l'
'm' 'n' 'o' 'p' 'q' 'r' 's' 't'
'u' 'v' 'w' 'x' 'y' 'z' '0' '1'
'2' '3' '4' '5' '6' '7' '8' '9'
Message: The invasion will start on the first of January 2023.
Encrypted: SejxqrEierbmrDiCjrDeJsbu89DWCHkgGS9E6tAG5 Ks2PBfCq uH
Decrypted: The invasion will start on the first of January 2023.
Perl
use v5.36;
use builtin <indexed floor>;
use experimental qw(builtin for_list);
use List::Util 'max';
sub table ($c, @V) { my $t = $c * (my $w = 2 + length max map { length } @V); ( sprintf( ('%'.$w.'s')x@V, @V) ) =~ s/.{1,$t}\K/\n/gr }
sub polybius ($text) {
my %p;
my $n = floor sqrt length $text;
for my($k,$v) (indexed split '', $text) {
$p{$v} = join ' ', $k%$n, int $k/$n
}
%p;
}
sub encrypt ($text, %P) {
my(%I, @c, $encrypted);
for my($k,$v) (%P) { $I{$v} = $k }
for my ($n,$char) (indexed split '', ($text =~ s/\s//gr)) {
for my($m,$i) (indexed split ' ', $P{$char}) { $c[$m][$n] = $i }
}
for my($i,$j) ($c[1]->@*, $c[0]->@*) { $encrypted .= $I{"$j $i"} }
$encrypted
}
sub decrypt ($text, %P) {
my($decrypted, $l, %I, @c) = ('', length($text));
for my($k,$v) (%P) { $I{$v} = $k }
for (split '', $text) {
for my($i,$j) (split ' ', $P{$_}) { unshift @c, $i, $j }
}
substr $decrypted, 0, 0, $I{ "$c[$_] $c[$_+$l]" } for 0 .. $l-1;
$decrypted;
}
for my($polybius,$message) (
join('','A'..'Z') =~ s/J//r, 'ATTACK AT DAWN',
'BGWKZQPNDSIOAXEFCLUMTHYVR', 'FLEE AT ONCE',
join('','_.', 'A'..'Z', 'a'..'z', '0'..'9'), 'The_invasion_will_start_on_the_first_of_January_2023.',
) {
my %Ptable = polybius $polybius;
say "\nUsing polybius:\n" . table sqrt length $polybius, split '', $polybius;
say 'Message : ' . $message;
say 'Encrypted : ' . (my $encrypted = encrypt $message, %Ptable);
say 'Decrypted : ' . decrypt $encrypted, %Ptable;
}
- Output:
Using polybius: A B C D E F G H I K L M N O P Q R S T U V W X Y Z Message : ATTACK AT DAWN Encrypted : DQBDAXDQPDQH Decrypted : ATTACKATDAWN Using polybius: B G W K Z Q P N D S I O A X E F C L U M T H Y V R Message : FLEE AT ONCE Encrypted : UAEOLWRINS Decrypted : FLEEATONCE Using polybius: _ . A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9 Message : The_invasion_will_start_on_the_first_of_January_2023. Encrypted : SejxqrEierbmrDiCjrDeJsbu89DWCHkgGS9E6tAG5_Ks2PBfCq_uH Decrypted : The_invasion_will_start_on_the_first_of_January_2023.
Phix
with javascript_semantics enum encrypt,decrypt function bifid(string msg, polybius, sequence p, integer n, ed) string res = "" sequence dx = {}, dy = {}, dxy for i=1 to length(msg) do integer k = find(msg[i],polybius)-1 dx &= floor(k/n)+1 dy &= remainder(k,n)+1 end for if ed=encrypt then dxy = split_by(dx&dy,2) else -- "simply reversing these steps" - yeah, right... dxy = columnize(split_by(flatten(columnize({dx,dy})),length(dx))) end if for i=1 to length(dxy) do integer {x,y} = dxy[i] res &= p[x][y] end for return res end function procedure test(string msg, polybius) integer n = sqrt(length(polybius)) if n=5 then msg = substitute(upper(msg),"J","I") end if sequence p = split_by(polybius,n) string enc = bifid(msg,polybius,p,n,encrypt), dec = bifid(enc,polybius,p,n,decrypt) printf(1,"For %dx%d polybius %s\n\n",{n,n,join(p,"\n ")}) printf(1,"Message : %s\nEncrypted: %s\nDecrypted: %s\n\n",{msg,enc,dec}) end procedure constant polybii = {tagstart('A','J'-'A')&tagstart('K','Z'-'J'), "BGWKZQPNDSIOAXEFCLUMTHYVR", " ."&tagstart('A',26)&tagstart('a',26)&tagstart('0',10)}, messages = {"ATTACKATDAWN","FLEEATONCE", "The invasion will start on the first of January 2023."} for t=1 to 3 do test(messages[t],polybii[t]) end for
- Output:
For 5x5 polybius ABCDE
FGHIK
LMNOP
QRSTU
VWXYZ
Message : ATTACKATDAWN
Encrypted: DQBDAXDQPDQH
Decrypted: ATTACKATDAWN
For 5x5 polybius BGWKZ
QPNDS
IOAXE
FCLUM
THYVR
Message : FLEEATONCE
Encrypted: UAEOLWRINS
Decrypted: FLEEATONCE
For 8x8 polybius .ABCDEF
GHIJKLMN
OPQRSTUV
WXYZabcd
efghijkl
mnopqrst
uvwxyz01
23456789
Message : The invasion will start on the first of January 2023.
Encrypted: SejxqrEierbmrDiCjrDeJsbu89DWCHkgGS9E6tAG5 Ks2PBfCq uH
Decrypted: The invasion will start on the first of January 2023.
Python
"""Bifid cipher. Requires Python >=3.7."""
import math
import pprint
import string
from itertools import chain
from itertools import zip_longest
from typing import Dict
from typing import Iterable
from typing import Iterator
from typing import Tuple
from typing import TypeVar
T = TypeVar("T")
def group(it: Iterable[T], n: int) -> Iterator[Tuple[T, ...]]:
"""Return the input iterable split in to `n` equal chunks, padded with `None`."""
return zip_longest(*[iter(it)] * n)
Square = Tuple[Tuple[str, ...], ...]
def polybius_square(alphabet: str) -> Square:
"""Return the given alphabet as a tuple of tuples, representing a Polybius square."""
return tuple(group(alphabet, math.ceil(math.sqrt(len(alphabet)))))
def polybius_map(square: Square) -> Dict[str, Tuple[int, int]]:
"""Return a reverse lookup for the given Polybius square."""
return {
square[i][j]: (i + 1, j + 1)
for i in range(len(square))
for j in range(len(square))
}
def encrypt(message: str, square: Square) -> str:
"""Encrypt a plaintext message using a bifid cipher with the given Polybius square."""
_map = polybius_map(square)
return "".join(
square[x - 1][y - 1]
for x, y in group(
chain.from_iterable(zip(*(_map[c] for c in message if c in _map))),
2,
)
)
def decrypt(message: str, square: Square) -> str:
"""Decrypt a ciphertext message using a bifid cipher with the given Polybius square."""
_map = polybius_map(square)
return "".join(
square[x - 1][y - 1]
for x, y in zip(
*group(
chain.from_iterable((_map[c] for c in message if c in _map)),
len(message),
)
)
)
def normalize(message: str) -> str:
"""Normalize a message for the typical Polybius square."""
return message.upper().replace("J", "I")
TYPICAL_POLYBIUS_SQUARE = polybius_square(
alphabet="".join(c for c in string.ascii_uppercase if c != "J")
)
EXAMPLE_POLYBIUS_SQUARE = polybius_square(
alphabet="BGWKZQPNDSIOAXEFCLUMTHYVR",
)
def main() -> None:
test_cases = [
("ATTACKATDAWN", TYPICAL_POLYBIUS_SQUARE), # 1
("FLEEATONCE", EXAMPLE_POLYBIUS_SQUARE), # 2
("FLEEATONCE", TYPICAL_POLYBIUS_SQUARE), # 3
(
normalize("The invasion will start on the first of January"),
polybius_square(alphabet="PLAYFIREXMBCDGHKNOQSTUVWZ"),
),
(
"The invasion will start on the first of January".upper(),
polybius_square(alphabet=string.ascii_uppercase + string.digits),
),
]
for message, square in test_cases:
pprint.pprint(square)
print("Message :", message)
print("Encrypted:", encrypt(message, square))
print("Decrypted:", decrypt(encrypt(message, square), square))
print("")
if __name__ == "__main__":
main()
- Output:
(('A', 'B', 'C', 'D', 'E'),
('F', 'G', 'H', 'I', 'K'),
('L', 'M', 'N', 'O', 'P'),
('Q', 'R', 'S', 'T', 'U'),
('V', 'W', 'X', 'Y', 'Z'))
Message : ATTACKATDAWN
Encrypted: DQBDAXDQPDQH
Decrypted: ATTACKATDAWN
(('B', 'G', 'W', 'K', 'Z'),
('Q', 'P', 'N', 'D', 'S'),
('I', 'O', 'A', 'X', 'E'),
('F', 'C', 'L', 'U', 'M'),
('T', 'H', 'Y', 'V', 'R'))
Message : FLEEATONCE
Encrypted: UAEOLWRINS
Decrypted: FLEEATONCE
(('A', 'B', 'C', 'D', 'E'),
('F', 'G', 'H', 'I', 'K'),
('L', 'M', 'N', 'O', 'P'),
('Q', 'R', 'S', 'T', 'U'),
('V', 'W', 'X', 'Y', 'Z'))
Message : FLEEATONCE
Encrypted: HADNAAZDSP
Decrypted: FLEEATONCE
(('P', 'L', 'A', 'Y', 'F'),
('I', 'R', 'E', 'X', 'M'),
('B', 'C', 'D', 'G', 'H'),
('K', 'N', 'O', 'Q', 'S'),
('T', 'U', 'V', 'W', 'Z'))
Message : THE INVASION WILL START ON THE FIRST OF IANUARY
Encrypted: VRSYXSIYTMQVIRSKISLPVLDTCKRTCAIVTMATCEX
Decrypted: THEINVASIONWILLSTARTONTHEFIRSTOFIANUARY
(('A', 'B', 'C', 'D', 'E', 'F'),
('G', 'H', 'I', 'J', 'K', 'L'),
('M', 'N', 'O', 'P', 'Q', 'R'),
('S', 'T', 'U', 'V', 'W', 'X'),
('Y', 'Z', '0', '1', '2', '3'),
('4', '5', '6', '7', '8', '9'))
Message : THE INVASION WILL START ON THE FIRST OF JANUARY
Encrypted: TBPDIPHJSPOTAIVMGPCZKNSCN09BFIHK64I7BM4
Decrypted: THEINVASIONWILLSTARTONTHEFIRSTOFJANUARY
Raku
Technically incorrect as the third part doesn't "Convert ... to upper case and ignore spaces".
sub polybius ($text) {
my $n = $text.chars.sqrt.narrow;
$text.comb.kv.map: { $^v => ($^k % $n, $k div $n).join: ' ' }
}
sub encrypt ($message, %poly) {
%poly.invert.hash{(flat reverse [Z] %poly{$message.comb}».words).batch(2)».reverse».join: ' '}.join
}
sub decrypt ($message, %poly) {
%poly.invert.hash{reverse [Z] (reverse flat %poly{$message.comb}».words».reverse).batch($message.chars)}.join
}
for 'ABCDEFGHIKLMNOPQRSTUVWXYZ', 'ATTACKATDAWN',
'BGWKZQPNDSIOAXEFCLUMTHYVR', 'FLEEATONCE',
(flat '_', '.', 'A'..'Z', 'a'..'z', 0..9).pick(*).join, 'The invasion will start on the first of January 2023.'.subst(/' '/, '_', :g)
-> $polybius, $message {
my %polybius = polybius $polybius;
say "\nUsing polybius:\n\t" ~ $polybius.comb.batch($polybius.chars.sqrt.narrow).join: "\n\t";
say "\n Message : $message";
say "Encrypted : " ~ my $encrypted = encrypt $message, %polybius;
say "Decrypted : " ~ decrypt $encrypted, %polybius;
}
- Output:
Using polybius: A B C D E F G H I K L M N O P Q R S T U V W X Y Z Message : ATTACKATDAWN Encrypted : DQBDAXDQPDQH Decrypted : ATTACKATDAWN Using polybius: B G W K Z Q P N D S I O A X E F C L U M T H Y V R Message : FLEEATONCE Encrypted : UAEOLWRINS Decrypted : FLEEATONCE Using polybius: H c F T N 5 f i _ U k R B Z V W 3 G e v s w j x q S 2 8 y Q . O m 0 E d h D r u M p 7 Y 4 A 9 a t X l I 6 g b z J P n 1 K L C o Message : The_invasion_will_start_on_the_first_of_January_2023. Encrypted : NGiw3okfXj4XoVE_NjWcLK4Sy28EivKo3aeNiti3N3z6HCHno6Fkf Decrypted : The_invasion_will_start_on_the_first_of_January_2023.
Wren
One way of enabling all 26 letters to be encrypted uniquely would be to use a 6 x 6 Polybius square including the 10 digits. We could then encrypt text using numerals as well.
However, the following just uses the standard version of the cipher.
import "./str" for Str
import "./seq" for Lst
class Bifid {
static encrypt(polybius, message) {
message = Str.upper(message).replace("J", "I")
var rows = []
var cols = []
for (c in message) {
var ix = polybius.indexOf(c)
if (ix == -1) continue
rows.add((ix/5).floor + 1)
cols.add((ix%5) + 1)
}
var s = ""
for (pair in Lst.chunks(rows + cols, 2)) {
var ix = (pair[0] - 1) * 5 + pair[1] - 1
s = s + polybius[ix]
}
return s
}
static decrypt(polybius, message) {
var rows = []
var cols = []
for (c in message) {
var ix = polybius.indexOf(c)
rows.add((ix/5).floor + 1)
cols.add((ix%5) + 1)
}
var lines = Lst.flatten(Lst.zip(rows, cols))
var count = lines.count/2
rows = lines[0...count]
cols = lines[count..-1]
var s = ""
for (i in 0...count) {
var ix = (rows[i] - 1) * 5 + cols[i] - 1
s = s + polybius[ix]
}
return s
}
}
var poly1 = "ABCDEFGHIKLMNOPQRSTUVWXYZ"
var poly2 = "BGWKZQPNDSIOAXEFCLUMTHYVR"
var poly3 = "PLAYFIREXMBCDGHKNOQSTUVWZ"
var polys = [poly1, poly2, poly2, poly3]
var msg1 = "ATTACKATDAWN"
var msg2 = "FLEEATONCE"
var msg3 = "The invasion will start on the first of January"
var msgs = [msg1, msg2, msg1, msg3]
for (i in 0...msgs.count) {
var encrypted = Bifid.encrypt(polys[i], msgs[i])
var decrypted = Bifid.decrypt(polys[i], encrypted)
System.print("Message : %(msgs[i])")
System.print("Encrypted : %(encrypted)")
System.print("Decrypted : %(decrypted)")
if (i < msgs.count-1) System.print()
}- Output:
Message : ATTACKATDAWN Encrypted : DQBDAXDQPDQH Decrypted : ATTACKATDAWN Message : FLEEATONCE Encrypted : UAEOLWRINS Decrypted : FLEEATONCE Message : ATTACKATDAWN Encrypted : EYFENGIWDILA Decrypted : ATTACKATDAWN Message : The invasion will start on the first of January Encrypted : VRSYXSIYTMQVIRSKISLPVLDTCKRTCAIVTMATCEX Decrypted : THEINVASIONWILLSTARTONTHEFIRSTOFIANUARY