Discussion :

[wozzy]

J'ai comme projet de créer un logiciel de cryptage (du genre de PGP)

Comment représenter en C les clés privées et publiques (très grands entiers sur énormément de bits ==> de l'ordre de 128 bits pour commencer)?

Merci d'avance

[MOD : En fait, il s'agit de C++]

[GoldenEye]

il faut créer une structure de type tableau de n éléments où n est le nombre de chiffres.
A partir de là il convient de réécrire les opérations de base d'addition, multiplication, division, modulo...

[Bob]

Ou peut on trouver les algo des operations de base. Parce que j'ai deja essaye de faire une classe, mais les algos me manquaient.

[haypo]

Je te conseille d'utiliser une librairie qui existe déjà, voir ma liste :
http://www.haypocalc.com/lien.php

Sinon, je me suis essayé à en écrire une, mais c'est galère-galère! Ces quelques pages pourront t'aider :
http://www.haypocalc.com/grandnbr/

@+ Haypo

[GoldenEye]

ces algos ne sont pas très durs. Il faut poser les opérations comme en CP ou CE1, travailler avec les retenues etc...

[Bob]

Non non, il ne faut pas poser les oprations comme a la main. ces algo sont bcp bcp bcp plus lents que ceux utlises par les processeurs.
C'est ceux la qu'il faut utiliser (ex: multiplication a la russer) avec seulement des divisions par 2 et des additions.
C'est ce genre d'algo que je cherche, mais aussi Division, modulo, Racine, enfin tt koi.
Si qqn pouvait me dire ou trouvers ces algo ca serait super.

[zul]

vous pourriez peut etre regarder la bibliotheque MP ici http://www.swox.com/gmp/.


ZUL

[Geronimo]

J'ai justement eu le même problème.

La librairie NTL est s'installe très bien et fonctionne très bien.

De plus, elle a toutes les fonctions nécessaires de générations de nombres premiers, etc... très pratiques pour le cryptage.

[tagwin]

bonjour,
ah vous parler de NTL ça tombe bien, c'est une bibliotheque C++ qui permet de manipuler de tres grand nombres (je ne sais meme pas si il y a une limite) et de faire des operations dessus (les operrateurs ont ete redefinis et bien d autres encore...).

j'ai téléchargé la bibliotheque sur le lien suivant: www.shoup.net/ntl

Par contre je ne sais pas comment l'installer, est ce que je dois la compiler ou juste l'utiliser en la plaçant dans un endrois bien pricis sachant que j'utlise DEV C++.

Merci

[Emmanuel Delahaye]

bonjour,
ah vous parler de NTL ça tombe bien, c'est une bibliotheque C++ qui permet de manipuler de tres grand nombres

Tu développes en C ou en C++ ?

[tagwin]

ouuups, je développe en C++ et j'utilise dev C++

[loufoque]

Non non, il ne faut pas poser les oprations comme a la main. ces algo sont bcp bcp bcp plus lents que ceux utlises par les processeurs.
C'est ceux la qu'il faut utiliser (ex: multiplication a la russer) avec seulement des divisions par 2 et des additions.

C'est exactement le même algorithme que la multiplication classique qu'on voit au primaire sauf que c'est en base 2 et pas en base 10...

[mchk0123]

Pour compléter ce qui a été dit, on peut aussi extrapoler ce principe au calcul de puissance (z = x ^ y).

Ceci étant PGP est un programme libre dont le code source est téléchargeable (attention il existe une version spécifique Internationale qui pose moins (ou pas ?) de problèmes concernant les legislations diverses en cours dans notre pays et les US) et contient tout ce qui faut pour apprendre comment faire.

[jobherzt]

C'est exactement le même algorithme que la multiplication classique qu'on voit au primaire sauf que c'est en base 2 et pas en base 10...

oui mais non, la multiplication "classique" est en O(n^2), alors qu'il existe d'autre methode un eu plus techniques (transformée de fourier rapide) qui descende en O(n log(n))

[Jean-Marc.Bourguet]

oui mais non, la multiplication "classique" est en O(n^2), alors qu'il existe d'autre methode un eu plus techniques (transformée de fourier rapide) qui descende en O(n log(n))

Et qui n'est rentable qu'a partir d'une certaine taille. Pour 128 bits, je doute que ce soit le cas.

Il y a aussi des algo en n^x avec x plus petit que 2. Si j'ai bonne memoire, il y a meme une famille de tel algo qui permet de choisir x aussi proche de 1 que desire.

[jobherzt]

Et qui n'est rentable qu'a partir d'une certaine taille. Pour 128 bits, je doute que ce soit le cas.

evidemment, il faudrait connaitre les constantes derriere, mais pour 128 bits il me semble qu'il faudrait que le rapport des contantes soit de l'ordre de 30 pour que ca revienne au meme....

et puis n'oublions pas qu'en crypto on a vite fait de manipuler un peu plus que 128 bits..

[Jean-Marc.Bourguet]

evidemment, il faudrait connaitre les constantes derriere, mais pour 128 bits il me semble qu'il faudrait que le rapport des contantes soit de l'ordre de 30 pour que ca revienne au meme....

et puis n'oublions pas qu'en crypto on a vite fait de manipuler un peu plus que 128 bits..

De memoire gmp utilise l'algo n^2 jusqu'au moins 512 bits, puis utilise d'autres algos et n'utilise la FFT qu'au moins a partir de 50000 bits. L'algo a base de FFT est tres lourd (et delicat a mettre en oeuvre parce qu'il fait intervenir des flottants et donc il faut bien controler la precision).

Pour 128 bits comme donne dans le message initial, je n'irais pas voir plus loin que l'algo classique.

Pour de la crypto plus generale, je crois que dans un premier temps j'utiliserais gmp ou une autre bibliotheque du genre et qu'ensuite si j'ai un probleme de perf (ou du temps a perdre, ou un probleme de license), je testerais Karatsuba et Toom-Cook.

[jobherzt]

De memoire gmp utilise l'algo n^2 jusqu'au moins 512 bits, puis utilise d'autres algos et n'utilise la FFT qu'au moins a partir de 50000 bits. L'algo a base de FFT est tres lourd (et delicat a mettre en oeuvre parce qu'il fait intervenir des flottants et donc il faut bien controler la precision).

ok, j'aurais appris quelque chose...

[mchk0123]

Pour reprendre ce que je disais plus haut, l'algo de calcul x * y en décomposant y en base 2 est simple à comprendre :

y = somme_sur_i(2 ^ yi) avec yi dans [0,1]

Ensuite il suffit de développer :

x * y = somme_sur_i(x * 2 ^ yi)

On remplace donc une multiplication de 2 entiers, par des sommes de plusieurs entiers (plus rapide) et des décalages successifs à gauche (trés rapide).

On peut même optimiser encore plus en faisant :

z0 = x
pour i dans [1, n], zi = zi-1 * 2

Ainsi on calcul itérativement les x * 2 ^ yi d'aprés x * 2 ^ yi-1 ce qui beaucoup plus rapide.

[Jean-Marc.Bourguet]

Pour reprendre ce que je disais plus haut, l'algo de calcul x * y en décomposant y en base 2 est simple à comprendre

C'est un algo qu'on utilise pour batir une multiplication quand on n'a pas de multiplication fournie par le processeur, mais pas pour batir une multiplication en precision multiple. C'est plus simple d'appliquer la méthode scolaire (avec une expression des nombres dans une base convenablement choisie; 10_000 et 65_536 -- 2^16 -- sont deux bons candidats quand on dispose de l'arithmetique en 32 bits; 1_000_000_000 et 4_294_967_296 -- 2^32 -- quand on dispose de l'arithmétique en 64 bits).