Problem of the Day -- Transposition Cipher

Transposition Cipher

One example of a transposition cipher is columnar transposition. The cipher works like this:

Pick a keyword
Lay your message out character by character in rows the same length of your key
Extra room can be filled by random characters
Arrange the columns according to the value of the character in the key (eg. socket = 541326)
Arrange the columns into rows

Here is an example using the key "socket" and the message "canyouprogramthis":

s o c k e t
c a n y o u
p r o g r a
m t h i s t

noh ors ygi art cpm uat

"noh" corresponds to the 3 characters below the letter "c" in "socket". Alphabetically speaking, "c" comes before the other letters in the word "socket" so the letters underneath it go first in the encrypted message.

Today's goal is to create a function that takes in a key (socket) and an encrypted message (noh ors ygi art cpm uat) and outputs the unencrypted message (canyouprogramthis).

As a bonus problem see if you can figure out the key for this message:

heeilsef twkdaohe eensmtry

Permalink: http://problemotd.com/problem/transposition-cipher/

Comments:

Daniel - 10 years, 8 months ago
The fun thing about this is that the key just needs to be the same length as the number of 'words'. For example, the key for "heeilsef twkdaohe eensmtry" can be any 3 letter word where the second letter comes earlier in the alphabet than the first, and the last letter comes later than the previous two letters in the alphabet. The words 'sky' and 'try' both work as a key, and even the word 'key' does. I'll write up the code for this later on today.

reply permalink
Max Burstein - 10 years, 8 months ago

haha yes indeed. As you can see it's not a very secure means of encryption.

reply permalink

Anonymous - 10 years, 8 months ago

Fun problem. In J:

decrypt=: dyad define
  , (/:^:2 x) {"1 |: > ' ' chopstring y
)

'socket' decrypt 'noh ors ygi art cpm uat'  NB. => canyouprogramthist

reply permalink

Max Burstein - 10 years, 8 months ago

Any chance you could explain how that works? J seems like a magical language

reply permalink
Anonymous - 10 years, 8 months ago
Lol sure. decrypt is a function. Inside the function body, x and y represent the left and right argument passed to the function. J is read from right to left:
```
' ' chopstring y    chop ciphertext y into words using space as delimiter
>                   unpack the individual words as rows of a matrix
|:                  transpose the matrix
```
The parenthesised expression on the left is
```
/:^:2 x             twice "grade" the key x
```
which yields 4 3 0 2 1 5, the ordered column indices that will "decrypt" the rows.

Then, {"1 uses this "grade" to put every row of the matrix into the order 4 3 0 2 1 5. Finally, the comma strings the rows of the matrix together to yield the decrypted message.

I'm just learning a little J for the giggles, sure bends the mind in a good way though :)

reply permalink
Max Burstein - 10 years, 8 months ago

Thanks for the explanation. It definitely is mind bending

reply permalink

toph - 10 years, 8 months ago

I'm just learning perl, but here we go. Also noticed that this only works if the key has unique letters, as "sockets" or "bookkeeper" you wouldn't be able to tell which of the same letters came first.

#!perl


my $key = "socket"; #<STDIN>;
my $encrypted = "noh ors ygi art cpm uat"; #<STDIN>;

my @groups = split ' ', $encrypted;

my @key_letters = split '', $key;

my %hash;

my $i = 0;
foreach my $letter (sort @key_letters) {
    $hash{$letter} = $groups[$i++];
}

for($i = 0; $i < length $hash{'s'}; $i++) {
    foreach (@key_letters) {
        print substr($hash{$_}, $i, 1);
    }
}

reply permalink

Hueho - 10 years, 8 months ago

# Code for ciphering

# Create character matrix from text
def matrixfy(text, len)
  desired = (text.size.to_f / len).ceil * len
  text.downcase.ljust(desired, "x").chars.each_slice(len).to_a
end

# Convert to matrix, sort columns according to corresponding key characters
def cipher(message, key)
  m = matrixfy(message, key.size).unshift(key.chars).transpose  
  m.sort_by! { |column| column.first }
  m.each { |column| column.shift }  
  m.map(&:join).join(' ')
end

# Code for deciphering

# Pack array as hash where keys are elements and values are indexes
def pack_as_hash(arr)
  result = {}
  arr.each_with_index { |e, i| result[e] = i }
  result
end

# Return array representing ordering
def order(str)
  chars = str.chars
  new_order = pack_as_hash(chars.sort)
  chars.each_with_object([]) { |chr, result| result << new_order[chr] }
end

# Reorder columns according to key
def decipher(message, key)
  m = message.split(' ').map!(&:chars)
  o = order(key)
  r = Array.new(key.size)
  o.each_with_index { |e, i| r[i] = m[e] }
  r.transpose.map(&:join).join
end

# Bruteforce and output results - due to how keys are used,
# we just use permutations of a sequence of numbers from 1 to the key
# length - we can find the key size just looking at the ciphered message
def brute_force(message)
  len = message.split(' ').size
  keys = ('1'..len.to_s).to_a.permutation.map(&:join)
  keys.each_with_object({}) { |k, result| result[k] = decipher(message, k) }
end

# Alternative way to cipher - meant to show that ciphering and deciphering
# this way is pretty much opposite operations
def alt_cipher(message, key)
  m = matrixfy(message, key.size).unshift(key.chars).transpose  
  o = order(key)
  r = Array.new(key.size)
  o.each_with_index { |e, i| r[e] = m[i] }
  m.map(&:join).join(' ')
end

reply permalink

Hueho - 10 years, 8 months ago
Oops, last line on alt_cipher should be: m.map(&:join).join(' ')

reply permalink
Hueho - 10 years, 8 months ago
...r.map

My bad.

reply permalink

Adam - 10 years, 8 months ago

A Haskell solution:

module Main where

import System.Environment
import Data.List (elemIndex, sort, transpose)


type Key = String
type EncodedMessage = String
type DecodedMessage = String


main :: IO ()
main = do
    args <- getArgs
    progName <- getProgName
    case args of
        [key, message] -> putStrLn . output $ decode key message
        _     -> putStrLn $ "Usage: " ++ progName ++ " key message"
    where output (Just decodedMessage) = decodedMessage
          output Nothing = "Invalid message or key"


decode :: Key -> EncodedMessage -> Maybe DecodedMessage
decode key input = do
    let columns = words input
    order <- orderKey key
    sortedColumns <- reorder columns order
    return $ concat . transpose $ sortedColumns


-- eg. socket -> [4, 3, 0, 2, 1, 5]
orderKey :: Key -> Maybe [Int]
orderKey key = mapM orderChar key where
    orderChar c = elemIndex c sortedKey
    sortedKey = sort key


reorder :: [String] -> [Int] -> Maybe [String]
reorder inputs indices
    | all (< length inputs) indices =
        Just $ foldr reorder' [] indices where
            reorder' index accum = inputs !! index : accum
reorder inputs indices
    | otherwise = Nothing

reply permalink

Isi - 10 years, 8 months ago
I made an encrypt script for this in python, which was really fun, but there was really no need to code anything to solve for "heeilsef....", since all the possible alternations of they key can be guessed by looking at the number of groups of N letters.

reply permalink

gulliver - 10 years, 8 months ago

A little late (the weekend is not almost here anymore) but here's my effort:

import itertools
import string  
def solve_transposition_cipher(message, key):
    '''
    this decodes the message
    the message will have spaces in between words
    '''
    message_list = message.split()
    n_col = len(key)
    n_row = len(message_list[0])

    key_list = list(key)
    index_list = range(0,n_col)
    zipped = zip(key_list, index_list)
    zipped_list = sorted(zipped)

    decoded = [''] * (n_col * n_row)
    for i in range(n_row):
        for j in range(n_col):
            col_index = zipped_list[j][1]
            decoded[i*n_col+col_index] = message_list[j][i]
    print ''.join(decoded)

def solve_unknown_message(message):
    message_list = message.split()
    n_col = len(message_list)
    possible_alphabet = string.lowercase[:n_col]
    possible_keys = list(itertools.permutations(possible_alphabet,n_col))
    for i in possible_keys:
        solve_transposition_cipher(message,i)

reply permalink

Byron - 10 years, 7 months ago

I think its a little messy but it gets the job done :) Python!

