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

Playfair cipher

J

Implementation:<lang J>alpha=: a.{~65+i.26 normalize=: {{ rplc&'JI'(toupper y)([-.-.)alpha }} bifid=: {{ m{~_2 (5&#.)\,|:5 5#:m i.normalize y }} difib=: {{ m{~5#.|:(|.@$$,)5 5#:m i.normalize y }}</lang>

Task examples:<lang J>ref1=: ~.normalize alpha ref2=: 'BGWKZQPNDSIOAXEFCLUMTHYVR' ref3=: 'PLAYFIREXMBCDGHKNOQSTUVWZ'

  ref1 bifid 'attack at dawn'

DQBDAXDQPDQH

  ref1 difib ref1 bifid 'attack at dawn'

ATTACKATDAWN

  ref2 bifid 'flee at once'

UAEOLWRINS

  ref2 difib ref2 bifid 'flee at once'

FLEEATONCE

  ref2 bifid 'attack at dawn'

EYFENGIWDILA

  ref2 difib ref2 bifid 'attack at dawn'

ATTACKATDAWN

  ref3 bifid 'The invasion will start on the first of January'

VRSYXSIYTMQVIRSKISLPVLDTCKRTCAIVTMATCEX

  ref3 difib ref3 bifid 'The invasion will start on the first of January'

THEINVASIONWILLSTARTONTHEFIRSTOFIANUARY</lang>

We could include both I and J by increasing the square size to 64: take all ascii characters in the range from 32 (space) to 126 (tilde). Discard the lower case letters. Discard four other characters. Use the remainder for the square.

Julia

Using the Raku example's test messages. <lang julia>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

</lang>

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.

Raku

Technically incorrect as the third part doesn't "Convert ... to upper case and ignore spaces".

<lang perl6>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;

}</lang>

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. <lang ecmascript>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()

}</lang>

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