Discussion :

[rmaker]

Mes bien chers tous, bonjour,

je fais appel à vous pour une question de mathématiques liée à la cryptographie. Je prends un nombre premier "grand", et j'en déduis un corps Z/pZ, qui est le corps avec l'addition et la multiplication modulo p. Dans des algorithmes comme El Gamal, par exemple, on dit: prendre un générateur du groupe multiplicatif de Z/pZ. C'est à dire qu'on cherche un nombre r tel que, pour tout élément non nul y du corps Z/pZ, il existe un entier a tel que r^a = y.

Ma question est: comment trouver ce générateur? Etant donné un nombre premier p, j'aimerais un algorithme qui me donne un nombre r qui génère le groupe multiplicatif du corps Z/pZ. Comment le calculer? Si je prends un nombre r "au hasard", j'aimerais éviter de calculer toutes ses puissances pour savoir s'il convient. Avez vous une idée? Un algorithme intelligent (qui ne calcule pas toutes les puissances d'un candidat)?

Merci pour votre aide!

[Flodelarab]

Bonjour

Si tu posais cette question dans , la réponse serait donné par un logarithme.
Mais ici, je crois que tu poses la question du logarithme discret, qui est réputé insoluble actuellement.

[rmaker]

Merci pour ta réponse. Effectivement, dans R, c'est facile.
Mais je ne suis pas d'accord avec toi. Je ne pose pas la question du logarithme discret, justement parce qu'elle est encore complexe à résoudre.

Je pose la question suivante: Le groupe multiplicatif d'un corps fini est cyclique. Il admet donc un générateur, et cherche un moyen pratique de trouver ce générateur. C'est tout.

Pour poser la même question autrement, je te cite cet article: elle choisit d'abord p suffisamment grand pour que le calcul du logarithme discret soit infaisable pratiquement dans le groupe multiplicatif ℤp*, g un générateur de ce groupe.

Toute ma question c'est: comment Alice calcule g le générateur du groupe, en pratique?

merci à vous

[pseudocode]

Bonjour,

Toute ma question c'est: comment Alice calcule g le générateur du groupe, en pratique?

En pratique, Alice ne choisit pas le n'importe quel premier "p" puis essaye ensuite de trouver un "g" qui soit générateur.

Pour sécuriser le chiffrement, il faut des conditions sur la factorisation de "p-1" pour éviter de boucler sur un petit ensemble de valeurs.
=> La factorisation de "p-1" doit avoir le minimum de facteurs possibles.
=> L'idéal étant un seul facteur premier "q": p-1 = k.q (avec k un entier).

(Note: pour k=2, on appelle "p" un safe-prime. Il y a des listes.)

Une fois cette condition posée, un élément quelconque de ℤp* a un ordre égal à 1, k, q ou p-1.

La probabilité de trouver un générateur du groupe est: phi(p-1) / (p-1) = phi(k)*phi(q) / (p-1), avec phi() = indicatrice d'Euler.

(Note: Pour k=2, la proba est phi(2)*phi(q) / (p-1) = (1)*(q-1) / (p-1) = (q-1) / (2q) ~ 0.5, c'est à dire 50% de chance.)

On peut donc procéder par des essais:
On prend un élément "g" de ℤp* au hasard, et on vérifie son ordre.
Si ordre(g) est différent de p-1, alors on prend une autre valeur de "g" et on réessaye.

En pratique, si k est assez petit, on peut conserver "g" même si ordre(g)=q.
On bouclera quand même sur un grand nombre de valeurs (car q est assez grand).

Algo:
1. choisir (p,k,q) tels que p premier, q premier, k petit et p-1=k.q (cas particulier: p un safe-prime, q=(p-1)/2, k=2)
2. g = random^k mod p
3. Si "g = 1", alors goto 2 (car ordre(g)= 1 ou k)
3. Sinon, g est un pseudo-générateur (car ordre(g)= q ou p-1)

[rmaker]

Merci, merci infiniment pour ta réponse!

[rmaker]

En fait, je n'ai pas très bien compris ta réponse, pseudocode:

2. g = random^k mod p
3. Si "g = 1", alors goto 2 (car ordre(g)= 1 ou k)
3. Sinon, g est un pseudo-générateur (car ordre(g)= q ou p-1)

Si tu prends p - 1 = kq
tu sais que l'ordre d'un élément r est un diviseur de p - 1, donc, c'est soit k, soit q puisqu'ils sont premiers par hypothèse. Dans ce cas, il te suffit de tester pow(r,k) et pow(r,q). Si les deux sont différents de 1, tu as bien un générateur. Je ne comprends pas la partie 2 et 3.

De plus, je n'ai pas trouvé de référence sur la notion de "pseudo générateur". Si tu peux, je suis preneur de toute source là dessus.

merci beaucoup