# 1 Construction

Assume that all data are encoded using the alphabet $$\Sigma = \{0,\dots,n-1\}$$ (where $$n$$ is the length of the alphabet).

Vigenère cipher (poly-alphabetic shift cipher). Given $$\ell \in \mathbb{Z}^+$$ which is the fixed length of the plaintext and $$t \in \mathbb{Z}^+$$ which is the fixed length of the key, define the following encryption scheme $$\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$$:

• Message space $$\mathcal{M} = \{0,\dots,n-1\}^\ell$$.
• Key space $$\mathcal{K} = k_1 k_2 \dots k_t = \{0,\dots,n-1\}^t$$.
• Ciphertext space $$\mathcal{C} = \{0,\dots,n-1\}^\ell$$.
• $$\mathsf{Gen}$$ outputs a key $$k \in \mathcal{K}$$ according to the uniform distribution.
• $$\mathsf{Enc}$$ takes as input a key $$k \in \mathcal{K}$$ and a message $$m \in \mathcal{M}$$, and outputs the ciphertext $\mathsf{Enc}_k(m_1 \dots m_\ell) = c_1 \dots c_\ell \textrm{, where } c_i := [(m_i+k_{[(i-1) \operatorname{mod} t] + 1}) \operatorname{mod} n].$
• $$\mathsf{Dec}$$ takes as input a key $$k \in \mathcal{K}$$ and a ciphertext $$c \in \mathcal{C}$$, and outputs the message $\mathsf{Dec}_k(c_1 \dots c_\ell) = m_1 \dots m_\ell \textrm{, where } m_i := [(c_i-k_{[(i-1) \operatorname{mod} t] + 1}) \operatorname{mod} n].$

($$k_{[(i-1) \operatorname{mod} t] + 1}$$ guarantees that for each $$i$$, a valid index from the range $$\{1,\dots,t\}$$ is selected, e.g., for $$i \in \{1,1+t,1+2t,\dots\}$$, $$k_1$$ is always used.)

Remark 1.1. In practice, the key length $$t$$ is not necessarily known (to the attacker). We fix it here as an integer so that $$\mathsf{Gen}$$ can choose a key uniformly from the finite key space.

# 2 Secrecy and Cryptanalysis

Notice that $$|\mathcal{K}| = n^t$$, $$|\mathcal{M}| = n^\ell$$. If $$|\mathcal{K}| < |\mathcal{M}|$$, then the scheme cannot be perfectly secret.

Theorem 2.1. Vigenère cipher is not perfectly secret when $$t < \ell$$.

Possible cryptanalysis:

1. When the key length $$t$$ is known, for all $$j \in \{1,\dots,t\}$$, extract all sequences $c_j,c_{j+t},c_{j+2t}\dots$ and apply frequency analysis.
2. When the key length is unknown, two approaches may be used to determine the key length $$t$$ efficiently:
• Kasiski’s method.
• Index of coincidence method.