Tweet
Bonjour à tous !
Petit tutoriel sur les suites mathématiques, les générateurs de nombres pseudo-aléatoires et la cryptographie.
Suites mathématiques
Introduction
Les suites se présentent sous deux formes.
(Ce sont purement des notions de 1ère. Ça ne doit pas poser de problème. 
)
Autrement on note sous forme de calcul.
Là en général beaucoup d'élèves décrochent.
C'est pourtant très simple. U0 indique la valeur de départ.
Si on multiplie ou que l'on élève à la puissance de la valeur N, on calcule la récurrence dans un seul terme.
Ensuite on peut l'appliquer à une fonction pour visualiser la courbe.
Exception
Certaine suites ne peuvent pas être transformés sous forme de calcul.
Par exemple :
Ici, les termes appelés font partie de la suite.
Pour calculer la chaîne, il est nécessaire de programmer une boucle.
Suites démultipliés
Autre exception qui permettra d'arriver au second point de ce tutoriel.
Pour obtenir une suite démultiplié, il suffit de créer plusieurs fonctions liés.
Exemple :
La suite démultiplié est bien entendu la fonction h().
Elle fait appel à deux autres fonctions en parallèle.
Générateur de nombres pseudo-aléatoires
Introduction
Les générateurs de nombres pseudo-aléatoires sont des algorithmes qui génère une série de nombres par séquence (ensembles de valeurs qui se répètent dans le temps).
Sur une seule valeur on ne peux pas voir la répétition, il faut en observer une liste. Les nombres pseudo-aléatoires générés par l'ordinateur ne vous permettra pas d'identifier la suite, puis-ce qu'elle est basé sur l'heure.
La graine (seed)
Les générateurs utilisent des graines. Ce sont des valeurs génératrices qui changent la séquence utilisé, évitant ainsi une possible répétition événementielle. La taille de la graine importe peux, on va en discuter tout prochainement.
Exemple de générateur de nombres pseudo-aléatoires en Python 2.7
J'ai un peux améliorer le générateur de Von Newman.
Pour augmenter la taille de la séquence, la fonction utilise une variable stocké "self.y" et retourne uniquement le résultat compris dans l'intervalle [A,B[.
Vous suivez toujours ?! La difficulté à totalement basculé.
D'ailleurs je pense que vous ignorez pourquoi j'ai fais un tutoriel sur les suites numériques et les générateurs de nombres pseudo-aléatoires. Patience ...
Cryptographie
Oui, oui la cryptographie !
La plupart des systèmes cryptographiques ont un point faible : les séquences.
Il s'agit d'une suite mathématique que l'on ne voit pas forcément mais qui impacte sur la sécurité du chiffrement.
Les chiffrements asymétriques, tel que le RSA, sont encore plus sensible à ce genre de phénomène mathématique.
Observation
Pour comprendre le mécanisme, étudions les répétitions des suites arithmétiques et des suites géométriques.
Voici les résultats :
Bon, j'ai peut être fumé la moquette en lançant cette expérience.
Mais elle est plutôt concluante pour expliquer le phénomène des boucles mathématiques.
Chiffrement en RSA
Pour déchiffrer du RSA, on part du principe que chiffrer N fois la valeur permet de retrouver la valeur initiale.
Voir mon script de RSA
Dans ce code source, on observe deux boucles.
La première calcule le nombre de tour pour que la valeur X chiffré en RSA retourne à sa valeur initiale X. Cette donnée est sauvegardé dans i.
La seconde, boucle sur i afin que la valeur Y chiffré en RSA retourne à son couple X.
Génial, non ?! Ce genre de petit problème est lié au phénomène que nous avons étudié : les séquences.
Conclusion
Les systèmes mathématiques (ou cryptographiques) ont un problème de séquence. Pour des chiffrement asymétriques, il suffit de compter sa taille et de boucler le nombre recherché. Pour des suites mathématiques et géométriques, on peut très simplement deviner la logique qui s'exerce dessus. Et pour les générateurs de nombres pseudo-aléatoires, elle restera une limite à son développement.
Attention, ce tutoriel n'est pas définitif. J'aurai sans doute besoin de ré-expliquer certain passages. Il est loin d'être facile à comprendre pour tout le monde..
Postez vos questions.
A bientôt !
Petit tutoriel sur les suites mathématiques, les générateurs de nombres pseudo-aléatoires et la cryptographie.
Suites mathématiques
Introduction
Les suites se présentent sous deux formes.
{Suite arithmétique} Un+1=Un+4 (Addition ou Soustraction)
{Suite géométrique} Un+1=Un*18 (Multiplication, Division ou Puissance)
{Suite géométrique} Un+1=Un*18 (Multiplication, Division ou Puissance)
)Autrement on note sous forme de calcul.
{Suite arithmétique} Un = U0+4*n
{Suite géométrique} Un = U0*18^n
{Suite géométrique} Un = U0*18^n
C'est pourtant très simple. U0 indique la valeur de départ.
Si on multiplie ou que l'on élève à la puissance de la valeur N, on calcule la récurrence dans un seul terme.
Ensuite on peut l'appliquer à une fonction pour visualiser la courbe.
{Suite arithmétique} f(x) = U0+4x
{Suite géométrique} g(x) = U0*18^x
{Suite géométrique} g(x) = U0*18^x
Certaine suites ne peuvent pas être transformés sous forme de calcul.
Par exemple :
Un+1 = Un*Un-1
Pour calculer la chaîne, il est nécessaire de programmer une boucle.
Suites démultipliés
Autre exception qui permettra d'arriver au second point de ce tutoriel.
Pour obtenir une suite démultiplié, il suffit de créer plusieurs fonctions liés.
Exemple :
f(x) = 4+7*x
g(x) = 2*3^x
h(x) = f(x)+g(x)+h((x-1))
g(x) = 2*3^x
h(x) = f(x)+g(x)+h((x-1))
Elle fait appel à deux autres fonctions en parallèle.
Générateur de nombres pseudo-aléatoires
Introduction
Les générateurs de nombres pseudo-aléatoires sont des algorithmes qui génère une série de nombres par séquence (ensembles de valeurs qui se répètent dans le temps).
Sur une seule valeur on ne peux pas voir la répétition, il faut en observer une liste. Les nombres pseudo-aléatoires générés par l'ordinateur ne vous permettra pas d'identifier la suite, puis-ce qu'elle est basé sur l'heure.
La graine (seed)
Les générateurs utilisent des graines. Ce sont des valeurs génératrices qui changent la séquence utilisé, évitant ainsi une possible répétition événementielle. La taille de la graine importe peux, on va en discuter tout prochainement.
Exemple de générateur de nombres pseudo-aléatoires en Python 2.7
Code:
# Par Yarflam # Python 2.7 class random: def __init__(self,seed): self.y=seed if seed > 1000 else 1111 def gen(self,a,b): self.y=(int(str(pow(self.y,2))[1:-1]) % 10000) self.y=self.y+1111 if self.y < 1000 else self.y return (self.y % (b-a))+a g=random(1111) i=0 while i < 60: print g.gen(5,50) raw_input() i=i+1 raw_input()
Pour augmenter la taille de la séquence, la fonction utilise une variable stocké "self.y" et retourne uniquement le résultat compris dans l'intervalle [A,B[.
Vous suivez toujours ?! La difficulté à totalement basculé.
D'ailleurs je pense que vous ignorez pourquoi j'ai fais un tutoriel sur les suites numériques et les générateurs de nombres pseudo-aléatoires. Patience ...
Cryptographie
Oui, oui la cryptographie !
La plupart des systèmes cryptographiques ont un point faible : les séquences.
Il s'agit d'une suite mathématique que l'on ne voit pas forcément mais qui impacte sur la sécurité du chiffrement.
Les chiffrements asymétriques, tel que le RSA, sont encore plus sensible à ce genre de phénomène mathématique.
Observation
Pour comprendre le mécanisme, étudions les répétitions des suites arithmétiques et des suites géométriques.
Voici les résultats :
Code:
Suite arithmétique +1 (0)123456789 +2 (0)468 (1)3579 +3 (0)369258147 +4 (0)4826 (1)5937 +5 (0)5 (1)6 (2)7 (3)8 (4)9 +6 (0)6284 (1)7395 +7 (0)741852963 +8 (0)864 (1)9753 +9 (0)987654321 Comment ça fonctionne ? Sur le côté vous avez la suite +1/+2/+3..., la valeur entre parenthèse est celle de départ. Par exemple avec la suite +3, on part de 0. 0+3 = 3 3+3 = 6 6+3 = 9 9+3 = (1)2 2+3 = 5 5+3 = 8 8+3 = (1)1 1+3 = 4 4+3 = 7 7+3 = (1)0 --> Retour à la case départ. On peut observer un parallélisme inverse. Soustraire 3 ou ajouter 7 reviendrai à la même chose. 8-3=5, 8+7=(1)5. Idem avec les couples (1,9) (2,8) (4,6). Yarflam est fou ! oO Attendez j'ai pas fini. ;) Suite géométrique *2 (1,3,7,9)->2486 (5)->0 *3 ->3971 ->2684 ->5 *4 (1,9)->46 (3,7)->28 (5)->0 *5 ->50 *6 (1)->6 (2)->2 (3)->8 (4,9)->4 (5)->0 *7 ->1793 ->2486 *8 (1,3,7,9)->2684 (5)->0 *9 ->19 ->28 ->37 ->46 ->5 Petit changement de notation. Les valeurs entre parenthèses n'apparaissent qu'une seule fois dans la suite géométrique. Exemple avec le multiple de 6, 9 donne : 9*6=(5)4 4*6=(2)4 Pareille à la suite mathématique, on retrouve des similitudes inverses. *7 et *3, *8 et *2.
Mais elle est plutôt concluante pour expliquer le phénomène des boucles mathématiques.
Chiffrement en RSA
Pour déchiffrer du RSA, on part du principe que chiffrer N fois la valeur permet de retrouver la valeur initiale.
Voir mon script de RSA
Code:
i=tant que y différent de x( y=chiffrement(y) ) tant que j différent de i( y=chiffrement(y) )
La première calcule le nombre de tour pour que la valeur X chiffré en RSA retourne à sa valeur initiale X. Cette donnée est sauvegardé dans i.
La seconde, boucle sur i afin que la valeur Y chiffré en RSA retourne à son couple X.
Génial, non ?! Ce genre de petit problème est lié au phénomène que nous avons étudié : les séquences.
Conclusion
Les systèmes mathématiques (ou cryptographiques) ont un problème de séquence. Pour des chiffrement asymétriques, il suffit de compter sa taille et de boucler le nombre recherché. Pour des suites mathématiques et géométriques, on peut très simplement deviner la logique qui s'exerce dessus. Et pour les générateurs de nombres pseudo-aléatoires, elle restera une limite à son développement.
Attention, ce tutoriel n'est pas définitif. J'aurai sans doute besoin de ré-expliquer certain passages. Il est loin d'être facile à comprendre pour tout le monde..
Postez vos questions.
A bientôt !
Commentaire