Decrypt an Autokey Cipher

Question

The autokey cipher is closely related to the Vigenère cipher (both were invented by Blaise de Vigenère). Decryption involves the encrypted message and the key. For simplicity, let us assume all characters in the message and key are lowercase letters (no spaces, numbers or symbols etc.).

How to decrypt the cipher

1. Convert all letters in the message and key into their 0-indexed counterparts. For example, 'A' is converted to 0, while 'Z' is converted to 25.
2. Subtract the first letter of the key from the first letter of the message, and wrap the result to be within 0 to 25 inclusive. For example, 2 - 6 = 22.
3. Append this result to both the plaintext message and the key.
4. Repeat steps 2 and 3 for each letter in the message. Notice that after the initial key runs out, the key becomes the plaintext.
5. Convert the plaintext message back into a string of capital letters.

Challenge

Write a program or function that, when given a message encrypted using an autokey cipher and its key, outputs the decrypted plaintext message.

• The message and key both contain only letters.
• You may assume that the message and key both contain at least 1 letter, but you cannot assume that the message is longer than the key.
• You may choose to have only lowercase or only capital letters.
• You may choose to instead take the input and output strings as lists of integers from 0 to 26 inclusive, however a program that processes letters is preferred.
  • For example, hyezvazczz, auto ==> helloworld would instead be [7, 24, 4, 25, 21, 0, 25, 2, 25, 25], [0, 20, 19, 14] ==> [7, 4, 11, 11, 14, 22, 14, 17, 11, 3]
  • You may also mix between string input/output and list input/output (e.g. input as two lists, output as string)

Test Cases

(format: message, key ==> plaintext)

hyezvazczz, auto ==> helloworld
amrkegkaikmoqsuwyacegikmoq, alphabet ==> abcdefghijklmnopqrstuvwxyz
lavxxwgwgusgfaugth, amet ==> loremipsumdolorsit
nlfpe, verylongkey ==> short

Answer 1

Haskell, 39 35 bytes

m#k=(`mod`26)<$>zipWith(-)m(k++m#k)

Attempt This Online!

Takes and returns lists of ints. The test suite adds a couple functions to convert to and from strings for convenience.

Explanation

The core thing we're doing here is zipping two lists on subtraction, followed by mod 26:

m#k=(`mod`26)<$>zipWith(-)m k
m#k=                           -- Operator # takes m(essage) and k(ey):
                zipWith(-)m k  -- Subtract elementwise, clipping to shorter length
    (`mod`26)<$>               -- Mod 26 each element

But we also need to recycle the plaintext as part of the key. Haskell's lazy evaluation makes this task straightforward. Instead of using k as the key directly, we use

k++m#k
k       -- The original key
 ++     -- concatenated with
   m#k  -- the result of the decryption

Answer 2

x86-64 machine code, 27 17 bytes

EDIT: -6 bytes thanks to @Command Master noting the "upwards" modulo branch can be deleted.

EDIT: -4 bytes thanks to @Neil pointing out sub al, [rdx].

ac 2a 02 79 02 04 1a 48 ff c2 aa 48 39 ce 75 f0  
c3

Input is provided via the RDI, RSI, RDX and RCX registers:

• RSI points to the input array
• RCX points to the end of the input array
• RDX points to the key array
• RDI points to the end of the key array

Output is written to RDI; there must be enough space after the end of the key array to store the output.

Input and output are in integer array form; one byte per number.

The register allocation matches the following C function prototype using the Linux x86-64 ABI:

extern void decrypt(char* output, const char* input, const char* key, const char* inputEnd);

Disassembly (Intel Syntax):

                 decrypt:
   0:   ac            lodsb         ; read input byte
   1:   2a 02         sub al, [rdx] ; subtract key byte
                 ; manual modulo operation:
   3:   79 02         jns .no_mod   ; if non-negative, don't adjust
                                    ; value range is [-25; 25], so this is fine
   5:   04 1a         add al,26
                 .no_mod:
   7:   48 ff c2      inc rdx
   a:   aa            stosb         ; write output
   b:   48 39 ce      cmp rsi,rcx
   e:   75 f0         jne decrypt
  10:   c3            ret 

A test suite is available here.

Answer 3

05AB1E, 11 bytes

ˆε¯˜Nè-₂%Dˆ

Try it online!

Explanation

This might be the first 05AB1E program I ever wrote which properly utilizes the global array. It saves the key in the global array, and each time appends something to it.

ˆε¯˜Nè-₂%Dˆ­⁡​‎‎⁡⁠⁡‏⁠‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌­
ˆ            # ‎⁡Add the key to the global array
ε            # ‎⁢For each element in the ciphertext:
 ¯           # Push the global array
 ˜           # Flatten it, to account for the first element being a list
 N           # Push the iteration index
 è           # And index it to the global array
 -           # subtract that from the current element
 ₂%          # mod 26
 D           # create a duplicate
 ˆ           # and add it to the global array (the other one is left for the map)

Answer 4

Vyxal, 84 bits^v2, 10.5 bytes

£⟑¥ḣ£-₄%:&J

Try it Online!

Or, try a test suite

Takes key then ciphertext. Uses lists of numbers for input and output, although the test case suite uses strings for convenience.

Explained

£⟑¥ḣ£-₄%:&J­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠⁠‎⁡⁠⁢⁢‏⁠‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠⁠⁠⁠‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌­
£            # ‎⁡Put the key in the register
 ⟑           # ‎⁢For each number in the ciphertext:
  ¥ḣ -       # ‎⁣  Subtract the head of the key from the ciphertext number
   ḣ£        # ‎⁤   and behead the key
      ₄%     # ‎⁢⁡   Modulo the result by 25
        :&J  # ‎⁢⁢   and append it to the key, leaving a copy on the stack
