Reprinted from: http://acm.uva.es/p/v7/795.html
 
  Sandorf's Cipher 

[Converted with LaTeX2HTML 98.1 release (February 19th, 1998) originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds - revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan - with significant contributions from: Jens Lippmann, Marek Rouchal, Martin Wilck and others.]

Count Mathias Sandorf, a hero of Jules Verne, encrypted the secret messages of the Trieste conspirators by using a cipher key a 6$\times$6 hard paper square with some holes in it. In figure 1 the holes are marked white. One edge of the cipher key has a pinch-mark. Empty messages are coded as empty strings. For encrypting a non empty message follow the Sandorf's algorithm below.

Figure 1: Sandorf's cipher key

1. Extend the message, by appending trailing `#' characters, until its length equals a multiple of 36, and then reverse the extended message. By convention, original messages do not end with # but, however, they can contain #. For example, the message:

Real Programmers use Fortran. Quiche Eaters use Pascal. is 55 characters long and has to be extended by appending 17 trailing #. Right after step 1, the message is:

#################.lacsaP esu sretaE ehciuQ . nartroF esu sremmargorP laeR

2. Position the cipher key on a sheet of paper, the pinch-mark facing upwards.

3. Copy the next 9 characters from the message (initially the first 9 characters) onto the paper through the holes of the cipher key, one character per hole, from left to right and top to bottom.

4. Turn the cipher key 90 degrees clockwise and repeat from step 3 until the key gets to its initial position, with the pinch-mark up. The result is a 6$\times$6 matrix of characters, called a coded group.

5. Repeat from step 2 until all characters of the message are copied into coded groups, then append the rows of the coded groups from the first row of the first generated coded group to the last row of the last generated coded group, following the order of rows in each group and the order of groups. For the given message there are two coded groups, shown below,

 

 

u#l# #   

geuhoc

as#r## 

raPir

ec##st

sutrl

##aa##  

rQae o

EP# ## 

emFR .

#e#s.

meanrs

which, when appended, yield the final encrypted message:

u#l# #as#r##ec##st##aa##EP# ## #e#s.geuhoc raPir sutrlrQae oemFR .meanrs

Input and Output 

Write a program that decrypts messages encrypted by using the Sandorf's algorithm. The encrypted messages are read from a text file, one message per line ending with a line-break. Lines can be of different length. All characters of a line (except the line-break) are part of the encrypted message which cannot exceed 108 characters. The decrypted messages are printed on the standard output file. Each output line contains a message in its original form, starting from the beginning of the line. Decoding the above encrypted message yields the result:

Real Programmers use Fortran. Quiche Eaters use Pascal.

Sample Input 

irdetn ihtoteao  pesms soiaCet snaoi  
#e#r# edt#aasdrtltn ca reyor feneiv
o#kginasksoaemlt f  odatrnip  as ene
w#lerhiomfte t rSp se ntt.is id,raal
o#r#i#etbanagvareioml  nbfooheo  lny
e# #s#holp#lpt#iiok# w#so  ts.tiis h

H### ##d#l##a####n##o)##Dg#(##i#n#o#

Sample Output 

Competition is a disease that sooner
or later infects every trade and
profession and makes it take a long
step forward. Still, it remains the
obligation of every honorable man
to oppose it with his skills.

(Donald Honig)
Miguel Revilla
2001-01-05