J-ottings 42: I (continue to) Spy with very little J ...
Vector 21:2, page 38
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 38
Way back in J-ottings 25, (the I-spy book of J) I described the basis of the cryptography which underlies the security of many of the millions of web transactions which take place every minute out in cyberspace. Such cryptographic systems based on substitution codes depend on using public and private keys. Although an identical technique is used for sending and receiving messages, it is nevertheless safe to broadcast one’s public key to allow any sender to mail you encrypted messages, since only you possess the private key which is essential to decrypt them. This property makes such codes non-reciprocal. Reciprocal coding techniques are more primitive, and trade off the simplicity of doing the same thing to encrypt and decrypt against the requirement that the single underlying key must be kept secret between all communicating parties.
One of the best known of these techniques uses the so-called Vigenère tables after a sixteenth century French diplomat of that name. The idea is that the communicating parties share a table of alphabetic characters which resolve a pair of characters into a single character. 26 by 26 blocks take quite a lot of space, so I shall demonstrate the principle with the six-character alphabet ‘ABCDES’. To make a Vigenère table, choose a word such as ‘BED’ which leads to a table keyword ‘BEDACS’ in which the characters not in the keyword are appended in alphabetic order. The table keyword then serves as row and column headers for the Vigenère table. To make the body of the table, start with the table keyword reversed and the remaining rows progressively shifted to the left :
Both the encrypt and the decrypt of the letter pair EC is then B. No doubt you can already glimpse how well J is adapted to producing such tables!
Messages are converted into character pairs by the parties agreeing a message keyword (this is quite separate from the table keyword) which is written by expanding it as often as is necessary beneath the message, so that if the message is “Abe’s dad’s a cad”, and the keyword is “SAD” write
Using the columns as indexes to the table gives the coded message
Now repeat this procedure for the coded message
… and back comes the original message :
Now repeat the procedure, only this time using J in order to make notes which capture the thinking underlying the various steps. First a utility verb maketab performs the progressive row left shifts :
makevtab=.|."0 1~i.@# NB. table of progressive shifts
(makevtab i.3);makevtab 'pqrs'
+-----+----+
|0 1 2|pqrs|
|1 2 0|qrsp|
|2 0 1|rspq|
| |spqr|
+-----+----+
For the Vigenère table which uses ‘SAD’ as the table keyword define
tkey=:'sadbce'
]vtab=:maketab |.tkey NB. Vig. table as fn. of tkey
ecbdas
cbdase
bdasec
dasecb
asecbd
secbda
With the same message as before, and ignoring blanks for simplicity, obtain the block of character pairs
and then use the table keyword to convert this into indices into vtab :
For convenience, use append items (,.) rather than laminate (,:) so that the indices are the primary lists (rows) and the code letters can be extracted by using box at rank 1 :
To decrypt, apply the same procedure to the encrypted message :
Now bring it all together in a single verb, for which there seems to be little point in struggling to achieve an ingenious tacit definition :
encrypt=.dyad :'(<"1 tkey i.y.,.(#y.)$x.){vtab'
'sad' encrypt msg NB.syntax is: mkey encrypt message
caceddbcdaba
and to decrypt use the same algorithm :
As confirmation, the above result should follow using any message keyword whose letters belong to the alphabet 'abcdes':
Sorting the rows and columns into alphabetic order is only a consideration if the table is to be displayed for human as opposed to computer use. With a six-letter alphabet, even this is hardly worth while, but with a full alphabet of 26 letters it would certainly be desirable. Alphabetic row ordering using the table keyword is achieved by
and column ordering by doing the same to the transpose, so that the form of vtab in which the row and column headings are both 'abcdes' is given by
An amended encryption algorithm now uses ordvtab to achieve the same end result :
alph=:'abcdes'
aencrypt=.dyad : '(<"1 alph i.y.,.(#y.)$x.){ordvtab'
'sad' aencrypt msg
caceddbcdaba
'sad' aencrypt ^:2 msg
abesdadsacad
Of course any anagram of the alphabet will do for the table keyword, and a convenient way of mapping integers into keywords is to make tkey a derivative of alph by using the “ordered anagram” verb A. :
vtab must be reassigned, and encrypt re-executed :
following which
Nothing new is required algorithmically to move up to a full alphabet, and there is no reason why spaces and other punctuation characters should not be thrown in for good measure. The variables alph, tkey and vtab have to be reassigned, and encrypt has to be re-executed:
alph=.' ',(97+i.26){a.
vtab=.makevtab |.tkey=.525 A. alph
encrypt=.dyad :'(<"1 tkey i.y.,.(#y.)$x.){vtab'
following which here is the encryption and decryption of a short message:
'vector' encrypt 'quick a lazy dog'
nvnc hcykeondqhu
'vector' encrypt^:2 'quick a lazy dog'
quick a lazy dog
A Vigenère cipher can be made more secure by performing a final alphabetic shift using a further key, call it a shift key :
The price of this extra security is that the encryption algorithm is no longer reciprocal. However, inverting the shift is simply a matter of applying minus to the shift key, so that the total operation is confirmed by
]x=.skey shift 'sad' encrypt 'quick a lazy dog'
txpgqyi miedjajc
'sad' encrypt (-skey)shift x
quick a lazy dog
The title of this article promised very little J. To demonstrate just how little, here is a summary in the form of a recipe for Vigenère based codes. First choose a global tkey, which might be explicit or generated by anagram number or otherwise, and then construct a global Vigenère table by
vtab=:makevtab |.tkey NB. Vig. table from table keyword
makevtab=.|."0 1~i.@# NB. make table of right shifts
then encrypt and decrypt messages using
which has the syntax <message keyword> encrypt <message> :
For the further security of a shift key use alph=./:~tkey and
Truly a lot with a little!