Valdis(_dot_)Kletnieks(_at_)vt(_dot_)edu wrote:
substitution ciphers are prone to frequency-analysis attacks,
This reminds me of something I recently wondered about, and now decided
to inflict on y'all. I've dealt with crypto just enough to be dangerous
to my OWN self; I'm no expert, so please bear with me.
How do cryptanalysis programs know when they've got it right? I am told
(by my dad, who did it in WWII, but hasn't kept up on the technology)
that the main way, barring having a specific string to match or other
distinguishing characteristic, is frequency analysis. That is, when
it's wrong, the letter (or rather, character) frequency distribution is
rather flat, but when it's right, it's spiky, in a manner that resembles
most human languages. (For instance, English has spikes at the classic
ETAOINSHRDLU spots, and lows at the "Scrabble letter" spots, though of
course these will generally be located differently if a simple
substitution cypher is used.) Are there other ways commonly used? For
now, I will proceed along the assumption (yes, I know what happens
then!) that this is still the main way.
Now, suppose you salt the plaintext with rarer characters, so as to
flatten out the distribution. That is, first you analyze the frequency
distribution of the plaintext, then compose a string of some given
length, that will have enough of the rarest characters to make the
frequency graph fairly flat, and then intermix them in some prescribed
manner. This could even be done in such a manner that any reasonably
long subset of the altered (but not yet "encrypted") plaintext would
have a fairly flat frequency graph, as opposed to, say, using up the
rarest characters first.
How would cryptanalysis programs deal with that? Do they usually apply
a "desalination" step to see if it can sensibly make a subset with a
spiky distribution? If so, how would it tell the actual message, from
any other spiky subset? (After all, even totally random garbage would
contain a multitude of spiky subsets!) Or is there some other reason
why the idea of adding such salt simply wouldn't help make encryption
more secure?
--
David J. Aronson, Software Engineer for hire in Philadelphia area
Resume, and other details, online at: http://dja2001.home.att.net
Looking for work[ers] in Philly? See the Yahoo group PhillyJobs.