Discussion :

[HacKSpideR]

Bonjour à tous,
Je vient vous demander de l'aide, j'ai déjà posé ce probleme sur un autre forum mais je n'ai pas encore eu de réponse.

Actuellement, je me suis lancé dans le dévellopement d'un logicielle permettant de communiquer entre deux ordinateurs de manière sécurisée. Je me suis donc mis à la rechercher d'algorithme de chiffrement qui pourrait me servir. Je suis tombé sur un article traitant de la "cryptographie grace aux courbes elliptiques". Les avantages de cette méthode serai la légéreté des calcules et des clés comparer à RSA qui demande des clés de 1024 bits. Il y'a pourtant deux probleme : la complexité de la méthode et les brevets déposés sur la méthode ...

Malheureusement, je ne suis qu'en première et je ne suis pas un génie en math ...
J'ai donc quelques problèmes avec le probleme du logarithme discret.

Je m'explique, je souhaiterai utiliser la méthode d'échange de clés de Diffie-Hellmann, d'après cette article : http://math.univ-bpclermont.fr/~rebo...jetMichael.pdf, pour ensuite "hasher" le résultat obtenue pour me servir du hash comme clé qui chiffrerai les données envoyées grâce à l'algorithme BlowFish.

L'article dit :

1. Alice et Bob choisissent une courbe elliptique E définie sur un corps fini Fq tel
que le logarithme discret (voir juste après) soit difficile à résoudre. Il choisissent
aussi un point P ∈ E(Fq ) tel que le sous-groupe généré par P ait un ordre de
grande taille. (En général, la courbe E et le point P sont choisis de manière à
ce que l’ordre soit un grand nombre premier.)
2. Alice choisit un nombre entier secret a, calcule Pa = aP et envoie Pa à Bob
3. Bob choisit un nombre entier secret b, calcule Pb = bP et envoie Pb à Alice
4. Alice calcule aPb = abP .
5. Bob calcule bPa = baP .
6. Alice et Bob utilisent une méthode quelconque connue pour extraire une clé
secrète de abP . Par exemple, ils peuvent utiliser les derniers 256 bits de la
première coordonnée de abP comme clé, ou ils peuvent hacher une des co
ordonnées de abP avec une fonction de hachage (voir la définition 2.5) pour
laquelle ils se sont mis d’accord.

D'après ce que j'ai compris, il faut donc se mettre d'accord sur une courbe elliptique : y^2 = x^3 +ax + b, ensuite choisir un point P sur cette courbe (grace à l'algorithme de Schoof si j'ai bien compris la fin de l'article) puis chaqu'un choisit un entier de grande taille qu'ils vont multiplié avec ce point P et donc le produit des 2 entiers et de P donnera la clé secréte. ( la courbe E, le point P, aP et bP sont publiques ).

J"aimerai savoir si je ne me trompe pas, car je n'ai pas trop compris le problème du logarithme discret et donc si me trompe je risque de ne pas m'en rendre compte

Et d'après vous, qu'elle serai la taille minimum des "variables" pour que l'échange soit sécurisée ?

J'éspére que vous pourrez m'aider

HacKSpideR

[lacaulac]

Eviron 128 bits je pense

[Acrim]

Si c'est le fait de travailler avec des courbes elliptiques qui t'embrouille un peu pour comprendre l'échange de clés Diffie-Hellman, tu peux dans un premier temps raisonner avec un groupe de la forme Z/pZ avec p un nombre premier(cf l'article de wikipedia sur Diffie-Hellman par exemple).

Mais pour résumer le problème du logarithme discret : Soit g un générateur de ton groupe et x un élément de ton groupe. Trouver le logarithme discret signifie trouver a tel que g^a = x .

L’intérêt des courbes elliptiques est qu'elles permettent l'utilisation de clefs plus petites pour un niveau de sécurité équivalent (a priori). Je crois que cela est lié au fait que les opérations de bases sont plus couteuses.

En espérant que cela t'aidera.

[souviron34]

L’intérêt des courbes elliptiques est qu'elles permettent l'utilisation de clefs plus petites pour un niveau de sécurité équivalent (a priori). Je crois que cela est lié au fait que les opérations de bases sont plus couteuses.

euh.. non...


C'est lié au fait qu'un log (par exemple) est l'inverse d'une exponentielle..

Et que donc log(100) = 2 en base 10...

log(1000) = 3..

D'où une "compression" de la clé...

Au lieu d'avoir 1000, on n'a que 3. En théorie ça peut s'appliquer aux bytes. Mais en pratique un log c'est un nombre à virgule flottante, c'est donc (en double-précision) 64 bits = 8 bytes sur un 32-bits.

Mais comme la cryptographie utilise des grands nombres représentés sur de grands nombres de bits, on peut donc drastiquement réduire la taille du résultat de l'encryptage...

Exemple : la valeur max d'un nombre double-précision en 32 bits est e+308. Représenté donc sur 64 bits. Si ce nombre est un log, c'est que la valeur initiale de la clé était e+(e+308)... C'est à dire 128 bits (euh... ou nettement plus... mes idées sont brouillées à cette heure-ci). On avait donc une clé 128 (ou nettement plus (voir plus haut)) bits représentée par un nombre 64 bits..


Pour la même chose.. puisque c'est le même nombre dérivé par une fonction connue (et son inverse aussi)

[Acrim]

La clef publique n'est pas l'exposant donc je ne suis pas sûr que ce que tu expliques aie une influence sur la taille de la clef.

Après une rapide recherche, il semble effectivement que la taille réduite des clés dans la ECC est liée à la "lenteur" de opérations utilisables pour résoudre la problème de log discret dans ce cadre.

[souviron34]

La clef publique n'est pas l'exposant donc je ne suis pas sûr que ce que tu expliques aie une influence sur la taille de la clef.

C'était juste un exemple pour montrer la difféence et l'intérêt d'une fonction comme un log ou autre, qui peut réduire considérablement le nombre de bits engagés ou la longueur de la chaîne/du nombre...