Discussion :

[Sir Caedes]

Bonjour à tous,

Je suis en train d'essayer d'élaborer un programme de cryptage RSA en Caml Light.

Je rencontre quelques difficultés, dans l'utilisation du type Big_int de Caml Light.

La premiere est que la fonction power_big_int_positive_big_int (exponentiation du premier argument à la puissance second argument)
est bugguée, elle ne renvoie pas les bons resultats dans la plupart des cas.
C'est un bug connu, mais qui n'a pas pour autant été corrigé dans la derniere version disponible pour windows (0.74) de Caml Light.

La deuxieme difficulté que je rencontre, est la suivante :
Ma fonction de decryptage (qui prend pour argument n , d (la clé privée) et M le nombre à decrypter ) me renvoie un "Uncaught exception : Out of Memory" lorsque je tente de prendre :

n=334411751 , d = 284254577 , M = 66875021

Néanmoins, si je rentre seulement les instructions de ma fonction directement, pas de out of memory, mais le calcul s'éternise.
(Est il normal que cela mette autant de temps à décrypter pour une clé de seulement 30 bits ? )


Bref que de problemes j'espere que vous pourrez m'apporter un peu d'aide...
Merci !

[Jedai]

Caml Light est un langage abandonné... Pour un projet sérieux il faut utiliser OCaml.

--
Jedaï

[Sir Caedes]

Bonsoir,

je viens d'installer Ocaml, pourrais-tu m'indiquer quelles sont les librairies à charger pour pouvoir utiliser des grands entiers, ainsi que les operations associées ?

Merci.

[Sir Caedes]

Je suis parvenu à les trouver, et j'ai à peu pres compris comment m'en servir.

Néanmoins, il subsiste un probleme, celui du débordement de mémoire
"Out of memory during evaluation."

J'ai tenté de calculer 128 à la puissance 5320923 par la fonction power_big_int_positive_big_int , mais encore "out of memory".
Je suis conscient qu'il s'agit de tres grands entiers, mais n'y a t-il pas un moyen d'éviter cela ?

Merci.

[Jedai]

128 à la puissance 5320923 ? (10^2)^5000000, autrement dit 10^(10^7) supérieur à 2^(10^7), autrement dit un nombre qu'on ne peut stocker sur moins de 1 Mo (largement sous évalué et avec une méthode de stockage idéale !) ? As-tu vraiment besoin de tels nombres ?

Essaie de coder la mise à la puissance avec une boucle, pour vérifier si l'implémentation supporte cette taille.

--
Jedaï

[Sir Caedes]

Mon programme doit pouvoir crypter et decrypter en RSA avec des clés assez grosses (mais raisonnables).
Je crois que le calcul précédent à été induit lors du décryptage avec une clé de 30 bits ou même moins
(générée ici http://www.bibmath.net/crypto/moderne/rsa.php3)
Donc je suppose que j'aurai besoin de manipuler au moins d'aussi grands nombres, à moins que je ne m'y prenne mal

[Jedai]

Tu t'y prend mal à coup sûr ! Par exemple tu ne fais pas de la mise à la puissance modulo, mais de la mise à la puissance directe puis du modulo, et c'est pour ça que tu arrives à ces chiffres ridiculement grands...

--
Jedaï

[Sir Caedes]

Voila c'est cela !
Comment pourrais-je faire pour améliorer ça ? :/

PS : j'ai codé la mise à la puissance comme tu me l'a dis, avec une boucle, si cela ne me renvoie pas de out_of_memory, en revanche cela met un temps infini, j'ai lancé le calcul cette nuit, et il n'est toujours pas terminé... Mais bon si tu me dis qu'on peut se passer d'aussi grands nombres, c'est inutile de toute façon

Edit : Peut-être en codant une fonction de puissance qui prenne le modulo à chaque multiplication effectuée ?

[Sir Caedes]

Probleme résolu