[NEWBIE]vigenere
cicap
For example with a key length of 4, against a plain text of 8 characters.
Sebastian Gottschalk
> How can I give a proof that Vigenere is not perfect, using Shannon theory?
Very simply. A perfect cipher is isomorph to addition within a group,
hence One Time Pad.
> For example with a key length of 4, against a plain text of 8 characters.
4 < 8
q.e.d.
Douglas A. Gwyn
> How can I give a proof that Vigenere is not perfect, using Shannon theory?
> For example with a key length of 4, against a plain text of 8 characters.
Sounds like a homework problem. Presumably you're expected to
use the definition of "perfect secrecy" and some basic probability
theory in your proof. Once you have some experience with such
matters, it is easy to see that the ciphertext characters at the
1st and 5th positions are related through a constraint induced
by the key repetition, which means that they have less entropy
than would be the case in the absence of the constraint. Just
work that up in your theoretical framework and you will have a
proof.
Mike Amling
> How can I give a proof that Vigenere is not perfect, using Shannon theory?
> For example with a key length of 4, against a plain text of 8 characters.
For perfect encryption, obtaining the ciphertext does not change your
a priori probabilities of various plaintexts. When you obtain the 8
character Vigenère ciphertext you speak of, though, a lot of plaintexts'
probabilities go to zero, namely those where the Vigenère key used for
the first four characters would be inconsistent with that used for the
second four characters.
--Mike Amling
Kristian Gjųsteen
>A perfect cipher is isomorph to addition within a group,
What exactly does this sentence mean? I cannot at first reading
distinguish it from nonsense.
--
Kristian Gjųsteen
Sebastian Gottschalk
Any cipher that is perfectly secure in terms of Shannon information
theory can be expressed / is strictly isomorph to the operation of
adding a randomly chosen key to the plaintext, assuming that the base
mathematical structure is a group and all values are uniformly
distributed. Hence One Time Pad.
Mike Amling
If the set of plaintexts and the set of ciphertexts have order N,
then the set of keys of a perfect cipher must have order which is >=N
and <=N!, and for each ciphertext c, the total probability of the keys
that map plaintext p to c must equal the total probability of the keys
that map plaintext q to c, for all p and q.
There are quite a few perfect ciphers, and I don't see how you can
claim that each of them is "adding" a key "to the plaintext". What is
the group operation? Composition of ciphers? I can make a perfect cipher
that is, for instance, not closed under composition.
--Mike Amling
Sebastian Gottschalk
> If the set of plaintexts and the set of ciphertexts have order N, then
> the set of keys of a perfect cipher must have order which is >=N and
> <=N!, and for each ciphertext c, the total probability of the keys that
> map plaintext p to c must equal the total probability of the keys that
> map plaintext q to c, for all p and q.
> There are quite a few perfect ciphers, and I don't see how you can
> claim that each of them is "adding" a key "to the plaintext".
The properties of a perfect cipher, as you stated above, are directly
equivalent to the properties of addition within a group.
> What is the group operation?
That depends on the isomorphism.
Kristian Gjųsteen
Let the alphabet be a group with more than two elements. The set
of keys is the set of sequences of permutations of the alphabet.
Encrypt by applying the permutations in sequence. Decrypt by applying
the inverse permutations.
This is clearly a perfect cipher, yet it is not "isomorphic" (for
any reasonable value of "isomorphic" that I can think of) to the
cipher that adds a random sequence to the plaintext.
--
Kristian Gjųsteen
Sebastian Gottschalk
As permutations are an (even associative) group with their sequential
application as operation, this is exactly an isomorphism.
Kristian Gjųsteen
First, talking about "associative groups" is nonsense. The group
operation is associative by definition.
Second, there is no point in saying repeatedly that they are
isomorphic. Say what an isomorphism is, and what the specific
isomorphism you claim exist is.
--
Kristian Gjųsteen