Exercices: Réseaux, routage et systèmes

Un système d'exploitation exécute trois processus selon la règle « premier arrivé, premier servi » (sans interruption). Les instants sont exprimés en secondes.

1. Donner, pour chaque processus, l'intervalle de temps pendant lequel il s'exécute.

2. Calculer le temps d'attente de chaque processus, c'est-à-dire la durée écoulée entre son arrivée et le début de son exécution, puis le temps d'attente moyen, arrondi au centième.

3. Citer les trois états classiques d'un processus et préciser, à l'instant 3 s, l'état de chacun des trois processus.

Cinq routeurs R1, R2, R3, R4 et R5 sont reliés par les liaisons suivantes : R1–R2, R2–R3, R3–R4, R1–R5 et R5–R4. Le protocole de routage utilisé est RIP, qui minimise le nombre de sauts.

1. Donner le chemin choisi par RIP pour aller de R1 à R4 et le nombre de sauts correspondant.

2. Donner la table de routage de R1 sous la forme d'un tableau à trois colonnes : destination, prochain routeur, nombre de sauts. Les destinations sont R2, R3, R4 et R5.

3. La liaison R1–R5 tombe en panne. Donner le nouveau chemin de R1 à R4 et le nombre de sauts.

On utilise le chiffrement de César avec la clef 3 : chaque lettre est remplacée par la lettre située 3 positions plus loin dans l'alphabet, en revenant au début après Z.

1. Chiffrer le mot « NSI ».

2. Déchiffrer le message « HQJLQH ».

3. Indiquer si ce chiffrement est symétrique ou asymétrique et justifier la réponse.

4. Expliquer pourquoi ce chiffrement est facile à casser en essayant toutes les clefs possibles. Donner le nombre de clefs non triviales à essayer.

Cinq routeurs sont reliés par les liaisons suivantes. Dans le protocole OSPF, le coût d'une liaison est égal à $10^9$ divisé par son débit en bits par seconde.

1. Calculer le coût de chacune des liaisons.

2. Donner la route choisie par RIP de R1 vers R5 et son coût total au sens d'OSPF.

3. Donner la route choisie par OSPF de R1 vers R5 et son coût total. Justifier en comparant avec au moins trois autres routes.

4. Expliquer pourquoi ce problème de routage est un problème de recherche d'un chemin de poids minimal dans un graphe pondéré.

Léa se connecte au site de sa banque en ligne par le protocole HTTPS. On décrit de façon simplifiée l'établissement de la communication.

1. Rappeler la différence entre un chiffrement symétrique et un chiffrement asymétrique, en précisant dans chaque cas quelle clef sert à chiffrer et quelle clef sert à déchiffrer.

2. Ordonner les étapes suivantes.

   a) Le navigateur de Léa chiffre une clef symétrique avec la clef publique du serveur.

   b) Une fois la clef publique du serveur reçue, le navigateur de Léa génère une clef symétrique aléatoire.

   c) Les échanges suivants sont chiffrés avec la clef symétrique.

   d) Le serveur déchiffre la clef symétrique reçue avec sa clef privée.

   e) Le navigateur de Léa obtient la clef publique du serveur.

3. Expliquer pourquoi une personne qui intercepte la clef publique du serveur et la clef symétrique chiffrée ne peut pas retrouver la clef symétrique.

4. Expliquer pourquoi on utilise ensuite un chiffrement symétrique plutôt que de continuer avec le chiffrement asymétrique.

5. Dix personnes veulent pouvoir communiquer deux à deux de façon confidentielle avec un chiffrement symétrique, chaque paire disposant de sa propre clef. Calculer le nombre de clefs nécessaires. Comparer avec le nombre de paires de clefs nécessaires avec un chiffrement asymétrique, chaque personne disposant d'une paire (clef publique, clef privée).

