Shifting alphabets
ht9j...@sneakemail.com
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
Douglas A. Gwyn
> 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.
That is an interesting question. If your idea that it is possible
exactly when N is odd is correct, perhaps a proof could be found
based on the decomposition of every permutation into the product
of 2-cycles. Good luck!
Milan VXdgsvt
> 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
>
> So, I started trying to PROVE this rule.
>
You could try the following proof by construction:
we have
abcdefgh
12345678
and want to find an offset of the bottom row.
1. So, either
a) there's no match and we're done, or
b) at least one column has a match. So, rotate the lower line by one
char to the right. For example, suppose the match was in column a:
abcdefgh
8A234567
2. if there are more than 2 undiscovered letters, go back to 1
3. now we have something like
abcdefgh
EG5BD8AC
a) If we started with odd number of characters and got something like:
abcdefg
CEGBD7A
now the last character must match itself and this is not a solution.
If we shifted one more time, we would arrive back at the first offset
which had a match, and thus this has no solution. Thus, for odd
lengths, solution does not always exist.
b) if we started with even number of characters, then either it's
abcdefgh
ba)EGFBDHAC which is solution, or it's
bb)EGHBDFAC which can be solved by one more shift:
CEGHBDFA (before, we tried N-2 shifts and identified all N-2
characters, so one more shift cannot match anything in the solved
letters; the shift breaks the matching pair and cannot create a new
pair)
This is in no way a *mathematical* proof, but I find it quite
convincing. It may need some polishing, especially the 3bb) part, but
I'm pretty sure it's all true.
Milan
ht9j...@sneakemail.com
Douglas A. Gwyn wrote:
> perhaps a proof could be found based on the decomposition
> of every permutation into the product of 2-cycles.
> Good luck!
Thanks for the advice, I'll try moving in that direction!
Milan VXdgsvt
> It may need some polishing, especially the 3bb) part
Thank you for the help! I'm going to have to spend some
more time looking at 3bb because I don't fully understand
it. Yet! :)
Thanks!
Donald