Grille (cryptography)
From Wikipedia, the free encyclopedia
In the history of cryptography, a grille cipher was a technique for encrypting a plaintext by writing it onto a sheet of paper through a pierced sheet (of paper or cardboard or similar). The earliest known description is due to the polymath Girolamo Cardano in 1550. His proposal was for a rectangular stencil allowing single letters, syllables, or words to be written, then later read, through its various apertures. The written fragments of the plaintext could be further disguised by filling the gaps between the fragments with anodyne words or letters. This variant is also an example of steganography, as are many of the grille ciphers.
Contents |
[edit] Cardan grille and variations
The Cardan grille was invented at a time when the concepts cryptography and steganography were often confused. For instance, though Sir Francis Bacon used them interchangeably on occasion, he recognised the modern distinction in his three principles which can be paraphrased as:
- a cipher method should not be difficult to use
- it should not be possible for others to recover the plaintext (called 'reading the cipher')
- in some cases, the presence of messages should not be suspected
It is difficult to fulfil all three conditions simultaneously. Condition 3 applies to steganography. Bacon meant that a cipher message should, in some cases, not appear to be a cipher at all. The original Cardan Grille met that aim.
Variations on the Cardano original, however, were not intended to fulfill condition 3 and generally failed to meet condition 2 as well. But, few if any ciphers have ever achieved this second condition, so the point is generally a cryptanalyst’s delight whenever the grille ciphers are used.
The attraction of a grille cipher for users lies in its ease of use (condition 1). In short, it's very simple.
[edit] Single-letter grilles
Not all ciphers are used for communication with others: records and reminders may be kept in cipher for use of the author alone. A grille is eaily usable for protection of brief information such as a key word or a key number in such a use.
In the example, a grille has eight irregularly place (ideally randomly) holes – equal to the length of a key word TANGIERS. The grille is placed on a gridded sheet (not required in actual practice) and the letters written in from top to bottom.
Removing the grille, the grid is filled with random letters and numbers. Then, one hopes, only the possessor of the grille or a copy can read out the hidden letters or numbers – which could, for example, be the key to a polyalphabetic cipher such as that proposed around the same time by Giambattista della Porta.
The grille and the grid are kept separately. If there is only one copy of the grille and one of the grid, the loss of either results in the loss of both.
Clearly, in the case of communication by grille cipher, both sender and recipient must possess an identical copy of the grille. The loss of a grille leads to the probable loss of all secret correspondence encrypted with that grille. Either the messages cannot be read (ie, decrypted) or someone else (with the lost grille) may be reading them.
A further use for such a grille has been suggested: it is a method of generating pseudo-random sequences from a pre-existing text. This view has been proposed in connection with the Voynich manuscript. It is an area of cryptography that David Kahn termed enigmatology and touches on the works of Dr John Dee and Shakespeare authorship which William F. Friedman examined with amusement.
[edit] Trellis ciphers
The Elizabethan spymaster Sir Francis Walsingham (1530-1590) is reported to have used a "trellis" to conceal the letters of a plaintext in communication with his agents. However, he generally preferred the combined code-cipher method known as a nomenclator. it was the practical state-of-the-art in his day. The trellis was described as a device with spaces that was reversible. It appears to have been a transposition tool that produced something much like the Rail fence cipher and resembled a chess board.
Cardano is not known to have proposed this variation, but he was a chess player who wrote a book on gaming, so the pattern would have been familiar to him. Whereas the ordinary Cardan grille has arbitrary perforations, if his method of cutting holes is applied to the white squares of a chess board a regular pattern results.
The encipherer begins with the board in the wrong position for chess. Each successive letter of the message is written in a single square. If the message is written vertically, it is taken off horizontally and vice versa.
After filling in 32 letters, the board is turned through 90 degrees and another 32 letters written (note that flipping the board horizontally or vertically is the equivalent). Shorter messages are filled with null letters (ie, [[padding (cryptography)|padding). Messages longer than 64 letters require another turn of the board and another sheet of paper. If the plaintext is too short, each square must be filled up entirely with nulls.
J M T H H D L I S I Y P S L U I A O W A E T I E E N W A P D E N E N E L G O O N N A I T E E F N K E R L O O N D D N T T E N R X
This transposition method produces an invariant pattern and is not satisfactorily secure for anything other than cursory notes.
33, 5, 41, 13, 49, 21, 57, 29, 1, 37, 9, 45, 17, 53, 25, 61, 34, 6, 42, 14, 50, 22, 58, 30, 2, 38, 10, 46, 18, 54, 26, 62, 35, 7, 43, 15, 51, 23, 59, 31, 3, 39, 11, 47, 19, 55, 27, 63, 36, 8, 44, 16, 52, 24, 60, 32, 4, 40, 12, 48, 20, 56, 28, 64
A second transposition is needed to obscure the letters. Following the chess analogy, the route taken might be the knight’s move. Or some other path can be agreed upon, such as a reverse spiral, together with a specific number of nulls to pad the start and end of a message.
[edit] Turning grilles
Rectangular Cardan grilles can be placed in four positions. The trellis or chessboard has only two positions, but it gave rise to a more sophisticated turning grille with four positions that can be rotated in two directions.
Baron Edouard Fleissner von Wostrowitz, a retired Austrian cavalry colonel, described a variation on the chess board cipher in 1880 and his grilles were adopted by the German army during the WWI.
One form of the Fleissner (or Fleißner) grille makes 16 perforations in an 8x8 grid – 4 holes in each quadrant. If the squares in each quadrant are numbered 1 to 16, all 16 numbers must be used once only. This allows many variations in placing the apertures.
The grille has four positions – North, East, South, West. Each position exposes 16 of the 64 squares. The encipherer places the grille on a sheet and writes the first 16 letters of the message. Then, turning the grille through 90 degrees, the second 16 are written, and so on until the grid is filled.
It is possible to construct grilles of different dimensions; however, if the number of squares in one quadrant is odd, even if the total is an even number, one quadrant or section must contain an extra perforation. Illustrations of the Fleissner grille often take a 6x6 example for ease of space; the number of apertures in one quadrant is 9, so three quadrants contain 2 apertures and one quadrant must have 3. There is no standard pattern of apertures: they are created by the user, in accordance with the above description, with the intention of producing a good mix.
The method gained wide recognition when Jules Verne used a turning grille as a plot device in his novel Mathias Sandorf, published in 1885. Verne had come across the idea in Fleissner’s treatise Handbuch die Kryptographie which appeared in 1881.
Fleissner Grilles were constructed in various sizes during the WWI and were used by the German Army at the end of 1916. Each grille had a different code name:- 5x5 ANNA; 6X6 BERTA; 7X7 CLARA; 8X8 DORA; 9X9 EMIL; 10X10 FRANZ.
Their security was weak, and they were withdrawn after four months.
Another method of indicating the size of the grille in use was to insert a key code at the start of the cipher text: E = 5; F = 6 and so on. The grille can also be rotated in either direction and the starting position does not need to be NORTH. Clearly the working method is by arrangement between sender and receiver and may be operated in accordance with a schedule.
In the following examples, two cipher texts contain the same message. They are constructed from the example grille, beginning in the NORTH position, but one is formed by rotating the grille clockwise and the other anticlockwise. The ciphertext is then taken off the grid in horizontal lines - but it could equally be taken off vertically.
CLOCKWISE
ITIT ILOH GEHE TCDF LENS IIST FANB FSET EPES HENN URRE NEEN TRCG PR&I ODCT SLOE
ANTICLOCKWISE
LEIT CIAH GTHE TIDF LENB IIET FONS FSST URES NEDN EPRE HEEN TRTG PROI ONEC SL&C
In 1925 Luigi Sacco of the Italian Signals Corps began writing a book on ciphers which included reflections on the codes of the Great War, Nozzioni di crittografia. He observed that Fleissner’s method could be applied to a fractionating cipher, such as a Delastelle BIFID or Four-Square, with considerable increase in security.
Grille ciphers are also useful device for transposing Chinese characters, and avoid the transliteration of the words into alphabetic or syllabitic charactes to which other ciphers (for expample, substitution ciphers) can be applied.
After WWI, machine encryption began to make simple cipher devices obsolete, and grille ciphers became largely obsolete. Yet, grilles provided seed ideas for transposition ciphers that are reflected in modern cryptography.
[edit] Unusual possibilities
[edit] The d'Agapeyeff cipher
The unsolved d’Agapeyeff cipher, which was set as a challenge in 1939, contains 14x14 dinomes and might be based on Sacco’s idea of transposing a fractionated cipher text by means of a grille.
[edit] A Third-Party Grille: the crossword puzzle
The distribution of grilles, an example of the difficult problem of key exchange, can be eased by taking a readily-available third-party grid in the form of a newspaper crossword puzzle. Although this is not strictly a grille cipher, it resembles the chessboard with the black squares shifted and it can be used in the Cardan manner. The message text can be written horizontally in the white squares and the ciphertext taken off vertically, or vice versa.
CTATI ETTOL TTOEH RRHEI MUCKE SSEEL AUDUE RITSC VISCH NREHE LEERD DTOHS ESDNN LEWAC LEONT OIIEA RRSET LLPDR EIVYT ELTTD TOXEA E4TMI GIUOD PTRT1 ENCNE ABYMO NOEET EBCAL LUZIU TLEPT SIFNT ONUYK YOOOO
Again, following Sacco’s observation, this method disrupts a fractionating cipher such as Seriated Playfair.
Crosswords are also a possible source of keywords. A grid of the size illustrated has a word for each day of the month, the squares being numbered.
[edit] Cryptanalysis
The original Cardano Grille was a literary device for gentlemen’s private correspondence. Any suspicion of its use can lead to discoveries of hidden messages where no hidden messages exist at all, thus confusing the cryptanalyst. As in the case of letters/numbers in a random grid, obtaining the grille itself is a chief goal of the attacker.
But all is not lost if a grille copy can[t be obtained. The later variants of the Cardano variant present problems which are common to all transposition ciphers. Frequency analysis wil show a normal distribution of letters, and will suggest the language in which the plaintext was written. The problem, easily stated though less easily accomplished, is to identify the transpositon pattern and so decrypto the ciphertext. Possession of several messages written using the same grille is a considerable aid.
Gaines, in her standard work on hand ciphers and their cryptanalysis, gave a lengthy account of transposition ciphers, and devoted a chapter to the turning grille.
[edit] References
- David Kahn, The Codebreakers — The Comprehensive History of Secret Communication from Ancient Times to the Internet, 1996, ISBN 0-684-83130-9.
- Helen Fouché Gaines, Cryptanalysis – a study of ciphers and their solutions, 1939; reprinted Dover Publications, New York, 1956
- Richard Deacon, A History of the British Secret Service, Frederick Mũller, London, 1969
- Luigi Sacco, Nozzioni di crittografia, privately printed, Rome, 1930; revised and reprinted twice as Manuale di crittografia
- Simon Singh, The Code Book - The Science of Secrecy from Ancient Egypt to Quantum Cryptography, Fourth Estate Limited, London, 1999: ISBN 1-85702-879-1
[edit] External links
- Schneider, Matthias (2004-03-30). The Turning Grille Toolset. Retrieved on 2006-05-30.
- Savard, John J. G. (1998). Methods of Transposition. A Cryptographic Compendium. Retrieved on 2006-05-30.
- The Voynich Manuscript. Retrieved on 2006-05-30.
- Grille. Classic Cryptography. ThinkQuest. Retrieved on 2006-06-01.
- Matthews, Robert A. J. Notes on the D'Agapeyeff Cipher. Retrieved on 2006-06-05.
