I've been interested in whether a Vigenere cipher without key repetition can be solved. If the key is random, it is a one-time pad and is theoretically unbreakable. On the other hand, if the key is a natural language text, I heard such a cipher (called a running key cipher) can be solved. But how?
I uploaded a new article about this: "Solving Running Key Ciphers (Manually/Digitally)".
It's a fun topic. I implemented both the Griffing and the Reddy and Knight algorithms in C, but it is not entirely clear what the Reddy and Knight algorithm was doing. For example what exactly does "sample" mean in the description? I didn't get the kind of results claimed. For Griffing, we have 7-gram data from AZDecrypt now, so that works a bit better.
ReplyDeleteI saw I'm not the only person who didn't understand what Reddy and Knight were doing. I did write to Reddy but didn't hear back.
https://crypto.stackexchange.com/questions/75559/running-key-gibbs-sampling
I thought "sampling A according to P" meant picking A that maximizes the probability P. But I was also wondering what exactly is done.
Delete"Sample spaces in P according to Pr(P)" seems to be trying many sets of word boundaries to choose the best set of boundaries in terms of Pr(P), or improving Pr(P) step by step as in hill climbing. Of course, "sampling" does not involve checking all the possibilities. Maybe the number of boundaries and the locations of those boundaries are randomly chosen and evaluated.
I think there are ways to evaluate Pr(P). (The likelihood of a given text string may be defined by n-gram statistics and the likelihood of a sequence of strings may be defined by some function (e.g., product) of the component strings.)
"Sample each word in P according to Pr(P)Pr(R)" seems to be similar to this: try many words in the strings for P (with R updated concurrently) to maximize the overall joint probability Pr(P)Pr(R).
To make it computationally tractable, instead of doing this for "each word (string)" one by one, we might repeat: picking one of the strings randomly and improving it as in hill climbing.
I don't do programming myself and I regret this is the best I can say.