Click for homepage
← SpellMaster
  
SpellMaster
Encryption algorithm · challenge

SpellMaster is a pocket lexicon from the mid-1980s. It has a simple built-in encryption algorithm that allows messages up to 25 characters to be encrypted or decrypted, subject to an 8 character key word. The algorithm is coded in Z80 assembler and is stored in a ROM that is soldered onto the PCB. So far, no attempt has been made to read out the ROM, as its type number is unknown.

Some of the source code of the encryption algorithm is listed in US Patent 4,891,775 that was filed in May 1988. See pages 16 and 17 of the PDF. The listing contains C-code in the comments, followed by the actual implementation in Z80 assembler. It is clear though, that the actual code in the ROM is different from the listing, as it yields different results. This page is an attempt to list some of the aspects of the algorithm that we were able to extract from the listing.

If anyone want to try to create a working simulator, we have listed some known PT/CT pairs, along with the corresponding key, further down this page. If you succeed this challenge, please let us know and we will happily add your efforts to this page.

Solutions

1

Python
Xavier Bonnetain

2

C-code
Michael Meyer

3

BBC BASIC
Paul Reuvers
  
Algorithm
The diagram below shows the construction of the algorithm and the order in which the events take place. The diagram is constructed partly from the recovered code and partly from recreated (working) simulations. In the first two steps, both the key and the plaintext are entered. The key is then expanded, whilst the plaintext is translated using a lookup table. Once this is done, the translated plaintext is converted to the numeric range 0-27. The keyword is then used to calculate the key, which is combined with the plaintext character to form the ciphertext.

SpellMaster algorithm for encryption

After each full conversion, the key is modified for the next round. This is done by adding the converted plaintext character to the current key, shifting all characters of the keyword one position to the left, and adding the new key at the rightmost position.

Sequence of events when encrypting
  1. Enter a keyword with up to 8 characters (A-Z)
  2. Enter the plaintext with up to 25 characters (A-Z, '-' or '?')
  3. Expand key to full 8-character length (if necessary) 1
  4. Translate plaintext using lookup table 2
  5. Convert translated plaintext from ASCII to 0-27 range 3
  6. Calculate key (K) by adding the 8 individual key characters (mod 28) 4,5
  7. Select a character from the converted plaintext (P)
  8. Subtract this character (P) from the calculated key (K) → (K-P)
  9. Store (K-P) mod 28 as the ciphertext result 4
  10. Calculate the key modifier by adding plaintext (P) to key (K) mod 28 4
  11. Left-shift keyword and add the result from the previous step at the right
  12. If there are more plaintext characters, goto step 7, else goto step 13
  13. Convert result from 0-27 range to ASCII
  1. Key expansion
    Any key that is shorter than 8 characters, will be repeated until all 8 positions are filled. This means that
    'AAA'
    will have the same effect as key '
    AAAAAAAA
    ', but '
    ABC
    ' will be expanded to
    'ABCABCAB'
    The default key (after installing new batteries) is '
    FRANKLIN
    '.
  2. Lookup tables
    There are two lookup tables that translate the input and output characters respectively. In the code these are identified as EncodeXlate and DecodeXlate. The contents of these tables are currently unknown, but theoretically it should be possible to reconstruct them from the known PT/CT pairs.
  3. 28 possible characters
    Note that the plaintext can contain 28 different characters: the 26 letters of the alphabet (A-Z), plus the hyphen (-) and question mark (?). This is different from the code published in the patent. The keyword can only contain the 26 letters of the alphabet, but its intermediate result can contain all 28 characters.
  4. MOD 28
    At various places in the code the modulo 28 of the intermediate result is calculated. Note that this is performed on a signed byte (8-bit) register and that the result will always be positive (or zero), unlike on most (modern) compilers. For this reason, it might be better to implement the modulo function manually.
  5. Signed bytes
    Note that at various places in the code, in particular when calculating the (modified) key, a signed byte (actually a
    signed char
    ) is used to store the intermediate result. Note that computers and C-compilers may behave differently when using a regualar
    char
    . Depending on the implementation, a
    char
    can be
    signed
    or
    unsigned
    . In this case, it must be
    signed
    .

