Solving a Numbered Key Cipher[1] by MATANZA
BION in the May June 2010 edition of the Cryptogram magazine introduced the "Numbered Key Cipher"[2]. The article in a slightly different form is accessable at this website under the title "The Numbered Key Cipher". The cipher uses an extended key including repeated letters followed by the unused letters ('residual') in alphabetical order for a plaintext alphabet set against displaced consecutive numbers for the ciphertext. This gives multiple choices for substitution.
In solving, it is quite helpful to be able to estimate the length of the extended key and the number of residual alphabetic letters. Because of the low frequency of most all of the residual letters one can often spot their location in the number sequence, and because they are in alphabetical order and only have one substitute, one may make good guesses on individual residual letters by frequency matching.
A good estimate of the key length and the number of residual letters can be made by using the statistical method of "expected number of blanks" as presented by Solomon Kullback[3], where a "blank" is a ciphertext element (in this case a number) having a zero frequency.
LENGTH OF EXPECTED NUMBER OF ROUNDED SUM
TEXT, N BLANKS, B(N) N + B(N)
(key length) (residue letters) (pt alphabet length)
20 14.5 25
30 11.9 42
40 10.1 50
50 8.9 59
60 8.0 68
70 7.2 77
80 6.6 87
100 5.7 106
125 4.9 130
150 4.4 154
175 4.0 179
200 3.6 204
TABLE I, expected number of blanks vs text length
In this application, N equals the key length, B(N) equals the number of residual letters, and N + B(N) is the length of the extended plaintext alphabet.
For example, the crypt, NK-2, in "The Numbered Key Cipher" article, the length of the keyed alphabet is by implication 57 -- the largest number is 56 and adding one for the 00 gives 57. By interpolation on the N + B(N) column of Table I, the expected number of blanks (rounded) would be 9 and the key length, 57 - 9 = 48. I'll leave the solution of this crypt to the reader.
Another crypt, NK-3, from BION's original article is,
NK-3. Numbered key. Motley crew. (andalldr-)
26 08 09 23 21 28 03 09 14 12 36 09 30 36 33 02 11 09 30 03 19 20
20 16 14 25 38 01 33 03 07 23 32 08 33 32 33 13 13 30 00 34 19 28
36 20 15 07 08 30 34 33 12 16 07 08 28 34 14 03 36 10 21 14 32 08
36 03 33 38 38 22 28 36 37 09 33 07 27 09 03 31 07 08 09 33 25 24
00 33 19 18 21 14 26 27 26 27 09 24 03 37 11 03 35 19 24 25 38 14
25 38 35 19 20 10 28 32 20 32 27 30 00 33 15 36 33 19 19 36 03 14
01 01 24 15 38 29 28 26 35 03 20 13 18 33 25 36 11 15 35 20 00 37
20 03 26 33 34 19 09.
NK-3 compiled frequencies:
00 4 08 6 16 2 24 4 32 5
01 3 09 9 17 0 25 5 33 13
02 1 10 2 18 2 26 5 34 4
03 11 11 3 19 8 27 4 35 4
04 0 12 2 20 8 28 6 36 9
05 0 13 3 21 3 29 1 37 3
06 0 14 7 22 1 30 5 38 6
07 5 15 4 23 2 31 1
For this crypt, the length of the keyed alphabet is not known, however it can be estimated using Table I. The crypt length is 161 characters. Assuming that the constructor uses all the available substitutions, the number of blanks of the ciphertext would probably remain the same as that of the underlying plaintext. Interpolating for 161 in the N column of Table I, the expected number of blanks would be four. Since in the number series of 00 to 38 there are four blanks (04, 05, 06 and 17), this would imply a keyed alphabet length of 39. If not all substitutes were used, it might be a bit higher. (actually, where the residue doesn't wrap around the end of the number sequence, the highest number plus one is a good estimate.)
From Table I, for an alphabet length of around 39, the expected length of the residue would be 12 and the key length around 27. Since the low frequency letters would tend to accumulate in the residue, it would be reasonable to assume that the key starts at 07 and ends around 35.
Expected letter frequencies for 161 letters of text[4]:
a 13 h 9 o 13 v 1
b 2 i 11 p 03 w 2
c 5 j - q - x -
d 7 k 1 r 11 y 2
e 21 l 6 s 10 z -
f 5 m 4 t 15
g 2 n 12 u 4
Using frequency matching on the residue, one could assume that 04, 05 and 06 are v, x, and z; 03 is r, s or possibly t, 02, q; 01, p ; 00, l or m. Since the crib, (andalldr-), contains the doubled l's, and the crypt does not contain '00 00', m is most probable. Maybe j and k have zero frequency and are 39 and 40. 33 has a somewhat high frequency of 13 which would be indicative of a higher frequency letter which only occurs once in the keyed alphabet --- either at the end of the key or beginning of the residue. If it were at the beginning of the residue it would almost have to be a.
00 4 m 08 6 16 2 24 4 32 5 (40) 0 k
01 3 p 09 9 17 0 25 5 33 13 ?
02 1 q 10 2 18 2 26 5 34 4
03 11 r/s/t 11 3 19 8 27 4 35 4
04 0 v 12 2 20 8 28 6 36 9
05 0 x 13 3 21 3 29 1 37 3
06 0 z 14 7 22 1 30 5 38 6
07 5 15 4 23 2 31 1 (39) 0 j
Spotting the crib would clarify things further. The ciphertext fragment, 33 15 36 33 19 19 36 03, is a likely candidate for the crib location, even without the helpful doubled 19, the repeated 33 which noted earlier could be a, with the repeated 36 as d which fits nicely in the residue order, and 03 for r which earlier was guessed as r, s or t:
33 15 36 33 19 19 36 03
a n d a l l d r
Giving,
00 4 m 08 6 16 2 24 4 32 5 (40) 0 k
01 3 p 09 9 17 0 25 5 33 13 a
02 1 q 10 2 18 2 26 5 34 4 b
03 11 r 11 3 19 8 l 27 4 35 4 c
04 0 v 12 2 20 8 28 6 36 9 d
05 0 x 13 3 21 3 29 1 37 3 f/g
06 0 z 14 7 22 1 30 5 38 6 h/i
07 5 15 4 n 23 2 31 1 (39) 0 j
And,
26 08 09 23 21 28 03 09 14 12 36 09 30 36 33 02 11 09 30 03 19 20
r d d a q (u) r l
20 16 14 25 38 01 33 03 07 23 32 08 33 32 33 13 13 30 00 34 19 28
h/i p a r a a m b l
36 20 15 07 08 30 34 33 12 16 07 08 28 34 14 03 36 10 21 14 32 08
d n b a b r d
36 03 33 38 38 22 28 36 37 09 33 07 27 09 03 31 07 08 09 33 25 24
d r a h/i h/i d f/g a r a
00 33 19 18 21 14 26 27 26 27 09 24 03 37 11 03 35 19 24 25 38 14
m a l r f/g(u) r c l h/i
25 38 35 19 20 10 28 32 20 32 27 30 00 33 15 36 33 19 19 36 03 14
h/i c m a n d a l l d r
01 01 24 15 38 29 28 26 35 03 20 13 18 33 25 36 11 15 35 20 00 37
p p n h/i c r a d (u)n c m f/g
20 03 26 33 34 19 09.
r a b l
Now recognizing that 38 is g rather than h or i, with 37 as f and also 11 as u (following q) we can, remembering the clue "motley crew," make out part of the last two lines:
00 33 15 36 33 19 19 36 03 14
m a n d a l l d r i
01 01 24 15 38 29 28 26 35 03 20 13 18 33 25 36 11 15 35 20 00 37
p p i n g c r o a n d u n c o m f
20 03 26 33 34 19 09.
o r t a b l e.
And then:
00 33 15 36 33 19 19 36 03 14
m a n d a l l d r i
01 01 24 15 38 29 28 26 35 03 20 13 18 33 25 36 11 15 35 20 00 37
p p i n g w e t c r o s s a n d u n c o m f
20 03 26 33 34 19 09.
o r t a b l e.
Adding the new found substitutes to part of the first two lines of the crypt yields,
26 08 09 23 21 28 03 09 14 12 36 09 30 36 33 02 11 09 30 03 19 20
t e e r e i d e d a q u e r l o
20 16 14 25 38 01 33 03
o i n g p a r
Which leads to,
26 08 09 23 21 28 03 09 14 12 36 09 30 36 33 02 11 09 30 03 19 20
t h e y w e r e i n d e n d a q u e e r l o
20 16 14 25 38 01 33 03
o k i n g p a r
Our updated recovered letters are now,
00 4 m 08 6 h 16 2 k 24 4 i 32 5
01 3 p 09 9 e 17 0 25 5 n 33 13 a
02 1 q 10 2 18 2 s 26 5 t 34 4 b
03 11 r 11 3 u 19 8 l 27 4 35 4 c
04 0 v 12 2 n 20 8 o 28 6 e 36 9 d
05 0 x 13 3 s 21 3 w 29 1 w 37 3 f
06 0 z 14 7 i 22 1 30 5 e 38 6 g
07 5 15 4 n 23 2 y 31 1 (39) 0 j
Which with a little imagination gives us the key: 'the sun sinks slowly in the west'.
As one may notice, not every assumption was right on the money (as is typically the case), but even so, pointed in the direction of the solution. k was not 40, but rather 16 in the key. 38 was g, not h or i. The key length was 26, not 27 and the residue length, 14 not 12.
_________________________________________
References
[1] Parts of the text are from the article: MATANZA, "Estimating Key Length of a Numbered Key Cipher", American Cryptogram Association (ACA), Cryptogram mag.(Cm), MJ 2011.
[2] BION, "The Numbered Key Cipher", ACA, Cm, MJ 2010. See also similar website article, "The Numbered Key Cipher".
[3] Solomon Kullback, Statistical Methods in Cryptanalysis, Aegean Park Press, Laguma Hills, CA, 1976, p27. Values in Table I were computed based on English frequency data from Elcy[4] rather than from telegraphic text as given in the reference.
[4] Helen Fouche Gaines, Elementary Cryptanalysis, American Photographic Publishing Co., Boston, 1944, Appendix, p 219.