| Welcome to Crypto. We hope you enjoy your visit. You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free. Join our community! If you're already a member please log in to your account to access all of our features: |
- Pages:
- 1
- 2
| Shifting Alphabets; How can I PROVE this rule? | |
|---|---|
| Topic Started: Sep 28 2005, 03:39 PM (418 Views) | |
| Donald | Sep 28 2005, 03:39 PM Post #1 |
|
Elite member
  ![]](http://209.85.122.85/static/1/pip_r.png)
|
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. From trial and error, it seems that for any alphabet with an EVEN number of letters, you can always find at least one shift of the crypt alphabet that will have no collisions with the plain alphabet. Note that even this carefully manipulated alphabet has ONE shift with no collisions:
However, if the 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:
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)
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. 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 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? |
 |
 
|
| Revelation | Sep 28 2005, 04:09 PM Post #2 |
Administrator
|
I am not sure I fully understand you, so this might not be the answer you were looking for. I take it you don't want any letter to be in the position of the letter beside it either, so B can't swap with A and C. This is with even:
And for uneven:
The dots indicate places that are excluded, because the letter meets its neighbour. You see with uneven, that A and B can't be placed, because the only possibility is at the same offset. |
|
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN | |
|
|
|
| Donald | Sep 28 2005, 05:00 PM Post #3 |
|
Elite member
|
No, a=B would be fine. Just a=A is forbidden. |
|
|
|
| insecure | Sep 28 2005, 07:18 PM Post #4 |
|
Elite member
|
You threw me, Donald. I don't understand what you're talking about. What you seem to be saying is that a monoalphabetic substitution cipher using an alphabet with an odd number of letters will always encode one letter as itself. And yet you can't be saying that, because it's obviously false. ROT-1 is the obvious counter-example:
So what did you mean? |
|
|
|
| Donald | Sep 28 2005, 07:51 PM Post #5 |
|
Elite member
|
Sorry, I haven't been clear at all. Let me start back further. The ACA (American Cryptogram Association) has a rule for mono substitution ciphers. The rule is that a letter must never encrypt to itself. SO, you must NOT have a=A or b=B. I was attempting to implement this rule in a cryptogram program I've been playing with. So when I would create an encrypted alphabet (some randomized version of an alphabet) I would then check it against the plain text, and if there was any place where they crypt and the plain were equal, (if any letter encrypted to itself) I would shift the crypt alphabet by 1 and try again. Now, the thought immediatly occured to me, could my program get into a loop? Can I run into a crypt alphabet that can NOT be shifted into a position where it has no collisions with the plain alphabet (where no letter encrypts to itself) Experimentation seemed to show that no matter how deliberatly I manipulated a crypt alphabet, I could always find at LEAST one shift where there would be no collisions. But, My program is designed to work with any particular alphabet you want to set it up for (So that it can switch languages easily). So I tried testing with different length alphabets. And I discovered that for alphabets with an odd length, I COULD construct cipher alphabets that did not have ANY shift without a collision. As in the above example. With plain text alphabet ABCDE and cipher aplhabet ACEBD EVERY possible shift has a collision with the plain text:
So every possible shift of alphabet ACEBD collides with the plain text somewhere. BUT, So far, I have not been able to construct a crypt alphabet with an even number of letters that does not have at least one position without any collisions. for example, with plain text alphabet ABCD and crypt ACDB
So, it seems to always work. but WHY? If your alphabet has an even number of letters, then for ANY crypt alphabet, there is always at least ONE shift that has no collisions with the plain alphabet. BUT, if your alphabet has an odd number of letters, there may be crypt alphabets that can NOT be shifted into a positions where they have no collisions with the plain. There has to be a simple mathmatical rule behind this, thats what I'm looking for. |
|
|
|
| Revelation | Sep 28 2005, 08:25 PM Post #6 |
|
Administrator
|
Isn't BCDEA a non-colliding solution? |
|
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN | |
|
|
|
| Donald | Sep 28 2005, 09:11 PM Post #7 |
|
Elite member
|
Yes. There ARE crypt alphabets for odd alphabets that have shifts without collisions. But there are ALSO crypt alphabets for odd alphabets that do NOT have any shifts without a collision. In other words, if I hadn't put in logic to escape out of my program loop, it would have just kept shifting them forever without ever finding an acceptable solution FOR THAT PARTICULAR crypt ALPHABET. It does not apply to ALL odd crypt alphabets, just some. BUT, for even alphabets I do not believe there are ANY crypt alphabets that do not have at least one collision free shift. So the mathmatical rule seems to be: Rule 1 The number of ODD crypt alphabets that do NOT have a collision free shift is greater than 1 for all ODD plain alphabets. Rule 2 The number of EVEN crypt alphabets that do NOT have a collision free shift is 0 for all EVEN plain alphabets. Now this rule appears to be true but I can't prove it. For Rule 1 I can prove it by example for any particular odd alphabet you wish to create (1, 3, 5, etc), but that doesn't prove it's true for ALL odd alphabets. Rule 2 I can prove for some low number even alphabets by example (you simply exhaust all possibilities and prove all of them have at least 1 collision free shift), but again, that doesn't PROVE it's a general rule. This LOOKS like it should be a very simple mathmatical principle, thats what I'm trying to find. Not because it matters, but just because it's BUGGING me. 
|
|
|
|
| insecure | Sep 29 2005, 12:38 AM Post #8 |
|
Elite member
|
Okay, I think I understand now. You suspect that there is always at least one Caesaresque shift of a mono key for an alphabet with 0 (mod 2) letters, that will prevent clashes of plain and cipher letter. You wish to prove this. I will think about it, and get back to you. I suspect the answer will lie in assuming it's impossible, trying to construct a counter-example and deducing an absurdity in the process (or - perhaps! - constructing the counter-example which would prove you wrong!). |
|
|
|
| insecure | Sep 29 2005, 03:02 AM Post #9 |
|
Elite member
|
I've had a think about this, but I can't yet see how to construct such a proof (either for or against your hypothesis). I'll go on thinking about it in background mode, but in the meantime I have a suggestion, if your programming is up to it, which it probably is. Now, this suggestion may or may not turn out to be useful for solving this problem, but whether it does or not, it is a useful programming technique in its own right, with a wealth of useful applications. Take a reasonably small alphabet with 0 mod 2 letters. 16 is an obvious choice. You have 16! possible keys, which is - er - precisely 20922789888000 possible keys. I do not believe you have tried them all! :-) (At a million a second, it would take eight months.) Before I go on, a word about data representation. Instead of worrying about a key of 16 letters, worry instead about a series of sixteen four-bit numbers, 0-15 obviously. Each key is formed as follows: Start with ABCDEFGHIJKLMNOP Consider a random series of 64 bits. No, this is not the numbers 0 through 15, jumbled up. This is a truly random (well, pseudorandom will do) bunch of bits. Here is an example: 0110 0111 0101 1101 0110 1010 1111 1001 0010 1001 1011 1110 1100 0011 0110 0101 To generate the key, we start with the first number, 0110, which is 6, of course. So we take the 0123456th letter, which is ABCDEFG - ah, G. That's the first letter in the key. Remove it from the group of letters, and move on to the next four bits: PARTIAL KEY: G KEY BANK: ABCDEFHIJKLMNOP BITSTREAM: 0111 0101 1101 0110 1010 1111 1001 0010 1001 1011 1110 1100 0011 0110 0101 Now take the next four bits, 0111, which is 7. Take the 01234567th letter out of what is left: ABCDEFHI - ah, I. Add it to the key, and remove it from the bank: PARTIAL KEY: GI KEY BANK: ABCDEFHJKLMNOP BITSTREAM: 0101 1101 0110 1010 1111 1001 0010 1001 1011 1110 1100 0011 0110 0101 And again. (I'm going to keep going until we hit the obvious problem, to show you how to skip round it.) This time we have 0101 which is 5. Take the 012345th letter, ABCDEF - ah, F: PARTIAL KEY: GIF KEY BANK: ABCDEHJKLMNOP BITSTREAM: 1101 0110 1010 1111 1001 0010 1001 1011 1110 1100 0011 0110 0101 And again. We have 1101 which is 13 decimal. Remember we start from 0, so we want the fourteenth letter (check again if you wish that this is consistent with the above examples). So that's ABCDEHJKLMNOP - er, er, go back round to A again. PARTIAL KEY: GIFA KEY BANK: BCDEHJKLMNOP BITSTREAM: 0110 1010 1111 1001 0010 1001 1011 1110 1100 0011 0110 0101 Continuing, we get: PARTIAL KEY: GIFAK KEY BANK: BCDEHJLMNOP BITSTREAM: 1010 1111 1001 0010 1001 1011 1110 1100 0011 0110 0101 PARTIAL KEY: GIFAKP KEY BANK: BCDEHJLMNO BITSTREAM: 1111 1001 0010 1001 1011 1110 1100 0011 0110 0101 PARTIAL KEY: GIFAKPJ KEY BANK: BCDEHLMNO BITSTREAM: 1001 0010 1001 1011 1110 1100 0011 0110 0101 and so on. Eventually, we end up with: KEY: GIFAKPJBEHONCDLM Okay, what we've done is found a way of turning a random bitstream - any old bitstream - into a way of generating a key. The next step is to find out in how many shifts it blocks. There are sixteen possible shifts, including what I will call C0 (C for Caesar). In the following analysis, I am shifting the mono key left under the plaintext alphabet. A right shift would give results the other way up, so to speak. We expect to find 16 blocks altogether, but some will probably occur on the same shift, in which case there is bound to be a non-blocking solution somewhere. We want to find a key, of course, where each shift gives exactly one block. C0 does not block. C1 does not block. C2 blocks (on H). C3 blocks (on A, L, M). C4 blocks (on E). C5 does not block. C6 blocks (on B, P). C7 does not block. C8 does not block. C9 blocks (on I). C10 blocks (on C, D, G, K). C11 does not block. C12 blocks (on O). C13 blocks (on F, J). C14 blocks (on N). C15 does not block. We score this key by the number of different blocking shifts. In this case, they are C2, C3, C4, C6, C9, C10, C12, C13, C14 - which is pretty high for a first go, I think. We postulate that a high blocking shift count is closer to our goal (disproving the hypothesis by finding a counter-example) than a low block. We generate a few hundred or a few thousand keys using the above technique, and then rank them in blocking shift count order. We take a certain percentage - say, 40% - of the lowest rankers, and discard them, retaining the 60% (or whatever) with the highest blocking shift scores. (You might want to write the top scorer to a file, for future reference, along with its score.) We now pair off those top 60% randomly, and "breed" them. We are interested at this stage in the original bitstreams used to generate the keys, so I hope you didn't discard them! There are two techniques involved in breeding: 1) Crossover 2) Mutation Crossover involves taking a random point P between 0 and N - 1 inclusive (where you have an N-letter alphabet). We are producing a new bitstream. Randomly identify one "parent" as dad. The other is mum. Copy the leftmost P bits from the father to the new child's leftmost bits. Copy the rightmost N - P bits from the mother to the rightmost bits of the child. Hey presto, crossover. Mutation means that you randomly change bits in the child. (Don't mutate too often in a single child, or this technique degenerates to Monte Carlo.) Keep breeding until all your empty slots (40% in this example) are filled. Then go round again. In theory, this will lead to closer and closer appoaches to the ideal, an N-blocking shift. Let it run in the background, overnight. By morning, you will either have your counter-example or, I hope, at least some close approaches to it, which might be tweaked by hand. The disadvantage of this method is that it can't prove that you're right. It can, however, prove that you are wrong, by constructing a counter-example. The technique is called a "genetic algorithm" (although it is in fact the bitstream data rather than the algorithm which actually has the "genetic" characteristic). I don't know if you want to code this up for the heck of it, but you may find it quite diverting as a programming exercise! I will keep trying to think of a better way. |
|
|
|
| Donald | Sep 29 2005, 12:03 PM Post #10 |
|
Elite member
|
Genetic algorithms ARE cool. I have never written one, but I am familiar with the concept. And thank you for that very nice example! However, in this case, while there is a very small chance it might find a counter-example for me, I'm not expecting it to, and THAT would be dissapointing.
But I think you may have given me a critical clue. I need to be working at this from the other direction. There is a simpler rule for alphabets WITH collisions than alphabets without. 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. I think proving that that is impossible if N is even must be the key. Hmmmm..... Donald |
|
|
|
| insecure | Sep 30 2005, 06:33 AM Post #11 |
|
Elite member
|
So let's try to construct an alphabet that has one and only one block at each shift. We start with AB. This clearly won't block if we shift it an odd number of places. Okay, so we try BA - but that's just a shift of AB anyway. So much for N=2. Let's try N=4. ABCD gives us a bit more scope. Now, we can use symmetry to establish that, if there is a full-blocking solution, there must be at least four such solutions - one starting with A, one with B, one with C and one with D (indeed, these will be shifts of the same solution). So let's take the solution starting with A, which is blocking. That means we must place B, C, and D all in non-blocking positions. There are, surprisingly, only two such positions: CDB, DBC. If we add the A back in, we get ACDBACDBACDB... and ADBCADBCADBC.... As you can see, these can be thought of as B, A or C, C or A, D. Each of those candidate keys is non-blocking at one point. Now, if we go to N=6, things get rather hairier. But we have a possible inroad into a solution. We note that the shifted key is cyclic by its very nature. So, given a fixed point A, we have to ensure that all the key letters we add in must appear at different offsets from A than in the "natural" (or, if you prefer, plaintext) alphabet - and all offsets between letter pairs must be different in the key than in the plaintext alphabet, where "offset" is defined as "distance around the circle" (in, say, a clockwise direction). Okay, so we are forbidden, in our construction of a "perfectly-blocking" key, from placing, say, D at an offset of 2 from B, and so on. That is, we have to ensure that all the letter pairs are not at the same offsets in the ciphertext alphabet as in the plaintext alphabet. So, back to N=6. I have done an exhaustive logical analysis of this alphabet, and concluded that there is no combination that will spread the blocks evenly over the shifts. (On reflection, it would have been quicker to brute-force it by writing a program!) I am increasingly of the opinion that the way forward is to look at the logical consequences of the offset rule (in modulo N, of course), but I am not yet sure how to take it further. |
|
|
|
| Revelation | Sep 30 2005, 06:35 AM Post #12 |
|
Administrator
|
The number of solutions with no letter in the same place is linked to the limit of the complete number of solutions as 1/e. If you then round the number you will have your solution. ex1: for n=2, 2!/e=0,7. This is rounded to 1. ex2: for n=5, 5!/e=44 Someone helped me out with this
|
|
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN | |
|
|
|
| insecure | Sep 30 2005, 07:09 AM Post #13 |
|
Elite member
|
Revelation: Sorry, but I don't understand how that helps Donald. Could you explain please? |
|
|
|
| Revelation | Sep 30 2005, 11:26 AM Post #14 |
|
Administrator
|
He asked for a mathematical solution to the question how many non-colliding letter swaps there were. |
|
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN | |
|
|
|
| Donald | Sep 30 2005, 12:17 PM Post #15 |
|
Elite member
|
And your answer looks very interesting! But I'm afraid I don't understand it. Could you explain what the math MEANS? For example, is e a variable, in which case, where does it's value come from, or do you actualy mean the mathmatical constant e, and if so, I'm very surprised that this problem would involve its use! Sorry for being slow. I like math, but I'm not very GOOD at it. Donald P.S. I also posted this question on Sci.crypt and have gotten some very interesting answers there. |
|
|
|
| 2 users reading this topic (2 Guests and 0 Anonymous) | |
| Go to Next Page | |
| « Previous Topic · General · Next Topic » |
- Pages:
- 1
- 2
11:31 PM Nov 27
