Cryptography Reference
In-Depth Information
1 (line 119). This action corresponds to one step forward in the search
tree. If (*) is false for a period, then the program jumps out of the period
test loop (going to
next val
; lines 113 through 120), and tests the next
value. Once all 256 values have been processed, the function returns,
which corresponds to one step backward in the search tree.
•
If
tree search()
can see from the period length values and the number
of bytes already known that all test cases have been analyzed, then it
considers the password found to be valid and prints it (line 68).
•
There are several particularities about this action:
- (*) cannot be tested for
knb
=
0, because every
compress
word is at
least 9 bits long, and no such word is found in the partially decrypted
text for a period length greater than 1 (line 75). Period length 1 is
nevertheless dealt with!
- Even if all key characters have already been fixed, there are
compress
words that haven't been tested for (*) yet: these are the words that
reach beyond the period boundary. Therefore, we let
knb
run not only
from 0 to
len
−
1, but to
len
+
1, and accordingly replace the
len
and
len
1 indices by 0 and 1. Lines 69 through 71 and 74 show that our
programming has to be extremely careful.
+
- Line 74 reveals a little trick: when searching for the next key char-
acter, we start with 'A' rather than '0', since we assume that pass-
words are composed mainly of letters. Though this little trick doesn't
shorten the overall computation time, it helps to get to a correct
password faster — even dramatically faster, depending on the tree struc-
ture.
•
Finally, we have a look at the
print result()
function, since it is not lim-
ited to printing the password. If 'abc' was used to Vigenere-encrypt a
plaintext, then trivially enough it is also encrypted to 'abcabc', 'abcab-
cabc', etc. For this reason,
print result()
stores up to 64 passwords and
checks for 'multiples' of these words.
Doubtlessly the program can be greatly improved, though it is generally quite
fast and reliable. No obvious problems occur with long files. On a UNIX-PC
(133-MHz Pentium, ESIX V.4.2),
vigc crk
found the correct solution from a
compressed 260-Kbyte file encrypted with a 60-character password within 16
seconds:
