Il n'est pas très compliqué de remarquer que la fiabilité des chiffres à substitution monoalphabétique ne sont pas très sûrs. Guy pourrait facilement déchiffrer le message d'Alice et Bob sans grand effort. C'est pourquoi le chiffrement polyalphabétique fut inventé. L'effet d'un chiffre à substitution polyalphabétique sur un texte est plus important que celui d'un chiffre à substitution monoalphabétique: il mélange la fréquence des lettres. Donc le mot « bonjour » pourrait théoriquement être « bbbbbbb » en utilisant la clé appropriée. Donc on pourrait dire qu'un chiffre de substitution polyalphabétique est un chiffre dans lequel les lettres du texte chiffré ne correspondent pas une-à-une aux lettres du texte non-chiffré.
Le principe est très simple et a été mis en oeuvre en premier par Blaise de Vigenère au seizième siècle. Étant diplomate de métier, Vigenère était constamment en prise avec des messages au contenu secret à transmettre à ses autorités et les chiffres à substitution monoalphabétique étaient relativement faciles à déchiffrer. Après avoir été diplomate pendant quelques années, il abandonna son métier pour se consacrer à l'étude de la cryptographie et développa le populaire chiffre de Vigenère. Ce chiffre consiste à utiliser 26 alphabets pour chiffrer le message, de là le nom de chiffre polyalphabétique.
La première chose à faire lorsqu'on veut encrypter un message en utilisant
le chiffre de Vigenère est de créer un carré de Vigenère comme celui
du tableau 1.
Le carré est construit en décalant les alphabets d'une lettre à chaque colonne ou ligne. Pour chiffrer un texte il faut donc premièrement définir une clé de chiffrement.