Deux processus P1 et P2 partagent deux ressources R1 et R2, chacune utilisable par un seul processus à la fois. Le processus P1 exécute les actions suivantes : demander R1, demander R2, utiliser les deux ressources, libérer R2, libérer R1. Le processus P2 exécute : demander R2, demander R1, utiliser les deux ressources, libérer R1, libérer R2. Une demande d'une ressource déjà occupée met le processus en attente jusqu'à sa libération.

1. Décrire un entrelacement des exécutions de P1 et de P2 qui provoque un interblocage. Préciser quelle ressource détient chaque processus et laquelle il attend.

2. Décrire un entrelacement des exécutions qui se termine normalement.

3. Expliquer pourquoi, dans la situation de la question 1, aucun des deux processus ne pourra progresser.

4. Proposer une modification de l'ordre des demandes de ressources qui élimine tout risque d'interblocage, et justifier.

Un réseau est constitué de cinq routeurs A, B, C, D et E. Les coûts OSPF des liaisons sont donnés par le dictionnaire suivant.

reseau = {

    "A": {"B": 2, "C": 1},

    "B": {"A": 2, "C": 2, "D": 5, "E": 10},

    "C": {"A": 1, "B": 2, "D": 8},

    "D": {"B": 5, "C": 8, "E": 3},

    "E": {"B": 10, "D": 3},

}

1. Dérouler à la main l'algorithme de recherche de plus court chemin depuis A en présentant, à chaque étape, le routeur retenu et les distances provisoires mises à jour.

2. En déduire la table de routage de A : pour chaque destination, le coût total et le prochain routeur.

3. La liaison A–B tombe en panne. Recalculer la table de routage de A.

4. Comparer les coûts de A vers E avant et après la panne, et conclure sur la nécessité, pour OSPF, de recalculer les routes en cas de modification du réseau.

Trois processus sont ordonnancés selon la politique du tourniquet avec un quantum de 2 s. Un processus qui n'a pas terminé à la fin de son quantum retourne à la fin de la file des processus prêts. Si un processus arrive à un instant inférieur ou égal à la fin d'une tranche, il est placé dans la file avant le processus interrompu à cet instant.

1. Construire le diagramme de Gantt de l'exécution, sous la forme d'une suite d'intervalles de temps associés aux processus.

2. Donner l'instant de fin de chaque processus, puis son temps de séjour (instant de fin moins instant d'arrivée) et le temps de séjour moyen, arrondi au centième.

3. Mener la même étude avec la règle « premier arrivé, premier servi » sans interruption.

4. Comparer les temps de séjour moyens obtenus et citer un avantage du tourniquet pour un système interactif.

On illustre le chiffrement symétrique par un chiffrement « ou exclusif » (XOR) avec une clef partagée. Pour deux bits $a$ et $b$, $a \oplus b$ vaut 1 si $a$ et $b$ sont différents et 0 sinon. L'opération s'applique bit à bit à des octets. En Python, l'opérateur correspondant est ^.

1. On considère le message $m = 01101001$ et la clef $k = 10110010$. Calculer $c = m \oplus k$, puis $c \oplus k$ et comparer avec $m$.

2. Justifier que, pour tous bits $a$ et $b$, $(a \oplus b) \oplus b = a$. En déduire que le même procédé permet de chiffrer et de déchiffrer.

3. On considère la fonction suivante.

def chiffre(texte, cle):

    return [ord(c) ^ cle for c in texte]

a) Donner le résultat de `chiffre("NSI", 42)`. On rappelle que `ord("N")` vaut 78, `ord("S")` vaut 83 et `ord("I")` vaut 73.

b) Écrire une fonction `dechiffre(liste, cle)` qui renvoie le texte d'origine.

1. La clef est un entier compris entre 0 et 255. Donner le nombre de clefs possibles et expliquer pourquoi ce chiffrement est vulnérable à une attaque par force brute.

2. Pour une clef de 128 bits, donner le nombre de clefs possibles sous la forme d'une puissance de 2.

3. Expliquer pourquoi la clef partagée pose un problème de transmission entre les deux interlocuteurs, et décrire comment un chiffrement asymétrique permet de le résoudre dans le cadre d'une communication HTTPS.