Challenges from competitors

[Madness]

@Mattyrat2027, there is a really good exposition of fitness functions at
http://practicalcryptography.com/cryptanalysis/text-characterisation/quadgrams/
I couldn’t explain it any better.
(Before anyone asks, I am not connected in any way to that website.)

The hill-climbing attack on the Pollux cipher goes like this:
The fitness function is based on 10-gram (dekagram) frequencies of English that has been encoded with Morse.
In other words, I took a big block of English text and encoded it, then I counted up how many times
………. occurs, then how many times ………_ occurs, etc., up to xxxxxxxxxx. There are 3^10 entries in
the table. The fitness function is otherwise the same as in the practicalcryptography.com example.
To climb the hill, it starts with a random key, which is a string of 36 dots, dashes, and x’s. At each step, it
changes one of these symbols to something else. If that results in a better fitness, it keeps the change and
continues. If not, it tries changing a different symbol in the the key. To avoid getting stuck in a local
max, the algorithm allows a downward step about 5% of the time, if the step is only a little bit downward.
When the fitness cannot be improved any longer, it spits out the key.
(Again, don’t assume that I invented this trick; I did not.)

@F6exb, could you please rephrase the question? I don’t understand what you are asking.

[F6exb]

@Madness,
In your example of hill climbing, there is a lot of “-” “x” and “.”

.x..x..x….-xx-..-x………-xx..xx -15.4769347575
.x..x..x…x-xx-..-x………-xx..xx -15.2620088256
.x..x..x…x-xx-..-x……….xx..xx -15.1371076389

Can you explain the meaning of these patterns ?

[Madness]

@F6exb, those are trial keys. The numbers after them are the values of the fitness.
I like to watch my programs work, so there is a lot of useless output.

[Mattyrat2027]

@Madness

Thanks for the link.

I have created a (rather crude) fitness function, working by grabbing a list of the 10000 most common words, and then automating an ‘if word in list: print(true)’ sort of thing.

How would you tell the code to iterate the changes in a hill climbing function?

[The-letter-wriggler]

TLW Cipher #1 Solution and Plaintext
====================================

KEY : Mixed Caersar shifts
[PT] : abcdefghijklmnopqrstuvwxyz
[CT] : BCDEFGHIJKLMNOPQRSTUVWXYZA shift 1 (odd shift on odd letters)
[CT] : CDEFGHIJKLMNOPQRSTUVWXYZAB shift 2 (even shift on even letters)

THE PLAINTEXT
=============
Excellent! You did it, the readable text appears before your very eyes! Shame you do not get a prize but hey, your prize is your cleverness.

DECRYPTION:
===========
One way to a decrypt…

As every odd letter has a Caesar shift of 1, and every even letter has a Ceasar shift of 2…
Do a Caesar shift 1 decrypt of the ciphertext, then delete every even letter
eycflmeotzovdjdjtuhfrfaeaclftfxuaqpfasscegosezovrwesyfyfsthbmfypueooougftbpsiaecuuhfyzovrqrjzfitypuscmewesnsst
giving
ECLETODDTHRAALTXAPASEOEOREYYSHMYUOOGTPIEUHYORRZIYUCEENS (odd letters only)

Do a Caesar shift 2 decrypt of the ciphertext, then delete every odd letter
dxbekldnsynucicistgeqezdzbkesewtzpoezrrbdfnrdynuqvdrxexersgalexotdnnntfesaorhzdbttgexynuqpqiyehsxotrbldvdrmres
giving
XELNYUIITEEDBEETPERBFRYUVREESAEODNTEARZBTEYUPIESORLVRES (even letters only)

The 2 decrypts
ECLETODDTHRAALTXAPASEOEOREYYSHMYUOOGTPIEUHYORRZIYUCEENS
XELNYUIITEEDBEETPERBFRYUVREESAEODNTEARZBTEYUPIESORLVRES

