Système & Réseaux ***************** 1 Rudiments de cryptographie *=*=*=*=*=*=*=*=*=*=*=*=*=*=* L'objectif de ce cours est de vous donner un aperçu des techniques de cryptographie qui sont utilisées dans des protocoles comme PGP, ssh ou ssl: chiffrage et déchiffrage, signature, authentification. 1.1 Problèmes ============== - Chiffrement / déchiffrement (protocoles symétriques / non symétriques) - Signature - Authentification - Tatouage (watermark) - Dissimulation 1.2 Un exemple d'algorithme de cryptographie: RSA ================================================== La méthode de cryptographie RSA, codage à clef publique, a été inventée en 1977 par R.-L. Rivest, A. Shamir et L. Adleman A method for obtaining digital signatures and Public-Key cryptosystems, communications of the A.C.M., février 1978. Quelques rappels sur les nombres premiers et les entiers modulos p (Z/pZ). Exercice 1 Trouver les nombres inversibles dans Z/5Z et Z/6Z. Théorème 1 Petit théorème de Fermat: Si p est un nombre premier, alors pour tout entier m, alors p m =mmod p. Variations: - Si p est un nombre premier, et si m n'est pas divisible par p, alors p-1 m =1mod p. - Si p et q sont deux nombres premiers, et si m est premier avec p et q, alors (p-1)(q-1) m =1mod pq. La méthode RSA est basée sur cette dernière variation. On prend deux grands nombres premiers p et q, et on note n le produit pq. On choisit ensuite un nombre e premier avec (p-1)(q-1). Alors e est inversible modulo (p-1)(q-1). On note d son inverse. On appelle alors: - clef publique le couple (n,e). - clef privée le couple (n,d); L'algorithme fonctionne alors comme suit: Algorithme 1 [Rivest, Shamir et Adleman] Soit M telnet lapcs.univ-lyon1.fr www GET /index.html Version un peu plus avancée: icare> telnet lapcs.univ-lyon1.fr www GET /index.html HTTP/1.0 Exemple 2 Envoyer un mail à la main: icare> telnet localhost smtp HELO univ-lyon1.fr MAIL FROM: le.pere.noel@antartique.fr RCPT TO: nthiery@localhost DATA Voilà plein de cadeaux! Le père noël . QUIT Cette méthode permet d'envoyer des faux mails. Elle ne marche pas toujours, car il y a des protections. De toutes les façons, IL NE FAUT PAS EN ABUSER ! Si un faux mail porte préjudice à quelqu'un, celui-ci peut engager des poursuites judiciaires, comme pour tout usage de faux documents. Exercice 7 Lire les news à la main: Essayez les commandes suivantes: lapcs> telnet news.univ-lyon1.fr nntp HELP LIST GROUP fr.comp.lang.php BODY 15090 HEAD 15090 ARTICLE 15090 NEXT HEAD BODY ARTICLE Exercice 8 Utiliser l'exercice précédent et les commandes UNIX que vous avez vues pour récupérer la liste de tous les groupes de discussion francais (fr.quelquechose). Indication: telnet est une application UNIX comme les autres; vous pouvez donc rediriger à volonté son entrée et sa sortie standard. Ne regardez pas la correction ci-dessous avant d'avoir vraiment essayé par vous-même! Correction 1 Version minimale: echo list | telnet news.univ-lyon1.fr nntp | grep fr Version avancée plus polie avec le serveur et garantissant que le fr est en début de ligne: (echo list; echo quit) | telnet news.univ-lyon1.fr nntp | grep 'fr.' Expliquez ce qu'il ce passe lorsque l'on exécute ces commande! 3.3 Comment cela marche les tuyaux ? ===================================== On utilise des niveaux d'abstraction successifs, chaque couche apportant une amélioration à la ``qualité de service''. Dans l'implantation de chaque couche, on a pas besoin de se préoccuper des détails d'implantation des couches inférieures. 1. Envoi d'un signal entre deux machines: couche physique (câble Ethernet, ligne de téléphone (normal/ADSL), fibre optique, faisceau lumineux, radio (faisceaux herziens, téléphone portable, réseau local sans fil), télégraphe, pigeon voyageur...) 2. Envoi d'un paquet entre deux machines directement connectées: Ethernet, PPP, PLIP, ... 3. Envoi d'un paquet avec routage entre machines sur des réseaux différents: IP 4. Envoi de suites de paquets avec garantie de qualité: TCP 5. Tuyaux et prises (socket) 6. Tuyaux sécurisés (authentification, chiffrement): ssl/ssh 7. Protocoles réseaux (http, smtp, nntp, nfs, samba, netware, ntp, ...) 8. Interfaces utilisateur (navigateur web, logiciel de mail, lecteur de news, ...) Toutes ces couches font l'objet de spécifications précises dans des standards. La plupart du temps sous forme de documents RFC (Request For Comments). Le développement d'Internet a été essentiellement permis par le fait que ces standards soient ouverts. 3.4 TP: les prises et tuyaux en java ===================================== La bibliothèque standard de java contient toutes les fonctions nécessaires pour utiliser des prises et tuyaux. Vous trouverez deux exemples d'utilisation dans l'archive suivante:americanhttp://lapcs.univ-lyon1.fr/ nthiery/DESS/Notes/Exemples/SR-TP3-Nicolas.Thiery-1.0.tar.gz Ce TP ne sera pas noté. Il est à faire pour le mercredi 29 janvier. Exercice 5 Écrivez une application java Aspirateur qui prends comme argument sur la ligne de commande l'URL d'un document sur le web, se connecte sur le serveur web correspondant et rappatrie le document dans un fichier. Par exemple, si on tape java Aspirateur http://lapcs.univ-lyon1.fr/nthiery/DESS/index.html l'application doit récupérer le fichier index.html et le sauvegarder dans le répertoire courant. Exercice 6 Écrivez un serveur qui calcule n!. Description du protocole: 1. Le serveur attends la connection d'un client. 2. Le client se connecte. 3. Le client envoie au serveur une ligne contenant un nombre n. 4. Le serveur lui renvoie une line contenant n!. 5. Boucle en 3. De plus: - Pour se déconnecter, le client envoie une ligne contennant la commande quit. - Si le client envoie n'importe quoi (nombre négatif, commande inconnue, ...), le serveur lui renvoie une ligne avec un message d'erreur. Exercice 7 Écrivez deux applications (un client et un serveur) qui permettent à deux personnes sur des machines différentes de dialoguer en s'envoyant des lignes de texte à tour de rôle. Mettez-vous d'accord entre groupes pour que tous vos programmes soient compatibles entre eux! 3.5 Calculs scientifiques et réseaux ===================================== Problème 2 En quoi les réseaux peuvent-ils être utiles pour les calculs scientifiques ? - Distribution rapide de logiciels - Distribution simplifiée de logiciels complexes à installer Versions de démonstration - Lancement de calculs sur plusieurs machines - Calcul parallèle (PVM, MPI, clusters, machines spécialisées) - Calcul massivement parallèle (seti@home) - Mise à disposition de puissance de calcul et de logiciels (centre de calcul medicis.polytechnique.fr) - Bases de données (encyclopédie des séquences d'entiers) - Documents scientifiques interactifs, éducation en ligne Problème 3 Quelles solutions techniques? - Côté client (on fournit le logiciel qui est exécuté sur le client): 1. Programme autonome 2. Bibliothèque pour un système existant 3. Bibliothèque précompilée (C, C++, fortran, java, ...) à lier avec un autre programme 4. Code exécuté dans le navigateur web: HTML+Javascript / Applet java 5. Distribution: source / binaire ? licence ? - Côté serveur (le logiciel est exécuté sur le serveur): 1. Connexion par ssh sur le serveur, et travail à distance avec les logiciels qui y sont installés (medicis.polytechnique.fr) 2. Interface web (linbox, encyclopédie des séquences d'entiers): 1. ``scripts'' CGI (programme appelé par le serveur web), souvent en perl 2. PHP/ASP + bases de données (code exécuté directement par le serveur web) 3. Interface avec protocole dédié (serveurs de calcul FGb+RS) Problèmes principaux: sécurité, simplicité d'emploi, fiabilité, efficacité, pérennité Problem 1 Quels sont les avantages et inconvénients de chacune d'entre elles? Pour chacune des applications ci-dessus, quelles sont les solutions raisonnables ? 3.6 Projet: jeu de Hex en réseau ================================= L'objectif du projet est d'améliorer le jeu de Hex que vous avez programmé en utilisant le réseau. Exercice 8 On suppose que deux programmes de jeu de dame sont connectés l'un à l'autre par un tuyau. Il va falloir décider comment ces deux programmes vont utiliser ce tuyau pour transmettre les informations nécessaires pour jouer l'un contre l'autre. Commencons par un exemple: voilà un dialogue typique entre deux humains jouant aux dames: 1. Joueur 1: Bonjour, tu joues aux dames avec moi ? 2. Joueur 2: Ok. je joue C3-D2 3. Joueur 1: je joue F4-E5 4. Joueur 2: je joue C5-E5 5. Joueur 1: nan, tu n'as pas le droit; essaye encore. 6. Joueur 2: je joue C5-E5 7. ... 8. Joueur 2: je joue F4-H6, t'as perdu! 9. Joueur 1: zut. Je joue plus. 10. Joueur 2: mauvais joueur; tant pis, à bientôt Un programme ne serait probablement pas capable de suivre un tel dialogue. Il y a des ambiguités, des bouts inutiles, des bouts sous-entendus. Le but de l'exercice est de formaliser ce type de dialogue pour qu'il puisse avoir lieu entre deux programmes; c'est-à-dire de mettre au point un protocole permettant à ces programmes d'échanger leurs coups pour mener à bien leur partie. Exercice 9 Joueur humain contre machine distante. 1. Écrire une application java qui implante ce protocole via son entrée et sa sortie standard. Ainsi, un joueur connaissant le protocole peut jouer directement avec lui en le lançant à la main. Vous pouvez écrire plusieurs variantes, avec des stratégies de jeu différentes. 2. Modifier le programme précédent pour en faire un serveur qui attends sur un port donné d'une machine distante. 3. Améliorer ce serveur pour qu'il gère plusieurs coups en même temps. 4. Modifier l'interface utilisateur pour qu'elle se connecte sur le serveur précédent pour permette à l'utilisateur de jouer contre la machine. Pour cela, vous pouvez créer une nouvelle classe ``RemotePlayer''; lorsqu'un objet o de cette classe est créé, il ouvre une connexion avec le serveur distant. Ensuite, lorsque l'on appelle la méthode nextMove de cet objet, celle-ci envoie les informations au serveur, et récupère le mouvement suivant. Exercice 10 Joueurs humains à distance. Écrire un serveur ``arbitre'' qui attends que les interfaces des deux joueurs (ou plus) se connectent dessus, et gère leur dialogue. Optionnel: étendre ce serveur pour qu'il gère plusieurs parties en même temps. TODO: faire utiliser les threads 3.7 Les Threads, ou processus légers ===================================== Références: - Tutorial java de SUN sur les processus légers americanhttp://java.sun.com/docs/books/tutorial/essential/threads/ - Des notes de cours en français sur les processus légers american[http://javahttp://cedric.cnam.fr/ farinone/CCAM/threads.pdf Exercice 11 Écrire une version du programme joueur humain contre joueur automatique sur la machine locale pour que le calcul du prochain coup ait lieu dans un autre processus léger. Pour cela, vous pouvez créer une nouvelle classe ``ThreadPlayer'' dont la méthode nextMove créé un nouveau processus léger; ce processus léger à son tour créé un objet de la classe GreedyPlayer (ou de n'importe quel joueur automatique), et appelle la méthode nextMove de cet objet. Exercice 12 Parallélisme: Écrire un joueur automatique qui recherche le meilleur coup en explorant récursivement l'arbre des possibilités, en parallélisant le calcul sur plusieurs machines. Une architecture possible: 1. On a une liste de machines disponibles. 2. Sur chaque machine tourne un serveur qui attends des connexions. Lorsqu'il en reçoit une, il lance un sous-processus (thread) qui traite la connexion (recevoir une requête, calculer une réponse, la renvoyer et se déconnecter). Pour limiter les dégats, le serveur peut tenir à jour le nombre de sous-processus lancés, et se déclarer «indisponible» s'il y en a trop. 3. Une requête consiste en la description d'un échiquier, d'une couleur (est-ce aux noirs ou aux blancs de jouer) et d'une profondeur p. Le programme fait une recherche dans l'arbre des possibilités et calcule le meilleur coup pour le joueur considéré, c'est-à-dire le coup qui maximise l'évaluation e à profondeur p. La réponse est composée du meilleur coup et de l'évaluation e. Bien entendu ce problème est à traiter récursivement: on parcoure la liste des coups possibles; pour chacun d'entre eux, on calcule la meilleure contre-attaque pour le joueur adverse, et l'évaluation correspondante; enfin on choisi le coup qui minimise la contre-attaque. 4. Chaque programme connaît la liste des machines. S'il le souhaite, il peut décider en cours de calcul de déléguer une partie du travail sur une autre machine. Pour cela, il peut rechercher un autre serveur disponible (s'il y en a un), et lui donner à résoudre une des sous-branches. 3.8 Références =============== Exemples de serveurs de calcul sur le web: - L'encyclopedie electronique des suites d'entiers (Sloane) americanhttp://www.research.att.com/ njas/sequences/ - Serveur de calcul d'algebre lineaire exacte americanlinalg.org Documents: - Usenet (protocole nntp) americanhttp://ecole.eu.org/doc/usenet/index.html - Les services de base d'internet (ftp http mail, nntp) americanhttp://ecole.eu.org/doc/cours4/internet2/ - Supports de cours de l'Ecole Ouverte de l'Internet americanhttp://ecole.eu.org/doc/supports.html - Documents sur l'utilisation d'UNIX sur Linux-France americanhttp://www.linux-france.org/ - Documents sur l'utilisation d'UNIX, sur le site des tuteurs americanhttp://www.eleves.ens.fr:/tuteurs/ - Un tutorial pour javascript americanhttp://www.pageresource.com/jscript/ - Un tutorial java americanhttp://javaboutique.internet.com/tutorials/Step/Chapter1/inde x.html - Tutorial sur les tuyaux (sockets) et java americanhttp://www.javaworld.com/jw-12-1996/jw-12-sockets.html - Les exemples présentés en cours americanhttp://www.lapcs.univ-lyon1.fr/ nthiery/DESS/Notes/Exemples/ ----------------------------------------------------------------------- Ce document a été traduit de LaTeX par HeVeA (http://pauillac.inria.fr/~maranget/hevea/index.html).