tous les documents
  • tous les documents
  • Images
  • Films
  • Rushes
  • Publications
  • Audio
Recherche avancée
Ensemble de recherche :
tous les documents
  • tous les documents
  • Images
  • Films
  • Rushes
  • Publications
  • Audio
Recherche par couleur
Ensemble de recherche :
tous les documents
  • tous les documents
  • Images
  • Films
  • Rushes
  • Publications
  • Audio
Code HTML Copiez-collez le code ci-dessous pour l'intégrer dans une page Web.
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 :
Lien Equipe-projet :
Lien Centre de Recherche :
Mots clés :
N° master :
1144
Durée :
06 min 40 sec
IsyTag :
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
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
Sélection
Voir Selection
Déposer ici pour retirer de la sélection