Looks like I had to sleep on it, I think now I know how to apply the formula to this cipher. Note that I'm not a cryptographer, treat this with a generous portion of salt.
U = H(k)/D
Assuming all keys are equally likely, H(k) is just the logarithm of the total number of possible keys. For Brumbaugh's cipher this is fixed and easy to compute combinatorially as in You are not allowed to view links. Register or Login to view.. H(k) reflects how many keys we need to go through in a brute force attack.
And D is the logarithm of the total number of all possible strings in the given alphabet divided by the number of all meaningful strings (those that we would find plausible as the solution to the cipher) per each new character of the plaintext. For example, for English appending a new character creates 26 possible new random strings, at the same time given 1.5 bits per character in English (as per the Wikipedia article), adding a new character to a string would on average produce 2 ** 1.5 or 2.83 new meaningful strings. So, D for a simple substitution in English is log2(26 / 2.83), or log2(26) - log2(1.5) or ~3.2.
Overall, D reflects how rare meaningful strings are. For example, if all possible combinations of Latin letters (say, AAA, AAB, AAC, ... ZZZZZZY, ZZZZZZZ...) were meaningful to us, we won't be able to decode the cipher, because any key would produce a different meaningful solution, and the proportion of all strings to meaningful strings would be 1, its logarithm would be 0 and U would be H(k) / 0 or infinite.
Instead of U as the length, we can think about base charset size to the power of U as the total number of all possible cipher texts of length U characters and then the equation in preudomath would just become:
log(total number of possible ciphertext of length U) = log(total number of possible keys) / log(number of new random plaintext strings when adding one character / mean number of new meaningful plaintext strings when adding one character)
or:
how long is the ciphertext we'll need = how many keys we need to go through vs how rare meaningful plaintexts are among random plaintexts
which looks understandable to me. The more keys we have to go through and the larger the number of possible meaningful plaintexts is, the longer should the ciphertext be to leave us with just one single working combination of a key and meaningful plaintext.
This would work as is for a simple substitution cipher, but the Brumbaugh's cipher is lossy, a few source characters are mapped to the same digit. The effect of this is that for the same number of meaningful and random plaintexts we have a lower number of the digit sequences, and what is important, the same digit sequence will correspond to multiple plaintexts and possibly multiple meaninful plaintexts.
If the goal is to identify the correct key AND the correct unique plaintext, then the outcome we are looking for is that, after bruteforcing all possible keys, not only there is only one digit sequence corresponding to a meaningful English plaintext, but this sequence also corresponds to one meaningful English plaintext only.
So, when computing D we can take the logarithm of (all of them per character): the total number of possible digit sequences (A) divided by the total number of digit sequences corresponding to meaningful plaintexts (B) and multiplied by the total number of meaninful plaintexts divided by the total number of corresponding unique digit sequences /C/.
(A) is simply 9, as there are 9 distinct digits. Assuming uniform distribution of plaintexts, /C/ is 3, as there are 3 times as many characters (27) as there are digits (9). (B) is 2.83 * 3, since by adding a new single digit we effectively add 3 possible characters (here is a caveat, see below).
So, if D = log2(A / B * C), then D = log2(9 / (2.83 * 3) * 3) = log2(9 / 2.83) ~ 0.5
If this is the right way of looking at it, then the result is the same as I computed based on a wrong assumption in my previous post:
U = 70 / 0.5 = 140
*the caveat: I think B depends on the specific mapping of plaintext into digits. In principle some variants of the key for Brumbaugh's cipher would be nearly impossible to use making the cipher too lossy to recover the plaintext no matter its length and hence no amount of ciphertext would lead to a unique solution.
U = H(k)/D
Assuming all keys are equally likely, H(k) is just the logarithm of the total number of possible keys. For Brumbaugh's cipher this is fixed and easy to compute combinatorially as in You are not allowed to view links. Register or Login to view.. H(k) reflects how many keys we need to go through in a brute force attack.
And D is the logarithm of the total number of all possible strings in the given alphabet divided by the number of all meaningful strings (those that we would find plausible as the solution to the cipher) per each new character of the plaintext. For example, for English appending a new character creates 26 possible new random strings, at the same time given 1.5 bits per character in English (as per the Wikipedia article), adding a new character to a string would on average produce 2 ** 1.5 or 2.83 new meaningful strings. So, D for a simple substitution in English is log2(26 / 2.83), or log2(26) - log2(1.5) or ~3.2.
Overall, D reflects how rare meaningful strings are. For example, if all possible combinations of Latin letters (say, AAA, AAB, AAC, ... ZZZZZZY, ZZZZZZZ...) were meaningful to us, we won't be able to decode the cipher, because any key would produce a different meaningful solution, and the proportion of all strings to meaningful strings would be 1, its logarithm would be 0 and U would be H(k) / 0 or infinite.
Instead of U as the length, we can think about base charset size to the power of U as the total number of all possible cipher texts of length U characters and then the equation in preudomath would just become:
log(total number of possible ciphertext of length U) = log(total number of possible keys) / log(number of new random plaintext strings when adding one character / mean number of new meaningful plaintext strings when adding one character)
or:
how long is the ciphertext we'll need = how many keys we need to go through vs how rare meaningful plaintexts are among random plaintexts
which looks understandable to me. The more keys we have to go through and the larger the number of possible meaningful plaintexts is, the longer should the ciphertext be to leave us with just one single working combination of a key and meaningful plaintext.
This would work as is for a simple substitution cipher, but the Brumbaugh's cipher is lossy, a few source characters are mapped to the same digit. The effect of this is that for the same number of meaningful and random plaintexts we have a lower number of the digit sequences, and what is important, the same digit sequence will correspond to multiple plaintexts and possibly multiple meaninful plaintexts.
If the goal is to identify the correct key AND the correct unique plaintext, then the outcome we are looking for is that, after bruteforcing all possible keys, not only there is only one digit sequence corresponding to a meaningful English plaintext, but this sequence also corresponds to one meaningful English plaintext only.
So, when computing D we can take the logarithm of (all of them per character): the total number of possible digit sequences (A) divided by the total number of digit sequences corresponding to meaningful plaintexts (B) and multiplied by the total number of meaninful plaintexts divided by the total number of corresponding unique digit sequences /C/.
(A) is simply 9, as there are 9 distinct digits. Assuming uniform distribution of plaintexts, /C/ is 3, as there are 3 times as many characters (27) as there are digits (9). (B) is 2.83 * 3, since by adding a new single digit we effectively add 3 possible characters (here is a caveat, see below).
So, if D = log2(A / B * C), then D = log2(9 / (2.83 * 3) * 3) = log2(9 / 2.83) ~ 0.5
If this is the right way of looking at it, then the result is the same as I computed based on a wrong assumption in my previous post:
U = 70 / 0.5 = 140
*the caveat: I think B depends on the specific mapping of plaintext into digits. In principle some variants of the key for Brumbaugh's cipher would be nearly impossible to use making the cipher too lossy to recover the plaintext no matter its length and hence no amount of ciphertext would lead to a unique solution.