Practical: Writing a Substitution and a Transposition Cipher
Chapter Fifty
Syllabus topic Computer Science Practical 5, Module 2, "Implementing Substitution and Transposition Ciphers"
Pages 306 to 310 of 678
The exercise, as MU sets it
Practical 5's first exercise reads: "Implementing Substitution and Transposition Ciphers: Design and implement algorithms to encrypt and decrypt messages using classical substitution and transposition techniques."
Three words in that sentence decide what the submission must contain. Algorithms, plural, so both families. Encrypt and decrypt, so the inverse must work, not only the forward direction. And design, so the key handling and the error cases are part of the work rather than an afterthought.
The program, in journal form
# Practical 1: substitution and transposition ciphers.
# Journal form: one program, both ciphers, encryption and decryption, with the
# input validation and the error cases a submission is marked on.
ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def clean(text):
"""Letters only, upper case. Everything else is discarded."""
return "".join(c for c in text.upper() if c in ALPHABET)
# ---------- substitution: the Caesar cipher, with a validated key -------------
def caesar(text, key, decrypt=False):
if not isinstance(key, int) or not 1 <= key <= 25:
raise ValueError("the Caesar key must be a whole number from 1 to 25")
k = -key if decrypt else key
return "".join(ALPHABET[(ALPHABET.index(c) + k) % 26] for c in clean(text))
# ---------- transposition: row transposition, with a validated key -----------
def check_perm(key):
digits = [int(d) for d in str(key)]
n = len(digits)
if sorted(digits) != list(range(1, n + 1)):
raise ValueError("the key must be a permutation of 1 to %d, not %r" % (n, key))
return digits
def row_encrypt(text, key, pad="X"):
order = check_perm(key)
n = len(order)
t = clean(text)
t += pad * (-len(t) % n)
grid = [t[i:i + n] for i in range(0, len(t), n)]
out = ""
for label in range(1, n + 1):
col = order.index(label)
out += "".join(row[col] for row in grid)
return out, grid
def row_decrypt(text, key):
order = check_perm(key)
n = len(order)
t = clean(text)
if len(t) % n:
raise ValueError("the ciphertext length %d is not a multiple of %d"
% (len(t), n))
rows = len(t) // n
cols, at = {}, 0
for label in range(1, n + 1):
cols[order.index(label)] = t[at:at + rows]
at += rows
return "".join("".join(cols[c][r] for c in range(n)) for r in range(rows))
# ------------------------------- the run --------------------------------------
plain = "Meet me after the toga party"
print("AIM: encrypt and decrypt a message by a substitution cipher and by a")
print(" transposition cipher, and show that each recovers the plaintext.")
print()
print("INPUT")
print(" plaintext :", plain)
print(" cleaned :", clean(plain))
print()
print("PART A, SUBSTITUTION: the Caesar cipher, key 3")
c = caesar(plain, 3)
print(" ciphertext :", c)
print(" decrypted :", caesar(c, 3, decrypt=True))
print(" recovered :", caesar(c, 3, decrypt=True) == clean(plain))
print()
print("PART B, TRANSPOSITION: row transposition, key 4312567")
ct, grid = row_encrypt(plain, 4312567)
print(" the grid, with the key across the top:")
print(" 4 3 1 2 5 6 7")
for row in grid:
print(" " + " ".join(row))
print(" read the columns in label order 1 to 7:")
print(" ciphertext :", ct)
print(" decrypted :", row_decrypt(ct, 4312567))
print(" recovered (with the padding X's):",
row_decrypt(ct, 4312567).rstrip("X") == clean(plain))
print()
print("PART C: the letter counts, which identify which cipher was used")
def counts(s):
return {ch: s.count(ch) for ch in sorted(set(s))}
print(" plaintext counts equal the TRANSPOSITION's counts:",
counts(clean(plain)) == counts(row_decrypt(ct, 4312567).rstrip("X")))
print(" and differ from the SUBSTITUTION's:",
counts(clean(plain)) != counts(c))
print()
print("PART D: the error cases, which a submission is marked on")
for bad_call, label in (
(lambda: caesar(plain, 0), "Caesar key 0"),
(lambda: caesar(plain, 26), "Caesar key 26"),
(lambda: caesar(plain, "three"), "Caesar key 'three'"),
(lambda: row_encrypt(plain, 4312568), "row key 4312568, no 7"),
(lambda: row_decrypt("ABCDE", 4312567), "ciphertext not a multiple of 7")):
try:
bad_call()
print(" %-32s accepted, WHICH IS A BUG" % label)
except ValueError as e:
print(" %-32s rejected: %s" % (label, e))
print()
print("CONCLUSION: both ciphers encrypt and decrypt correctly. The substitution")
print("changes the letters and the transposition only their order, which the")
print("letter counts in Part C demonstrate. Both are broken and neither may be")
print("used to protect anything; they are on the syllabus for the ideas.")Practical: Writing a Substitution and a Transposition Cipher
AIM: encrypt and decrypt a message by a substitution cipher and by a
transposition cipher, and show that each recovers the plaintext.
INPUT
plaintext : Meet me after the toga party
cleaned : MEETMEAFTERTHETOGAPARTY
PART A, SUBSTITUTION: the Caesar cipher, key 3
ciphertext : PHHWPHDIWHUWKHWRJDSDUWB
decrypted : MEETMEAFTERTHETOGAPARTY
recovered : True
PART B, TRANSPOSITION: row transposition, key 4312567
the grid, with the key across the top:
4 3 1 2 5 6 7
M E E T M E A
F T E R T H E
T O G A P A R
T Y X X X X X
read the columns in label order 1 to 7:
ciphertext : EEGXTRAXETOYMFTTMTPXEHAXAERX
decrypted : MEETMEAFTERTHETOGAPARTYXXXXX
recovered (with the padding X's): True
PART C: the letter counts, which identify which cipher was used
plaintext counts equal the TRANSPOSITION's counts: True
and differ from the SUBSTITUTION's: True
PART D: the error cases, which a submission is marked on
Caesar key 0 rejected: the Caesar key must be a whole number from 1 to 25
Caesar key 26 rejected: the Caesar key must be a whole number from 1 to 25
Caesar key 'three' rejected: the Caesar key must be a whole number from 1 to 25
row key 4312568, no 7 rejected: the key must be a permutation of 1 to 7, not 4312568
ciphertext not a multiple of 7 rejected: the ciphertext length 5 is not a multiple of 7
CONCLUSION: both ciphers encrypt and decrypt correctly. The substitution
changes the letters and the transposition only their order, which the
letter counts in Part C demonstrate. Both are broken and neither may be
used to protect anything; they are on the syllabus for the ideas.Practical: Writing a Substitution and a Transposition Cipher
What each part is for, and what it earns
Part A, the substitution. The Caesar cipher, because it is the cipher the theory chapters introduced first and because it can be checked by eye. clean() strips everything that is not a letter, which is the decision the exercise calls design: a submission that crashes on a space has not designed anything.
Part B, the transposition. Row transposition with the key 4312567, which the theory chapter worked. The grid is printed with the key across the top, because the marking of this exercise turns on whether the columns were read in label order, and printing the grid makes it checkable.
Part C, the identification. The letter counts of the plaintext match the transposition's exactly and differ from the substitution's. That single comparison is the answer to "how would you tell which kind of cipher was used", and it is worth including because the question is asked.
Part D, the error cases. Five bad inputs, all rejected with a message that says what was wrong: a Caesar key of 0, of 26, of the wrong type; a row key that is not a permutation; and a ciphertext whose length is not a multiple of the key length. Note what the program prints if a bad input is accepted: "accepted, WHICH IS A BUG". A test that cannot fail is not a test, and the same rule that governs this book's checkers governs a journal's own tests.
The write-up MU's internal assessment expects
The internal 20 marks are two class tests and two assignments, and an assignment on this module is normally the journal. So the write-up matters as much as the code.
Aim. One sentence. What is being implemented and what will be demonstrated.
Theory, in three or four sentences. A substitution replaces symbols and keeps positions; a transposition keeps symbols and changes positions; the Caesar cipher shifts by a fixed amount modulo 26; row transposition writes in rows of n and reads the columns in the order the key labels them.
Algorithm. Numbered steps for each cipher, in words, before the code.
Program. The listing.
Output. What it printed, copied exactly.
Conclusion. That both ciphers encrypt and decrypt correctly; that the letter counts distinguish them; and, importantly, that both are broken and neither may be used to protect anything. A conclusion that recommends the Caesar cipher has failed the subject rather than the exercise.
Practical: Writing a Substitution and a Transposition Cipher
Viva questions this exercise attracts, with their answers
"Why 26 in the modulus?" Because the alphabet has 26 letters and the cipher is arithmetic on letter positions, so the arithmetic wraps at 26.
"What if the key is 26?" A shift of 26 is a shift of 0, so the ciphertext equals the plaintext. That is why the program rejects it and why the keyspace is 25 and not 26.
"Why did you pad the last row?" Because the columns must be equal in length for the ciphertext to be read and written back unambiguously. The padding character must be one the receiver can recognise and remove, which is why X is conventional.
"Your decryption returned the padding. Is that a bug?" No, it is what the algorithm returns. Removing it is a separate step that requires knowing the original length or recognising the padding, and a submission should say which it chose.
"How would you break each of these?" The Caesar cipher by trying all 25 keys. The transposition by recognising from the letter counts that it is a transposition, guessing the number of columns, and searching the column orders with digram frequencies as the score.
"Why not use these ciphers?" Because the Caesar keyspace is 25 and a transposition preserves letter frequencies exactly, so both are broken in minutes by hand.
Quick revision
- MU's exercise wants both families, both directions, and design, which means key validation.
- Journal form: aim, theory, algorithm, program, output, conclusion.
clean()first: letters only, upper case. A program that crashes on a space has not been designed.- Print the grid with the key above it, because the marking turns on reading the columns in label order.
- Letter counts identify the family: identical to the plaintext's means a transposition.
- Test the error cases, and make the test say so when a bad input is accepted.
- Reject a Caesar key outside 1 to 25, a row key that is not a permutation, and a ciphertext whose length is not a multiple of the key length.
- The conclusion must say both ciphers are broken.
Test yourself
1. What does MU's exercise require beyond encryption? Decryption, since it asks for algorithms to encrypt and decrypt; both families, since it names substitution and transposition; and design, which covers validating the key and handling input that is not plain letters.
2. Why must the Caesar key be restricted to 1 to 25? Because a key of 0 or 26 leaves the message unchanged, and any key is equivalent to its remainder modulo 26, so the distinct useful keys are exactly 1 to 25. A program accepting 0 or 26 would report an encryption that had not encrypted.
Practical: Writing a Substitution and a Transposition Cipher
3. Why is the last row of a row transposition padded? So that every column has the same number of letters. Without that, the receiver cannot tell how many letters belong to each column, and the ciphertext cannot be written back into the grid unambiguously.
4. How do the letter counts distinguish the two ciphers? A transposition only rearranges letters, so the ciphertext's letter counts are exactly the plaintext's. A substitution replaces letters, so its counts are a relabelling and generally differ from the plaintext's. Comparing the counts therefore identifies which family produced a ciphertext.
5. Name three error cases this program must reject. A Caesar key outside the range 1 to 25, or one that is not a whole number; a row transposition key that is not a permutation of 1 to n, such as 4312568, which has no 7; and a ciphertext presented for row decryption whose length is not a multiple of the key length.
6. What should the conclusion of this journal say? That both ciphers encrypt and decrypt correctly and that the letter counts distinguish them; and that both are broken, the Caesar cipher by exhaustive search of 25 keys and the transposition by recognising it from the letter counts and searching the column orders, so neither may be used to protect anything.
7. Your decryption returns MEETMEAFTERTHETOGAPARTYXXXXX. Is the program wrong? No. The trailing X's are the padding the encryption added to fill the last row, and returning them is what the algorithm does. Removing them is a separate decision which requires either knowing the original length or recognising the padding character, and the journal should state which was chosen.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.