cs_jupiter
Messages postés34Date d'inscriptionlundi 5 août 2002StatutMembreDernière intervention 9 janvier 2009
-
27 janv. 2005 à 08:27
Saros
Messages postés921Date d'inscriptionvendredi 20 décembre 2002StatutMembreDernière intervention23 septembre 2010
-
15 mars 2005 à 23:09
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
Saros
Messages postés921Date d'inscriptionvendredi 20 décembre 2002StatutMembreDernière intervention23 septembre 2010 15 mars 2005 à 23:09
Bah pour le nombre n donné, il n'y a qu'ne décomposition possible, en deux nombres premiers, puisque n est lui-même produit de ces deux nombres...
kenjimax
Messages postés82Date d'inscriptiondimanche 3 août 2003StatutMembreDernière intervention10 août 2007 15 mars 2005 à 22:43
Ce n'est pas un vrai cryptage RSA, enfin pas dans le sens ou un cryptage RSA est théoriquement "invulnérable". Les nombres ne sont pas assez grands !
"Il faudrait faire une routine qui décompose un nombre en facteurs premiers, de sorte à donner directement p et q à partir de n.
"
Ca c'est idiot :D Tout nombre n n'est pas le produit de deux nombres premiers, loin de là ! On définie toujours une clé publique selon cette méthode : on prend deux nombres premiers que l'on multiplie entre eux (pour eviter une possible factorisation de n qui permettrait d'économiser beaucoup de temps pour le décryptage sans clé, à l'aide des propriétés des congruences
Cela dit, si le programme est lent, c'est aussi (et surtout ?) parce que le VB n'est pas fait pour ce genre de calcul brut. L'assembleur en serait capable.
En tout cas, voila encore une source qui gagnerait à etre programmée en 64bits :) Ca viendra !
Saros
Messages postés921Date d'inscriptionvendredi 20 décembre 2002StatutMembreDernière intervention23 septembre 2010 31 janv. 2005 à 08:50
On peut aussi chercher, pour calculer m^n mod b, le premier entier i qui vérifie m^i mod b = 1
Il suffit alors de calculer m^(n mod i) mod b
Le système de la décomposition binaire est astucieux :)
cs_Warny
Messages postés473Date d'inscriptionmercredi 7 août 2002StatutMembreDernière intervention10 juin 2015 30 janv. 2005 à 17:08
Salut,
Pour accelerer un modulo avec des puissances de grands nombres il faut utiliser la propriété suivante :
(n * m) mod x = (n mod x) * (m mod x)
ensuite pour réduire le nombre de calculs tu peux t'appuyer sur des propriétés du genre :
m^(x+y) = m^x * m^y
et
m^(x*y) = (m^x) ^y
par exemple pour faire
15^6 mod 29 = 5
tu décomposes en
(((15^3) mod 29) ^2 mod 29) = 5
si tu doit calculer un nombre ou e est premier tu fais
15^7 mod 29 ((((15^3) mod 29) ^2 mod 29) * 15) mod 29 17
le plus rapide est de se rapprocher des puissances de 2 et de cacher un grand nombre de calculs
par exemple
14^29 mod 31=
14^16 * 14^8 * 14^4 * 14 mod 31 (il faut s'appuyer sur une décomposition binaire de e pour aller plus vite)
la on calcule
14^4 mod 29 = (14^2 mod 29)^2 mod 29
14^8 mod 29 = (14^4 mod 29)^2 mod 29 (on récupère le résultat précédent
14^16 mod 29 = (14^8 mod 29)^2 mod 29
puis on multiplie les termes les uns après les autres avec les modulos
résultat : très peu de calculs, des calculs simples, peu de mémoire utilisée.
Saros
Messages postés921Date d'inscriptionvendredi 20 décembre 2002StatutMembreDernière intervention23 septembre 2010 27 janv. 2005 à 09:37
Et puis j'ai une idée pour le calcul simple de modulo avec de grandes puissances, j'implémente un bout de code puis je te l'envoie
Saros
Messages postés921Date d'inscriptionvendredi 20 décembre 2002StatutMembreDernière intervention23 septembre 2010 27 janv. 2005 à 09:35
Et puis c'est bizarre que l'utilisateur soit obligé d'entrer p et q, on dirait qu'il a le choix alors qu'en fait il n'y a qu'une seule possibilité... Il faudrait faire une routine qui décompose un nombre en facteurs premiers, de sorte à donner directement p et q à partir de n.
truc.CStrToByte(1)
tu as oublié les guillemets :) heureusement que VB fait la conversion...
Et puis aussi, dans le message crypté, fais des modulos 256 partout, parce que le caractère 305 il existe pas ^^
Et puis ça te permet d'écrire le message crypté directement dans un fichier texte, sans écrire les chiffres à la bourin, mais en écrivant les caractères... Je ne sais pas si je me suis bien expliqué :)
Private t() As Long
t ne contient que des Byte, ça mange beaucoup de mémoire pour rien
Quand tu cryptes, fais des DoEvents quelque fois, je suis en train d'essayer avec 241 et 353, je te dis pas comment ça rame (2,6 GHz 2 procs) ^^
Au fait, je viens de lire le Compte-rendu, où tu as écrit pourquoi de Alice vers Jean le u avait des ratés, fais pas attention à mon premier message
Et puis pour le cryptage avec 241 et 353 j'ai fini par abandonner... Mais je persiste qu'il devrait y avoir un moyen d'accélérer notablement le calcul, je sais que de nos jour le cryptage se réalise avec des nombre n pouvant aller jusqu'à 130 chiffres.
Voilà, sinon c'est la première fois que je vois une implémentation de l'algorithme depuis que j'ai appris c'était quoi le RSA, donc j'ai trouvé bien interressant :)
Pis ça vaut bien un 9/10
Saros
Messages postés921Date d'inscriptionvendredi 20 décembre 2002StatutMembreDernière intervention23 septembre 2010 27 janv. 2005 à 09:14
Problème lors du cryptage : dans "Bonjour" le u se transforme en (R).
cs_jupiter
Messages postés34Date d'inscriptionlundi 5 août 2002StatutMembreDernière intervention 9 janvier 2009 27 janv. 2005 à 08:27
Bonjour,
Le programme boucle lors de la création du compte après avoir saisi par exemple 97 et q=1.
Manque également dans le zip le .doc d'explications dont tu nous parles.
15 mars 2005 à 23:09
15 mars 2005 à 22:43
"Il faudrait faire une routine qui décompose un nombre en facteurs premiers, de sorte à donner directement p et q à partir de n.
"
Ca c'est idiot :D Tout nombre n n'est pas le produit de deux nombres premiers, loin de là ! On définie toujours une clé publique selon cette méthode : on prend deux nombres premiers que l'on multiplie entre eux (pour eviter une possible factorisation de n qui permettrait d'économiser beaucoup de temps pour le décryptage sans clé, à l'aide des propriétés des congruences
Cela dit, si le programme est lent, c'est aussi (et surtout ?) parce que le VB n'est pas fait pour ce genre de calcul brut. L'assembleur en serait capable.
En tout cas, voila encore une source qui gagnerait à etre programmée en 64bits :) Ca viendra !
31 janv. 2005 à 08:50
Il suffit alors de calculer m^(n mod i) mod b
Le système de la décomposition binaire est astucieux :)
30 janv. 2005 à 17:08
Pour accelerer un modulo avec des puissances de grands nombres il faut utiliser la propriété suivante :
(n * m) mod x = (n mod x) * (m mod x)
ensuite pour réduire le nombre de calculs tu peux t'appuyer sur des propriétés du genre :
m^(x+y) = m^x * m^y
et
m^(x*y) = (m^x) ^y
par exemple pour faire
15^6 mod 29 = 5
tu décomposes en
(((15^3) mod 29) ^2 mod 29) = 5
si tu doit calculer un nombre ou e est premier tu fais
15^7 mod 29 ((((15^3) mod 29) ^2 mod 29) * 15) mod 29 17
le plus rapide est de se rapprocher des puissances de 2 et de cacher un grand nombre de calculs
par exemple
14^29 mod 31=
14^16 * 14^8 * 14^4 * 14 mod 31 (il faut s'appuyer sur une décomposition binaire de e pour aller plus vite)
la on calcule
14^4 mod 29 = (14^2 mod 29)^2 mod 29
14^8 mod 29 = (14^4 mod 29)^2 mod 29 (on récupère le résultat précédent
14^16 mod 29 = (14^8 mod 29)^2 mod 29
puis on multiplie les termes les uns après les autres avec les modulos
résultat : très peu de calculs, des calculs simples, peu de mémoire utilisée.
27 janv. 2005 à 09:37
27 janv. 2005 à 09:35
truc.CStrToByte(1)
tu as oublié les guillemets :) heureusement que VB fait la conversion...
Et puis aussi, dans le message crypté, fais des modulos 256 partout, parce que le caractère 305 il existe pas ^^
Et puis ça te permet d'écrire le message crypté directement dans un fichier texte, sans écrire les chiffres à la bourin, mais en écrivant les caractères... Je ne sais pas si je me suis bien expliqué :)
Private t() As Long
t ne contient que des Byte, ça mange beaucoup de mémoire pour rien
Quand tu cryptes, fais des DoEvents quelque fois, je suis en train d'essayer avec 241 et 353, je te dis pas comment ça rame (2,6 GHz 2 procs) ^^
Au fait, je viens de lire le Compte-rendu, où tu as écrit pourquoi de Alice vers Jean le u avait des ratés, fais pas attention à mon premier message
Et puis pour le cryptage avec 241 et 353 j'ai fini par abandonner... Mais je persiste qu'il devrait y avoir un moyen d'accélérer notablement le calcul, je sais que de nos jour le cryptage se réalise avec des nombre n pouvant aller jusqu'à 130 chiffres.
Voilà, sinon c'est la première fois que je vois une implémentation de l'algorithme depuis que j'ai appris c'était quoi le RSA, donc j'ai trouvé bien interressant :)
Pis ça vaut bien un 9/10
27 janv. 2005 à 09:14
27 janv. 2005 à 08:27
Le programme boucle lors de la création du compte après avoir saisi par exemple 97 et q=1.
Manque également dans le zip le .doc d'explications dont tu nous parles.