.gif)
Grille (cryptography)
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.
Sir Francis Bacon
gave three fundamental conditions for ciphers. Paraphrased, these are:
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.
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 is 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 (i.e., 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 ciphers supposedly embedded in the works of Shakespeare proving that Francis Bacon
wrote them, which William F. Friedman
examined and discredited.
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 (i.e., 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.
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 World War I. These grilles are often named after Fleissner, although he took his material largely from a German work, published in Tübingen in 1809, written by Klüber who attributed this form of the grille to Cardano.
Bauer notes that grilles were used in the 18th century, for example in 1745 in the administration of the Dutch Stadthouder William IV. Later, the mathematician C. F. Hindenburg studied turning grilles more systematically in 1796. '[they]are often called Fleissner grilles in ignorance of their historical origin.'
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 der Kryptographie which appeared in 1881.
Fleissner Grilles were constructed in various sizes during World War I 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; they avoid the transcription of words into alphabetic or syllabic characters to which other ciphers (for example, substitution cipher
s) can be applied.
After World War I, machine encryption made simple cipher devices obsolete, and grille ciphers fell into disuse except for amateur purposes. Yet, grilles provided seed ideas for transposition ciphers that are reflected in modern cryptography.
, 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.
, 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.
But all is not lost if a grille copy can't be obtained. The later variants of the Cardano grille present problems which are common to all transposition ciphers. Frequency analysis
will 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 transposition pattern and so decrypt 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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a grille cipher was a technique for encrypting a plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
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
Polymath
A polymath is a person whose expertise spans a significant number of different subject areas. In less formal terms, a polymath may simply be someone who is very knowledgeable...
Girolamo Cardano in 1550. His proposal was for a rectangular stencil
Stencil
A stencil is a thin sheet of material, such as paper, plastic, or metal, with letters or a design cut from it, used to produce the letters or design on an underlying surface by applying pigment through the cut-out holes in the material. The key advantage of a stencil is that it can be reused to...
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
Steganography
Steganography is the art and science of writing hidden messages in such a way that no one, apart from the sender and intended recipient, suspects the existence of the message, a form of security through obscurity...
, as are many of the grille ciphers.
Cardan grille and variations
The Cardan grille was invented as a method of secret writing. The word cryptography became the more familiar term for secret communications from the middle of the 17th century. Earlier, the word steganography was common. The other general term for secret writing was cypher - also spelt cipher. There is a modern distinction between cryptography and steganographySir Francis Bacon
Francis Bacon
Francis Bacon, 1st Viscount St Albans, KC was an English philosopher, statesman, scientist, lawyer, jurist, author and pioneer of the scientific method. He served both as Attorney General and Lord Chancellor of England...
gave three fundamental conditions for ciphers. Paraphrased, these are:
- 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.
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 easily usable for protection of brief information such as a key word or a key number in such a use.Giambattista della Porta
Giambattista della Porta , also known as Giovanni Battista Della Porta and John Baptist Porta, was an Italian scholar, polymath and playwright who lived in Naples at the time of the Scientific Revolution and Reformation....
.
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 is 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 (i.e., 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
Voynich manuscript
The Voynich manuscript, described as "the world's most mysterious manuscript", is a work which dates to the early 15th century, possibly from northern Italy. It is named after the book dealer Wilfrid Voynich, who purchased it in 1912....
. It is an area of cryptography that David Kahn termed enigmatology and touches on the works of Dr John Dee
John Dee (mathematician)
John Dee was an English mathematician, astronomer, astrologer, occultist, navigator, imperialist and consultant to Queen Elizabeth I. He devoted much of his life to the study of alchemy, divination and Hermetic philosophy....
and ciphers supposedly embedded in the works of Shakespeare proving that Francis Bacon
Baconian theory
The Baconian theory of Shakespearean authorship holds that Sir Francis Bacon, lawyer, philosopher, essayist and scientist, wrote the plays conventionally attributed to William Shakespeare, and that the historical Shakespeare was merely a front to shield the identity of Bacon, who could not take...
wrote them, which William F. Friedman
William F. Friedman
William Frederick Friedman was a US Army cryptographer who ran the research division of the Army's Signals Intelligence Service in the 1930s, and parts of its follow-on services into the 1950s...
examined and discredited.
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.
Padding (cryptography)
-Classical cryptography:Official messages often start and end in predictable ways: My dear ambassador, Weather report, Sincerely yours, etc. The primary use of padding with classical ciphers is to prevent the cryptanalyst from using that predictability to find cribs that aid in breaking the...
). 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.
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.Edouard Fleissner von Wostrowitz
Edouard Fleissner von Wostrowitz , also spelt Fleißner, is remembered as the author of a short book on cryptography and as the proponent of a modified Cardan grille known as a turning grille. See Grille...
, 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 World War I. These grilles are often named after Fleissner, although he took his material largely from a German work, published in Tübingen in 1809, written by Klüber who attributed this form of the grille to Cardano.
Bauer notes that grilles were used in the 18th century, for example in 1745 in the administration of the Dutch Stadthouder William IV. Later, the mathematician C. F. Hindenburg studied turning grilles more systematically in 1796. '[they]are often called Fleissner grilles in ignorance of their historical origin.'
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
Jules Verne
Jules Gabriel Verne was a French author who pioneered the science fiction genre. He is best known for his novels Twenty Thousand Leagues Under the Sea , A Journey to the Center of the Earth , and Around the World in Eighty Days...
used a turning grille as a plot device in his novel Mathias Sandorf
Mathias Sandorf
Mathias Sandorf was an 1885 adventure book by French writer Jules Verne. It was first serialized in Le Temps in 1885, and it was Verne's epic Mediterranean adventure. It employs many of the devices that had served well in his earlier novels: islands, cryptograms, surprise revelations of identity,...
, published in 1885. Verne had come across the idea in Fleissner’s treatise Handbuch der Kryptographie which appeared in 1881.
Fleissner Grilles were constructed in various sizes during World War I 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
Luigi Sacco
Luigi Sacco was an Italian general and cryptanalyst.-References:...
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
Bifid cipher
In classical cryptography, the bifid cipher is a cipher which combines the Polybius square with transposition, and uses fractionation to achieve diffusion...
or Four-Square
Four-square cipher
The four-square cipher is a manual symmetric encryption technique. It was invented by famous French cryptographer Felix Delastelle.The technique encrypts pairs of letters , and thus falls into a category of ciphers known as polygraphic substitution ciphers...
, with considerable increase in security.
Grille ciphers are also useful device for transposing Chinese characters; they avoid the transcription of words into alphabetic or syllabic characters to which other ciphers (for example, substitution cipher
Substitution cipher
In cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a regular system; the "units" may be single letters , pairs of letters, triplets of letters, mixtures of the above, and so forth...
s) can be applied.
After World War I, machine encryption made simple cipher devices obsolete, and grille ciphers fell into disuse except for amateur purposes. Yet, grilles provided seed ideas for transposition ciphers that are reflected in modern cryptography.
The d'Agapeyeff cipher
The unsolved D'Agapeyeff cipherD'Agapeyeff cipher
The D'Agapeyeff cipher is an as-yet unbroken cipher that appears in the first edition of Codes and Ciphers, an elementary book on cryptography published by the Russian-born English cartographer Alexander D'Agapeyeff in 1939....
, 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.
A Third-Party Grille: the crossword puzzle
The distribution of grilles, an example of the difficult problem of key exchangeKey exchange
Key exchange is any method in cryptography by which cryptographic keys are exchanged between users, allowing use of a cryptographic algorithm....
, 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.
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. Letters and numbers in a random grid can take shape without substance. 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 grille present problems which are common to all transposition ciphers. Frequency analysis
Frequency analysis
In cryptanalysis, frequency analysis is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers....
will 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 transposition pattern and so decrypt 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.