import math
import random
import string

def EncryptMessage( aKey, aMessage ):
    concatStr = aKey + aMessage
    msgLength = aMessage.__len__()
    keyLength = aKey.__len__()
    matrixrows = math.ceil(msgLength / keyLength) + 1

    # The concat string has to be equal rows so we need to add filler #
    for x in range((keyLength - (msgLength % keyLength))):
        concatStr += random.choice(string.ascii_letters).lower()


    # Make the matrix to hold our values
    Matrix = [[ concatStr[x + (y * keyLength)] for x in range(keyLength)] for y in range(matrixrows)]

    # Get our cyphers
    cyphers = []

    # The cyper is made of a row of letters and we build it here
    for cols in range(keyLength):
         cyp = ""
         for rows in range( matrixrows ):
             cyp += Matrix[rows][cols]

         # We want to ignore the first key value
         cyphers.append( cyp )

    # Now we sort the cypers using socket
    cyphers.sort()

    # Remove the socket letters
    for x in range(keyLength):
        cyphers[x] = cyphers[x][1:]

    return " ".join(cyphers)


def DecryptMessage( aKey, encrypt):
    encryptLength = encrypt.__len__()
    keyLength = aKey.__len__()
    matrixrows = math.ceil( encryptLength/ keyLength)


    sortedKey = list(aKey)
    sortedKey.sort()


    msgList = encrypt.split()

    #Add the key to the start of the list
    for x in range(keyLength):
        msgList[x] = sortedKey[x] + msgList[x]

    #Now we have to find the original place
    isSorted = False
    concatStr = []

    while not isSorted:
        isSorted = True
        for x in range(keyLength):
            for y in range(keyLength):
                if msgList[x][0] == aKey[y] and x != y and msgList[x][0] != msgList[y][0]:
                    msgList[x], msgList[y] = msgList[y], msgList[x]
                    isSorted = False
                    break

    msgList = ''.join(msgList)



    for x in range(keyLength):
        for y in range(matrixrows):
            concatStr.append( msgList[(x * matrixrows) + y] )



    Matrix = [[ concatStr[(x * matrixrows)+ y] for x in range(keyLength)] for y in range(matrixrows)]

    return ''.join(str(Matrix))

key = "BobbySimmons"
message = "youwillnevergitthisoneiamsureofitifyoudoyouareagod"



print("Key: " + key)
print("Message: " + message)

# First we encrypt the message
encryptedMsg = EncryptMessage( key, message )

print( "" )
print( "-= Encryped Message =- " )
print( encryptedMsg )

print( "" )
print( "-= Decryped Message =- " )
decryptedMsg = DecryptMessage( key, encryptedMsg )
print( ''.join(decryptedMsg) )

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

Transposition Cipher

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri