2
$\begingroup$

I was wondering why mathematically we can know the key in the Vigenère cipher if we know in advance a message and its encryption.

$\endgroup$
  • $\begingroup$ (What did you try to see if you could reconstruct a key from one pair plain and cipher text?) $\endgroup$ – greybeard Nov 17 '19 at 1:47
1
$\begingroup$

A Vigenère cypher on an alphabet of size $M$, which we identify with the integers modulo $M$, works as follows.

The key is an arbitrary word, $k_0 \ldots k_{\ell-1}$.

Given a plaintext $p_0 \ldots p_{n-1}$, the ciphertext $c_0 \ldots c_{n-1}$ is given by $$ c_i = p_i + k_{i \bmod \ell} \bmod M. $$ For example, suppose that we are trying to encipher decimal digits, and use as key the word 2019. If we want to encrypt the plaintext 18446744073709551616, then we form the following table:

plain  18446744073709551616
key    20192019201920192019
cipher 38538753274629643625

(In this case $n$ was divisible by $\ell$, but that need not be the case.)

In this table, the key repeats enough times, and each digit of the cipher is just the sum of the digits above it, throwing away the carry (for example, from 4 and 9 we get 3 rather than 13).

To decipher a ciphertext $c_0 \ldots c_{n-1}$, we simply reverse the process: $$ p_i = c_i - k_{i \bmod \ell} \bmod M. $$ In the table above, given the cipher and the key, we just need to subtract the key from the cipher, borrowing if necessary (so 3-9=4 since 13-9=4).

Similarly, given a plaintext/ciphertext pair, we can recover the key in the sense of constructing the sequence $$ k_i = c_i - p_i \bmod M. $$ This recovers the key up to its length $\ell$, which need not be known in advance.

In the table above, given the ciphertext and the plaintext, we subtract the latter from the former to obtain

201920192019201920192019

Out of which we can guess that the key is 2019.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thank you very much! $\endgroup$ – alberto123 Nov 16 '19 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.