Recovered code
Below is (some of) the C-code that we were able to recover from the source listing in US Patent 4,891,775. Note that this code is not complete and does not produce correct results.

      // definitions
      define CODEWORDSIZE 8;
      define WORDBUFSIZE 26;
      
      // global variables
      char CodeWord[CODEWORDSIZE + 1];
      char WorkWord[WORDBUFSIZE + 1];
      
      void StoreCodeWord (word) {
        char *word;
        char i;
        char j;
        char length;
      
        length = strlen(word);
        j = 0;
      
        for (i = 0; i < CODEWORDSIZE; i++) {
          CodeWord[i] = *(word + j);
          j++;
          if (j >= length) j = 0;
        }
        CodeWord[CODEWORDSIZE] = 0;
      
      }
      
      
      void InitCodeword (void) {
        StoreCodeWord("FRANKLIN");
      }
      
      
      void EncodeWord (void) {
        DoCipher(0);
      }
      
      
      void DecodeWord (void) {
        DoCipher(1);
      }
      
      
      void DoCipher (dir) {
        char key;
        char i;
        char j;
        char length;
        char [tempcode[CODEWORDSIZE + 1];
      
        length = strlen(word_buf);
         
        // Convert input text to 0-27 range
        for (i = 0; i < length; i++) {
          if (dir == 0) {
            word_buf[i] = EncodeXlate[word_buf[i] - 'A'];
          }
          else {
            word_buf[i] = word_buf[i] - 'A';
          }
        }
      
        // Take copy of the key
        strcpy(tempcode, CodeWord);
      
        // Encrypt or decrypt the text
        for (i = 0; i < length; i++) {
      
          // Calculate key
          key = 0;
          for (j = 0; j < CODEWORDSIZE; j++) {
            key += (tempcode[j] - 'A');
          }
          key = key mod 26;
      
          // Apply key
          WorkWord[i] = ((key - word_buf[i]) mod 26);
      
          // Modify key
          if (dir == 0) {
            key = (key + word_buf[i]) mod 26;
          }
          else {
            key = (key + WorkWord[i]) mod 26;
          }
          for (j = 1; j < CODEWORDSIZE; j++) {
            tempcode[j-1] = tempcode[j];
          }
          tempcode[CODEWORDSIZE-1] = key;
      
        }
         
        // Convert result back to ASCII range
        for (i = 0; i < length; i++) {
          if (dir == 0) {
            WorkWord[i] += 'A';
          }
          else {
            WorkWord[i] = DecodeXlate[WordWord[i]] + 'A';
          }
          WordWord[length] = 0;
        }
        ShowString{WorkWord);
      
      }
     
    

Examples of known PT/CT pairs
Key Plaintext Ciphertext
CATS DOGSDOGSDOGSDOGS WXCQ-DSUCEKQD-WU
CAT DOGSDOGSDOGSDOGS QLGAGVHPOCWEXCID
SECRECY CRYPTOMUSEUM-FOREVER LRCHZHE-GQBBSJROQ--R
SECRECY LONG-LIVE-CRYPTOMUSEUM ?HIJVVI-XLXOKRKI?SKIQX
AAAAAAAA AAAAAAAAAA VTPL?DL?HV
AAAA BBBB OTBZ
AAAAAAAA BBBBBBBBBBBBBBBB OTBZNRZNVAJRJFVR
AAA BBBBBBBBBBBBBBBBBBBBBBBBB OTBZNRZNVAJRJFVRVVOTVBBJB
AAAAAAAA BBBBBBBBBB OTBZNRZNVA
AAAAAAAA ABCDEFGHIJKLMNOPQRSTUVWXY VMHTL?QFPCBKSZCJGRZM-EEEZ
AAAAAAAA BCDEFGHIJKLMNOPQRSTUVWXYZ OLXXXIRHMTOWV-JWBPCGQEIFY
AAAAAAAA CDEFGHIJKLMNOPQRSTUVWXYZA GN?HEJTIUVSJOV-ZLVFSUYZEH
AAAAAAAA DEFGHIJKLMNOPQRSTUVWXYZAB ABHIRHMYSZVONCRTFEJSUZAHA
AAAAAAAA IS-SPELLMASTER-ALIVE? PRQGBETNKDV?EHYE-RELK
BBBBBBBB IS-SPELLMASTER-ALIVE? XERHCFUOLZWAFIZF?SM-L
Solutions
  1. 29 July 2022 (9:13) — Xavier Bonnetain
    The first one to solve the mystery is Xavier Bonnetain, a researcher in cryptography in the CARAMBA team at LORIA in Nancy (France). He made small changes to the recovered C-code and managed to reconstruct the alphabet substitution table from the published PT/CT pairs. His solution is written in the Phyton programming language.  More...

  2. 29 July 2022 (22:54) — Michael Meyer
    The second one to solve the problem independently is Michael Meyer, who was also able to reconstruct the alphabet substitution table from the published PT/CT pairs. His solution is written in the C-language and closely follows the recovered code.  More...

  3. 3 August 2022 - Paul Reuvers
    The third working simulator was made by Paul Reuvers (Crypto Museum) and is written in BBC BASIC. Paul already managed to reconstruct the translation table at the start of the challenge, but it took a little wile to grasp the concept of calculating the key in a signed byte.  More..
Further information
Any links shown in red are currently unavailable. If you like the information on this website, why not make a donation?
© Crypto Museum. Created: Tuesday 26 July 2022. Last changed: Wednesday, 03 August 2022 - 20:12 CET.
Click for homepage