|
|
|
|
← 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.
|
1Python Xavier Bonnetain 2C-code Michael Meyer 3BBC BASIC Paul Reuvers
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.
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
|
 |
 |
- Enter a keyword with up to 8 characters (A-Z)
- Enter the plaintext with up to 25 characters (A-Z, '-' or '?')
- Expand key to full 8-character length (if necessary) 1
- Translate plaintext using lookup table 2
- Convert translated plaintext from ASCII to 0-27 range 3
- Calculate key (K) by adding the 8 individual key characters (mod 28) 4,5
- Select a character from the converted plaintext (P)
- Subtract this character (P) from the calculated key (K) → (K-P)
- Store (K-P) mod 28 as the ciphertext result 4
- Calculate the key modifier by adding plaintext (P) to key (K) mod 28 4
- Left-shift keyword and add the result from the previous step at the right
- If there are more plaintext characters, goto step 7, else goto step 13
- Convert result from 0-27 range to ASCII
|
 |
-
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 '.
-
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.
-
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.
-
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.
-
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 .
|
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
|
|
- 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...
- 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 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..
|
|
|
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.
|
 |
|
|
|
|