Transcript Example: ND02A24 - University of North Dakota

Use of a MS Access Pattern
Word Database to Solve
Aristocrats
By: Michael C. Schroeder
(MSCREP)
Berwick, ME
The Basics of Pattern Words:
•
•
•
•
What is a pattern word? - A word in which one or more letters repeated.
(For example the word ‘banana’.)
How do I determine a words pattern? - The simplest method is to use
the word as the keyword of a K1 cipher with shift zero. The cipher text
equivalent of the word using this system is the word pattern. (The
pattern for ‘banana’ is ‘abcbcb’.)
Why is this important? - A words underlying pattern is not destroyed
when it is encoded in a mono-alphabetic substitution cipher. The wide
variety of possible word patterns ensures most are not associated with
many words (e.g., The pattern abcbcb has 10 words.). Consequently,
the identification of pattern words can provide a powerful tool in the
solution of Aristocrats.
How do I do that? - A number of tables of pattern words, organized by
pattern, are available for use. A small list of about 20 K words can be
found in ‘Cryptanalysis for Microcomputers’ by Caxton C. Foster.
Why Use a Computerized Database? :
•
•
•
•
•
Much larger lists can be stored and searched. The Foster list has
about ~20K words while my database has about 250K words (both
pattern and patternless words).
A computerized search is much more thorough and accurate (i.e.,
Searches are completed in seconds not minutes).
A large source of material for use as database input already exists in a
format (digital) ready for exploitation.
Use of a computer database allows searches not possible with a
pattern word list or dictionary (e.g., Searches of ‘patternless’ words or a
search for all 8 character words that start with ‘w’ and end with ‘n’.).
The computer database output is in a format ready for further computer
manipulation.
A Lexicon of Database Terms
•
•
Database: A collection of data and objects related to a particular topic
or purpose. For example, a business database might contain the data
on products, orders, customers, and employees, etc...
Table: A container for the data on a specific subject. For example, the
above database might contain a table with employee information.
– Record: The collection of data that makes up a single item in a table. For
example, the employee table would contain a single record for each
employee.
• Field: A single item of data within a record. For instance, an employee
record might contain a field for name, DOB, SSN, address, phone
number, etc…
• Index: A field that has been ‘sorted’ to speed up searches of the data.
For example, the Name field is sorted alphabetically in the phone book
(a paper database) to speed up data retrieval.
•
Query: A question asked about the data stored in the tables in the
database. The design of a query tells the database exactly what data
to retrieve (e.g., What is John Smith’s phone number?).
Database Details:
•
•
There are two separate databases, one for English and one for foreign
languages.
‘Diction’ is the English language database:
– One data table with 280,516 records, indexed on pattern.
– Three fields for each record: Word, Length and Pattern.
•
‘Xeno’ is the foreign language database:
– One table with 744,559 records, indexed on pattern.
– Four fields for each record: Word, Language, Length and Pattern.
– Entries for ten languages: Danish, Dutch, Esperanto, French, German,
Italian, Latin, Portuguese, Spanish and Swedish.
•
Database is designed to allow search by:
– Word Pattern (Search on ‘abcbcb’ provides 10 words).
– Partial plain text (Search on bl*ck’ provides ‘black’ and ‘block’).
– Both Pattern and Partial Text (Search on ‘abcbcb’ and ‘ba****’ provides
‘banana’.
•
Additional Features:
– Function for conversion of cipher text to pattern.
– Ability to hunt for plain text fragment at the start, end or within a word.
How is the Database Used?:
•
The database is primarily used in one in one of three ways:
– Pattern Word Method: Search the cryptogram for pattern words. Search on
any patterns found to see if the possible words aid in the solution.
– Partial Text Method: For words in the cryptogram where a few letters are
known, search to find matches for pattern and partial text.
– Method of Coupled Words: In some cases, cryptograms have no pattern
words for easy exploitation. However, there are almost always cases where
one word has all or most of the letters in a second word. Such a pair of
‘coupled’ words provide patterns that can be used narrow down the possible
pairs.
•
Let’s do a couple of illustrative examples!
Example: ND02A24
A-24. Royal Water. K2 (89)
ANGO-KA
PAGP BWZHP CNVBRUCIRBHU PUHV KHFC
THFBHU PUHV KPD GDWV QN PIUCWSHDFD FR
VHDDRIJW TRQIW SWFPID DGUC ZRIV.
Example: ND02A24 (Pattern Word/Partial Text Method)
•
The example contains four pattern words. Let’s examine these to see if
any may be useful.
•
Results:
Cipher Text
PAGP
VHDDRIJW
PIUCWSHDFD
CNVBRUCIRBHU
Pattern
abca
abccdefg
abcdefghih
abcdefagedhf
No. Words
205
917
119
001
•
The last is very promising! It provides CNVBRUCIRBHU =
‘hydrochloric’. Substitute and look for more targets of opportunity.
•
We see that we can narrow down the other pattern words using the
partial plain text we have for each:
PIUCWSHDFD
*lch**i***
VHDDRIJW
di**ol**
Example: ND02A24
Cipher Text: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Plane Text: *rh****il****y***o**cd****
PAGP BWZHP CNVBRUCIRBHU PUHV KHFC
**** r**i* hydrochloric *cid *i*h
THFBHU PUHV KPD GDWV QN PIUCWSHDFD FR
*i*ric *cid *** ***d *y *lch**i*** *o
VHDDRIJW TRQIW SWFPID DGUC ZRIV
di**ol** *o*l* ****l* **ch *old
Example: ND02A24
•
Searching these two patterns on both pattern and known plain text
provides only one possibility for each:
PIUCWSHDFD = ‘alchemist’ & VHDDRIJW = ‘dissolve’.
•
Substitution now provides a nearly complete solution.
Example: ND02A24
Cipher Text: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Plane Text: *rhs*t*ilv***y*a*om*cde***
PAGP BWZHP CNVBRUCIRBHU PUHV KHFC
a**a re*ia hydrochloric acid *ith
THFBHU PUHV KPD GDWV QN PIUCWSHDFD FR
*itric acid *as *sed *y alchemists to
VHDDRIJW TRQIW SWFPID DGUC ZRIV
dissolve *o*le metals s*ch *old
Example: JF02A24
A-24. Trouble, trouble. K4 (101)
PETROUSHKA
EUTPOCVW SUNVPEACO BDMACOTUN JMDOCBEV,
NSYMPV NWXPDMOT; OEDJSMV LPUMYN AVEJ,
BPDSEYCT ADSEL, BTMAUN NWJXSVMY CWNOTDMP.
Example: JF02A24 (Complete Couple)
• Example contains a word (‘BDMACOTUN’ labeled word1) which
contains all of the letters in a second word (‘BTMAUN’, labeled
word2). This is an example of a complete couple.
• First, store the possible values for word1:
– Load a table with all the words in the database with the correct
pattern (abcdefghi) [4216 words].
– Remove words which have self encrypted letters (e.g., Words
beginning in b or having d as a second letter.). [2642 words]
– Assemble and store the possible value of word2 for each possible
word1 in a field labeled ‘fragment’.
• Second, store the possible values for word2:
– Load a second table with all the words in the database with the
correct pattern (abcdef) [10299 words].
– Remove words which have self encrypted letters (e.g., Words
beginning in b or having t as a second letter.). [7109 words]
Example: JF02A24
• Use a query to output the values of word1 and word2 for which
the value of ‘fragment’ in the first table matches a value of word2
in the second table (12 possible couples).
• A quick perusal of the 12 possibilities leads to picking the couple
‘frightened’ and ‘feigned’ as the most likely based on the
cryptogram title (i.e., ‘Trouble, trouble’).
• Substitution shows the couple to be correct since many partial
words are now obvious.
Example: JF02A24
Cipher Text: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Plane Text: gfhr********ist****en*****
EUTPOCVW SUNVPEACO BDMACOTUN JMDOCBEV
*ne*th** *ns***ght frightens *irthf**
NSYMPV NWXPDMOT OEDJSMV LPUMYN AVEJ
s**i** s***rite t*r**i* **ni*s g***
BPDSEYCT ADSEL BTMAUN NWJXSVMY CWNOTDMP.
f*r***he gr*** feigns s*****i* h*steri*.
Example: JF02A25
A-25. Spectral fantasy. K4 (100)
DYETI
FJGSKPU-WTON, DJGSCON LWGSJ QGVTFOH:
LPKJZC LZJI, KOGVO KGHPS, PFLWGN PFAM,
HLJFZOC HJZIPS, VPZNOS VFPTHO, QTLWHGJ
QZPTSNOF.
Example: JF02A25 (Incomplete Couple)
• Example contains a word (‘QZPTSNOF’ labeled word1) which
contains most of the letters in a second word (‘VPZNOS’,
labeled word2). This is an example of a incomplete couple.
• First, store the possible values for word1:
– Load a table with all the words in the database with the correct
pattern (abcdefgh) [7206 words].
– Remove words which have self encrypted letters. [5364 words]
– Assemble and store the possible fragment of word2 based on the
known letters in word1 (PZNOS). Store in a field labeled
‘fragment1’.
• Second, store the possible values for word2:
– Load a second table with all the words in the database with the
correct pattern (abcdef) [10299 words].
– Remove words which have self encrypted letters. [7265 words]
– Assemble and store the fragment of word2 based on the known
letters in word2 (PZNOS). Store in a field labeled ‘fragment2’.
Example: JF02A25
• Use a query to output the values of word1 and word2 for which
the value of ‘fragment1’ in the first table matches a value of
‘fragment2’ in the second table [118 possible couples].
• Eliminate couples for which there is an inconsistency between
values for the unused letter in word1 and word2 (I.e., The value
of cipher text letter V in word2 can not be the same as one of
the values of cipher text letters Q, T, or F in word1 [96 couples].
• A quick perusal of the 96 possibilities leads to picking the couple
‘flounder’ and ‘golden’ as the most likely based on the
cryptogram title (i.e., ‘Spectral fantasy’).
• Substitution shows the couple to be correct since many partial
words are now obvious.
• Note, that if too many possibilities exist for a meaningful choice,
the above process can be extended to a word3 (or word4, etc…)
using the the know word1/word2 couples to generate fragment3
values. (Cipher word VFPTHO is a tempting target, since it has
letters common with both word1 and word2.)
Example: JF02A25
Cipher Text: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Plane Text: *****r*******deof*nu*g***l
FJGSKPU-WTON DJGSCON LWGSJ QGVTFOH:
r**n*o*-*ued ***n*ed ***n* f*gure*:
LPKJZC LZJI KOGVO KGHPS PFLWGN PFAM
*o**l* *l** *e*ge ***on or***d or**
HLJFZOC HJZIPS VPZNOS VFPTHO QTLWHGJ
***rle* **l*on golden grou*e fu*****
QZPTSNOF.
flounder.