Shifting alphabets

Over on the "Crypto Forum"
http://s13.invisionfree.com/Crypto/index.php?act=idx

We've been discussing Feistel Networks,
http://s13.invisionfree.com/Crypto/index.php?showtopic=25

Attacking Vigenere ciphers with the Kasiski method and index of
coincidence,
http://s13.invisionfree.com/Crypto/index.php?showtopic=10&st=15

And, recently, we've been examining an issue about shifting alphabets
that I wanted to bring up here in order to get an expanded point of
view.
http://s13.invisionfree.com/Crypto/index.php?showtopic=32

One of the ACA's rules is that a monosubstition cipher must never
encrypt a letter as itself. I was writing a program to generate
ciphers and attempting to implement this rule, when I ran into an
interesting question that I can't seem to find a satisfactory answer
to.

The question:
For any given plaintext alphabet of length N, is it possible to find a
crypt alphabet arrangement that can NOT be shifted into a position
where it has zero collisions with the plain text alphabet.

>>From trial and error, it seems that for any plaintext alphabet with an
EVEN number of letters, you can ALWAYS find at least one shift of ANY
crypt alphabet that will have no collisions with the plaintext
alphabet.

For example, note that even this carefully manipulated alphabet has ONE
shift with no collisions:

abcdefghijklmnopqrstuvwxyz
CEGIKMOQSUWYZBDFHJLNPRTVXA

All other 25 shifts of this crypt alphabet will collide with one
plaintext letter, but this one shift has no collisions. And that SEEMS
to be a rule for plaintext alphabets with an even length.

However, if the plaintext alphabet has an ODD number of letters, this
rule does not hold. For many arrangements of the crypt alphabet there
may be no shift that is without collisions. For example:

abcde
-----
ACEBD <-collides at A
DACEB <-collides at C
BDACE <-collides at E
EBDAC <-collides at B
CEBDA <-collides at D

So, it appears to be that for a plaintext alphabet with an EVEN length,
EVERY possible crypt alphabet will have at least one shift with no
collisions. But for a plaintext alphabet with an ODD length, there do
exist arrangements of crypt alphabets that can NOT be shifted into a
position where they have no collisions. (Note: Not that ALL odd length
crypt alphabets can't be shifted into a non colliding position, just
that there DO exist some that can't)

So, I started trying to PROVE this rule.

Consider it as a matrix with L (letter positions) as the x coord and S
(shift number) as the y coord. We'll work with a 4 letter alphabet to
make this easy. So if I choose to collide with 1,1 for the first
shift, I automatically block (2,2),(3,3) and (4,4) because the "A" must
propagate in it's current position through each remaining shift. I
ALSO
block all x coord 1 positions in the matrix since we already used that
letter.

Or, to put it as a formula, colliding at a particular coord (S,L)
blocks all coords (L+i,S+i) AND (L,s+i) where i=1 to M-1 (M=size of
the alphabet)

 L1234
S ----
1:c <-colliding here
2:** <-blocks all of these other coords.
3:* *
4:* *

Now I can play with this matrix, or with shifting the alphabets
directly, and I can SEE it happening. If the alphabet has an even
length, you can't create a crypt alphabet that collides at every shift.
 But for the life of me, I can't come up with a way to prove this
mathematically.

Another and more promising approach is to try and disprove the rule for
colliding alphabets.

In order for a crypt alphabet to have a collision at each and every
shift for a plaintext alphabet of length N, the crypt alphabet must
have N shifts with collisions. And the only way it can do that is if it
has One (and only One) collision at each shift.

It should be possible to prove that the above is impossible when N is
even. But so far, no luck on my part. <sigh>

It's not the least bit important, it doesn't actually have any impact
on my program (Since I have to account for "odd" length alphabets
anyway), but it's BUGGING me. It's been bugging me for quite some time
now.

So, I was curious if anyone with a better mathematical/logic background
than I have could help me out here. How do you PROVE that, if your
alphabet's length is even, there is ALWAYS at least one shift position
for your crypt alphabet that does not have any collisions with the
plain?

Thanks!
Donald
Received on Thu Sep 29 21:58:47 2005