-------------------------------------------------------------------------------- LJNB http://journal.bidon.ca/ Publié à chaque 3e vendredi du mois Édition 2002.03 -------------------------------------------------------------------------------- « Il faut porter encore en soi un chaos pour pouvoir mettre au monde une étoile dansante. » - Friedrich Nietzsche LJNB est un mensuel traitant d'informatique. Pour vous abonner ou désabonner, consultez: http://journal.bidon.ca/parcourrier.html Table des matières ------------------ - Nouvelles en bref.....................................................editeurs - Défis.................................................................editeurs - Grappes d'ordinateurs Linux de type Beowulf.............................benoit - L'encryption et informatique quantique, 1re partie......................thaBob - Événements à surveiller...............................................editeurs - Suggestions du mois (nouvelle section)................................editeurs - Votre dose de Perl (mod_perl)..............................................MPM +-------------------+ --| Nouvelles en bref |---------------------------------------------(editeurs)-- +-------------------+ Cette section publie des nouvelles de milieux communautaires ou académiques reliées au thème de ce journal. Si vous avez une nouvelle intéressante à contribuer, contactez-nous: editeurs@journal.bidon.ca - 4 mars 2002 [contribué par bgm] Le Gulus a obtenu une commandite de 1300$ de l'AGEG (Association Générale des Étudiants en Génie) et Unibroue pour l'achat d'un serveur Internet et un projet dans la faculté de Génie. J'en profite pour faire un rappel du festival de clustering qui aura lieu samedi le 23 mars à Sherbrooke (voir la section "Événements à surveiller".) Je paie une bière à celui qui apporte un Cray! + Détails: http://www.gulus.org/ - 16 mars 2002 [contribué par LastCall_] Il y aura un "LAN Party" à but non lucratif le 10, 11 et 12 mai 2002 à l'École de Technologie Supérieure (ÉTS). Ouvert à plus de 200 joueurs de tous les âges. Plusieurs serveurs dédiés, connection Internet et tournois avec des prix alléchants. Ambiance, musique, etc. Des prix de présence seront aussi remis par tirage au sort. Admission: 30$ avant le 2 mai, 10$ de plus à la porte. + Détails: http://lan.etsmtl.ca/ +------+ --| Défi |----------------------------------------------------------(editeurs)-- +------+ Chaque mois, nous vous proposerons des défis sur des sujets variés, puis, le mois suivant, nous publierons les solutions les plus intéressantes parmis celles que nous aurons reçu, tout dépendant de la simplicité ou originalité du code source, ou des résultats. Envoyez-nous vos solutions par courrier à editeurs@journal.bidon.ca avec les mots "défi: nom_du_défi" dans le sujet. Consultez la section défi sur notre site web (http://journal.bidon.ca/defi/) pour plus de détails (surtout à propos des contraintes) et pour des mise à jour (précisions, indices, etc.) s'il y a lieu. Ces défis devraient être vus comme un équivalent à des mots croisés dans un journal conventionnel, i.e. une source de divertissement. ++ (200203_01) Brassage de cartes - Proposé par: Alex Boisvert (Folle Course Informatique (FCI), édition 2000) [1] La plupart des jeux de cartes font appel au hasard pour mettre du piquant dans une partie. Le brassage de cartes est donc une opération importante qui détermine, indirectement, le déroulement de la partie. Pour certains joueurs peu scrupuleux, le brassage de cartes est un art. Évidemment, à qui sait mettre les chances de son côté reviendra le magot... Problème: Vous devez écrire un programme qui simule le brassage « parfait » d'un paquet de cartes qui contient N cartes uniques. La technique du brassage est exécutée comme suit: On coupe le paquet à la ième (m) carte à partir du dessus pour obtenir deux piles: celle du dessus et celle du dessous (la carte m se trouve dans le paquet du dessus). Le mélange commence en déposant la carte du dessous de la pile du dessus, suivie de la carte du dessous de la pile du dessous. Le mélange se poursuit en déposant une carte d'une des deux piles, en alternance, jusqu'à ce qu'une des deux piles soit vide. Le reste des cartes vont sur le dessus de la nouvelle pile. Le problème est de trouver le nombre de brassage parfaits consécutifs pour retrouver, à la toute fin, le paquet dans son ordre original. Exemple: Supposons un paquet de cartes ayant N = 5 cartes. On le coupe successivement à la 3ième (m = 3) carte: Paquet original: 1 2 3 4 5 Après le premier brassage: 1 4 2 5 3 Après le second brassage: 1 5 4 3 2 Après le 3ième brassage: 1 3 5 2 4 Et après le 4ième brassage, on retrouve le paquet original, donc la réponse est 4. Fichier d'entrée: Le fichier que vous devez lire doit être le premier paramètre passé à votre programme (argv[1] en C/C++). L'entrée est composée de deux valeurs: le nombre N de cartes uniques dans le paquet et l'endroit où est coupé le paquet m. Les valeurs sont données sur une ligne: Ex: "5 3" -> Paquet de 5 cartes, coupé à la 3e carte. Le nombre de cartes uniques varie entre 2 et 501 alors que l'endroit où couper varie entre 1 et le nombre de cartes dans le paquet moins 1. Fichier de sortie: Vous devez afficher à l'écran le nombre de brassages parfaits nécessaires pour retrouver le paquet dans son ordre original. [1] La FCI est un concours informatique annuel qui a lieu dans plusieurs universités québécoises et ailleurs dans le monde (en 2001, il y avait une univ des États-Unis et une de France). Nous avons pigé et légèrement adapté le texte dans les archives de la FCI sans leur authorisation. En fait, c'est la FCI qui nous a donné l'idée de lancer des défis à chaque mois et nous vous encourageons à y participer l'automne prochain. URL: http://www.gel.usherb.ca/fci/ ++ Contraintes générales s'appliquant à tous les défis de programmation: - Langages acceptés: C, C++, Perl, Python, Java - Inscrire en commentaire la ligne de compilation (même si c'est bidon) et votre adresse e-mail (toto at serveur.net) dans l'entête de votre programme. - Librairies C/C++ permises: ncurses, Xlib, GTK/Glib, QT, Mesa / OpenGL. - Svp ne pas utiliser de dépendances que nous aurons probablement pas sur notre systême, surtout si la solution est en Perl/Python/Java. (plus de détails: http://journal.bidon.ca/defi/contraintes.html) +---------------------------------------------+ --| Grappes d'ordinateurs Linux de type Beowulf |---------------------(benoit)-- +---------------------------------------------+ Benoît des Ligneris benoit.des.ligneris at physique.usherb.ca Date: 2002/03/05 10:01:35 - Revision: 1.4 Table des matières * [1]Qu'est-ce qu'une grappe d'ordinateurs ? + [2]Haute Performance - [High Performance (HA)] + [3]Équilibrage de charge - [Load Balancing] + [4]Haute Disponibilité - [High Disponibility (HA)] * [5]Historique : Pourquoi Linux ! + [6]Qu'est-ce qu'une grappe de type Beowulf + [7]Historique des Beowulf + [8]Linux partout ? + [9]Pourquoi Linux * [10]Conclusion Résumé: Les grappes d'ordinateurs ou [clusters] sont en train de connaître un développement majeur, en particulier celles qui utilisent le système d'exploitation à source ouverte Linux. Les raisons sont multiples : * L'interconnexion des ordinateurs de la planète justifie de plus en plus une approche de type grappe (dans ce cas on parle même de grille [grid]). * Les besoins en capacité de calcul vont beacoup plus vite que l'accroissement de la vitesse des processeurs dans tous les domaines : physique, biologie/génétique, intelligence artificielle, météo, animations, recherche, ... * La croissance du traffic sur internet est de de 100% tous les six mois. Cette croissance est à comparer à la loi de Moore qui indique que la puissance des processeurs double tous les 18 mois. L'approche ordinateur unique (et gigantesque) est donc dépassée pour les projets d'envergure. Dans ce premier article nous allons voir ce qu'est une grappe d'ordinateurs et quels services elle peut rendre. Qu'est-ce qu'une grappe d'ordinateurs ? S'il est important d'essayer de définir précisément ce qu'est une grappe d'ordinateur, ce n'est pas chose facile : les experts en parralélisme et les experts en calcul distribué ne parviennent pas à se mettre d'accord aussi n'entrerons nous pas dans cette guerre de clocher plutôt stérile. La définition la plus générale est la suivante : c'est un groupe d'ordinateur reliés entre eux présentant, sous certains conditions, l'apparence d'une ressource informatique unique. Haute Performance - [High Performance (HA)] Ce premier type de grappe est le plus ancien. L'idée ici est de relier des ordinateurs entre eux afin de bénéficier d'une puissance de calcul accrue. Un logiciel de gestion de travaux [q]ueuing system donne à l'utilisateur l'impression d'utiliser un ordinateur unique. Il est ainsi possible de traiter des problèmes complexes, à condition qu'ils soit possible de les fractionner en petites parties s'exécutant sur un des noeuds de la grappe de calcul. Voici quelques applications de ce premier type de grappe : la prédiction du temps (météo), la cryptographie (briser un code), des éléments finis (calcul de structure, mouvement des plaques tectoniques, astronomie, ...), physique du solide, ... Équilibrage de charge - [Load Balancing] Ici, l'idée est d'utiliser plusieurs ordinateurs pour équilibrer la charge sur l'ensemble des ordinateurs de la grappe. Ceci permet d'avoir des temps de réponse et une capacité de gérer un grand nombre de requètes par seconde bien plus importante qu'un serveur unique. Ce type de grappe est d'un intérêt majeur pour les sites ayant un traffic très important. Des exemples concrets incluent le moteur de recherche google (www.google.com) qui sert plus de 150 millions de pages par jour (desservies par plus de 10.000 PC Linux ;-). Haute Disponibilité - [High Disponibility (HA)] L'idée ici est de fournir un service 24h/24h et ce tout le temps. Dans le jargon informatique on appelle cela le temps de fontionnement sans panne [uptime]. Dans le milieu des télécommunications par exemple, il est nécessaire d'être en état de marche 99.999999% du temps soit moins de 0.3 seconde de panne par an. Un cluster permet de réaliser cela en multipliant le nombre de machines capables de rendre le service souhaité et en développant un mécanisme de détection de panne qui permet à une machine ``valide'' de remplacer une machine en panne en un temps très court (de l'ordre de la ms en général). L'utilisateur n'a alors absolument pas conscience que le service lui est rendu depuis une autre machine et encore moins que c'est une grappe qui lui a répondu. Historique : Pourquoi Linux ! Avant d'essayer de répondre à cette question, nous allons nous concentrer sur un type précis de grappe. Qu'est-ce qu'une grappe de type Beowulf En fait, les grappes de calcul dont je vais parler sont de type "Beowulf". Bien qu'il n'y ait pas de définition précise de ce qu'est exactement une grappe Beowulf, on peut tout de même dire qu'une grappe est dite de type Beowulf si elle n'utilise que des composants standard [Components Of The Shelf (COTS)] c'est à dire des équipements qui seraient à leur place dans des PC de bureau au moment de leur achat. Cette définition est donc très variable au cours du temps. Historique des Beowulf Un petit historique des Beowulfs s'impose. La ``preuve de concept'' des machines de type Beowulf a été réalisé en 1994 par Thomas Sterling et Donald Becker. Leur cluster, baptisé Wiglaf, avait 16 noeuds qui étaient constitués d'un 80486 à 100MHz, 16 Mb de RAM et d'un disque dur de 540 Mb à 1 Gb chacuns. Chaque noeud était un PC "de bureau" tout à fait classique incluant la boite métallique. Les noeuds communiquaient entre eux à l'aide de cartes ethernet 10 Mb et, presque naturellement, leur système d'exploitation était ... Linux (RedHat 5.0). Le point d'engorgement du système était constitué par le réseau. Des cartes ethernet ont donc été rajoutées à chaque machine pour faire de l'agrégat de bande passante [Channel Bonding] afin de contourner cette limitation ``physique'' et ainsi augmenter drastiquement les performances du cluster. Linux partout ? Le reigne des superordinateurs semble terminé et il suffit de consulter les sites de référence comme top500.org. Les plus puissants ordinateurs au monde sont des grappes (ordinateurs de type SP de IBM) et cela ne va pas changer tout de suite. Il ne s'agit pas de grappes de type Beowulf mais à priori rien ne s'oppose à ce que les Beowulf deviennent dans un avenir prôche les plus puissantes machines au monde : se sont eux qui offrent le meilleur rapport puissance sur prix. Devant cette véritable révolution, un autre outil d'analyse (et un autre classement donc) réservé aux grappes Beowulf a été créé : clusters.top500.org Sur les 50 Beowulf les plus puissantes on retrouve 45 grappes utilisant Linux ce qui représente 90% des 50 Beowulf les plus puissantes au monde ! Ainsi, Linux s'est imposé comme le standard de facto pour réaliser des grappes. Pourquoi Linux La première raison est le prix. En effet, réaliser une grappe où chaque composante logiciel est payante est quasiment impossible. Imaginez payer 1000 licences windows pour simplement avoir le droit de faire marcher votre super-ordinateur ! La seconde est la position de Linux dans le mileu informatique. Linux est issu du monde des serveurs et il supporte donc une myriade de protocoles obscurs et complexes ce qui lui permet de se comporter très efficacement dans un environnement comme celui des grappes d'ordinateurs. Le système (Linux donc!) se doit d'être un joint très versatile qui permet de relier facilement et efficacement tous les noeuds de la grappe afin de présenter à l'usager et aux administrateurs l'image d'un système unique (Single System Image) La troisième est lié au fait que Linux est constitué d'un ensemble de logiciels libres et ou à sources ouvertes. Cet aspect est capital car les Beowulf étant révolutionnaires lors de leur invention ils nécessitaient (et nécessitent toujours !) de créer des logiciels de très bas niveau. Il est impossible de créer ces logiciels spécialisés ``par dessus'' un système d'exploitation dont les sources sont inconnues. Enfin, Linux est bien positionné dans le monde académique. Le concept même de grappe Beowulf étant issu de ce mileu, Linux a été utilisé comme base pour le développement des grappes. Ceci fait qu'il existe aujourd'hui une base très solide de développeurs et d'utilisateurs de logiciels pour les grappes Linux. Conclusion Nous avons vu quels services pouvaient rendre une grappe d'ordinateurs (Haute Performance, Équilibrage de Charge et Haute Disponiblité) ainsi que l'historique des grappes de type Bewoulf. Linux est le système de référence pour ces superordinateurs du futur. Beowulf, héros mythique des saga scandinave était le neveu de Hygelac roi de la tribu des Geats. Il a défait le monstre cannibale Grendel qui menaçait d'anéantir cette tribu. Nul doute que Linux et les grappes de type Beowulf sauront défaire d'ici quelques années superordinateurs au cours d'une saga qui ne manquera ni d'héroïsme ni de combats ! Les raisons sont financières et technologiques : le coût de développement des microprocesseurs est tel qu'il ne restera plus, à moyen terme, qu'une famille de microprocesseur (les autres éyant cantonnée à un marché de niche) ce qui va faciliter la création de grappes Beowulf en diminuant encore leur rapport puissance sur prix. +----------------------------------------------------+ --| L'encryption et informatique quantique, 1re partie |--------------(thaBob)-- +----------------------------------------------------+ Par thabob - thabob@ground418.ath.cx http://grounded.ath.cx/thabob/bobbytharooky.gpg 4853 EF00 32C7 E8B2 1BDF D084 C058 ABED 379B 3A6E -------[ Table des matières ] - Introduction + à qui? + pourquoi? + mise en garde, erreures, améliorations - Concepts de bases + concepts d'encryptions + pourquoi l'encryption standard est-elle mauvaise? + concepts de physique + représentation quantique des donnés. - Les clés quantiques + le protocole de Bennett et Brassard ---[ Introduction ] Tout d'abord, ce texte s'adresse principalement aux personnes passionnées de cryptographie. Il présente une vision complètement différente de l'encryption. Des méthodes qui semblent vouloir révolutionner la cryptographie moderne puisqu'elles s'appuient sur des lois de physique infranchissables. Avant d'aborder cette première partie qui est en quelques sortes qu'une introduction, j'aimerais d'abord clarifier certaines choses. Je suis loin de me considérer comme un expert en cryptographie, je maîtrise beaucoup plus les notions de physique car j'ai eu l'occasion de les acquérir au cour de ma formation académique. J'invite quiconque à me commenter ou me corriger par email. Ces commentaires m'aideront à mieux écrire les prochaines parties de ce texte. Le but de l'encryption quantique est de créer une encryption imbrisable et un schéma de distribution des clés basé sur les lois de la physique. ---[ Concepts de base ] Voici un petit survol des concepts importants en crypto et en physique. Il s'agit d'une vulgarisation rapide, mais essentielle pour certains à la compréhension de ce qui va suivre. Le troisième point traite de la représentation quantique des données et établit les fondements du "quantum computing". + Concepts primaires d'encryption L'encryption symétrique crypte un message selon une clé secrète prédéterminée. Cette clé doit être connue par le destinataire du message pour que celui-ci puisse décrypter ce message. L'auteur doit donc s'entendre avec le destinataire sur la clé à utiliser. En plus que la clé doit être transmise 'secrètement' au destinataire, la sécurité de l'algorithme repose sur des théories mathématiques non vérifiées et la rapidité des ordinateurs disponibles pour tester toutes les clés possibles. Distributed.net se spécialise dans cette attaque par force brute qui consiste à tester successivement toutes les clés. Après avoir brisé une clef DES (56 bits) en 22 heures, ils s'attaquent présen- tement à RC5-64. Le principal désavantage de l'encryption symétrique est qu'il faut s'être entendus sur la clé à utiliser avant de procéder à l'encrpytion. Je ne peux pas envoyer un message à une personne que je connais pas, puisque je n'ai pas de façon sécuritaire d'échanger une clef secrète de façon sécuritaire. Une réponse à ce cercle vicieux est l'encryption asymétrique, ou plutôt l'utilisation de clés différentes dans le processus d'encryption et de décryption. Elle fut d'abord réalisée en 1978 par trois chercheurs du MIT. L'apparition de l'encryp- tion à clés publiques révolutionna la crypto puisqu'elle nous permet d'envoyer des messages cryptés sans nous être entendus sur une clé secrète. Si Bob veut envoyer un message à Alice, il ouvrira l'équivalent d'un bottin des Pages Blanches, trouvera la clé publique d'Alice et l'utilisera pour crypter le message. Comme Alice est la seule à posséder la clé privée, elle sera la seule à pouvoir lire le message. Le tout est basé sur des fonctions mathématiques dont l'inverse est (aujourd'hui) extrêmement difficile à calculer. Pour une introduction plus complète, je vous propose le texte écrit par bgm [1] sur le site de mtl2600 ou encore, le bon vieux 'Cryptographie Appliquée' de Bruce Schneier, pour avoir un peu plus qu'une introduction. + Concepts de base en physique Plusieurs personnes ignorent quel modèle est approprié pour représenter de la lumière. L'utilisation des propriétés corpusculaires du photon permet des applications intéressantes principalement pour la représentation quantique des données. Mais d'abord, comment définir le photon? Il s'agit en fait d'une particule oscillante se dirigeant de façon plus souvent rectiligne à une vitesse limite 'c' (2,998*10^8 m/s). On peut utiliser un polarisateur pour polariser les photons linéairement et s'assurer qu'ils auront tous le même angle d'oscil- lation. Les photons sortants seront donc tous parallèles à l'axe de transmission du polarisateur. On pourrait comparer la polarisation à un processus de filtra- tion qui laisse passer seulement les photons qui oscillent parallèlement à l'axe de transmission. Il s'agit ici d'une vulgarisation grossière d'un modèle régi par des lois beaucoup plus complexes. Bien que la mécanique quantique soit un sujet palpitant, ce n'est pas vraiment le sujet principal de cet article. Je préciserai au fur et à mesure les notions qui se rattachent plus à l'encryption. + Représentation quantique des donnés Un ordinateur standard traite les donnés à l'aide de nombres binaires (bits), en utilisant une série de 1 et de 0. Avec des bits, on peut représenter un nombre qui correspond à une lettre dans la chaîne ASCII. Les données quantiques marchent un peu de la même façon. Le qubit ou quantum bit est représenté à l'aide d'atomes ou de photons. On distingue deux états fondamentaux de ces particules: le spin up et le spin down. Comme le 1 et le 0, le spin up & down servent de base pour générer l'ensemble des données quantiques. C'est en 1929 que Paul Dirac proposa un modèle correct pour quantifier le moment cinétique (le spin) des particules quantiques. C'est malheureusement le genre de matière présent dans les livres de physique, mais trop souvent oublié par les profs de cégep. :) Une interaction intéressante de ces propriétés est celle de l'emboîtement quantique (Quantum Entanglement, pour utiliser le terme exact). Elle est le résultat de la superposition des états (le spin ou encore la polarisation) de deux particules quantiques. Cette superposition amène des 'entre-états' qui sont le résultat de l'interaction entre les deux particules. Le changement d'état d'une particule va affecter l'état de la particule qui est en relation avec cette dernière. Dans l'introduction faite par le Centre For Quantum Computation [2], ils utilisent un excellent exemple pour expliquer la relation qu'il peut y avoir entre les différents états et comment par le fait même, elle ne s'applique pas à la physique quantique. Ils montrent comment l'état d'un banquier qui subit un cambriolage (mort ou vivant) varie selon le fait que le fusil ait tiré ou pas. Si le fusil a tiré, alors le banquier est mort. S'il n'a pas tiré, alors le banquier est toujours vivant. Dans cet exemple, il y a corrélation entre les deux états. Mais contrairement aux particules quantiques, il n'y a pas d'entre deux possible. Le banquier ne peut pas être mort et vivant à la fois. C'est le principe de superposition d'états qui rends ces entre deux possibles pour les particules quantiques. Bien sûr, il faut supposer que le banquier ne meurt pas d'une crise cardiaque ou encore que le voleur ne rate pas sa cible. ---[ La distribution des clés quantiques ] Comme expliqué plus haut, l'utilisation des clés (publiques ou secrète) dans la cryptographie moderne est incontournable. Nous avons aussi mentionné que cette crypto est basée sur des mathématiques non vérifiées et n'importe qui peut avoir accès au texte encrpyté. Avec l'encryption quantique, les choses fonctionnent un peu différemment. Caleb Lyness [3], de l'université de Cape Town, utilise une phrase tout à fait appropriée pour exprimer cette notion: "Les donnés quantiques ne peuvent pas être lues à moins que des informations sur l'état avec lesquelles ils ont été préparés soit connu. Toute tentative de lecture ou de copie des donnés sans l'information requise, modifiera les donnés de façon significative." Ce qui veux dire en clair, que le texte crypté ainsi que la clé ne peuvent pas être lus ou interceptés. À ma connaissance, il s'agit d'une application directe de l'emboî- tement quantique expliqué plus haut. Il y a trois principaux cryptosystèmes quantiques pour la distribution des clés: - Un cryptosystème qui encode pour deux observateurs qui se connaissent pas. (le protocole de Barnett et Brassard, 1984) - Un cryptosystème qui encode selon les propriétés de l'emboîtement quantique et du théorème de Bell. (Proposé par Ekert en 1990) - Un cryptosystème qui encode à partir des deux vecteurs d'états non orthogonaux. (proposé par C.H. Bennett en 1992) Dans cette première partie, nous toucherons uniquement au protocole de Bennett et Brassard. De plus, c'est le seul qui été réalisé dernièrement à une distance de 1 km. Les deux autres seront expliqués dans la deuxième partie de ce texte. ---[ Le protocole de Bennett et Brassard ] Ce protocole utilise des photons polarisés pour établir la communication. Nous avons donc un émetteur et un récepteur. Par convention notre émetteur va émettre les photons avec un des quatre angles de polarisation suivantsÊ: 0, 45, 90 ou 135 degrés. Le destinataire pourra, à l'aide de son récepteur, mesurer l'angle de polarisation. En utilisant les lois de la physique quantique, l'on peut déterminer si l'angle est de 0 ou encore de 90 degrés. Ou encore, le récepteur peut mesurer si le photon est polarisé à un angle de 45 ou de 135 degrés. Il ne peut jamais mesurer les deux modes simultanément, de plus si l'on mesure un photon avec un mauvais angle de polarisation, l'on se retrouve avec une valeur aléatoire. Par exemple, si l'on veut mesurer la polarisation d'un photon polarisé à 90 (horizontalement) avec un récepteur configuré pour les polarisa- tions diagonales, l'on va se retrouver avec une valeur aléatoire. +++ Voici le processus détaillé en quelques étapes toutes simples: ---------------------------[ sur un canal quantique 1) Alice décide une série de nombres binaires (exemple: 1001011010111) qu'elle envoie à l'aide de photons (en utilisant le spin up et down) avec un des quatre angles de polarisation (0, 90, 45 ou 135). 2) Bob décide au hasard avec quelle polarisation il lit les photons. Ce que Bob lit ne correspond pas nécessairement à ce que Alice a envoyé, puisque la valeur des binaires que Bob lit dépend de l'angle de polarisation avec lequelle il a lu les photons. ---------------------------[ sur un canal publique 3) Bob envoie à Alice les modes de lectures (rectiligne ou diagonale) utilisés pour les qubits. 4) Alice répond à Bob, par oui ou non, si les modes étaient corrects. Si c'est le cas, alors Bob saura qu'il pourra correctement interpréter les résultats reçus. Par exemple, si le mode est rectiligne, Bob pourra savoir si c'est 0 ou 90 degrés. Dans aucun cas Alice et Bob discutent sur le canal public des données transmises, seulement des modes. Les données ainsi obtenues (i.e. le résultat des qubits interprétables) formeront la clé d'encryption. 5) Alice et Bob échangent ensuite une petite partie de la clé pour s'assurer qu'elle est identique. La moindre erreur voudra dire que le message a été enregistré ou intercepté par une troisième personne. Ils ne peuvent pas s'assurer que le signal quantique ne sera pas intercepté, mais si cela arrive, ils pourront le détecter assez facilement. Ils utilisent par la suite un protocole de correction des erreurs qui leur permettent de confirmer la fiabilité de leurs données. Malgré tout, il existe des types d'attaques qui peuvent mettre en péril la sécurité de ce protocole, mais ils ne sont pas réalisables en pratique. Elles seront discutées dans la 2e partie de ce texte. N'hésitez pas à me contacter si vous avez des interrogations sur les parties moins claires ou plus subtiles de ce texte. Plusieurs principes de mécanique quantiques sont encore vagues. Il est dur de résumer une théorie quand certains chercheurs ne s'entendent pas sur les détails. ---[ Références ] [1] http://mtl2600.org/textes/intro_crypto_partie1.html [2] http://www.qubit.org/intros/entang/ [3] http://www.cs.uct.ac.za/courses/CS400W/NIS/papers99/clyness/ [4] http://www.qubit.org/intros/crypt.html +-------------------------+ --| Événements à surveiller |---------------------------------------(editeurs)-- +-------------------------+ Samedi 23 mars: - [Sherb] Linux-Québec "NG" @9~10H00: Réunion mensuelle ayant pour but de faire le point et de faire avancer les projets et activités organisées par le groupe lui-même ou d'autres groupes locaux. Après quelques discussions, la réunion se termine avec une répartition de tâches. Notez qu'exceptionnellement, la réunion a lieu à Sherbrooke au Carrefour de l'Information (juste avant le Festival de Clustering du Gulus) - Bilingue - Gratuit et ouvert à tous. + Détails: http://www.linux-quebec.org/archives/annonces/threads.html - [Sherb] Festival de Clustering du Gulus de 12H00 à 16H30. Un cluster est un ensemble d'ordinateurs reliés en réseau qui forment un plus ordinateur virtuel. Ceci permet, par exemple, de faire des calculs scientifiques de façon plus rapide qu'avec un seul ordinateur. Lors du premier Festival de Clustering du Gulus, nous aurons l'occasion de créer un cluster maison avec certains ordinateurs du Carrefour de l'Informa- tion, et d'autres que VOUS aurez apportés! De plus, il y a un conférencier de Ericsson et des experts en clustering de l'Université de Sherbrooke. - Bilingue - Gratuit et ouvert à tous. + Détails: http://www.gulus.org/ Jeudi 4 avril: - [Mtl] Perl Mongers @18H00: Présentation sur un sujet relié à Perl. Consultez leur site web 1-2 semaines avant la présentation pour connaitre le sujet. Les réunions ont lieu dans les bureaux de HBE Software, au 460 Ste-Catherine O, Suite 210 (près du métro McGill) - Bilingue - Gratuit et ouvert à tous. + Détails: http://montreal.pm.org/ Vendredi 5 avril: - [Mtl] 2600 Montréal @17H00: Réunion mensuelle. Discussions informelles reliées à l'informatique. Dans la café du 1000 Gauchetière (métro Bonaventure), près du Dunkin Donuts. - Bilingue - Gratuit et ouvert à tous. + Détails: http://www.mtl2600.org/reunions/ Mercredi 10 avril: - [Mtl] Linux-Qubec @19H00: À la salle B-505 de l'École Polytechnique de Mtl, Karim Yaghmour, de la compagnie Open Source Opersys, discutera des modalités de l'utilisation de Linux dans les systèmes embarqués (plates-formes de développement, systèmes de fichiers sur disque "FLASH", compilation croisée, etc.) - Bilingue - Gratuit et ouvert à tous. + Détails: http://www.linux-quebec.org/Rencontres.html - [Qc] Linuq @19H00: Pas encore confirmé et détails pas encore affichés sur leur site web. Dans les locaux de l'Université Laval - Francophone - Faut être membre (étudiants: 5$/an, sinon 20$/an, peut être payé sur place) + Détails: http://www.linuq.org/ Vendredi 12 avril: - [Mtl] Montreal LUG @19H00: Présentation sur un sujet relié à Linux et discussion générale sur Linux. Au Cégep Vanier (métro Côte Vertu), local F223 - Anglophone - Gratuit et ouvert à tous. + Détails: http://www.mlug.ca/ (contient un plan détaillé pour les directions) Vous avez un événement à signaler? Contactez-nous: editeurs@journal.bidon.ca +---------------------+ --| Suggestions du mois |-------------------------------------------(editeurs)-- +---------------------+ Vous lisez sans doute les mêmes sites que nous, mais parfois, par un moment d'inattention, en suivant quelques liens de façon distraite, l'on découvre d'excellents sites web ou autres ressources injustement peu connues. Cette section est donc dédiée aux ressources peu connues et, comme d'habitude, nous vous invitons à nous faire part de vos découvertes. - Excellentes ressources sur la programmation de bas niveau et comparaisons entre diverses architectures et processeurs. (suggestion de patrick) + URL: http://www.azillionmonkeys.com/qed/tech.shtml - Le livre "Linux Device Drivers, 2nd Edition" est disponible gratuitement par le web. C'est un très bon point de départ pour s'initier aux modules du noyau Linux et définitivement meilleur que la 1re édition. (suggestion de françois) + URL: http://www.xml.com/ldd/chapter/book/ - LaTeX est un formatteur de texte extrêmement puissant, mais légèrement plus difficile à apprendre que certains outils graphiques. N'empêche que ça s'apprend assez bien en lisant des exemples que l'on trouve un peu partout sur Google, ce tutoriel/référence détaillé et en français est un excellent complément. (suggestion de bgm) + URL: http://www.laas.fr/~matthieu/cours/latex2e/ +--------------------+ --| Votre dose de Perl |-------------------------------------------------(MPM)-- +--------------------+ La version originale en ligne (et en anglais) de cet article est disponible à cette adresse : http://www.flatlineconstruct.com/talk/understanding_mod_perl/ Vous retrouverez ici une version traduite et adaptée par LastCall_. mod_perl par Benoît Beausejour ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ Comme son nom l'indique, mod_perl est un module. Pour être plus précis, c'est un module pour le serveur web Apache. Les principaux objectifs de mod_perl sont d'inclure un interpréteur Perl dans le serveur pour donner la possibilité à un programmeur d'écrire des extensions Apache et des modules en utilisant Perl. Il amène des avantages significatifs en termes de performance, d'extensibilité, de pré-chargements de code et sauve au serveur beaucoup de chargements d'interpréteurs supplémentaires. En incorporant l'interpréteur dans le serveur, le programmeur à accès aux API internes du serveur web Apache, ce qui lui donne la possibilité d'étendre les fonctions dans différentes phases du cycle de vie de la requête. Il peut alors personnaliser la phase de requête pour ajouter des fonctionnalités à ses applications web. Il peut aussi introduire des nouvelles directives de configuration, contrôler la configuration du serveur en utilisant Perl et beaucoup plus. Pour bien comprendre mod_perl il faut connaître les 3 environnements qui sont combinés pour former mod_perl : Perl, Apache et mod_perl lui-même. - Environnement Perl Perl utilise deux types de ramasse-miettes (garbage collection) : le compteur de références et le balayage (mark-and-sweep). Le compteur de référence est le principal ramasse-miettes [NDLR: arrêtez de rire c'est la traduction officielle de l'OLF, hehe] de Perl. Chaque objet en Perl possède un compteur qui détermine le nombre de références à l'objet. Lorsque le compteur tombe à 0, l'objet est libéré de la mémoire pour la portée courante ('perldoc perlobj'). Ce genre de ramasse-miettes récolte 99% des objets, mais parfois il se peut que les objets lui filent entre les mains comme dans l'exemple suivant : { my $var; $var = \$var; } Normallement, $var devrait être libérée à la fin de la portée, mais non, quelque chose ne va pas! Son compteur de référence n'est pas à 0. Donc le ramasse-miette ne va pas l'attraper et $var ne sera jamais libéré. Voici un autre exemple de ce genre de problème : package Foo; sub new { my $classname = shift; my $self = {}; $self->{right_hand} = $self; $self->{left_hand} = $self; return bless $self, $classname; } 1; Les objets qui sont créés avec des références circulaires comme ceci ne seront pas attrapé par le principal ramasse-miettes de Perl. Par contre, le balayage va réussir à libérer ces objets de la mémoire. Lorsque l'interpréteur Perl arrête, ce ramasse-miettes va balayer tout les objets dans la pile mémoire et va les détruire (DESTROY()). En voici un exemple (tiré de 'perldoc perlobj') : #!/usr/bin/perl package UnFreeable; sub new { my $classname = shift; my $test; $test = \$test; warn "CREATING " . \$test; return bless \$test, $classname; } sub DESTROY { my $self = shift; warn "DESTROYING $self"; } package main; warn "starting program"; { my $a = UnFreeable->new; my $b = UnFreeable->new; $$a = 0; # break selfref warn "leaving block"; } warn "just exited block"; warn "time to die..."; exit; résultat : starting program at /tmp/test line 18. CREATING SCALAR(0x8e5b8) at /tmp/test line 7. CREATING SCALAR(0x8e57c) at /tmp/test line 7. leaving block at /tmp/test line 23. DESTROYING UnFreeable=SCALAR(0x8e5b8) at /tmp/test line 13. just exited block at /tmp/test line 26. time to die... at /tmp/test line 27. DESTROYING UnFreeable=SCALAR(0x8e57c) during global destruction. Pour bien comprendre le lien entre les ramasse-miettes de Perl et mod_perl il faut aussi savoir la manière que Perl gère la mémoire. C'est plutôt simple : lorsque Perl a besoin d'allouer de la mémoire, il va allouer tout ce qu'il a de besoin pour faire la tâche. Par exemple, si le contenu d'une variable est de 1Mo, Perl va alors allouer 1Mo pour la variable. Lorsque la variable est rendue en dehors de portée ou bien que le ramasse-miette l'attrape, Perl ne va pas libérer tout de suite ce 1Mo au noyau du système d'exploitation : il va le réutiliser pour d'autres besoins plus tard dans son exécution. Cette mémoire va donc être réutilisée jusqu'à temps que Perl termine son exécution, donc lorsque le ramasse-miettes de balayage se produit. - Environnement Apache Apache utilise un arrangement de processus pré-chargés pour servir les requêtes. Ceci implique donc un processus maître de contrôle qui est associé au port HTTP (80) et qui écoute les prochaines requêtes. Lorsqu'une requête est effectuée, le processus de contrôle va expédier cette requête à un des processus enfants qui va s'en occuper. Chaque processus enfant est une copie du processus de contrôle (fork). Ils partagent une mémoire de base commune, mais ils possèdent leurs propres espaces mémoires car après tout, ce sont des processus. Chaque espace mémoire réellement occupé par le processus enfant est calculé en prenant la taille du processus par rapport au pourcentage de mémoire partagée. Ce pourcentage est réduit à l'exécution lorsque des "copy-on- write" sont effectués. - Environnement mod_perl À la base, mod_perl est un environnement Perl qui s'exécute à l'intérieur des enfants du serveur Apache. Il y a un interpréteur par enfant et la grosseur de celui-ci est ajouté à la taille standard de l'enfant. L'interpréteur s'exécute donc à l'intérieur de l'enfant et s'arrête seulement lorsque celui-ci arrête. (Peu importe s'il se fait tuer par le système de contrôle de Apache ou s'il s'arrête simplement par lui-même.) Il y a toujours un ou plusieurs enfants qui s'exécutent. Ce qui veut dire qu'une requête peut être servie par un enfant ou un autre et que leurs espaces mémoires sont différents. Donc, les valeurs à l'exécutions sont différentes à l'intérieur de chaque interpréteur. mod_perl s'exécute à l'intérieur de l'enfant, donc il est initialement complètement partagé. Avec les "copy-on-write", la mémoire devient départagée graduellement. (deux ou plusieurs processus partagent une page de mémoire, un veut la changer, les autres ne veulent pas, donc une copie est faite juste pour ce processus) mod_perl peut se diviser en deux type : Apache::Registry et les gestionnaires mod_perl(Interface de programmation Perl Apache). Avec cette combinaison d'environnement, il y a plusieurs changements comparé au CGI normal. Lorsque mod_perl est utilisé, chaque script ou module Perl qui sont chargés et exécutés sont mis en antémémoire (cache), donc la phase de compilation est seulement exécutée une fois. De cette façon, le serveur passe la plupart de son temps à exécuter le code au lieu de compiler. Les scripts en mod_perl ne sont pas exécutés dans un endroit principal : ils s'exécutent dans un espace de noms qui permet à Apache::Registry de mettre en antémémoire leur code unique par enfant. À cause que le script se fait entourer par la routine "handler()", les marques __END__ et __DATA__ de Perl ne peuvent être utilisées. print "Content-type: text/html\n\r\n\r"; print "Test script\n"; devient : package Apache::ROOT::perl::test_2epl; use Apache qw(exit); sub handler { print "Content-type: text/html\n\r\n\r"; print "Test script\n"; } Ajouter la marque __END__ au script casserait donc la routine "handler()". Aussi, les variables globale seront persistante en mod_perl jusqu'à temps que l'enfant meure. Il est donc important d'utiliser "strict" lorsque l'on programme en mod_perl. Avec mod_perl, chaque routine de chaque script Apache::Registry est imbriquée dans la routine gestionnaire. Ceci veut donc dire que les symboles globaux ne sont pas main::globals mais bien des variables lexicales. Ceci cause certains problèmes quand les routines dans le script (qui sont maintenant des routines imbriqués) accèdent à une variable globale. Les valeurs globales de la sous- routine interne sont donc copiées de la portée précédente et mises en antémé- moire pour des prochains appels de fonctions. Prenons par exemple un simple compteur: #!/usr/bin/perl use strict; print "Content-type: text/plain\n\r\n\r"; my $lexical_global = 0; increment(); sub increment { $lexical_global++; print "Counter = $lexical_global\n"; } La variable lexicale "$lexical_global" dans ce script est mise en antémémoire par la routine "increment()", alors sa valeur n'est pas zéro dans la prochaine exécution du script présent dans l'antémémoire dans cet enfant. L'exécution répété de ce script en mod_perl donne donc un résultat du genre : 1 2 3 4 1 2 3 5 6 7 8 4 5 6 ... Puisque l'interpréteur s'exécute dans le processus Apache enfant, l'appel de fonction "exit()" est rattaché à la fonction "Apache::exit()". Dans les versions de Perl au dessous de 5.6, un appel à "exit()" va littéralement faire quitter l'enfant. Vous voyez le problème? De plus, les appelles de fonction "die()" sont rattachés à une routine anonyme : $SIG{__DIE__} = sub { print STDERR @_; Apache::exit(); } De plus, le STDIN et le STDOUT en mod_perl sont reliés directement à l'interface de connexion (socket) de la requête. Aussi, les blocs BEGIN sont exécutés seulement lorsque le code est compilé, donc une fois par module/script. Les blocs END sont exécutés quand le script a terminé son exécution (cas spécial). Finalement, il y a une morale à retenir de mod_perl : Soyez concis, soyez précis, soyez strict. - Gestionnaires mod_perl (mod_perl handlers) Pour bien comprendre comment agissent les gestionnaires mod_perl, il faut regarder le processus de réponse de requêtes de Apache. Voici les étapes de l'ancien processus CGI sans mod_perl : - Recevoir la requête - Réveiller un enfant - Lance l'interpréteur - Compile le code - Exécute le code - Arrête l'interpréteur - Répond au client Comme étant expliqué précédemment, plusieurs de ces étapes ne sont exécutés qu'une seule fois dans mod_perl au lieu d'à chaque requête. Voici maintenant de quoi à l'air en détail la boucle d'attente de mod_perl : - Attente ("wait()") - Requête d'après lecture (Post Read Request) - Traduction du URL (URL parsing) - Analyse syntaxique (parsing) de l'entête - Contrôle de l'accès - Authentification - Autorisation - Vérification du type MIME - Réponse (content handler) - Écriture au journal - Attente Chaque interface de programmation du gestionnaire mod_perl définit une routine "handler()" qui sera utilisé comme un "main()" pour cette phase. sub handler { my $r = shift; # l'objet de la requête Apache (voir plus bas) # Faire quelque chose! return SOME_STATUS_CODE; } L'ajout du prototype $$ à la routine "handler()" permet à mod_perl d'appeler le gestionnaire comme une méthode au lieu d'une fonction. Un module appelé Apache::constants définit les valeurs pour les codes d'états. Par exemple, le code "OK" veut dire que le gestionnaire à réussi, et donc de poursuivre au prochain. "DECLINED" veut dire que ce gestionnaire va être sauté, et donc d'aller au suivant. "DONE" indique que c'est réussi, mais qu'il faut quitter la boucle de requête. "SERVER_ERROR" et "UNAUTHORIZED" quittent la boucle de requête avec un erreur. Voici un exemple de comment nous installons un gestionnaire : package MyProject::Foo; use strict; use Apache::constants qw(:common); sub handler { my $r = shift; print "Hello World\n"; return OK; } Pour ajouter ceci comme une réponse (content handler; dans la phase de réponse) nous utilisons les options suivantes de configuration d'Apache : # Charger le module gestionnaire PerlModule MyProject::Foo # L'installer PerlHandler MyProject::Foo PerlModule va donc ajouter une entrée explicite à MyProject::Foo dans @INC pour qu'il ne se fasse pas charger une seconde fois plus tard. L'objet de la requête Apache est à la base de l'interface de programmation Perl/Apache. Il s'occupe de gérer différentes choses : - Prendre et modifier des informations sur le document demandé - Prendre les entêtes HTTP entrantes - Prendre et modifier les entêtes HTTP sortantes - Lire des données de documents en entrée - Créer des données de documents en sortie - Prendre des informations sur la transaction - Écrire le journal (log) des erreurs et avertissements - Contrôler le processus de transaction - Prendre les paramètres de configuration du module Du coté d'Apache, il y a plusieurs directives de configuration possible : - Les sections - PerlModule : Utilise (use) un module perl et le compile en mémoire - PerlRequire : Compile un script perl - PerlFreshRestart : Recharge les modules quand le serveur est redémarré * - PerlChildInitHandler : Installe un gestionnaire tout de suite après la création de l'enfant. - PerlPostReadRequestHandler : Installe un gestionnaire après que la requête rentre et avant que le URL soit traduit - PerlInitHandler : Premier gestionnaire appelé sur une requête (aussi nommé PerlPostReadRequestHandler) - PerlTransHandler : Appelé lors de l'interprétation de l'URL - PerlHeaderParserHandler : Analyse syntaxique des entêtes une dernière fois avant la phase de la réponse - PerlAccessHandler : Simple contrôle d'accès basé sur l'environnement de la requête - PerlAuthenHandler : Vérifie le nom d'utilisateur / mot de passe - PerlAuthzHandler : Vérifie si l'utilisateur est autorisé à accéder au service demandé. - PerlTypeHandler : Assigne un type MIME provisoire à la requête - PerlFixupHandler : Dernier changement de la modification de l'environnement avant la réponse. - PerlHandler : La phase de réponse (content handler) - PerlLogHandler : Écriture des informations au journal - PerlCleanupHandler - Nettoie ce qui à été laisser si nécessaire. - PerlChildExitHandler - Opération de dernière minute avant qu'un enfant meure. - PerlDispatchHandler - Pseudo phase pour changer l'ordre de la phase de requête * * Il est à noter que PerlDispatchHandler et PerlFreshRestart sont pour usage maléfique seulement... hehe :-) Ces gestionnaires mod_perl peuvent donc être enchaînés dans n'importe quelle phase de la boucle de requête. Il y a deux façons d'enchaîner les gestionnaires : - Chaîne d'exécution : Phase GEST1 GEST2 GEST3 GEST4 - Chaîne de sortie : Phase GEST1 FILTREGEST GÉNÉRATION GÉNÉRATION - Accès à une base de données Le nombre de gestionnaire de base de données est calculé ainsi : nombre par enfant * nombre d'enfants ( $dbh_per_child * $num_childs ) L'utilisation de Apache::DBI apporte de grandes améliorations de performances, car elle place en antémémoire les gestionnaires de base de donnée. Donc le nombre de ceux-ci diminue à : le nombre d'enfants. ( $num_childs ) Une utilisation de "prepare_cached" au lieu de "prepare" sauve beaucoup de temps de traitement et l'appel de la fonction "finish()" est importante. Donc, si la mise en antémémoire des accès à la base de données n'est pas utilisée, c'est la descente aux enfers. - Prochain article Dans le prochain article, nous allons voir plus en profondeur les différentes choses à faire avec les gestionnaires mod_perl ainsi que de la configuration d'Apache. Si quelque chose vous semble flou dans cet article, il est fortement conseillé de se référer aux références. De plus, vous retrouverez des exemples à l'adresse suivante : http://www.flatlineconstruct.com/talk/ understanding_mod_perl/mod_perl_examples.tar.gz [Références] - http://perl.apache.org - http://perl.apache.org/guide - "Writing Apache Modules with Perl and C" http://www.oreilly.com/catalog/wrapmod/ - http://www.apache.org - http://www.perl.com - http://www.perl.org Cette dose de Perl vous à été présenté par : Les Missionnaires Perl de Montréal (MPM) http://montreal.pm.org/ -------------------------------------------------------------------------------- LJNB http://journal.bidon.ca/ Publié à chaque 3e vendredi du mois Édition 2002.03 --------------------------------------------------------------------------------