Vous devez être connecté afin d'accéder à ce service
temps d'exécution du AES et du RSA
38 réponses
kabina
Bonjour,
j'ai calculé les différents temps d'exécution des algorithmes AES et RSA et voici ce que j'ai obtenu:
AES 128 bits de clé, 2,58 Mo de fichier à chiffrer avec un temps de 203 ms
AES 128 bits de clé, 9,16 Mo de fichier à chiffrer avec un temps de 500 ms et RAM utilisé 21695k
RSA 2048 bits de clé, 2,58 Mo de fichier à chiffrer avec un temps de 21621 ms et RAM 8590 k
RSA 2048 bits de clé, 9,16 Mo de fichier à chiffrer avec un temps de 74583 ms et RAM 22665 k
notez que je calcule juste le temps de l'opération de chiffrement et pas les entrées/sorties(lecture du fichier à chiffré et enregistrement du fichier chiffré) ni la récupération des certificat .cer et .p12 (clé publique et clé privée)
ce n'est pas dur, mais c'est loin d'être appliqué "dans la vraie vie".
Certes, mais je le déplorais à haute voix.
la génération de e prend un temps nul, la vérification de sa primalité prend un temps non négligeable devant les tests sur p et q qui de longueur moitié sont testé plus rapidement.
On n'a pas besoin de e premier, juste de e premier à phi(N); la probabilité est phi(phi(N))/phi(N), fois 2 si on génère des nombres impairs. C'est typiquement assez proche de 1, et demande juste de savoir calculer un pgcd.
e petit est "selon toute vraisemblance" un risque permettant de forger "plus facilement" des signatures, je vois moins où c'est génant pour du wrapping.
Pourtant, il y a plutôt plus d'attaques sur le chiffrement RSA à e petit que sur la signature.
parles-tu de "Realizing Hash-n-Sign Signatures under Std Assumptions" ?
Oui, et du follow-up qui vient de faire surface sur ePrint.
Sylvain SF wrote in message <4a36aa33$0$17746$ba4acef3@news.orange.fr>:
ce n'est pas dur, mais c'est loin d'être appliqué "dans la vraie vie".
Certes, mais je le déplorais à haute voix.
la génération de e prend un temps nul, la vérification de sa primalité
prend un temps non négligeable devant les tests sur p et q qui de
longueur moitié sont testé plus rapidement.
On n'a pas besoin de e premier, juste de e premier à phi(N); la
probabilité est phi(phi(N))/phi(N), fois 2 si on génère des nombres
impairs. C'est typiquement assez proche de 1, et demande juste de savoir
calculer un pgcd.
e petit est "selon toute vraisemblance" un risque permettant de forger
"plus facilement" des signatures, je vois moins où c'est génant pour
du wrapping.
Pourtant, il y a plutôt plus d'attaques sur le chiffrement RSA à e petit
que sur la signature.
parles-tu de "Realizing Hash-n-Sign Signatures under Std Assumptions" ?
Oui, et du follow-up qui vient de faire surface sur ePrint.
ce n'est pas dur, mais c'est loin d'être appliqué "dans la vraie vie".
Certes, mais je le déplorais à haute voix.
la génération de e prend un temps nul, la vérification de sa primalité prend un temps non négligeable devant les tests sur p et q qui de longueur moitié sont testé plus rapidement.
On n'a pas besoin de e premier, juste de e premier à phi(N); la probabilité est phi(phi(N))/phi(N), fois 2 si on génère des nombres impairs. C'est typiquement assez proche de 1, et demande juste de savoir calculer un pgcd.
e petit est "selon toute vraisemblance" un risque permettant de forger "plus facilement" des signatures, je vois moins où c'est génant pour du wrapping.
Pourtant, il y a plutôt plus d'attaques sur le chiffrement RSA à e petit que sur la signature.
parles-tu de "Realizing Hash-n-Sign Signatures under Std Assumptions" ?
Oui, et du follow-up qui vient de faire surface sur ePrint.
Erwan David
Mehdi Tibouchi écrivait :
Erwan David wrote in message :
Ça facilite l'implémentation des reste chinois... J'ai vu les même contraintes sur des crypto-processeurs embarqués (sur carte à puce ou terminaux de paiement).
Argh, des restes chinois dans de l'embarqué ? Et les attaques par fautes ?
Il suffit de ne pas l'utiliser... Mais les contraintes restent là.
-- Le travail n'est pas une bonne chose. Si ça l'était, les riches l'auraient accaparé
Mehdi Tibouchi <medtib@alussinan.org> écrivait :
Erwan David wrote in message
<m2ski04uz3.fsf@minuetto.depot.rail.eu.org>:
Ça facilite l'implémentation des reste chinois... J'ai vu les même
contraintes sur des crypto-processeurs embarqués (sur carte à puce ou
terminaux de paiement).
Argh, des restes chinois dans de l'embarqué ? Et les attaques par
fautes ?
Il suffit de ne pas l'utiliser... Mais les contraintes restent là.
--
Le travail n'est pas une bonne chose. Si ça l'était,
les riches l'auraient accaparé
Ça facilite l'implémentation des reste chinois... J'ai vu les même contraintes sur des crypto-processeurs embarqués (sur carte à puce ou terminaux de paiement).
Argh, des restes chinois dans de l'embarqué ? Et les attaques par fautes ?
Il suffit de ne pas l'utiliser... Mais les contraintes restent là.
-- Le travail n'est pas une bonne chose. Si ça l'était, les riches l'auraient accaparé
remy
Mehdi Tibouchi a écrit :
Erwan David wrote in message :
Ça facilite l'implémentation des reste chinois... J'ai vu les même contraintes sur des crypto-processeurs embarqués (sur carte à puce ou terminaux de paiement).
Argh, des restes chinois dans de l'embarqué ? Et les attaques par fautes ?
il parle de la perturbation de l'autentification sous forme de TD voir td6-rsa.pdf sinon il y a un superbe cours sur les cordes
remy
-- http://remyaumeunier.chez-alice.fr/
Mehdi Tibouchi a écrit :
Erwan David wrote in message
<m2ski04uz3.fsf@minuetto.depot.rail.eu.org>:
Ça facilite l'implémentation des reste chinois... J'ai vu les même
contraintes sur des crypto-processeurs embarqués (sur carte à puce ou
terminaux de paiement).
Argh, des restes chinois dans de l'embarqué ? Et les attaques par
fautes ?
Ça facilite l'implémentation des reste chinois... J'ai vu les même contraintes sur des crypto-processeurs embarqués (sur carte à puce ou terminaux de paiement).
Argh, des restes chinois dans de l'embarqué ? Et les attaques par fautes ?
il parle de la perturbation de l'autentification sous forme de TD voir td6-rsa.pdf sinon il y a un superbe cours sur les cordes
remy
-- http://remyaumeunier.chez-alice.fr/
remy
Mehdi Tibouchi a écrit :
Erwan David wrote in message :
Ça facilite l'implémentation des reste chinois... J'ai vu les même contraintes sur des crypto-processeurs embarqués (sur carte à puce ou terminaux de paiement).
Argh, des restes chinois dans de l'embarqué ? Et les attaques par fautes ?
il parle de la perturbation de l'autentification sous forme de TD voir td6-rsa.pdf sinon il y a un superbe cours sur les codes
remy
-- http://remyaumeunier.chez-alice.fr/
-- http://remyaumeunier.chez-alice.fr/
Mehdi Tibouchi a écrit :
Erwan David wrote in message
<m2ski04uz3.fsf@minuetto.depot.rail.eu.org>:
Ça facilite l'implémentation des reste chinois... J'ai vu les même
contraintes sur des crypto-processeurs embarqués (sur carte à puce ou
terminaux de paiement).
Argh, des restes chinois dans de l'embarqué ? Et les attaques par
fautes ?
Ça facilite l'implémentation des reste chinois... J'ai vu les même contraintes sur des crypto-processeurs embarqués (sur carte à puce ou terminaux de paiement).
Argh, des restes chinois dans de l'embarqué ? Et les attaques par fautes ?
il parle de la perturbation de l'autentification sous forme de TD voir td6-rsa.pdf sinon il y a un superbe cours sur les codes
remy
-- http://remyaumeunier.chez-alice.fr/
-- http://remyaumeunier.chez-alice.fr/
Thomas Pornin
According to Mehdi Tibouchi :
Argh, des restes chinois dans de l'embarqué ?
L'embarqué est souvent pauvre en puissance de calcul, et les restes chinois permettent un x4 sur la vitesse, ce qui ne se méprise pas.
Et les attaques par fautes ?
De ce que j'ai cru observer, la tendance générale de la pratique industrielle, face aux attaques à composante matérielle (comme les attaques par faute, mais aussi la DPA), est de les contrer avec du matériel (blindage physique et électromagnétique, détecteurs divers de conditions anormales,...). Ce sont surtout les attaques par chronométrage ("timing attacks") qui font peur parce que ça fait intervenir une mesure passive de l'extérieur, mais dans le cas de RSA, un masquage semble assez efficace, aussi bien en termes de protection que de temps de calcul (on sélectionne r aléatoire, on multiplie par r^e en entrée, on divise par r en sortie).
Dans certains domaines (par exemple, les cartes à puce pour décodeurs de télévision satellite), la cible de sécurité n'est pas une robustesse absolue, mais juste une robustesse suffisante pour limiter le nombre d'attaquants potentiels à des taux accessibles aux techniques classiques et non-informatiques de police.
--Thomas Pornin
According to Mehdi Tibouchi <medtib@alussinan.org>:
Argh, des restes chinois dans de l'embarqué ?
L'embarqué est souvent pauvre en puissance de calcul, et les restes
chinois permettent un x4 sur la vitesse, ce qui ne se méprise pas.
Et les attaques par fautes ?
De ce que j'ai cru observer, la tendance générale de la pratique
industrielle, face aux attaques à composante matérielle (comme les
attaques par faute, mais aussi la DPA), est de les contrer avec du
matériel (blindage physique et électromagnétique, détecteurs divers de
conditions anormales,...). Ce sont surtout les attaques par
chronométrage ("timing attacks") qui font peur parce que ça fait
intervenir une mesure passive de l'extérieur, mais dans le cas de RSA,
un masquage semble assez efficace, aussi bien en termes de protection
que de temps de calcul (on sélectionne r aléatoire, on multiplie par r^e
en entrée, on divise par r en sortie).
Dans certains domaines (par exemple, les cartes à puce pour décodeurs de
télévision satellite), la cible de sécurité n'est pas une robustesse
absolue, mais juste une robustesse suffisante pour limiter le nombre
d'attaquants potentiels à des taux accessibles aux techniques classiques
et non-informatiques de police.
L'embarqué est souvent pauvre en puissance de calcul, et les restes chinois permettent un x4 sur la vitesse, ce qui ne se méprise pas.
Et les attaques par fautes ?
De ce que j'ai cru observer, la tendance générale de la pratique industrielle, face aux attaques à composante matérielle (comme les attaques par faute, mais aussi la DPA), est de les contrer avec du matériel (blindage physique et électromagnétique, détecteurs divers de conditions anormales,...). Ce sont surtout les attaques par chronométrage ("timing attacks") qui font peur parce que ça fait intervenir une mesure passive de l'extérieur, mais dans le cas de RSA, un masquage semble assez efficace, aussi bien en termes de protection que de temps de calcul (on sélectionne r aléatoire, on multiplie par r^e en entrée, on divise par r en sortie).
Dans certains domaines (par exemple, les cartes à puce pour décodeurs de télévision satellite), la cible de sécurité n'est pas une robustesse absolue, mais juste une robustesse suffisante pour limiter le nombre d'attaquants potentiels à des taux accessibles aux techniques classiques et non-informatiques de police.
--Thomas Pornin
Thomas Pornin
According to Sylvain SF :
la génération de e prend un temps nul, la vérification de sa primalité prend un temps non négligeable devant les tests sur p et q qui de longueur moitié sont testé plus rapidement.
Si on s'y prend bien, la vérification que e est premier avec p-1 et q-1 prend un temps _vraiment_ nul (plutôt que négligeable). En effet, la méthode de base pour générer un nombre premier p est de tirer des nombres aléatoires, de tester la primalité du résultat, et de recommencer tant qu'on n'a pas un nombre premier.
Maintenant, on a un cerveau et on sait s'en servir, donc on se dit que le nombre premier p sera forcément impair, donc autant s'arranger pour que le bit de poids faible vaille 1. Ça divise par deux le nombre moyen de tirages qu'il faut faire.
Ensuite, on continue à se servir du même cerveau, donc on se dit : en fait, en choisissant des candidats seulement impairs, ce qu'on fait, c'est décider _a priori_ que p = 1 mod 2 et de ne choisir des candidats vérifiant cette égalité. Le même processus devrait être extensible à d'autres petits nombres premiers comme 3, 5, 7, 11... Quand on choisit des nombres impairs aléatoire, une fois sur 3 on tombe sur un multiple de 3, une fois sur 5 sur un multiple de 5, etc, et on voudrait éviter ces candidats qui nous font faire des tests de primalité pour rien.
Donc on commence par sélectionner a priori, et aléatoirement, ce que vaudra notre futur p modulo 2, 3, 5, 7, 11... en choisissant forcément des valeurs non nulles à chaque fois. Par exemple, on sélectionne ceci :
p = 1 mod 2 p = 2 mod 3 p = 1 mod 5 p = 4 mod 7 p = 8 mod 11
Par les restes chinois, ça nous apprend que les candidats que nous chercherons seront égaux à 1691 mod 2310 (2310 = 2*3*5*7*11). On sélection chaque candidat en tirant un nombre aléatoire t entre 2^511/2310 et 2^512/2310 (si on vise un nombre premier de 512 bits), et le candidat est t*2310+1691, qui, par construction, respecte nos modulos exposés ci-dessus. Cette méthode s'assure que l'on évite les faux candidats "triviaux", ceux qui sont divisible par un petit nombre premier. On peut montrer qu'environ 79.2% des entiers choisis aléatoirement seront divisibles par 2, 3, 5, 7 ou 11 ; donc cette méthode élimine 4 faux candidats sur 5, là où simplement fixer le bit de poids faible à 1 n'en vire qu'un sur deux: d'où une accélération d'un facteur 2.5...
Dans la pratique, on ne s'arrête pas à 11, on va jusqu'a 23, parce que 2*3*5*7*11*13*17*19*23 = 223092870, ce qui tient encore sur 32 bits. En allant jusqu'à 23, on vire 83.6% des faux candidats (donc une génération trois fois plus rapide que si on se contentait de fixer le bit à 1).
Maintenant qu'on a cette méthode, qu'on veut utiliser pour des raisons de performance, on peut se dire : voyons, on veut p premier, mais on peut aussi que p-1 et e n'aient pas de facteur commun. On pourrait choisir, a priori, que e = 3, et le problème devient alors : on veut que le p choisi soit différent de 1 modulo 3. Or, justement, la méthode de sélection commence par choisir ce que vaudra p modulo certains nombres, dont 3. Il suffit de forcer p = 2 mod 3 dans la méthode ci-dessus pour avoir la garantie que tous les candidats sélectionnés seront non seulement non divisibles par 3, mais également adéquats pour un RSA avec e = 3 comme exposant public. Le coût de la sélection de l'exposant public devient nul.
--Thomas Pornin
According to Sylvain SF <sylvain@boiteaspam.info>:
la génération de e prend un temps nul, la vérification de sa primalité
prend un temps non négligeable devant les tests sur p et q qui de
longueur moitié sont testé plus rapidement.
Si on s'y prend bien, la vérification que e est premier avec p-1 et q-1
prend un temps _vraiment_ nul (plutôt que négligeable). En effet, la
méthode de base pour générer un nombre premier p est de tirer des
nombres aléatoires, de tester la primalité du résultat, et de
recommencer tant qu'on n'a pas un nombre premier.
Maintenant, on a un cerveau et on sait s'en servir, donc on se dit que
le nombre premier p sera forcément impair, donc autant s'arranger pour
que le bit de poids faible vaille 1. Ça divise par deux le nombre moyen
de tirages qu'il faut faire.
Ensuite, on continue à se servir du même cerveau, donc on se dit : en
fait, en choisissant des candidats seulement impairs, ce qu'on fait,
c'est décider _a priori_ que p = 1 mod 2 et de ne choisir des candidats
vérifiant cette égalité. Le même processus devrait être extensible à
d'autres petits nombres premiers comme 3, 5, 7, 11... Quand on choisit
des nombres impairs aléatoire, une fois sur 3 on tombe sur un multiple
de 3, une fois sur 5 sur un multiple de 5, etc, et on voudrait éviter
ces candidats qui nous font faire des tests de primalité pour rien.
Donc on commence par sélectionner a priori, et aléatoirement, ce que
vaudra notre futur p modulo 2, 3, 5, 7, 11... en choisissant forcément
des valeurs non nulles à chaque fois. Par exemple, on sélectionne ceci :
p = 1 mod 2
p = 2 mod 3
p = 1 mod 5
p = 4 mod 7
p = 8 mod 11
Par les restes chinois, ça nous apprend que les candidats que nous
chercherons seront égaux à 1691 mod 2310 (2310 = 2*3*5*7*11). On
sélection chaque candidat en tirant un nombre aléatoire t entre
2^511/2310 et 2^512/2310 (si on vise un nombre premier de 512 bits), et
le candidat est t*2310+1691, qui, par construction, respecte nos modulos
exposés ci-dessus. Cette méthode s'assure que l'on évite les faux
candidats "triviaux", ceux qui sont divisible par un petit nombre
premier. On peut montrer qu'environ 79.2% des entiers choisis
aléatoirement seront divisibles par 2, 3, 5, 7 ou 11 ; donc cette
méthode élimine 4 faux candidats sur 5, là où simplement fixer le bit de
poids faible à 1 n'en vire qu'un sur deux: d'où une accélération d'un
facteur 2.5...
Dans la pratique, on ne s'arrête pas à 11, on va jusqu'a 23, parce que
2*3*5*7*11*13*17*19*23 = 223092870, ce qui tient encore sur 32 bits. En
allant jusqu'à 23, on vire 83.6% des faux candidats (donc une génération
trois fois plus rapide que si on se contentait de fixer le bit à 1).
Maintenant qu'on a cette méthode, qu'on veut utiliser pour des raisons
de performance, on peut se dire : voyons, on veut p premier, mais on
peut aussi que p-1 et e n'aient pas de facteur commun. On pourrait
choisir, a priori, que e = 3, et le problème devient alors : on veut que
le p choisi soit différent de 1 modulo 3. Or, justement, la méthode de
sélection commence par choisir ce que vaudra p modulo certains nombres,
dont 3. Il suffit de forcer p = 2 mod 3 dans la méthode ci-dessus pour
avoir la garantie que tous les candidats sélectionnés seront non
seulement non divisibles par 3, mais également adéquats pour un RSA avec
e = 3 comme exposant public. Le coût de la sélection de l'exposant
public devient nul.
la génération de e prend un temps nul, la vérification de sa primalité prend un temps non négligeable devant les tests sur p et q qui de longueur moitié sont testé plus rapidement.
Si on s'y prend bien, la vérification que e est premier avec p-1 et q-1 prend un temps _vraiment_ nul (plutôt que négligeable). En effet, la méthode de base pour générer un nombre premier p est de tirer des nombres aléatoires, de tester la primalité du résultat, et de recommencer tant qu'on n'a pas un nombre premier.
Maintenant, on a un cerveau et on sait s'en servir, donc on se dit que le nombre premier p sera forcément impair, donc autant s'arranger pour que le bit de poids faible vaille 1. Ça divise par deux le nombre moyen de tirages qu'il faut faire.
Ensuite, on continue à se servir du même cerveau, donc on se dit : en fait, en choisissant des candidats seulement impairs, ce qu'on fait, c'est décider _a priori_ que p = 1 mod 2 et de ne choisir des candidats vérifiant cette égalité. Le même processus devrait être extensible à d'autres petits nombres premiers comme 3, 5, 7, 11... Quand on choisit des nombres impairs aléatoire, une fois sur 3 on tombe sur un multiple de 3, une fois sur 5 sur un multiple de 5, etc, et on voudrait éviter ces candidats qui nous font faire des tests de primalité pour rien.
Donc on commence par sélectionner a priori, et aléatoirement, ce que vaudra notre futur p modulo 2, 3, 5, 7, 11... en choisissant forcément des valeurs non nulles à chaque fois. Par exemple, on sélectionne ceci :
p = 1 mod 2 p = 2 mod 3 p = 1 mod 5 p = 4 mod 7 p = 8 mod 11
Par les restes chinois, ça nous apprend que les candidats que nous chercherons seront égaux à 1691 mod 2310 (2310 = 2*3*5*7*11). On sélection chaque candidat en tirant un nombre aléatoire t entre 2^511/2310 et 2^512/2310 (si on vise un nombre premier de 512 bits), et le candidat est t*2310+1691, qui, par construction, respecte nos modulos exposés ci-dessus. Cette méthode s'assure que l'on évite les faux candidats "triviaux", ceux qui sont divisible par un petit nombre premier. On peut montrer qu'environ 79.2% des entiers choisis aléatoirement seront divisibles par 2, 3, 5, 7 ou 11 ; donc cette méthode élimine 4 faux candidats sur 5, là où simplement fixer le bit de poids faible à 1 n'en vire qu'un sur deux: d'où une accélération d'un facteur 2.5...
Dans la pratique, on ne s'arrête pas à 11, on va jusqu'a 23, parce que 2*3*5*7*11*13*17*19*23 = 223092870, ce qui tient encore sur 32 bits. En allant jusqu'à 23, on vire 83.6% des faux candidats (donc une génération trois fois plus rapide que si on se contentait de fixer le bit à 1).
Maintenant qu'on a cette méthode, qu'on veut utiliser pour des raisons de performance, on peut se dire : voyons, on veut p premier, mais on peut aussi que p-1 et e n'aient pas de facteur commun. On pourrait choisir, a priori, que e = 3, et le problème devient alors : on veut que le p choisi soit différent de 1 modulo 3. Or, justement, la méthode de sélection commence par choisir ce que vaudra p modulo certains nombres, dont 3. Il suffit de forcer p = 2 mod 3 dans la méthode ci-dessus pour avoir la garantie que tous les candidats sélectionnés seront non seulement non divisibles par 3, mais également adéquats pour un RSA avec e = 3 comme exposant public. Le coût de la sélection de l'exposant public devient nul.
--Thomas Pornin
Sylvain SF
Thomas Pornin a écrit :
According to Sylvain SF :
la génération de e prend un temps nul, la vérification de sa primalité prend un temps non négligeable devant les tests sur p et q qui de longueur moitié sont testé plus rapidement.
Si on s'y prend bien, la vérification que e est premier avec p-1 et q-1 prend un temps _vraiment_ nul (plutôt que négligeable).
e premier avec (p - 1) et (q - 1) se vérifie par un calcul de PGCD qui est très rapide (négligeable). ce qui prendrait du temps serait de générer p et q jusqu'à ce qu'ils satisfassent cette condition si aucune précaution n'a été prise sur la génération de e.
ici, comme dans la réponse de Mehdi ("e premier à phi(N)") le déroulement me semble inversé: e peut certes être généré une fois n (donc p et q) connus, mais il peut également être le premier terme généré (car imposé par "l'extérieur") - le problème est bien alors de générer un e premier (ce qui peut prendre de 100 à 1000 ms pour un nombre dans [2^2047 .. 2^2048]).
Par les restes chinois, ça nous apprend que les candidats que nous chercherons seront égaux à 1691 mod 2310 (2310 = 2*3*5*7*11).
2310 était clair mais je n'intuite pas le 1691 ?!...
Sylvain.
Thomas Pornin a écrit :
According to Sylvain SF <sylvain@boiteaspam.info>:
la génération de e prend un temps nul, la vérification de sa primalité
prend un temps non négligeable devant les tests sur p et q qui de
longueur moitié sont testé plus rapidement.
Si on s'y prend bien, la vérification que e est premier avec p-1 et q-1
prend un temps _vraiment_ nul (plutôt que négligeable).
e premier avec (p - 1) et (q - 1) se vérifie par un calcul de
PGCD qui est très rapide (négligeable).
ce qui prendrait du temps serait de générer p et q jusqu'à ce
qu'ils satisfassent cette condition si aucune précaution n'a
été prise sur la génération de e.
ici, comme dans la réponse de Mehdi ("e premier à phi(N)")
le déroulement me semble inversé: e peut certes être généré
une fois n (donc p et q) connus, mais il peut également être
le premier terme généré (car imposé par "l'extérieur") - le
problème est bien alors de générer un e premier (ce qui peut
prendre de 100 à 1000 ms pour un nombre dans [2^2047 .. 2^2048]).
Par les restes chinois, ça nous apprend que les candidats que nous
chercherons seront égaux à 1691 mod 2310 (2310 = 2*3*5*7*11).
2310 était clair mais je n'intuite pas le 1691 ?!...
la génération de e prend un temps nul, la vérification de sa primalité prend un temps non négligeable devant les tests sur p et q qui de longueur moitié sont testé plus rapidement.
Si on s'y prend bien, la vérification que e est premier avec p-1 et q-1 prend un temps _vraiment_ nul (plutôt que négligeable).
e premier avec (p - 1) et (q - 1) se vérifie par un calcul de PGCD qui est très rapide (négligeable). ce qui prendrait du temps serait de générer p et q jusqu'à ce qu'ils satisfassent cette condition si aucune précaution n'a été prise sur la génération de e.
ici, comme dans la réponse de Mehdi ("e premier à phi(N)") le déroulement me semble inversé: e peut certes être généré une fois n (donc p et q) connus, mais il peut également être le premier terme généré (car imposé par "l'extérieur") - le problème est bien alors de générer un e premier (ce qui peut prendre de 100 à 1000 ms pour un nombre dans [2^2047 .. 2^2048]).
Par les restes chinois, ça nous apprend que les candidats que nous chercherons seront égaux à 1691 mod 2310 (2310 = 2*3*5*7*11).
2310 était clair mais je n'intuite pas le 1691 ?!...
Sylvain.
Thomas Pornin
According to Sylvain SF :
2310 était clair mais je n'intuite pas le 1691 ?!...
1691 est l'unique entier x entre 0 et 2309 tel que : x = 1 mod 2 x = 2 mod 3 x = 1 mod 5 x = 4 mod 7 x = 8 mod 11 et on calcule 1691 à partir de 1, 2, 1, 4 et 8 en appliquant le théorème des restes chinois.
--Thomas Pornin
According to Sylvain SF <sylvain@boiteaspam.info>:
2310 était clair mais je n'intuite pas le 1691 ?!...
1691 est l'unique entier x entre 0 et 2309 tel que :
x = 1 mod 2
x = 2 mod 3
x = 1 mod 5
x = 4 mod 7
x = 8 mod 11
et on calcule 1691 à partir de 1, 2, 1, 4 et 8 en appliquant
le théorème des restes chinois.
2310 était clair mais je n'intuite pas le 1691 ?!...
1691 est l'unique entier x entre 0 et 2309 tel que : x = 1 mod 2 x = 2 mod 3 x = 1 mod 5 x = 4 mod 7 x = 8 mod 11 et on calcule 1691 à partir de 1, 2, 1, 4 et 8 en appliquant le théorème des restes chinois.
