Chaînes de caractères et code de César

Une chaîne de caractères est une suite de caractères (lettres, chiffres, symboles, espaces) traitée comme une seule valeur, par exemple un nom, une adresse IP ou un message. Ce chapitre présente les opérations du programme sur les chaînes (concaténation, extraction au début, au milieu ou à la fin, recherche d'un motif), leur traduction en Python, les algorithmes classiques sur les mots, puis deux chiffrements : le code de César et le chiffrement affine.

Écrire une chaîne

En Python, une chaîne s'écrit entre guillemets doubles ou simples : "BTS SIO" ou 'BTS SIO'. On choisit les doubles quand le texte contient une apostrophe : "l'adresse IP". Quelques caractères spéciaux s'écrivent avec une barre oblique inverse :

La chaîne vide "" ne contient aucun caractère ; sa longueur est 0. Elle sert à initialiser une chaîne qu'on construit dans une boucle, comme 0 initialise une somme.

Les opérations de base

La concaténation n'accepte que des chaînes : "Poste " + 12 lève TypeError. Il faut convertir : "Poste " + str(12).

Les caractères sont numérotés à partir de 0, comme les éléments d'une liste. Mais une chaîne Python est non modifiable : s[0] = "X" lève TypeError: 'str' object does not support item assignment. Pour « modifier » une chaîne, on en construit une nouvelle. C'est l'une des raisons pour lesquelles le programme recommande de considérer la chaîne comme un type à part entière, plutôt que comme un tableau de caractères.

Extraire le début, le milieu ou la fin

Le programme demande les fonctions d'extraction « en début, milieu ou fin ». En pseudo-code, on les écrit souvent Gauche, Droite et Milieu (comme dans un tableur) ; en Python, on utilise le découpage (slicing) s[début:fin], qui prend les caractères de l'indice début inclus à fin exclu, comme range.

Un découpage ne lève jamais d'erreur d'indice : s[:100] renvoie toute la chaîne si elle est plus courte. Accéder à un caractère seul, en revanche (s[100]), lève IndexError.

Chercher un motif

find renvoie −1 quand le motif est absent, comme la recherche séquentielle du cours. La méthode voisine index lève une ValueError à la place.

Transformer et tester

Ces méthodes renvoient une nouvelle chaîne et ne modifient pas s. Écrire s.upper() seul, sans affecter le résultat, ne sert à rien : il faut s = s.upper().

Découper et assembler

split découpe une chaîne selon un séparateur et renvoie une liste de morceaux ; join fait l'inverse.

ip = "192.168.10.25"
octets = ip.split(".")
print(octets)
print(int(octets[3]) + 1)

ligne = "jdupont;Dupont;Jean;Comptabilité"
champs = ligne.split(";")
print(champs[1], champs[3])

print(" ".join(["Bonjour", "le", "BTS"]))
print("-".join(octets))

['192', '168', '10', '25']
26
Dupont Comptabilité
Bonjour le BTS
192-168-10-25

Sans argument, split() découpe sur les espaces (un ou plusieurs) : " trois mots ici ".split() donne ["trois", "mots", "ici"]. Les morceaux sont des chaînes : convertis-les si ce sont des nombres.

Formater un affichage

Construire un message, c'est assembler du texte et des valeurs. Trois façons, de la plus simple à la plus pratique :

nom = "Léa"
moyenne = 15.756
rang = 2

print("Élève :", nom, "- moyenne :", moyenne)              # print avec virgules
print("Élève : " + nom + " - rang : " + str(rang))         # concaténation
print(f"Élève : {nom} - moyenne : {moyenne:.2f} - rang : {rang}")  # f-string
print(f"|{nom:<8}|{rang:>4}|")                             # alignements

Élève : Léa - moyenne : 15.756
Élève : Léa - rang : 2
Élève : Léa - moyenne : 15.76 - rang : 2
|Léa     |   2|

Dans une f-string (une chaîne précédée de f), chaque expression entre accolades est remplacée par sa valeur. Après le deux-points, un format : .2f pour deux décimales, <8 pour aligner à gauche sur 8 caractères, >4 à droite sur 4. Le programme n'exige pas cette mise en forme, mais elle rend tes affichages nets en quelques caractères.

Parcourir une chaîne

Comme une liste, une chaîne se parcourt caractère par caractère avec for. Compter les voyelles d'un mot :

Fonction NbVoyelles(mot : chaîne) : entier
    nb ← 0
    Pour chaque c dans mot Faire
        Si c est dans "aeiouy" Alors
            nb ← nb + 1
        FinSi
    FinPour
    Retourner nb
FinFonction

def nb_voyelles(mot):
    nb = 0
    for c in mot.lower():
        if c in "aeiouyàâéèêëîïôùûü":
            nb = nb + 1
    return nb


print(nb_voyelles("Algorithmique"), nb_voyelles("Réseaux"))

6 4

mot.lower() évite d'oublier les majuscules, et la chaîne de voyelles inclut les lettres accentuées : en français, sans elles, « Réseaux » n'aurait que 3 voyelles.

Construire une chaîne suit le motif de l'accumulateur, avec la chaîne vide comme point de départ. Inverser un mot sans [::-1] :

def inverser(mot):
    resultat = ""
    for c in mot:
        resultat = c + resultat   # chaque caractère passe devant
    return resultat


print(inverser("routeur"))

ruetuor

Codes des caractères

Chaque caractère a un code numérique : c'est ce nombre que l'ordinateur stocke. Python utilise Unicode, dont les 128 premiers codes reprennent l'ancienne table ASCII. ord(c) donne le code d'un caractère, chr(n) le caractère d'un code.

Les lettres majuscules ont des codes consécutifs, de 65 à 90 : la position d'une majuscule dans l'alphabet (A = 0, B = 1… Z = 25) est ord(c) - 65. C'est la base des chiffrements qui suivent. C'est aussi pourquoi "Z" < "a" : 90 est inférieur à 97.

Le code de César

Le code de César remplace chaque lettre par celle qui se trouve k rangs plus loin dans l'alphabet, en revenant au début après Z. La clé k est un entier de 1 à 25. Avec k = 3, A devient D, B devient E, et X devient A.

Si p est la position d'une lettre (A = 0), sa position chiffrée est c = (p + k) MOD 26. Le MOD 26 réalise le retour au début : pour X (23) avec k = 3, (23 + 3) MOD 26 = 0, soit A. Pour déchiffrer, on recule : p = (c - k) MOD 26, ce qui revient à chiffrer avec la clé -k.

Fonction Cesar(texte : chaîne, k : entier) : chaîne
// Chiffre les lettres majuscules ; les autres caractères sont recopiés
    resultat ← ""
    Pour chaque c dans texte Faire
        Si c ≥ "A" ET c ≤ "Z" Alors
            p ← code(c) - 65
            resultat ← resultat + caractere((p + k) MOD 26 + 65)
        Sinon
            resultat ← resultat + c
        FinSi
    FinPour
    Retourner resultat
FinFonction

def cesar(texte, k):
    """Chiffre les majuscules de texte avec la clé k ; le reste est recopié."""
    resultat = ""
    for c in texte:
        if "A" <= c <= "Z":
            p = ord(c) - 65
            resultat = resultat + chr((p + k) % 26 + 65)
        else:
            resultat = resultat + c
    return resultat


chiffre = cesar("BONJOUR", 3)
print(chiffre)
print(cesar(chiffre, -3))
print(cesar("BTS SIO", 13), cesar(cesar("BTS SIO", 13), 13))

ERQMRXU
BONJOUR
OGF FVB BTS SIO

Avec k = 13 (le ROT13), chiffrer deux fois redonne le texte de départ, puisque 13 + 13 = 26. En Python, % renvoie toujours un reste positif quand le diviseur est positif : (1 - 3) % 26 vaut 24, et le déchiffrement avec une clé négative fonctionne sans précaution. En C# ou en JavaScript, il faudrait écrire ((p - k) % 26 + 26) % 26, car leur % peut être négatif (chapitre 2).

Casser un message chiffré par force brute, c'est une boucle sur les 25 clés :

def cesar(texte, k):
    resultat = ""
    for c in texte:
        if "A" <= c <= "Z":
            resultat = resultat + chr((ord(c) - 65 + k) % 26 + 65)
        else:
            resultat = resultat + c
    return resultat


message = "WKH SDVVZRUG LV VLR"
for k in range(1, 26):
    essai = cesar(message, -k)
    if "PASSWORD" in essai:
        print("Clé", k, ":", essai)

Clé 3 : THE PASSWORD IS SIO

Ici, on cherche un mot attendu dans le texte déchiffré. Sans indice, on afficherait les 25 essais et on lirait celui qui a un sens.

Le chiffrement affine

Le chiffrement affine généralise César : c = (a × p + b) MOD 26, avec deux clés a et b. César est le cas a = 1. Pour que deux lettres différentes ne donnent jamais la même lettre chiffrée, a doit être premier avec 26, c'est-à-dire PGCD(a, 26) = 1 : a est impair et n'est pas 13. Les valeurs possibles sont 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 et 25.

Avec a = 5 et b = 8, chiffrons BTS SIO :

BTS SIO devient NZU UWA.

Pour déchiffrer, il faut résoudre c ≡ a × p + b (mod 26), donc p ≡ a' × (c − b) (mod 26), où a' est l'inverse de a modulo 26 : l'entier tel que a × a' MOD 26 = 1. Pour a = 5, a' = 21, car 5 × 21 = 105 = 4 × 26 + 1. On le trouve en essayant les entiers de 1 à 25, ou avec pow(a, -1, 26) en Python. Le calcul de l'inverse modulaire est détaillé au cours d'arithmétique (inverse modulaire), avec pourquoi a doit être premier avec 26 (chiffrement affine).

def affine(texte, a, b):
    resultat = ""
    for c in texte:
        if "A" <= c <= "Z":
            p = ord(c) - 65
            resultat = resultat + chr((a * p + b) % 26 + 65)
        else:
            resultat = resultat + c
    return resultat


def inverse_mod26(a):
    """Renvoie l'inverse de a modulo 26, ou -1 s'il n'existe pas."""
    for x in range(1, 26):
        if a * x % 26 == 1:
            return x
    return -1


def affine_dechiffre(texte, a, b):
    a_inv = inverse_mod26(a)
    resultat = ""
    for c in texte:
        if "A" <= c <= "Z":
            p = (a_inv * (ord(c) - 65 - b)) % 26
            resultat = resultat + chr(p + 65)
        else:
            resultat = resultat + c
    return resultat


chiffre = affine("BTS SIO", 5, 8)
print(chiffre, inverse_mod26(5), affine_dechiffre(chiffre, 5, 8))

NZU UWA 21 BTS SIO

inverse_mod26 est une recherche séquentielle sur les 25 candidats. Si a n'est pas premier avec 26 (par exemple a = 4), aucun x ne convient et la fonction renvoie −1 : le message ne pourrait pas être déchiffré, car deux lettres auraient le même chiffré. Les sujets d'algorithmique et d'arithmétique du BTS utilisent volontiers ces chiffrements : le programme cite « codage, cryptage et décryptage » parmi les thèmes d'exercices.

Exercices

def est_palindrome(mot):
    n = len(mot)
    for i in range(n // 2):
        if mot[i] != mot[n - 1 - i]:
            return False
    return True


def est_palindrome_phrase(phrase):
    lettres = phrase.lower().replace(" ", "")
    return est_palindrome(lettres)


print(est_palindrome("kayak"), est_palindrome("réseau"))
print(est_palindrome_phrase("Engage le jeu que je le gagne"))

def ip_valide(ip):
    octets = ip.split(".")
    if len(octets) != 4:
        return False
    for o in octets:
        if not o.isdigit():
            return False
        if int(o) > 255:
            return False
    return True


for essai in ["192.168.1.10", "10.0.0", "256.1.1.1", "192.168.a.1", "172.16.0.1"]:
    print(essai, ip_valide(essai))

192.168.1.10 True
10.0.0 False
256.1.1.1 False
192.168.a.1 False
172.16.0.1 True

def identifiant(prenom, nom):
    brut = prenom[0] + nom
    brut = brut.lower().replace(" ", "").replace("-", "")
    return brut[:8]


print(identifiant("Jean", "Dupont"))
print(identifiant("Marie", "Le Goff-Martin"))

def nb_mots(phrase):
    nb = 0
    dans_un_mot = False
    for c in phrase:
        if c != " " and not dans_un_mot:
            nb = nb + 1
            dans_un_mot = True
        elif c == " ":
            dans_un_mot = False
    return nb


print(nb_mots("  Le BTS   SIO  "), len("  Le BTS   SIO  ".split()))