Each symbol selection he would move to the left or right, but not repeat a symbol. If he was encoding E, then he didn’t stay on one symbol and repeat. He would move to the left or right, but not stop, repeat, then change direction. That would be consistent with your idea that he was trying not to repeat symbols by row. Rather, instead of avoiding repeats by row, he kept shifting to the right or left, but didn’t stop and make a period 1 repeat. It’s just an idea, but could explain what you were talking about, not repeating symbols by row. Always shifting left or right would make it look like that. Just an idea, maybe too soon to say.
And by far the majority of 3 symbol cycles do not have any period 1 unigram repeats.
That is a good idea. It could go from left-to-right and then from right-to-left, alternating, this would create perfect palindromic cycles. I have created such a cipher and it scored very high on my palindromic test so it is not that. A random shift does not create enough cycles. And a left-to-right to right-to-left + random shift still scores high on my palindromic test. Perhaps you need to try a few ciphers.
@doranchak, you said that the cycles in the 340 are easily improved by simple manipulations, I was wondering if my cipher would have the same result.
Oh! OK. I should dust off my hillclimber and give it a try.
Sure, I would like to know if the 340 is special in that way.
To me an isomorphism is like an equivalence category.
Cycles DEFDEF and XYZXYZ are isomorphic because they can both be represented by the new sequence ABCABC.
So, multiple cycles can be included in this same "category" or isomorphism. It is a mathematic term that I’m probably not using correctly.
I just was not familiar with the term, ofcourse I understood that ABC could represent different groups of symbols, that is a given. Cycle ngram analysis is very interesting!
2) Additionally, when considering substrings, I recompute the isomorphism. For example, "BCABCAB" is converted back to "ABCABCA".
Our routine differs in this point. ABC could be BCA or CBA. ABA could be BAB, CBC, CAC, ACA or BCB right? I thought about it and concluded it complicates quickly and dismissed it for the sake of computing time and consistency.
This is way worse than Powerball lottery..one might focus on letters with less homophones, however, which could still make sense (e.g. finding the homophones for the letters YOU), just wanted to comment on that before someone starts to crash his calculation with some memory error
Try a hill climber. AZdecrypt has a cycle merge hill climber which works on the 408 and reduces it to a 1:1 substitution cipher. So bad that the 340 is more random…
Each symbol selection he would move to the left or right, but not repeat a symbol. If he was encoding E, then he didn’t stay on one symbol and repeat. He would move to the left or right, but not stop, repeat, then change direction. That would be consistent with your idea that he was trying not to repeat symbols by row. Rather, instead of avoiding repeats by row, he kept shifting to the right or left, but didn’t stop and make a period 1 repeat. It’s just an idea, but could explain what you were talking about, not repeating symbols by row. Always shifting left or right would make it look like that. Just an idea, maybe too soon to say.
And by far the majority of 3 symbol cycles do not have any period 1 unigram repeats.
That is a good idea. It could go from left-to-right and then from right-to-left, alternating, this would create perfect palindromic cycles. I have created such a cipher and it scored very high on my palindromic test so it is not that. A random shift does not create enough cycles. And a left-to-right to right-to-left + random shift still scores high on my palindromic test. Perhaps you need to try a few ciphers.
I am starting to make messages to see how my own cycle chunk ( "isomorphic pattern" ) test works. So far using 5-gram ABCBA for high frequency letters and 6-gram ABAABA for low frequency letters is creating a lot of false perfect cycles ABABAB in many instances. But I am only checking the first six positions in the pattern and I should change that.
The isomorphic pattern test could be applied in different ways. Encoding start position and direction, odd / even positions, etc.
Are you comfortable with the reliability of the test? Do you think that we need to try simple messages with designated patterns to see more about how the test works? You probably have already done that, I see some work on other messages above.
During the work week I get hasty and forget to be artful about making test messages that emulate as many of the 340 stats as possible. Would trying to match other 340 stats matter? Except that there should be about 63 symbols I think. Any other specific stats that you want, like cycle score, unigram repeat distances, etc.? It would be nice to be able to say that the test has been applied to a variety of different patterns, etc. and get a better feel for interpreting the results and tinker with the test. Maybe you guys already have that.
Do you want a random left right shift message to see if the highest scoring patterns mostly do not have P1 repeats?
I just had an idea. But before I start implementing, I would like to ask you for advice:
Let’s say that in z340 the order of the columns was changed (e. g. with a keyword), but after substitution. Like most others, I believe that if there was a transposition, it was performed before the substitution. However, in this case it would still be possible because such a transposition only has a horizontal effect (I hope my description is not too confusing). Even observations like the high amount of rows without repeats would not be affected.
This could lead to the fact that in the final cipher you occasionally find cycles that are simply overlays / correlations of the original.
If I haven’t said any total rubbish so far: Would a hillclimber or genetic algorithm find the original sequence if you use the cycle score as fitness function? Or would there be too many false positives? Has this been tried yet?
Another possibility would be that Zodiac did several steps in the substitution process. For example, he first substituted columns 1,5,9,10,11,13,16 and 17 from left to right, top to bottom. After that he substituted columns 2,3,4,6,7,8,12,14 and 15. Regarding to the cycles this would have the same effect like the first idea in this post. Well… in this case that can’t be everything, because otherwise z340 would already be solved.
Largo, that idea sounds very plausible to me. In my transposition experiments, I found that certain rearrangements cause more bigrams/fragments to appear, and some cause better cycles to appear. But I don’t think I’ve come across rearrangements that amplify both phenomena. I think it’s definitely still worth exploring.
Allright, perhaps I can contribute to the cycle investigation in the next days. But I have one more question: does anyone have a piece of source code with an efficient way to find cycles? I don’t want to reinvent the wheel =) I remember an older post from Jarlve, but unfortunately I can’t find it any more. Thank you in advance!
I’ve been using brute force searches lately but the most efficient algorithm I’m aware of is REMOVE_HOMOPHONES mentioned in the King and Bahler paper.
Here’s my old crappy Java implementation of it:
But I would first recommend reading the paper, because it goes into detail about the speed efficiencies of their algorithm:
http://www.oranchak.com/king-homophonic-ciphers.pdf
Unfortunately, I think the algorithm gets easily confused when the cycles are imperfect.
@doranchak, you said that the cycles in the 340 are easily improved by simple manipulations, I was wondering if my cipher would have the same result.
Oh! OK. I should dust off my hillclimber and give it a try.
Sure, I would like to know if the 340 is special in that way.
Here are some row swaps that boost your m2 cycles measurement:
01 +E7'D*!$3*.)HSF1$ 04 ITC#X3>E14#]+HLX 02 M&^*%Y6[ZU=($VQ,* 02 M&^*%Y6[ZU=($VQ,* 03 $R+>)*'/KG$(*8V$B 01 +E7'D*!$3*.)HSF1$ 04 ITC#X3>E14#]+HLX 03 $R+>)*'/KG$(*8V$B 05 -3*=$)*@II^1HQ$[> 06 !YP^<RU:T,<?$IO; 06 !YP^<RU:T,<?$IO; 07 #QK*5A"$9I0&CE*^. 07 #QK*5A"$9I0&CE*^. 05 -3*=$)*@II^1HQ$[> 08 +0D]M/JV$!K'*QR46 08 +0D]M/JV$!K'*QR46 09 )-4Z"MI$8H1?9'?E& 20 @K$*#$U:?RW2,Y*9E 10 7^A?(!-B)V?Z+55A 10 7^A?(!-B)V?Z+55A 11 *Q_M9KX+G_/$2-4%E 12 ]R!;SFL)_<*8"1I3& 12 ]R!;SFL)_<*8"1I3& 11 *Q_M9KX+G_/$2-4%E 13 #N=#HL';Y$O0Z*F@[ 13 #N=#HL';Y$O0Z*F@[ 14 S!X.V"':$*-^V:DK 14 S!X.V"':$*-^V:DK 15 3UF,*E!8AB"TQ$7K> 15 3UF,*E!8AB"TQ$7K> 16 [4=*["^H#$XME*T3 16 [4=*["^H#$XME*T3 17 C49+[]PG>-;%5#X* 17 C49+[]PG>-;%5#X* 18 &N)T/RE1@?N3>2SI 18 &N)T/RE1@?N3>2SI 19 Q#]P$P'[JU*;O*:1@ 19 Q#]P$P'[JU*;O*:1@ 20 @K$*#$U:?RW2,Y*9E 09 )-4Z"MI$8H1?9'?E&
m_2s_cycles goes from 2202.52 to 2678.40
pcs2 goes from 312.40 to 422.92
pcs3 goes from 112.04 to 289.30
Here are dumps of the L3 cycles for the "before" and "after" ciphers:
http://zodiackillerciphers.com/jarlve-c … cycles.txt
http://zodiackillerciphers.com/jarlve-c … cycles.txt
The row swap operations have caused more cycles to appear. Here are the counts by run length (example: ABCABCABC has a run length of 3):
Before swaps:
Run length 2: 4059
Run length 3: 236
Run length 4: 11
After swaps:
Run length 2: 6395
Run length 3: 478
Run length 4: 27
Incidentally, it only takes a single row swap operation (swap rows 9 and 20) to boost the m2 score from 2202.52 to 2415.13:
01 +E7'D*!$3*.)HSF1$ 01 +E7'D*!$3*.)HSF1$ 02 M&^*%Y6[ZU=($VQ,* 02 M&^*%Y6[ZU=($VQ,* 03 $R+>)*'/KG$(*8V$B 03 $R+>)*'/KG$(*8V$B 04 ITC#X3>E14#]+HLX 04 ITC#X3>E14#]+HLX 05 -3*=$)*@II^1HQ$[> 05 -3*=$)*@II^1HQ$[> 06 !YP^<RU:T,<?$IO; 06 !YP^<RU:T,<?$IO; 07 #QK*5A"$9I0&CE*^. 07 #QK*5A"$9I0&CE*^. 08 +0D]M/JV$!K'*QR46 08 +0D]M/JV$!K'*QR46 09 )-4Z"MI$8H1?9'?E& 20 @K$*#$U:?RW2,Y*9E 10 7^A?(!-B)V?Z+55A 10 7^A?(!-B)V?Z+55A 11 *Q_M9KX+G_/$2-4%E 11 *Q_M9KX+G_/$2-4%E 12 ]R!;SFL)_<*8"1I3& 12 ]R!;SFL)_<*8"1I3& 13 #N=#HL';Y$O0Z*F@[ 13 #N=#HL';Y$O0Z*F@[ 14 S!X.V"':$*-^V:DK 14 S!X.V"':$*-^V:DK 15 3UF,*E!8AB"TQ$7K> 15 3UF,*E!8AB"TQ$7K> 16 [4=*["^H#$XME*T3 16 [4=*["^H#$XME*T3 17 C49+[]PG>-;%5#X* 17 C49+[]PG>-;%5#X* 18 &N)T/RE1@?N3>2SI 18 &N)T/RE1@?N3>2SI 19 Q#]P$P'[JU*;O*:1@ 19 Q#]P$P'[JU*;O*:1@ 20 @K$*#$U:?RW2,Y*9E 09 )-4Z"MI$8H1?9'?E&
Do you want a random left right shift message to see if the highest scoring patterns mostly do not have P1 repeats?
Do whatever smokie, I will have almost no time this week except to answer some stuff on the forum.
Incidentally, it only takes a single row swap operation (swap rows 9 and 20) to boost the m2 score from 2202.52 to 2415.13:
I did not know that.
To me, the simplest explanation as to why the cycles in the 340 react well to simple manipulations are because the sequential homophonic substiution is more random. And I think that has to be considered first and foremost. You have posted some numbers but what do you think?
Do you want a random left right shift message to see if the highest scoring patterns mostly do not have P1 repeats?
Do whatever smokie, I will have almost no time this week except to answer some stuff on the forum.
O.k. that is good. I am fairly busy as well. Maybe in a few days I will make some messages.
Incidentally, it only takes a single row swap operation (swap rows 9 and 20) to boost the m2 score from 2202.52 to 2415.13:
I did not know that.
To me, the simplest explanation as to why the cycles in the 340 react well to simple manipulations are because the sequential homophonic substiution is more random. And I think that has to be considered first and foremost. You have posted some numbers but what do you think?
That seems to be a reasonable assumption. Although, there are row swaps that also boost Z408’s m2 score, but to a lesser extent.
The row swap "greedy search" algorithm I made does this:
For each possible pair of rows,
1) Swap them and measure the effect on cycle score.
2) Retain only the swap that has the strongest effect.
3) Keep the resulting modified cipher, and repeat steps 1 and 2 until no more improvements are possible.
For Z340, the m2 cycle score goes from 2150.72 to 2778.56 (29.2% improvement) via these swaps:
01 HER>pl^VPk|1LTG2d 01 HER>pl^VPk|1LTG2d 02 Np+B(#O%DWY.<*Kf) 02 Np+B(#O%DWY.<*Kf) 03 By:cM+UZGW()L#zHJ 05 _9M+ztjd|5FP+&4k/ 04 Spp7^l8*V3pO++RK2 04 Spp7^l8*V3pO++RK2 05 _9M+ztjd|5FP+&4k/ 03 By:cM+UZGW()L#zHJ 06 p8R^FlO-*dCkF>2D( 06 p8R^FlO-*dCkF>2D( 07 #5+Kq%;2UcXGV.zL| 07 #5+Kq%;2UcXGV.zL| 08 (G2Jfj#O+_NYz+@L9 09 d<M+b+ZR2FBcyA64K 09 d<M+b+ZR2FBcyA64K 08 (G2Jfj#O+_NYz+@L9 10 -zlUV+^J+Op7<FBy- 12 2<clRJ|*5T4M.+&BF 11 U+R/5tE|DYBpbTMKO 18 ++)WCzWcPOSHT/()p 12 2<clRJ|*5T4M.+&BF 10 -zlUV+^J+Op7<FBy- 13 z69Sy#+N|5FBc(;8R 14 lGFN^f524b.cV4t++ 14 lGFN^f524b.cV4t++ 20 >MDHNpkSzZO8A|K;+ 15 yBX1*:49CE>VUZ5-+ 17 RcT+L16C<+FlWB|)L 16 |c.3zBK(Op^.fMqG2 15 yBX1*:49CE>VUZ5-+ 17 RcT+L16C<+FlWB|)L 16 |c.3zBK(Op^.fMqG2 18 ++)WCzWcPOSHT/()p 19 |FkdW<7tB_YOB*-Cc 19 |FkdW<7tB_YOB*-Cc 11 U+R/5tE|DYBpbTMKO 20 >MDHNpkSzZO8A|K;+ 13 z69Sy#+N|5FBc(;8R
For Z408, the m2 cycle score goes from 2855.73 to 3047.52 (6.7% improvement):
01 9%P/Z/UB%kOR=pX=B 01 9%P/Z/UB%kOR=pX=B 02 WV+eGYF69HP@K!qYe 02 WV+eGYF69HP@K!qYe 03 MJY^UIk7qTtNQYD5) 03 MJY^UIk7qTtNQYD5) 04 S(/9#BPORAU%fRlqE 04 S(/9#BPORAU%fRlqE 05 k^LMZJdrpFHVWe8Y 05 k^LMZJdrpFHVWe8Y 06 @+qGD9KI)6qX85zS( 06 @+qGD9KI)6qX85zS( 07 RNtIYElO8qGBTQS#B 07 RNtIYElO8qGBTQS#B 08 Ld/P#B@XqEHMU^RRk 08 Ld/P#B@XqEHMU^RRk 09 cZKqpI)Wq!85LMr9# 09 cZKqpI)Wq!85LMr9# 10 BPDR+j=6N(eEUHkF 10 BPDR+j=6N(eEUHkF 11 ZcpOVWI5+tL)l^R6H 11 ZcpOVWI5+tL)l^R6H 12 I9DR_TYrde/@XJQA 12 I9DR_TYrde/@XJQA 13 P5M8RUt%L)NVEKH=G 13 P5M8RUt%L)NVEKH=G 14 rI!Jk598LMlNA)Z(P 15 zUpkA9#BVW+VTtOP 15 zUpkA9#BVW+VTtOP 16 ^=SrlfUe67DzG%%IM 16 ^=SrlfUe67DzG%%IM 18 peXqWq_F#8c+@9A9B 17 Nk)ScE/9%%ZfAP#BV 20 VZeGYKE_TYA9%#Lt_ 18 peXqWq_F#8c+@9A9B 17 Nk)ScE/9%%ZfAP#BV 19 %OT5RUc+_dYq_^SqW 19 %OT5RUc+_dYq_^SqW 20 VZeGYKE_TYA9%#Lt_ 14 rI!Jk598LMlNA)Z(P 21 H!FBX9zXADd7L!=q 21 H!FBX9zXADd7L!=q 22 _ed##6e5PORXQF%Gc 22 _ed##6e5PORXQF%Gc 23 Z@JTtq_8JI+rBPQW6 23 Z@JTtq_8JI+rBPQW6 24 VEXr9WI6qEHM)=UIk 24 VEXr9WI6qEHM)=UIk
Since it is a greedy search, it might be getting stuck in local maxima. A good hillclimber would probably find even better combinations of row swap operations.
Expanding the search to include other operations (Swapping columns, swapping rectangular regions, flipping/rotating, etc) will probably find even better improvements to the cycle score, even for Z408.
I think if we consider the hypothesis that cycles were damaged by some transposition operations, we have to be careful about finding many false positives in putative un-transformations. Also, if we include even more kinds of cycling as has been discussed here recently, the "false positive" effect is potentially magnified.
I think if we consider the hypothesis that cycles were damaged by some transposition operations, we have to be careful about finding many false positives in putative un-transformations. Also, if we include even more kinds of cycling as has been discussed here recently, the "false positive" effect is potentially magnified.
Can you please run the cipher I put up through the same row swap test and share its improvement percentage. Thank you.
I think if we consider the hypothesis that cycles were damaged by some transposition operations, we have to be careful about finding many false positives in putative un-transformations. Also, if we include even more kinds of cycling as has been discussed here recently, the "false positive" effect is potentially magnified.
Can you please run the cipher I put up through the same row swap test and share its improvement percentage. Thank you.
Sure – I posted it earlier: viewtopic.php?p=56791#p56791
Here are some row swaps that boost your m2 cycles measurement:
01 +E7'D*!$3*.)HSF1$ 04 ITC#X3>E14#]+HLX 02 M&^*%Y6[ZU=($VQ,* 02 M&^*%Y6[ZU=($VQ,* 03 $R+>)*'/KG$(*8V$B 01 +E7'D*!$3*.)HSF1$ 04 ITC#X3>E14#]+HLX 03 $R+>)*'/KG$(*8V$B 05 -3*=$)*@II^1HQ$[> 06 !YP^<RU:T,<?$IO; 06 !YP^<RU:T,<?$IO; 07 #QK*5A"$9I0&CE*^. 07 #QK*5A"$9I0&CE*^. 05 -3*=$)*@II^1HQ$[> 08 +0D]M/JV$!K'*QR46 08 +0D]M/JV$!K'*QR46 09 )-4Z"MI$8H1?9'?E& 20 @K$*#$U:?RW2,Y*9E 10 7^A?(!-B)V?Z+55A 10 7^A?(!-B)V?Z+55A 11 *Q_M9KX+G_/$2-4%E 12 ]R!;SFL)_<*8"1I3& 12 ]R!;SFL)_<*8"1I3& 11 *Q_M9KX+G_/$2-4%E 13 #N=#HL';Y$O0Z*F@[ 13 #N=#HL';Y$O0Z*F@[ 14 S!X.V"':$*-^V:DK 14 S!X.V"':$*-^V:DK 15 3UF,*E!8AB"TQ$7K> 15 3UF,*E!8AB"TQ$7K> 16 [4=*["^H#$XME*T3 16 [4=*["^H#$XME*T3 17 C49+[]PG>-;%5#X* 17 C49+[]PG>-;%5#X* 18 &N)T/RE1@?N3>2SI 18 &N)T/RE1@?N3>2SI 19 Q#]P$P'[JU*;O*:1@ 19 Q#]P$P'[JU*;O*:1@ 20 @K$*#$U:?RW2,Y*9E 09 )-4Z"MI$8H1?9'?E&m_2s_cycles goes from 2202.52 to 2678.40
So that works out to a 21.6% increase.
