Lien vers la page du documentCopiez/collez ce lien pour l'envoyer par email, l'inclure dans une page web ou le partager sur les réseaux sociaux.
Code HTMLCopiez-collez le code ci-dessous pour l'intégrer dans une page Web.
Taille d'affichage :
Titre :
Concours Alkindi : Matthieu Lequesne
Légende - Résumé :
Matthieu Lequesne est doctorant en cryptographie au sein de l'équipe-projet ; il donne la correction de l'exercice "réseau" dans le cadre du concours Alkindi. Il s'agit de comprendre quelles cases sont accessibles ou non sur une grille. Le concours Alkindi est une compétition de cryptographie ouverte aux classes de 4e, 3e et 2nde.
Nom de fichier :
Inria-1144_AlKindi2018_MLequesne.mp4
Titre :
Concours Alkindi : Matthieu Lequesne
Année :
2018
Durée (min) :
00:06:40
Publications :
http://videotheque.inria.fr/videotheque/doc/1144
Autres versions :
Master VF : 1144 Master VEN : Autre : Lien externe :
accessible
- case
- cases
- cryptographie
- déplacement
- diagonale
- exercice
- flèche
- gauche
- grille
- petit
- problème
- utiliser
- version
Transcription automatiqu :
Bonjour Je m'appelle Mathieu Lequesne Je suis doctorant en cryptographie à Sorbonne Université et je travaille à Inria Paris au sein de l'équipe SECRET Je suis aussi organisateur du concours AlKindi et aujourd'hui je vais vous parler de l'exercice Réseaux Alors lorsqu'on arrive sur l'exercice la première chose qu'on voit c'est une grille avec un point qui peut se déplacer Alors on clique sur les flèches pour comprendre quels sont les déplacements possibles du point et on voit on constate qu'il y a certaines cases sur lesquelles on peut aller et certaines cases sur lesquelles on ne pourra jamais se déplacer Et donc l'objectif de l'exercice c'est de comprendre exactement sur l'ensemble des cases de la grille sur quelques cases on pourra se déplacer et sur quelles cases on n'aura pas le droit d'aller C'est comme si on avait un échiquier avec un nouveau pion qui respecterait des règles de déplacement particulières et de comprendre donc quelles cases sont accessibles et quelles cases ne sont pas accessibles Il y a trois versions de difficulté de chaque exo Sur la première version c'est relativement simple on voit que on peut se déplacer à gauche à droite en haut en bas en allant deux cases à gauche deux cases à droite On peut se déplacer sur la partie haute la grille facilement On peut voir sur quelle case de chaque zone on peut se rendre Pour les zones qui sont dans la partie inférieure de la grille donc dans lesquelles on n'a pas le droit de se rendre directement on comprend vite qu'on peut se positionner au-dessus et compter de deux en deux et voir quelles sont les cases qui sont accessibles et quelles sont les cases qui ne sont pas accessibles Pour la version intermédiaire Là tout de suite c'est un petit peu plus compliqué puisque Les flèches avec lesquelles on a le droit de se déplacer les déplacements autorisés sont un petit peu moins pratiques Lorsqu'on par exemple on va se déplacer vers le haut on a pas juste une flèche qui va le haut Néanmoins lorsqu'on essaie par exemple de regarder si on peut atteindre la case en haut à gauche on voit que en alternant une flèche puis l'autre à chaque fois en fait on se déplace d'une case en haut à gauche sur la diagonale Et donc en fait en répétant ce déplacement une fois qu'on est sur une case on peut se déplacer n'importe où sur la diagonale concernée Donc on peut atteindre toutes les diagonales de cette façon et cette astuce nous permet de beaucoup mieux visualiser quelles sont les cases sur lesquelles on a le droit de se rendre quelles sont les cases sur lesquelles on n'a pas le droit de se rendre Et donc peut conclure quels sont les points dans chaque zone qui sont accessibles et valider cet exercice Donc lorsqu'on découvre le sujet de la version difficile On voit qu'ici il y a quelque chose de nouveau qui se passe c'est à dire que les flèches sont grandes et en fait lorsqu'elles dépassent d'un côté on revient de l'autre côté C'est comme si on faisait le tour de la grille en mathématiques on dit que c'est un tort Alors Du coup on a on comprend encore moins quels sont les les bons déplacements qu'on a droit d'effectuer Mais pour simplifier les choses on va essayer d'utiliser la même astuce que à l'exercice précédent à la version précédente à savoir qu'on va essayer d'identifier des déplacements plus petits qu'on a le droit d'effectuer Donc par exemple si on répète si on utilise les flèches pour se déplacer vers la gauche qu'on fait tout le tour au bout d'un certain temps on se rend compte qu'on s'est retrouvé juste deux cases plus bas que la position d'origine sur la diagonale Donc c'est ici la flèche verte Donc en fait on peut en répétant cette opération se déplacer de deux cases en bas à droite suivant la flèche verte Maintenant si je rajoute encore un déplacement Je vois que je me retrouve sur la même ligne mais trois cases à gauche comme on voit sur la flèche grise donc ça aussi c'est un déplacement autorisé Donc en fait on peut se dire que ces petites flèches on peut les obtenir en répétant en itérant les grandes flèches Maintenant si j'utilise ces petites flèches en fait si je fais ce déplacement équivalent à la flèche grise une fois puis deux fois le déplacement diagonal équivalent à la flèche verte et puis une fois encore la flèche rouge où est ce que je me suis retrouvé par rapport à la position initiale je suis juste une case en haut à gauche sur la diagonale Donc en fait on itérant tous les déplacements on peut au final se retrouver juste une case en haut à gauche sur la diagonale Donc comme à la version précédente finalement on se rend compte que on peut se déplacer partout sur les diagonales en haut à gauche ou en bas à droite Et une fois qu'on a remarqué ça et seulement là on peut beaucoup mieux comprendre quelles sont les positions qu'on peut atteindre et donc décider dans chaque zone quelles sont les cases qui sont atteignables et valider l'exercice Quel rapport avec la cryptologie Alors ici on est face à un problème qui peut être soit très facile si on a des petites flèches des flèches qui sont pratiques pour se déplacer en haut en bas à droite à gauche Et le même problème peut devenir très difficile si on a des longues flèches qui vont dans des directions qui sont pas forcément bien identifiées Donc en fait ça c'est quelque chose qu'on aime bien utiliser en cryptographie Un problème qui peut être très difficile de manière générale et en même temps devenir très facile si on a une astuce qui le simplifie Ici l'astuce ça va être de pouvoir comprendre comment construire des petites flèches C'est comme si vous imaginez que vous avez un cadenas à code Bon si vous essayez si vous ne connaissez pas la combinaison il va falloir utiliser essayer toutes les combinaisons ça va être difficile de l'ouvrir Maintenant si vous avez le secret si vous avez la combinaison ça va aller très vite Ben ici c'est la même chose et on pourrait dire que votre secret votre combinaison secrète c'est la connaissance des petites flèches L'objet mathématique on étudie ici s'appelle un réseau un réseau euclidien et les flèches qu'on voit ici c'est ce qu'on appelle mathématiquement des vecteurs Et donc la question qu'on a étudié c'est comment trouver le plus petit vecteur dans un réseau c'est à dire la plus petite flèche sur la grille ça c'est un problème qui existe qui est étudié qui s'appelle le shortest vector problem donc le problème du plus petit vecteur Donc il faut imaginer que c'est exactement le même problème que ce qu'on a fait ici mais ça peut être sur une grille en deux dimensions mais aussi en trois dimensions est dans des dimensions beaucoup plus grande et plus la dimension de sa grande plus difficile à résoudre Et donc ce problème mathématique propose une alternative à ce qui est utilisé actuellement pour sécuriser nos communications et constitue peut-être le futur de la cryptographie
À voir aussi…
Albums (sélection d'images)
Fichiers en téléchargement
Inria-1144_AlKindi2018_MLequesne.mp4
Format : .mp4
550 Mo
1920 x 1080 pixels
Inria-1144_AlKindi2018_M_HD.MP4
Format : .mp4
244,5 Mo
1024 x 576 pixels
Moyenne définition - équivalent DVD Encodage PAL .MP4 H264 5 Mbits/s Encodage PAL .MP4 H264 5 Mbits/s