Weave the letters together odd-even, odd-even etc to get the plaintext.
By Railfence – 2 rails
E_C_L_E_T_O_D_D_T_H_R_A_A_L_T_X_A_P_A_S_E_O_E_O_R_E_Y_Y_X_E_L_N_Y_U_I_I_T_E_E_D_B_E_E_T_P_E_R_B_F_R_Y_U_V_R_E_
_X_E_L_N_Y_U_I_I_T_E_E_D_B_E_E_T_P_E_R_B_F_R_Y_U_V_R_E_E_S_A_E_O_D_N_T_E_A_R_Z_B_T_E_Y_U_P_I_E_S_O_R_L_V_R_E_S
EXCELLENTYOUDIDITTHEREADABLETEXTAPPEARSBEFOREYOURVERYEYESSHAMEYOUDONOTGETAPRIZEBUTHEYYOURPRIZEISYOURCLEVERNESS

[The-letter-wriggler]

TLW Cipher #2 Solution and Plaintext
====================================

KEY  : ASCII/ASCII shift 13 [The 95 printable Characters (space to tilde)]
[PT] :  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_

abcdefghijklmnopqrstuvwxyz{|}~
[CT] : -./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefghijklmnopqrstuvwxyz{|}~ !"#$%&'()*+,

You enter a cave and find that you are in a maze of little twisty passages, they all look different, you walk on and find you are in a maze of little twisting passages, it sure looks different you walk on, you are now in a maze of twisting little passages, different looking again so you walk on, you now feel lost in a maze of twisty little passages all seemingly different you move on and you find you are in a little maze of twisting passages all different, you take another route to find you are in a little maze of twisty passages all different, you keep moving through the passages noticing you are in a little twisty maze of passages then in a twisting little maze of passages and then you are in a twisting maze of little passages, you start to panic but go on, now you are in a twisty little maze of passages, all different but wait, what is that ahead? you move into a twisty maze of little passages with light at the end of one passage, you run down that passage and enter into daylight, you are free of the cave!
(Inspired from the Colossal Cave Adventure a text based adventure, ninteen seventy five – seventy seven)

[The-letter-wriggler]

TLW Cipher #2 Solution and Plaintext
==================================== (Reposted)

KEY : 95 Character (space to tilde) ASCII/ASCII shift 13
[PT] : !”#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
[CT] : -./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ !”#$%&'()*+,

You enter a cave and find that you are in a maze of little twisty passages, they all look different, you walk on and find you are in a maze of little twisting passages, it sure looks different you walk on, you are now in a maze of twisting little passages, different looking again so you walk on, you now feel lost in a maze of twisty little passages all seemingly different you move on and you find you are in a little maze of twisting passages all different, you take another route to find you are in a little maze of twisty passages all different, you keep moving through the passages noticing you are in a little twisty maze of passages then in a twisting little maze of passages and then you are in a twisting maze of little passages, you start to panic but go on, now you are in a twisty little maze of passages, all different but wait, what is that ahead? you move into a twisty maze of little passages with light at the end of one passage, you run down that passage and enter into daylight, you are free of the cave!
(Inspired from the Colossal Cave Adventure a text based adventure, ninteen seventy five – seventy seven)

[Madness]

@Mattyrat2027,
Here is some Python code from the Pollux hill-climbing program:

from random import randrange, choice
parent = ["x"]*len(s) # parent key is a list of x's; length of list is the number of ciphertext symbols
pfit = -99.
count = 0
while count < 1000:
    child = parent[:]
    x = randrange(len(child))
    y = choice([".","-","x"])
    child[x] = y           # changes one element of child key
    p = decrypt(c,s,child) # decrypts to morse, not to english
    cfit = fitness(p)      # fitness is based on english that has been encoded with morse code
    if cfit <= pfit:
        count += 1
    else:
        count = 0
    if (cfit > pfit) or ((cfit > 1.05*pfit) and (randrange(100) < 5)):
        pfit = cfit
        parent = child[:]
        print unpack(parent),pfit # unpack() just makes it look prettier

My fitnesses are all negative, so interpret 1.05*pfit as pfit-epsilon, where epsilon is some small number.

I hope that answers your question.

[Author]

Posts