💎

Created with the help of Luminespire.

Answer 5

Charcoal, 14 bytes

⭆θ§β↨⊞Ｏη⁻ι§ηκ⁰

Try it online! Link is to verbose version of code. Takes input as two integer arrays and outputs a string. Explanation:

 θ              Input message
⭆               Map over values and join
   β            Lowercase letters
  §             Cyclically indexed by
         ι      Current value
        ⁻       Minus
           η    Input key
          §     Indexed by
            κ   Current index
     ⊞Ｏη        Push to input key
    ↨        ⁰  Last integer (i.e. the one just pushed)
⭆               Implicitly print

16 bytes to output as an array:

Ｉ﹪Ｅθ↨⊞Ｏη⁻ι§ηκ⁰Ｌβ

Try it online! Link is to verbose version of code. Explanation: As above, but the §β is removed, ⭆ is replaced with Ｅ to generate an array rather than a string, the %Ｌβ reduces modulo 26 (a literal 26 would require a separator from the literal 0), and Ｉ casts to string for implicit print.

16 bytes to input the message as a string and the key as an array and output a string:

⭆θ§β↨⊞Ｏη⁻⌕βι§ηκ⁰

Try it online! Link is to verbose version of code. Explanation: The ⌕β converts the message from letters to integers.

23 bytes to input the key as a string:

⭆θ§⊞Ｏυ§β⁻⌕βι⌕β§⁺⪪η¹υκ±¹

Try it online! Link is to verbose version of code. Explanation:

 θ                      Input message
⭆                       Map over characters and join
       β                Lowercase letters
      §                 Cyclically indexed by
           ι            Current message letter
         ⌕β             Convert to integer
        ⁻               Minus
                 η      Input key
                ⪪ ¹     Split into characters
               ⁺        Concatenated with
                   υ    Predefined empty list
              §         Indexed by
                    κ   Current message index
            ⌕β          Convert to integer
   ⊞Ｏυ                  Push to predefined empty list
  §                  ±¹ Last value i.e. character just pushed
                        Implicitly print

I tried several interesting alternative algorithms and the next best one was 24 bytes:

≔Ｅη⟦⌕βι⟧η⭆θ§β↨⊞Ｏ§ηκ⌕βι±¹

Try it online! Link is to verbose version of code. Explanation:

≔Ｅη⟦⌕βι⟧η

Convert the key from a string to a list of lists of integers e.g. [[0], [20], [19], [14]].

⭆θ§β↨⊞Ｏ§ηκ⌕βι±¹

Convert each letter from the message to an integer, push it to the cyclically indexed key list, convert that from base -1, and convert back from an integer to a letter.

Answer 6

R, 58 51 bytes

\(m,k){for(i in seq(m))k=c(k,m[i]<-(m-k)[i]%%26);m}

Attempt This Online!

---

R, 58 bytes

f=\(m,k)if(sum(m|1))c(l<-(m-k)[1]%%26,f(m[-1],c(k[-1],l)))

Attempt This Online!

Original recursive approach.

Answer 7

Python, 55 bytes

lambda m,k:[k.append(v:=c-K)or v%26for c,K in zip(m,k)]

Uses the fact that list iterator (and so zip too) does not copy, it holds a "reference", and zip'ping a growing array works as expected here. Saves 3 bytes by moving %26 to output part — key bytes do not have to belong to \$[0;\,25]\$, modulus can be applied later. Accepts and outputs numeric lists.

Test cases taken from @SuperStormer's answer.

Attempt This Online!

Answer 8

JavaScript (ES6), 47 bytes

Expects (msg)(key) as two arrays of integers in \$[0\dots25]\$. Returns an array in the same format.

m=>k=>m.map((c,i)=>k.push(v=(c-k[i]+26)%26)&&v)

Try it online!

Answer 9

Python, 57 bytes

def f(m,k,i=0):
 for c in m:m[i]=v=(c-k[i])%26;k+=v,;i+=1

Attempt This Online!

Outputs by modifying arguments.

Answer 10

Scala, 128 124 bytes

Saved 4 bytes thanks to the comment of @SuperStormer

---

Golfed version. Try it online!

def d(c:Seq[Int],k:Seq[Int],p:Seq[Int]=Seq()):Seq[Int]=if(c.isEmpty)p else{val n=(c(0)-k(0)+26)%26;d(c.tail,k.tail:+n,p:+n)}

Ungolfed version. Try it online!

object Main {
  def decryptAutokey(cipherText: List[Int], key: List[Int]): List[Int] = {
    def decrypt(cipherText: List[Int], key: List[Int], plainText: List[Int]): List[Int] = cipherText match {
      case cipherHead :: cipherTail => 
        val newLetter = (cipherHead - key.head + 26) % 26
        decrypt(cipherTail, key.tail :+ newLetter, plainText :+ newLetter)
      
      case Nil => plainText
    }
    decrypt(cipherText, key, List())
  }

  def main(args: Array[String]): Unit = {
    val cipherText = List(7, 24, 4, 25, 21, 0, 25, 2, 25, 25)
    val key = List(0, 20, 19, 14)
    val plainText = decryptAutokey(cipherText, key)
    val plainTextChars = plainText.map(p => (p + 'a').toChar)
    println(plainTextChars.mkString(""))
  }
}