j'implémente le chiffre d'El Gamal, mais dans sa spécification, on
doit (sans que cela ne soit obligatoire) utiliser un élément primitif
alpha appartenant à ZZp* (p étant le nombre premier utilisé dans cet
algorithme).
Je cherche un algorithme concret et efficace (que je peux implémenter)
pour générer un élément primitif valable à partir du nombre p ou pour
tester si un nombre alpha < p - 1 est primitif.
Autremement dit, je cherche un moyen de trouver un générateur de (Zp*,
x).
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
pornin
According to awr :
j'implémente le chiffre d'El Gamal, mais dans sa spécification, on doit (sans que cela ne soit obligatoire) utiliser un élément primitif alpha appartenant à ZZp* (p étant le nombre premier utilisé dans cet algorithme).
En fait, pour obtenir une sécurité correcte, il faut utiliser un élément g tel que si on note r l'ordre du groupe engendré par g, alors r possède au moins un facteur premier q d'au moins 160 bits. La raison en est qu'il existe des attaques génériques sur le logarithme discret dont l'efficacité est proportionnelle à la racine de la taille du plus grand facteur premier de l'ordre du groupe engendré par g. Autrement dit, si g respecte la condition que j'ai énoncée ci-dessus, alors ces algorithmes auront un coût d'au moins 2^80 (la racine carrée de 2^160), donc seront computationnellement infaisables.
Une méthode pour obtenir p et g (et q) tels que décrits ci-dessus est celle du standard de signature DSS (qui n'est, fondamentalement, qu'une variante des signatures El-Gamal). Ce standard est décrit dans FIPS-186-2-change1, et est téléchargeable depuis : http://csrc.nist.gov/publications/fips/
Chose rare pour un standard, il est raisonnablement court et lisible.
Une autre méthode courante est de générer p nombre premier de la forme p = 2 * u + 1 où "u" est un autre nombre premier. Dans ce cas, tout élément "g" modulo p, à part 0, 1 et p-1, engendre un groupe d'ordre u ou 2*u, donc convient pour El-Gamal. En particulier, g = 2 est un générateur correct pour El-Gamal, et permet d'optimiser le calcul.
Générer un tel p peut être un peu coûteux en temps de calcul (pas monumentalement, mais coûteux quand même). On peut réutiliser un "p" existant, de la bonne forme, et déterminé suivant un processus public et vérifiable (pour éviter un "p" "plombé", c'est-à-dire d'une forme particulière qui facilite les attaques). La RFC 2412 contient en annexe de telles valeurs de "p" (dans le cadre du protocole "OAKLEY" mais ça ne change rien ici)(cf http://www.faqs.org/rfcs/rfc2412.html).
--Thomas Pornin
According to awr <arnaud.w@laposte.net>:
j'implémente le chiffre d'El Gamal, mais dans sa spécification, on
doit (sans que cela ne soit obligatoire) utiliser un élément primitif
alpha appartenant à ZZp* (p étant le nombre premier utilisé dans cet
algorithme).
En fait, pour obtenir une sécurité correcte, il faut utiliser un élément
g tel que si on note r l'ordre du groupe engendré par g, alors r possède
au moins un facteur premier q d'au moins 160 bits. La raison en est
qu'il existe des attaques génériques sur le logarithme discret dont
l'efficacité est proportionnelle à la racine de la taille du plus
grand facteur premier de l'ordre du groupe engendré par g. Autrement
dit, si g respecte la condition que j'ai énoncée ci-dessus, alors ces
algorithmes auront un coût d'au moins 2^80 (la racine carrée de 2^160),
donc seront computationnellement infaisables.
Une méthode pour obtenir p et g (et q) tels que décrits ci-dessus est
celle du standard de signature DSS (qui n'est, fondamentalement, qu'une
variante des signatures El-Gamal). Ce standard est décrit dans
FIPS-186-2-change1, et est téléchargeable depuis :
http://csrc.nist.gov/publications/fips/
Chose rare pour un standard, il est raisonnablement court et lisible.
Une autre méthode courante est de générer p nombre premier de la forme
p = 2 * u + 1 où "u" est un autre nombre premier. Dans ce cas, tout
élément "g" modulo p, à part 0, 1 et p-1, engendre un groupe d'ordre
u ou 2*u, donc convient pour El-Gamal. En particulier, g = 2 est un
générateur correct pour El-Gamal, et permet d'optimiser le calcul.
Générer un tel p peut être un peu coûteux en temps de calcul (pas
monumentalement, mais coûteux quand même). On peut réutiliser un "p"
existant, de la bonne forme, et déterminé suivant un processus
public et vérifiable (pour éviter un "p" "plombé", c'est-à-dire d'une
forme particulière qui facilite les attaques). La RFC 2412 contient
en annexe de telles valeurs de "p" (dans le cadre du protocole "OAKLEY"
mais ça ne change rien ici)(cf http://www.faqs.org/rfcs/rfc2412.html).
j'implémente le chiffre d'El Gamal, mais dans sa spécification, on doit (sans que cela ne soit obligatoire) utiliser un élément primitif alpha appartenant à ZZp* (p étant le nombre premier utilisé dans cet algorithme).
En fait, pour obtenir une sécurité correcte, il faut utiliser un élément g tel que si on note r l'ordre du groupe engendré par g, alors r possède au moins un facteur premier q d'au moins 160 bits. La raison en est qu'il existe des attaques génériques sur le logarithme discret dont l'efficacité est proportionnelle à la racine de la taille du plus grand facteur premier de l'ordre du groupe engendré par g. Autrement dit, si g respecte la condition que j'ai énoncée ci-dessus, alors ces algorithmes auront un coût d'au moins 2^80 (la racine carrée de 2^160), donc seront computationnellement infaisables.
Une méthode pour obtenir p et g (et q) tels que décrits ci-dessus est celle du standard de signature DSS (qui n'est, fondamentalement, qu'une variante des signatures El-Gamal). Ce standard est décrit dans FIPS-186-2-change1, et est téléchargeable depuis : http://csrc.nist.gov/publications/fips/
Chose rare pour un standard, il est raisonnablement court et lisible.
Une autre méthode courante est de générer p nombre premier de la forme p = 2 * u + 1 où "u" est un autre nombre premier. Dans ce cas, tout élément "g" modulo p, à part 0, 1 et p-1, engendre un groupe d'ordre u ou 2*u, donc convient pour El-Gamal. En particulier, g = 2 est un générateur correct pour El-Gamal, et permet d'optimiser le calcul.
Générer un tel p peut être un peu coûteux en temps de calcul (pas monumentalement, mais coûteux quand même). On peut réutiliser un "p" existant, de la bonne forme, et déterminé suivant un processus public et vérifiable (pour éviter un "p" "plombé", c'est-à-dire d'une forme particulière qui facilite les attaques). La RFC 2412 contient en annexe de telles valeurs de "p" (dans le cadre du protocole "OAKLEY" mais ça ne change rien ici)(cf http://www.faqs.org/rfcs/rfc2412.html).
--Thomas Pornin
carra_bea
(Thomas Pornin) wrote in message news:<brsm81$1l4g$...
Une autre méthode courante est de générer p nombre premier de la forme p = 2 * u + 1 où "u" est un autre nombre premier. Dans ce cas, tout élément "g" modulo p, à part 0, 1 et p-1, engendre un groupe d'ordre u ou 2*u, donc convient pour El-Gamal. En particulier, g = 2 est un générateur correct pour El-Gamal, et permet d'optimiser le calcul.
je ne suis pas sur de bien comprendre l'avantage de cette méthode car
il y a une autre attaque sur le log discret sur Zp qui fait que p doit être aussi grand (environ 1024 bits), il ne suffit pas que p-1 possède un grand facteur premier de taille 160. Donc fabriquer p de la forme 2u+1 revient à avoir un u de taille 1023 ......... Un autre soucis je prend u=7 2u+1 n'est pas pemier ........
pornin@nerim.net (Thomas Pornin) wrote in message news:<brsm81$1l4g$1@biggoron.nerim.net>...
Une autre méthode courante est de générer p nombre premier de la forme
p = 2 * u + 1 où "u" est un autre nombre premier. Dans ce cas, tout
élément "g" modulo p, à part 0, 1 et p-1, engendre un groupe d'ordre
u ou 2*u, donc convient pour El-Gamal. En particulier, g = 2 est un
générateur correct pour El-Gamal, et permet d'optimiser le calcul.
je ne suis pas sur de bien comprendre l'avantage de cette méthode car
il y a une autre attaque sur le log discret sur Zp qui fait que p doit
être aussi grand (environ 1024 bits), il ne suffit pas que p-1 possède
un grand facteur premier de taille 160. Donc fabriquer p de la forme
2u+1 revient à avoir un u de taille 1023 .........
Un autre soucis je prend u=7 2u+1 n'est pas pemier ........
(Thomas Pornin) wrote in message news:<brsm81$1l4g$...
Une autre méthode courante est de générer p nombre premier de la forme p = 2 * u + 1 où "u" est un autre nombre premier. Dans ce cas, tout élément "g" modulo p, à part 0, 1 et p-1, engendre un groupe d'ordre u ou 2*u, donc convient pour El-Gamal. En particulier, g = 2 est un générateur correct pour El-Gamal, et permet d'optimiser le calcul.
je ne suis pas sur de bien comprendre l'avantage de cette méthode car
il y a une autre attaque sur le log discret sur Zp qui fait que p doit être aussi grand (environ 1024 bits), il ne suffit pas que p-1 possède un grand facteur premier de taille 160. Donc fabriquer p de la forme 2u+1 revient à avoir un u de taille 1023 ......... Un autre soucis je prend u=7 2u+1 n'est pas pemier ........
pornin
According to betty :
(Thomas Pornin) wrote in message news:<brsm81$1l4g$...
Une autre méthode courante est de générer p nombre premier de la forme p = 2 * u + 1 où "u" est un autre nombre premier. Dans ce cas, tout élément "g" modulo p, à part 0, 1 et p-1, engendre un groupe d'ordre u ou 2*u, donc convient pour El-Gamal. En particulier, g = 2 est un générateur correct pour El-Gamal, et permet d'optimiser le calcul.
je ne suis pas sur de bien comprendre l'avantage de cette méthode car
il y a une autre attaque sur le log discret sur Zp qui fait que p doit être aussi grand (environ 1024 bits), il ne suffit pas que p-1 possède un grand facteur premier de taille 160.
J'ai écrit : "Une _autre_ méthode". Ce n'est pas le même p. Il faut choisir : soit on prend un p tel que q est premier, q divise p-1 et q fait 160 bits, soit on prend un p tel que (p-1)/2 est premier. Le premier cas est celui de DSS, et FIPS 186-2-Change1 décrit une méthode pour obtenir de tels paramètres, notamment le générateur g. Le second cas permet d'utiliser g=2, ce qui fournit des calculs plus efficaces, mais le choix de p est plus coûteux en temps de calcul.
Donc fabriquer p de la forme 2u+1 revient à avoir un u de taille 1023 ......... Un autre soucis je prend u=7 2u+1 n'est pas pemier ........
Ben oui, ça ne marche pas toujours. La façon standard de faire est de : 1. choisir un u de 1023 bits, impair 2. si u n'est pas premier, revenir en 1 3. si 2u+1 n'est pas premier, revenir en 1
À la louche, on va essayer dans les 500000 nombres "u" impairs avant d'en trouver un qui marche. Avec un bon PC et un bon programme, ce sera fait en moins d'une heure. On peut optimiser ça de diverses manières. Mais c'est quand même beaucoup, aussi on préfère souvent utiliser des paramètres existants, tels ceux du protocole OAKLEY. Je rappelle que pour faire du Diffie-Hellman ou du El-Gamal, il n'y a aucun problème à utiliser les mêmes paramètres pour plusieurs paires de clés.
--Thomas Pornin
According to betty <carra_bea@yahoo.fr>:
pornin@nerim.net (Thomas Pornin) wrote in message
news:<brsm81$1l4g$1@biggoron.nerim.net>...
Une autre méthode courante est de générer p nombre premier de la forme
p = 2 * u + 1 où "u" est un autre nombre premier. Dans ce cas, tout
élément "g" modulo p, à part 0, 1 et p-1, engendre un groupe d'ordre
u ou 2*u, donc convient pour El-Gamal. En particulier, g = 2 est un
générateur correct pour El-Gamal, et permet d'optimiser le calcul.
je ne suis pas sur de bien comprendre l'avantage de cette méthode car
il y a une autre attaque sur le log discret sur Zp qui fait que p doit
être aussi grand (environ 1024 bits), il ne suffit pas que p-1 possède
un grand facteur premier de taille 160.
J'ai écrit : "Une _autre_ méthode". Ce n'est pas le même p. Il faut
choisir : soit on prend un p tel que q est premier, q divise p-1 et
q fait 160 bits, soit on prend un p tel que (p-1)/2 est premier. Le
premier cas est celui de DSS, et FIPS 186-2-Change1 décrit une méthode
pour obtenir de tels paramètres, notamment le générateur g. Le second
cas permet d'utiliser g=2, ce qui fournit des calculs plus efficaces,
mais le choix de p est plus coûteux en temps de calcul.
Donc fabriquer p de la forme 2u+1 revient à avoir un u de taille 1023
.........
Un autre soucis je prend u=7 2u+1 n'est pas pemier ........
Ben oui, ça ne marche pas toujours. La façon standard de faire est de :
1. choisir un u de 1023 bits, impair
2. si u n'est pas premier, revenir en 1
3. si 2u+1 n'est pas premier, revenir en 1
À la louche, on va essayer dans les 500000 nombres "u" impairs avant
d'en trouver un qui marche. Avec un bon PC et un bon programme, ce sera
fait en moins d'une heure. On peut optimiser ça de diverses manières.
Mais c'est quand même beaucoup, aussi on préfère souvent utiliser des
paramètres existants, tels ceux du protocole OAKLEY. Je rappelle que
pour faire du Diffie-Hellman ou du El-Gamal, il n'y a aucun problème à
utiliser les mêmes paramètres pour plusieurs paires de clés.
(Thomas Pornin) wrote in message news:<brsm81$1l4g$...
Une autre méthode courante est de générer p nombre premier de la forme p = 2 * u + 1 où "u" est un autre nombre premier. Dans ce cas, tout élément "g" modulo p, à part 0, 1 et p-1, engendre un groupe d'ordre u ou 2*u, donc convient pour El-Gamal. En particulier, g = 2 est un générateur correct pour El-Gamal, et permet d'optimiser le calcul.
je ne suis pas sur de bien comprendre l'avantage de cette méthode car
il y a une autre attaque sur le log discret sur Zp qui fait que p doit être aussi grand (environ 1024 bits), il ne suffit pas que p-1 possède un grand facteur premier de taille 160.
J'ai écrit : "Une _autre_ méthode". Ce n'est pas le même p. Il faut choisir : soit on prend un p tel que q est premier, q divise p-1 et q fait 160 bits, soit on prend un p tel que (p-1)/2 est premier. Le premier cas est celui de DSS, et FIPS 186-2-Change1 décrit une méthode pour obtenir de tels paramètres, notamment le générateur g. Le second cas permet d'utiliser g=2, ce qui fournit des calculs plus efficaces, mais le choix de p est plus coûteux en temps de calcul.
Donc fabriquer p de la forme 2u+1 revient à avoir un u de taille 1023 ......... Un autre soucis je prend u=7 2u+1 n'est pas pemier ........
Ben oui, ça ne marche pas toujours. La façon standard de faire est de : 1. choisir un u de 1023 bits, impair 2. si u n'est pas premier, revenir en 1 3. si 2u+1 n'est pas premier, revenir en 1
À la louche, on va essayer dans les 500000 nombres "u" impairs avant d'en trouver un qui marche. Avec un bon PC et un bon programme, ce sera fait en moins d'une heure. On peut optimiser ça de diverses manières. Mais c'est quand même beaucoup, aussi on préfère souvent utiliser des paramètres existants, tels ceux du protocole OAKLEY. Je rappelle que pour faire du Diffie-Hellman ou du El-Gamal, il n'y a aucun problème à utiliser les mêmes paramètres pour plusieurs paires de clés.
--Thomas Pornin
carra_bea
Ben oui, ça ne marche pas toujours. La façon standard de faire est de : 1. choisir un u de 1023 bits, impair 2. si u n'est pas premier, revenir en 1 pour être bien sur d'avoir tout saisie, nous sommes bien d'accord que pour
des entiers de cette taille là, on ne peut se contenter que d'un test de primalité probabiliste pour vérifier la primalité de u ??
Ben oui, ça ne marche pas toujours. La façon standard de faire est de :
1. choisir un u de 1023 bits, impair
2. si u n'est pas premier, revenir en 1
pour être bien sur d'avoir tout saisie, nous sommes bien d'accord que pour
des entiers de cette taille là, on ne peut se contenter que d'un test de primalité
probabiliste pour vérifier la primalité de u ??
Ben oui, ça ne marche pas toujours. La façon standard de faire est de : 1. choisir un u de 1023 bits, impair 2. si u n'est pas premier, revenir en 1 pour être bien sur d'avoir tout saisie, nous sommes bien d'accord que pour
des entiers de cette taille là, on ne peut se contenter que d'un test de primalité probabiliste pour vérifier la primalité de u ??
pornin
According to betty :
pour être bien sur d'avoir tout saisi, nous sommes bien d'accord que pour des entiers de cette taille là, on ne peut se contenter que d'un test de primalité probabiliste pour vérifier la primalité de u ??
L'usage courant est d'utiliser un test probabiliste parce que ça va beaucoup plus vite et c'est plus simple à implémenter que les tests non-probabilistes. On veut aller vite dans notre cas, parce qu'on va tester beaucoup de valeurs "u" de 1023 bits avant d'en trouver une qui soit première, et telle que p=2*u+1 soit également un nombre premier.
Maintenant, un test probabiliste, c'est très bien quand même. Le test classique (Miller-Rabin) a un risque de déclarer premier un nombre qui ne l'est pas d'environ 25% au plus, à chaque passe. En appliquant 50 fois le test, le risque de déclarer premier un nombre qui ne l'est pas est inférieur à 2^(-100), c'est-à-dire nettement inférieur à la probabilité que l'ordinateur utilisé pour faire les calculs ait eu des vapeurs à ce moment-là (un rayon cosmique qui passe, et hop, un bit en mémoire qui passe spontanément de 0 à 1). C'est donc plus que suffisant.
Si malgré tout, le fait d'avoir seulement un test probabiliste vous empêche de dormir, vous pouvez toujours sélectionner p avec un test probabiliste (mais rapide), puis, une fois p trouvé, vérifier avec un test non-probabiliste que p et (p-1)/2 sont bien des nombres premiers. Il existe des tests non-probabilistes qui ont un temps d'exécution "acceptable" pour des nombres de 1024 bits.
--Thomas Pornin
According to betty <carra_bea@yahoo.fr>:
pour être bien sur d'avoir tout saisi, nous sommes bien d'accord que
pour des entiers de cette taille là, on ne peut se contenter que d'un
test de primalité probabiliste pour vérifier la primalité de u ??
L'usage courant est d'utiliser un test probabiliste parce que ça va
beaucoup plus vite et c'est plus simple à implémenter que les tests
non-probabilistes. On veut aller vite dans notre cas, parce qu'on va
tester beaucoup de valeurs "u" de 1023 bits avant d'en trouver une qui
soit première, et telle que p=2*u+1 soit également un nombre premier.
Maintenant, un test probabiliste, c'est très bien quand même. Le test
classique (Miller-Rabin) a un risque de déclarer premier un nombre
qui ne l'est pas d'environ 25% au plus, à chaque passe. En appliquant
50 fois le test, le risque de déclarer premier un nombre qui ne l'est
pas est inférieur à 2^(-100), c'est-à-dire nettement inférieur à la
probabilité que l'ordinateur utilisé pour faire les calculs ait eu des
vapeurs à ce moment-là (un rayon cosmique qui passe, et hop, un bit en
mémoire qui passe spontanément de 0 à 1). C'est donc plus que suffisant.
Si malgré tout, le fait d'avoir seulement un test probabiliste vous
empêche de dormir, vous pouvez toujours sélectionner p avec un test
probabiliste (mais rapide), puis, une fois p trouvé, vérifier avec un
test non-probabiliste que p et (p-1)/2 sont bien des nombres premiers.
Il existe des tests non-probabilistes qui ont un temps d'exécution
"acceptable" pour des nombres de 1024 bits.
pour être bien sur d'avoir tout saisi, nous sommes bien d'accord que pour des entiers de cette taille là, on ne peut se contenter que d'un test de primalité probabiliste pour vérifier la primalité de u ??
L'usage courant est d'utiliser un test probabiliste parce que ça va beaucoup plus vite et c'est plus simple à implémenter que les tests non-probabilistes. On veut aller vite dans notre cas, parce qu'on va tester beaucoup de valeurs "u" de 1023 bits avant d'en trouver une qui soit première, et telle que p=2*u+1 soit également un nombre premier.
Maintenant, un test probabiliste, c'est très bien quand même. Le test classique (Miller-Rabin) a un risque de déclarer premier un nombre qui ne l'est pas d'environ 25% au plus, à chaque passe. En appliquant 50 fois le test, le risque de déclarer premier un nombre qui ne l'est pas est inférieur à 2^(-100), c'est-à-dire nettement inférieur à la probabilité que l'ordinateur utilisé pour faire les calculs ait eu des vapeurs à ce moment-là (un rayon cosmique qui passe, et hop, un bit en mémoire qui passe spontanément de 0 à 1). C'est donc plus que suffisant.
Si malgré tout, le fait d'avoir seulement un test probabiliste vous empêche de dormir, vous pouvez toujours sélectionner p avec un test probabiliste (mais rapide), puis, une fois p trouvé, vérifier avec un test non-probabiliste que p et (p-1)/2 sont bien des nombres premiers. Il existe des tests non-probabilistes qui ont un temps d'exécution "acceptable" pour des nombres de 1024 bits.
--Thomas Pornin
macron
Le jeudi 18 Décembre 2003 à 14:06 par arnaud.w :
Bonjour, j'implémente le chiffre d'El Gamal, mais dans sa spécification, on doit (sans que cela ne soit obligatoire) utiliser un élément primitif alpha appartenant à ZZp* (p étant le nombre premier utilisé dans cet algorithme). Je cherche un algorithme concret et efficace (que je peux implémenter) pour générer un élément primitif valable à partir du nombre p ou pour tester si un nombre alpha < p - 1 est primitif. Autremement dit, je cherche un moyen de trouver un générateur de (Zp*, x). Merci d'avance.
Pourquoi ne peut-on pas faire encore plus simple : On cherche p premier de L bits et g un générateur de (Z/pZ)* 1) Trouver e et d premiers de L/2 bits 2) Regarder si p = 2*e*d + 1 est premier Si non, retourner à l'étape 1) Si oui, garder p. 3) Pour tester si un élément g de (Z/pZ)* est générateur, il suffit alors de vérifier que : g^(e*d), g^(2*e) et g^(2*d) sont différents de 1. Le nombre de générateurs est phi(p-1) = (e-1)*(d-1), donc on a une probabilité d'environ 1/2 de trouver un générateur à chaque essai. Si je ne me trompe pas, avec cette méthode on a un VRAI générateur, et non un "pseudo-générateur" d'un ordre 'assez grand" comme dans DSS. De plus cette méthode m'a l'air à peu près aussi peu coûteuse que celle du standard DSS. (J'ai testé avec LQ2 bits, c'est même plus rapide que DSS).
Le jeudi 18 Décembre 2003 à 14:06 par arnaud.w :
> Bonjour,
>
> j'implémente le chiffre d'El Gamal, mais dans sa spécification,
> on
> doit (sans que cela ne soit obligatoire) utiliser un élément
> primitif
> alpha appartenant à ZZp* (p étant le nombre premier
> utilisé dans cet
> algorithme).
>
> Je cherche un algorithme concret et efficace (que je peux implémenter)
> pour générer un élément primitif valable à
> partir du nombre p ou pour
> tester si un nombre alpha < p - 1 est primitif.
>
> Autremement dit, je cherche un moyen de trouver un générateur de
> (Zp*,
> x).
>
> Merci d'avance.
Pourquoi ne peut-on pas faire encore plus simple :
On cherche p premier de L bits et g un générateur de (Z/pZ)*
1) Trouver e et d premiers de L/2 bits
2) Regarder si p = 2*e*d + 1 est premier
Si non, retourner à l'étape 1)
Si oui, garder p.
3) Pour tester si un élément g de (Z/pZ)* est générateur, il suffit alors de vérifier que :
g^(e*d), g^(2*e) et g^(2*d) sont différents de 1.
Le nombre de générateurs est phi(p-1) = (e-1)*(d-1), donc on a une probabilité d'environ 1/2 de trouver un générateur à chaque essai.
Si je ne me trompe pas, avec cette méthode on a un VRAI générateur, et non un "pseudo-générateur" d'un ordre 'assez grand" comme dans DSS.
De plus cette méthode m'a l'air à peu près aussi peu coûteuse que celle du standard DSS.
(J'ai testé avec L=512 bits, c'est même plus rapide que DSS).
Bonjour, j'implémente le chiffre d'El Gamal, mais dans sa spécification, on doit (sans que cela ne soit obligatoire) utiliser un élément primitif alpha appartenant à ZZp* (p étant le nombre premier utilisé dans cet algorithme). Je cherche un algorithme concret et efficace (que je peux implémenter) pour générer un élément primitif valable à partir du nombre p ou pour tester si un nombre alpha < p - 1 est primitif. Autremement dit, je cherche un moyen de trouver un générateur de (Zp*, x). Merci d'avance.
Pourquoi ne peut-on pas faire encore plus simple : On cherche p premier de L bits et g un générateur de (Z/pZ)* 1) Trouver e et d premiers de L/2 bits 2) Regarder si p = 2*e*d + 1 est premier Si non, retourner à l'étape 1) Si oui, garder p. 3) Pour tester si un élément g de (Z/pZ)* est générateur, il suffit alors de vérifier que : g^(e*d), g^(2*e) et g^(2*d) sont différents de 1. Le nombre de générateurs est phi(p-1) = (e-1)*(d-1), donc on a une probabilité d'environ 1/2 de trouver un générateur à chaque essai. Si je ne me trompe pas, avec cette méthode on a un VRAI générateur, et non un "pseudo-générateur" d'un ordre 'assez grand" comme dans DSS. De plus cette méthode m'a l'air à peu près aussi peu coûteuse que celle du standard DSS. (J'ai testé avec LQ2 bits, c'est même plus rapide que DSS).
