temps d'exécution du AES et du RSA
kabina
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)
A votre avis est ce que c'est coh�rent !!!!
merci � vous et bonne soir�e.
Erwan David
> 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)
>
> A votre avis est ce que c'est coh�rent !!!!
>
> merci � vous et bonne soir�e.
�a va d�pendre de l'impl�mentation, de la machine, du chainage, et dans
le cas de RSA de l'algorithme de chiffrement � clef secr�te utilis� (on
ne chifre JAMAIS plusieurs m�ga octets en RSA).
--
Le travail n'est pas une bonne chose. Si �a l'�tait,
les riches l'auraient accapar�
kabina
> kabina �crivait�:
>
>> Bonjour,
>>
>> j'ai calcul� les diff�rents temps d'ex�cution des
>> algorithmes AES et RSA et
>> voici ce que j'ai obtenu:
>>
>> 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
>> temps de 74583 ms
>> et RAM 22665 k
>>
>> pas les
>> entr�es/sorties(lecture du fichier � chiffr� et
>> enregistrement du fichier
>> (cl� publique et cl�
>> priv�e)
>>
>> A votre avis est ce que c'est coh�rent !!!!
>>
>> merci � vous et bonne soir�e.
>>
>
> chainage, et dans
> le cas de RSA de l'algorithme de chiffrement � clef secr�te
> utilis� (on
> ne chifre JAMAIS plusieurs m�ga octets en RSA).
>
> --
> Le travail n'est pas une bonne chose. Si �a l'�tait,
> les riches l'auraient accapar�
oui je sais que le mieux c'est d'utiliser un chiffrement hybride.
Ce que je suis entrain de faire est dans le cadre d'un projet ou je dois
v�rifier par moi m�me les vitesses d'ex�cution (illustrer la lenteur du RSA).
machine
Processor : Intel(R) Core(TM) 2 CPU T5200 1,6GHZ.
Ram : 1,00 Go.
Mode ECB (RSA)
a+
Sylvain SF
> 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�, 9,16 Mo de fichier � chiffrer avec un temps de 500 ms et
> RAM utilis� 21695k
21.2 Mo pour traiter 9.16 Mo signifie s�rement que vous stockez
le r�sultat dans un buffer diff�rent de celui d'entr�e, c'est souvent
non requis, le chiffrement �tant r�alis� "en place" de plus si l'on
traite d'un flux, un tampon (de 128, 256+ Ko) est suffisant pour faire
le traitement � la vol�e, lire l'int�gralit� du flux d'entrant avant
de le traiter (et donc allouer un buffer de sa taille) est �galement
g�n�ralement inutile.
vos "conclusions" sont la m�moire requise sont de fait non pertinentes.
concernant les performances brutes d'un AES 128 bits, elles peuvent
varier d'une impl�mentation � une autre et de l'architecture du CPU,
vous n'indiquez pas l'impl�mentation; bien not� l'usage d'un T5200
(1,6GHZ, FSB 533MHz, L2 2Mo) qui est CPU "bas de gamme" pour portable.
avec un CPU "de desktop" (E8400), une impl�mentation C compil�e par
MS cl 14, 10Mo sont trait�s en moins de 200ms (� 2GHz, le CPU n'a pas
le temps de switcher � 3GHz) - 5 � 50ms par m�gaoctet sont des
chiffres ordinaires.
> 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
cela n'a aucun sens !
que veux dire ici "temps d'ex�cution de l'algorithme RSA" ??
vous appliquez un /chiffrement/ et donc une exponentiation avec 2
ou 3 bits (de l'exponent publique) ou un /d�chiffrement/ et donc
une exponentiation avec (de l'ordre de) 1024 bits (+/- 1024) ?
sur les 10 Mo d'entr�e vous traitez combien d'octets � la fois ?
cela ne peux pas �tre 256 sous peine de risquer d'avoir des nombres
sup�rieurs au modulus de la cl�, donc combien ? 255, 245 ?...
(avec un exposant publique de 0x010001, je traite 10Mo pris par
paquet de 255 octets en 17 sec.).
> 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)
pareil.
> A votre avis est ce que c'est coh�rent !!!!
c'est surtout d�nu� de sens !!
si on vous a demand� de "v�rifier par vous m�me la lenteur du RSA",
on ne vous a s�rement pas demander de v�rifier qu'un chiffrement RSA
est d�bile, ou alors vous pouvez dire � ce demandeur qu'il est d�bile.
un algo sym�trique a des contraintes, dont performance intrins�que,
temps constant (!!), facilit� d'impl�mentation hard, ...
un algo asym�trique a aussi des contraintes mais elles sont tout �
fait diff�rentes, r�sistance de la cl� priv�e, facilit� de publication
de la cl� publique (g�n�ration et taille des certs), ...
si le but de cet exercice est de "montrer" qu'il vaut mieux chiffrer
en AES qu'en RSA, c'est une insulte au bon sens et � la compr�hension
�l�mentaire de la crypto.
Sylvain.
kabina
> kabina a �crit :
>> Bonjour,
>>
>> j'ai calcul� les diff�rents temps d'ex�cution des
>> algorithmes AES et RSA et
>> voici ce que j'ai obtenu:
>>
>> de 203 ms
>> AES 128 bits de cl�, 9,16 Mo de fichier � chiffrer avec un temps
>> de 500 ms et
>> RAM utilis� 21695k
>>
>
> 21.2 Mo pour traiter 9.16 Mo signifie s�rement que vous stockez
> le r�sultat dans un buffer diff�rent de celui d'entr�e,
> c'est souvent
> non requis, le chiffrement �tant r�alis� "en
> place" de plus si l'on
> traite d'un flux, un tampon (de 128, 256+ Ko) est suffisant pour faire
> flux d'entrant avant
> de le traiter (et donc allouer un buffer de sa taille) est �galement
> g�n�ralement inutile.
>
> vos "conclusions" sont la m�moire requise sont de fait non
> pertinentes.
>
> concernant les performances brutes d'un AES 128 bits, elles peuvent
> CPU,
> vous n'indiquez pas l'impl�mentation; bien not� l'usage d'un
> T5200
> (1,6GHZ, FSB 533MHz, L2 2Mo) qui est CPU "bas de gamme" pour
> portable.
>
> compil�e par
> MS cl 14, 10Mo sont trait�s en moins de 200ms (� 2GHz, le CPU n'a
> pas
> le temps de switcher � 3GHz) - 5 � 50ms par m�gaoctet sont
> des
> chiffres ordinaires.
>
>> RSA 2048 bits de cl�, 2,58 Mo de fichier � chiffrer avec un
>> temps de 21621 ms
>> et RAM 8590 k
>> temps de 74583 ms
>> et RAM 22665 k
>>
>
> cela n'a aucun sens !
>
> vous appliquez un /chiffrement/ et donc une exponentiation avec 2
> une exponentiation avec (de l'ordre de) 1024 bits (+/- 1024) ?
>
> cela ne peux pas �tre 256 sous peine de risquer d'avoir des nombres
> sup�rieurs au modulus de la cl�, donc combien ? 255, 245 ?...
> (avec un exposant publique de 0x010001, je traite 10Mo pris par
> paquet de 255 octets en 17 sec.).
>
>> pas les
>> entr�es/sorties(lecture du fichier � chiffr� et
>> enregistrement du fichier
>> (cl� publique et cl�
>> priv�e)
>>
>
> pareil.
>
>> A votre avis est ce que c'est coh�rent !!!!
>>
>
> c'est surtout d�nu� de sens !!
>
> si on vous a demand� de "v�rifier par vous m�me la
> lenteur du RSA",
> on ne vous a s�rement pas demander de v�rifier qu'un chiffrement
> RSA
> est d�bile, ou alors vous pouvez dire � ce demandeur qu'il est
> d�bile.
>
> un algo sym�trique a des contraintes, dont performance
> intrins�que,
> temps constant (!!), facilit� d'impl�mentation hard, ...
> un algo asym�trique a aussi des contraintes mais elles sont tout
> �
> fait diff�rentes, r�sistance de la cl� priv�e,
> facilit� de publication
> de la cl� publique (g�n�ration et taille des certs), ...
>
> si le but de cet exercice est de "montrer" qu'il vaut mieux chiffrer
> compr�hension
> �l�mentaire de la crypto.
>
> Sylvain.
tout d'abord je vous remercie de votre aide.
Je ne vois pas � quel moment j'ai dis que le but de l'exercice est de monter
qu'il vaut mieux chiffrer en AES qu'en RSA !!!!!!!!!!!
Je sais bien que chaque algorithme a des avantages et des inconv�nients!!!!! et
tout d�pend de ce que on veut en faire. c'est �l�mentaire.
Peut �tre que je me suis mal exprim�!! quand je dis comparaison c'est pas dans
le sens qui est mieux que qui!!!! et c'est d�nu� de sens d'interpr�ter les
choses de la sorte!!! c'est comparaison en terme de rapidit� de chiffrement. Et
a ce que je sache RSA est plus lent, je r�p�te plus lent pas moins bon ou plus
bon (pas de jugement subjectif) que le AES.
Toute fois je vous l'accorde j'ai pas donn� certaines pr�cisions importantes:
Je calcule le temps de chiffrement du RSA et du AES.
Pour le RSA je traite 245 � la fois
Impl�mentation JAVA
Merci encore une fois et a+
Sylvain SF
>
> tout d'abord je vous remercie de votre aide.
merci de ne pas quoter inutilement tout le texte!
> Je ne vois pas � quel moment j'ai dis que le but de l'exercice est de monter
> qu'il vaut mieux chiffrer en AES qu'en RSA !!!!!!!!!!!
serait-ce:
"AES 128 bits de cl�, 2,58 Mo de fichier � chiffrer ..."
"RSA 2048 bits de cl�, 2,58 Mo de fichier � chiffrer ..."
si ce n'est pas une comparaison de chiffrement cela y ressemblait
ou �tait tr�s mal formul�, choisissez.
> a ce que je sache RSA est plus lent, je r�p�te plus lent pas moins bon ou plus
> bon (pas de jugement subjectif) que le AES.
je n'ai pas parl� (non plus) de jugement subjectif de valeur.
j'ai dit que la comparaison n'a pas de sens, r�p�ter qu'il est
"plus lent" continue � ne pas avoir de sens puisque les 2
op�rations (chiffrement sym�trique vs wrapping/signature asym)
ne sont nullement comparables (dire que dessiner un motif au
pinceau est plus lent que peindre uniform�ment au pistolet
serait aussi peu pertinent).
AES peut �tre compar� � DES (RCx, ...), RSA peut �tre compar�
� DSA ou ECDSA.
Sylvain.
Mehdi Tibouchi
>
> je n'ai pas parl� (non plus) de jugement subjectif de valeur.
> j'ai dit que la comparaison n'a pas de sens
Les deux sont des permutations pseudo-al�atoires (enfin, pour le textbook
RSA ce n'est pas vrai mais passons), donc si, la comparaison a un sens.
Apr�s tout, on pourrait se demander pourquoi on n'utilise pas RSA aussi
pour faire du chiffrement sym�trique avec les deux parties partageant une
m�me clef secr�te.
J'ai un peu de mal � comprendre la v�h�mence avec laquelle a �t�
accueillie cette question. Il est vrai que de prime abord elle m�ritait
une clarification, mais sachant qu'elle a �t� apport�e, c'est bon, on a
compris qu'il s'agissait juste d'un exercice � vocation p�dagogique.
Au passage, je trouve inqui�tante l'id�e qu'un chiffrement RSA, c'est
forc�ment avec un exposant de 2 ou 3 bits. Je sais bien que certaines
normes imposent e = 3 ou 65537, mais merci de ne pas en faire une r�gle
g�n�rale (RSA avec petit exposant public a des faiblesses notoires que
n'a pas RSA avec exposant public al�atoire).
Sylvain SF
> Sylvain SF wrote in message <4a352b95$0$12617$ba4a...@news.orange.fr>:
>> je n'ai pas parl� (non plus) de jugement subjectif de valeur.
>> j'ai dit que la comparaison n'a pas de sens
>
> Les deux sont des permutations pseudo-al�atoires (enfin, pour le textbook
> RSA ce n'est pas vrai mais passons), donc si, la comparaison a un sens.
AES est une permutation d�terministe et RSA un calcul num�rique.
je ne comprends pas votre r�sum�.
> Apr�s tout, on pourrait se demander pourquoi on n'utilise pas RSA aussi
> pour faire du chiffrement sym�trique avec les deux parties partageant une
> m�me clef secr�te.
"clef secr�te" signifiant "algo. sym�trique", je ne me demande pas
pourquoi on n'utilise pas RSA.
> J'ai un peu de mal � comprendre la v�h�mence avec laquelle a �t�
> accueillie cette question. Il est vrai que de prime abord elle m�ritait
> une clarification, mais sachant qu'elle a �t� apport�e, c'est bon, on a
> compris qu'il s'agissait juste d'un exercice � vocation p�dagogique.
j'ai un peu de mal � voir o� il y aurait une v�h�mence.
> Au passage, je trouve inqui�tante l'id�e qu'un chiffrement RSA, c'est
> forc�ment avec un exposant de 2 ou 3 bits. Je sais bien que certaines
> normes imposent e = 3 ou 65537, mais merci de ne pas en faire une r�gle
> g�n�rale (RSA avec petit exposant public a des faiblesses notoires que
> n'a pas RSA avec exposant public al�atoire).
je n'ai pas une g�n�ralit� de 65537, je l'ai indiqu� comme cons�quence
� l'hypoth�se (non confirm�e par le PO) du traitement par une cl�
*publique*, si le PO avait utilis� un exposant priv� "long" (de l'ordre
de 2048 bits) pour son calcul, il n'aurait pas mis 74 sec pour traiter
10Mo mais plut�t une dur�e proche de l'heure!
ceci relativisant �galement la port�e de la dite comparaison.
Sylvain.
kabina
Je persiste et je suis signe que je fais une comparaison en terme de VITESSE et
stop entre AES et RSA.
Dans ce petit exercice, Je n'utilise pas le RSA pour la signature mais bien
m�me s'il n'est pas recommander pour le chiffrement. Alors pourquoi je fais ceci
et bien parce que dans le cours on a vu le chiffrement sym�trique avec ses
avantages et ses inconv�nients (comme le transfert de la cl� secr�te ). Parmi
les raisons pour lesquelles la crypto asym�trique � vu le jour c'est de trouver
une solution � ce probl�me de transfert d'o� cl� publique cl� priv�e or tout
n'est pas parfait parmi les inconv�nients du RSA il y a le temps de chiffrement.
Finalement on a compris qu'il serai mieux de combiner les deux avec la cl�
sym�trique chiffrement du message ensuite avec RSA chiffrement de la cl�
sym�trique
tout ce qui vient d'�tre dit je souhaite le r�aliser moi m�me donc chiffr� un
texte avec AES et avec RSA et sortir avec la conclusion que le mieux c'est de
combiner les deux.
kabina
> Sylvain SF wrote in message <4a352b95$0$12617$:
>>
>> je n'ai pas parl� (non plus) de jugement subjectif de valeur.
>> j'ai dit que la comparaison n'a pas de sens
>>
>
> textbook
> RSA ce n'est pas vrai mais passons), donc si, la comparaison a un sens.
> pour faire du chiffrement sym�trique avec les deux parties partageant
> une
> m�me clef secr�te.
>
> J'ai un peu de mal � comprendre la v�h�mence avec laquelle
> a �t�
> accueillie cette question. Il est vrai que de prime abord elle m�ritait
> une clarification, mais sachant qu'elle a �t� apport�e,
> c'est bon, on a
> p�dagogique.
>
> Au passage, je trouve inqui�tante l'id�e qu'un chiffrement RSA,
> c'est
> forc�ment avec un exposant de 2 ou 3 bits. Je sais bien que certaines
> normes imposent e = 3 ou 65537, mais merci de ne pas en faire une r�gle
> g�n�rale (RSA avec petit exposant public a des faiblesses
> notoires que
> n'a pas RSA avec exposant public al�atoire).
merci vous avez tout compris tester en travaux pratiques quelque aspect du
cours.
Sylvain SF
>>
> Je n'arrive pas � ne pas citer tout le texte dites moi comment vous faites.
ben on le s�lectionne et on l'efface, tout simplement.
(sauf si vous postez depuis une page ou�be qui l'emp�che peut �tre).
> Je persiste et je suis signe que je fais une comparaison en terme de VITESSE et
> stop entre AES et RSA.
c'�tait clair.
> Dans ce petit exercice, Je n'utilise pas le RSA pour la signature mais bien
> m�me s'il n'est pas recommander pour le chiffrement. Alors pourquoi je fais ceci
> et bien parce que dans le cours on a vu le chiffrement sym�trique avec ses
> avantages et ses inconv�nients (comme le transfert de la cl� secr�te ).
c'est un inconv�nient, mais il existe des solutions pour chaque type
d'usage.
en effet vous n'utilisez pas la signature (lire la cl� priv�e) pourtant
votre exemple / comparaison devrait inclure le d�chiffrement par le
destinataire, celui-ci r�alisera un calcul tout � fait �quivalent �
une g�n�ration de signatures - soit un temps de calcul de 50 � 100 fois
plus important que le chiffrement avec la cl� publique.
> les raisons pour lesquelles la crypto asym�trique � vu le jour c'est de trouver
> une solution � ce probl�me de transfert d'o� cl� publique cl� priv�e or tout
> n'est pas parfait parmi les inconv�nients du RSA il y a le temps de chiffrement.
euh non, la crypto. asym�trique n'est pas n�e pour r�pondre au transfert
de cl� secr�tes, mais elle (dont le RSA) s'y pr�te assez bien.
> Finalement on a compris qu'il serai mieux de combiner les deux avec la cl�
> sym�trique chiffrement du message ensuite avec RSA chiffrement de la cl�
> sym�trique
c'est en effet comme cela que fonctionne 100% des syst�mes (y compris
SSL, y compris �change inter-serveurs, ...).
la cl� sym�trique est un simple al�a qui est communiqu� au destinataire
"wrapp�" (chiffr�) par sa cl� publique.
> tout ce qui vient d'�tre dit je souhaite le r�aliser moi m�me donc chiffr� un
> texte avec AES et avec RSA et sortir avec la conclusion que le mieux c'est de
> combiner les deux.
le "mieux" d�pends de l'op�ration exacte et des contraintes externes;
en ce sens il n'y avait pas de v�h�mence mais il n'y a pas non plus
de pros�lytisme pour un couplage syst�matique.
si vous souhaitez prot�ger des informations "courtes" (un fichier d'un
centaine d'octets) vous pouvez tout � fait le chiffrer directement avec
votre cl� publique; si, autre cas, le stockage de la cl� RSA priv�e
(qui m�rite au moins autant d'attention que celui d'une cl� secr�te
partag�e) ne peut pas �tre garanti ou encore si le calcul par cl� priv�
ne peut pas �tre fait (un PC le fait sans probl�me, un win-phone un peu
moins ais�ment), la cl� sym�trique peut aussi �tre g�n�r� � partir d'un
mot de passe (Cf crypto dite "PBE" (password based encryption)), elle
n'est alors plus directement partag�e mais reg�n�r�e.
Sylvain.
kabina
> kabina a �crit :
>>>
>>>
>> Je n'arrive pas � ne pas citer tout le texte dites moi comment vous
>> faites.
>>
>
> ben on le s�lectionne et on l'efface, tout simplement.
> (sauf si vous postez depuis une page ou�be qui l'emp�che peut
> �tre).
>
>> Je persiste et je suis signe que je fais une comparaison en terme de
VITESSE
>> et
>> stop entre AES et RSA.
>>
>
>
>> Dans ce petit exercice, Je n'utilise pas le RSA pour la signature mais bien
>> fais ceci
>> et bien parce que dans le cours on a vu le chiffrement sym�trique avec
>> ses
>> avantages et ses inconv�nients (comme le transfert de la cl�
>> secr�te ).
>>
>
> c'est un inconv�nient, mais il existe des solutions pour chaque type
> d'usage.
>
> en effet vous n'utilisez pas la signature (lire la cl� priv�e)
> pourtant
> votre exemple / comparaison devrait inclure le d�chiffrement par le
> destinataire, celui-ci r�alisera un calcul tout � fait
> �quivalent �
> une g�n�ration de signatures - soit un temps de calcul de 50
> � 100 fois
> plus important que le chiffrement avec la cl� publique.
>
>> les raisons pour lesquelles la crypto asym�trique � vu le jour
>> c'est de trouver
>> une solution � ce probl�me de transfert d'o� cl�
>> n'est pas parfait parmi les inconv�nients du RSA il y a le temps de
>> chiffrement.
>>
>
> euh non, la crypto. asym�trique n'est pas n�e pour
> r�pondre au transfert
> de cl� secr�tes, mais elle (dont le RSA) s'y pr�te assez
> bien.
>
>> Finalement on a compris qu'il serai mieux de combiner les deux avec la
>> sym�trique chiffrement du message ensuite avec RSA chiffrement de la
>> cl�
>> sym�trique
>>
>
> c'est en effet comme cela que fonctionne 100% des syst�mes (y compris
> SSL, y compris �change inter-serveurs, ...).
> la cl� sym�trique est un simple al�a qui est
> communiqu� au destinataire
> "wrapp�" (chiffr�) par sa cl� publique.
>
>> tout ce qui vient d'�tre dit je souhaite le r�aliser moi
>> texte avec AES et avec RSA et sortir avec la conclusion que le mieux c'est
de
>> combiner les deux.
>>
>
> contraintes externes;
> en ce sens il n'y avait pas de v�h�mence mais il n'y a pas non
> plus
> de pros�lytisme pour un couplage syst�matique.
>
> si vous souhaitez prot�ger des informations "courtes" (un
> fichier d'un
> centaine d'octets) vous pouvez tout � fait le chiffrer directement avec
> votre cl� publique; si, autre cas, le stockage de la cl� RSA
> priv�e
> (qui m�rite au moins autant d'attention que celui d'une cl�
> secr�te
> partag�e) ne peut pas �tre garanti ou encore si le calcul par
> cl� priv�
> ne peut pas �tre fait (un PC le fait sans probl�me, un win-phone
> un peu
> moins ais�ment), la cl� sym�trique peut aussi �tre
> g�n�r� � partir d'un
> mot de passe (Cf crypto dite "PBE" (password based encryption)), elle
> reg�n�r�e.
>
> Sylvain.
"les raisons pour lesquelles la crypto asym�trique � vu le jour
c'est de trouver
une solution � ce probl�me de transfert d'o� cl�
n'est pas parfait parmi les inconv�nients du RSA il y a le temps de
chiffrement.
euh non, la crypto. asym�trique n'est pas n�e pour
r�pondre au transfert
de cl� secr�tes, mais elle (dont le RSA) s'y pr�te assez
bien."
j'ai pas dit les raisons j'ai dit parmi les raisons.
"c'est un inconv�nient, mais il existe des solutions pour chaque type
d'usage."
bien �videment .
"en effet vous n'utilisez pas la signature (lire la cl� priv�e)
pourtant
votre exemple / comparaison devrait inclure le d�chiffrement par le
destinataire, celui-ci r�alisera un calcul tout � fait
�quivalent �
une g�n�ration de signatures - soit un temps de calcul de 50
� 100 fois
plus important que le chiffrement avec la cl� publique."
je ne pense pas parce que dans mon exemple le destinataire d�chiffre avec sa
cl� priv�e le texte chiffr� en entier alors que dans une signature l'�metteur
chiffre avec sa cl� priv�e l'empreinte digital.
merci � vous
Mehdi Tibouchi
>>
>> Les deux sont des permutations pseudo-al�atoires (enfin, pour le textbook
>> RSA ce n'est pas vrai mais passons), donc si, la comparaison a un sens.
>
> AES est une permutation d�terministe et RSA un calcul num�rique.
> je ne comprends pas votre r�sum�.
Savez-vous ce qu'est une permutation pseudo-al�atoire�? Si oui, je ne
comprends pas ce que vous ne comprenez pas. Sinon, Wikipedia devrait
r�pondre � votre question.
>> Apr�s tout, on pourrait se demander pourquoi on n'utilise pas RSA aussi
>> pour faire du chiffrement sym�trique avec les deux parties partageant une
>> m�me clef secr�te.
>
> "clef secr�te" signifiant "algo. sym�trique", je ne me demande pas
> pourquoi on n'utilise pas RSA.
Je pense que vous voyez tr�s bien de quelle fa�on on peut utiliser RSA
comme algorithme de chiffrement sym�trique par blocs. Il y a plusieurs
bonnes raisons pour ne pas le faire, et l'une d'entre elle est le temps
de calcul, mais je ne vois pas le mal qu'il y aurait � essayer pour s'en
rendre compte.
> je n'ai pas une g�n�ralit� de 65537, je l'ai indiqu� comme cons�quence
> � l'hypoth�se (non confirm�e par le PO) du traitement par une cl�
> *publique*, si le PO avait utilis� un exposant priv� "long" (de l'ordre
> de 2048 bits) pour son calcul, il n'aurait pas mis 74 sec pour traiter
> 10Mo mais plut�t une dur�e proche de l'heure!
> ceci relativisant �galement la port�e de la dite comparaison.
Il n'y a pas de diff�rence entre un chiffrement par une clef publique
al�atoire et un d�chiffrement par une clef priv�e �galement al�atoire. Et
on peut parfaitement faire en sorte que l'une ou l'autre soit petite (et
si l'on n'a pas �tudi� pr�cis�ment le probl�me, les deux sont de
mauvaises id�es).
Sylvain SF
>
> je ne pense pas parce que dans mon exemple le destinataire d�chiffre avec sa
> cl� priv�e le texte chiffr� en entier alors que dans une signature l'�metteur
> chiffre avec sa cl� priv�e l'empreinte digital.
?!? dans votre exemple vous chiffrez 2,58 ou 9,16 Mo avec la cl�
publique, si ces data n'ont pas vocation a �tre d�chiffr� par
quelqu'un autant ne pas les chiffrer.
pour une signature, il ne signera que "l'empreinte" en effet,
celle-ci sera courte (160, 256, au pire 256 bits) et r�sulte d'un
calcul "one-way" ayant (en moyenne) des performances comparables
� un cipher sym�trique.
Sylvain.
Sylvain SF
> Sylvain SF wrote in message <4a35551c$0$17747$ba4a...@news.orange.fr>:
>>> Les deux sont des permutations pseudo-al�atoires (enfin, pour le textbook
>>> RSA ce n'est pas vrai mais passons), donc si, la comparaison a un sens.
>> AES est une permutation d�terministe et RSA un calcul num�rique.
>> je ne comprends pas votre r�sum�.
>
> Savez-vous ce qu'est une permutation pseudo-al�atoire ? Si oui, je ne
> comprends pas ce que vous ne comprenez pas. Sinon, Wikipedia devrait
> r�pondre � votre question.
oui je sais ce que sais. par contre (je r�p�te) je ne comprends
pas le but de cette remarque (de cette porte ouverte); de votre
compl�ment je dois peut �tre comprendre que je peux googler 3000
r�ponses possibles ou wikip�dier � loisir pour essayer de donner
un sens � votre texte; d�sol� mais je n'ai pas envie (le temps)
de jouer.
>>> Apr�s tout, on pourrait se demander pourquoi on n'utilise pas RSA aussi
>>> pour faire du chiffrement sym�trique avec les deux parties partageant une
>>> m�me clef secr�te.
>> "clef secr�te" signifiant "algo. sym�trique", je ne me demande pas
>> pourquoi on n'utilise pas RSA.
>
> Je pense que vous voyez tr�s bien de quelle fa�on on peut utiliser RSA
> comme algorithme de chiffrement sym�trique par blocs. Il y a plusieurs
> bonnes raisons pour ne pas le faire, et l'une d'entre elle est le temps
> de calcul, mais je ne vois pas le mal qu'il y aurait � essayer pour s'en
> rendre compte.
pourquoi jouez-vous � l'avocat d'une cause jamais mise en question ?
personne n'a indiqu� qu'il �tait mal de ci ou �a.
> Il n'y a pas de diff�rence entre un chiffrement par une clef publique
> al�atoire et un d�chiffrement par une clef priv�e �galement al�atoire.
pas de diff�rence algorithmique ? certes, juste une diff�rence
de temps de calcul.
> on peut parfaitement faire en sorte que l'une ou l'autre soit petite (et
> si l'on n'a pas �tudi� pr�cis�ment le probl�me, les deux sont de
> mauvaises id�es).
vous pouvez faire en sorte d'avoir un exposant priv� de 17 bits et un
exp. public de 2048 bits, si cela vous chante; cela ne changera rien
au fait que les temps de calcul utilisant l'un ou l'autre exposant
seront tr�s diff�rents et qu'une op�ration de chiffrement/d�chiffrement
ne peux pas �tre �valuer avec le seul calcul le moins lourd.
Sylvain.
kabina
> kabina a �crit :
>>
>> je ne pense pas parce que dans mon exemple le destinataire d�chiffre
>> avec sa
>> signature l'�metteur
>> chiffre avec sa cl� priv�e l'empreinte digital.
>>
>
> ?!? dans votre exemple vous chiffrez 2,58 ou 9,16 Mo avec la cl�
> publique, si ces data n'ont pas vocation a �tre d�chiffr�
> par
> quelqu'un autant ne pas les chiffrer.
>
> pour une signature, il ne signera que "l'empreinte" en effet,
> calcul "one-way" ayant (en moyenne) des performances comparables
>
> Sylvain.
"?!? dans votre exemple vous chiffrez 2,58 ou 9,16 Mo avec la cl�
publique, si ces data n'ont pas vocation a �tre d�chiffr�
par
quelqu'un autant ne pas les chiffrer."
je pense que vous avez mal lu ce que j'ai �cris, il y a difference entre
"je ne pense pas que dans mon exemple le destinataire d�chiffre avec sa
cl� priv�e le texte chiffr� en entier"
qui veut bien dire que le destinataire ne d�chiffre pas avec sa cl� priv�, et
ce que moi j'ai �cris:
"je ne pense pas parce que dans mon exemple le destinataire d�chiffre avec sa
cl� priv�e le texte chiffr� en entier"
pour expliquer qu'il d�chiffre tout le texte contrairement � la signature.
merci � vous
Mehdi Tibouchi
>>
>> Savez-vous ce qu'est une permutation pseudo-al�atoire ? Si oui, je ne
>> comprends pas ce que vous ne comprenez pas. Sinon, Wikipedia devrait
>> r�pondre � votre question.
>
> oui je sais ce que sais.
Alors vous savez que, pour une clef al�atoire, AES, comme tout bon block
cipher, cherche � �tre une permutation pseudo-al�atoire. Le premier
r�sultat qui distingue, de mani�re tr�s th�orique, AES d'une permutation
al�atoire a d'ailleurs �t� annonc� seulement tr�s r�cemment.
RSA n'est pas une permutation pseudo-al�atoire, mais ce n'est pas
compl�tement imm�diat, et si l'on rajoute un padding, on s'en rapproche
beaucoup.
>> Il n'y a pas de diff�rence entre un chiffrement par une clef publique
>> al�atoire et un d�chiffrement par une clef priv�e �galement al�atoire.
>
> pas de diff�rence algorithmique ? certes, juste une diff�rence
> de temps de calcul.
��Al�atoire��, ici, signifie en particulier que la clef publique et la
clef secr�te font toutes les deux essentiellement 2048 bits. C'est la
bonne fa�on d'utiliser RSA quand on veut que les preuves de s�curit�
s'appuyant sur la difficult� du probl�me RSA standard s'appliquent.
Sylvain SF
>
> "je ne pense pas parce que dans mon exemple le destinataire d�chiffre avec sa
> cl� priv�e le texte chiffr� en entier"
ok, mal lu (�a commence � �tre en effet fatiguant � lire cette pur�e
giganews).
donc il d�chiffrera l'ensemble par bloc de 256 octets pour r�cup�rer
248 octets de clair � la fois, et cela lui prendra une heure (retour
� mon post n - 3).
> pour expliquer qu'il d�chiffre tout le texte contrairement � la signature.
"contrairement � une signature" ou RSA ignore compl�tement ce
qu'�tait le message d'origine et sa taille ?!???
vous avez raison c'est tout contraire.
Sylvain.
kabina
> Mehdi Tibouchi a �crit :
>> Sylvain SF wrote in message <4a352b95$0$12617$:
>>> j'ai dit que la comparaison n'a pas de sens
>>>
>>
>> textbook
>> RSA ce n'est pas vrai mais passons), donc si, la comparaison a un sens.
>>
>
> je ne comprends pas votre r�sum�.
>
>> Apr�s tout, on pourrait se demander pourquoi on n'utilise pas RSA aussi
>> pour faire du chiffrement sym�trique avec les deux parties partageant
>> une
>> m�me clef secr�te.
>>
>
> je ne me demande pas
> pourquoi on n'utilise pas RSA.
>
>> laquelle a �t�
>> une clarification, mais sachant qu'elle a �t� apport�e,
>> c'est bon, on a
>> p�dagogique.
>>
>
> j'ai un peu de mal � voir o� il y aurait une
> v�h�mence.
>
>> Au passage, je trouve inqui�tante l'id�e qu'un chiffrement RSA,
>> c'est
>> forc�ment avec un exposant de 2 ou 3 bits. Je sais bien que certaines
>> normes imposent e = 3 ou 65537, mais merci de ne pas en faire une r�gle
>> g�n�rale (RSA avec petit exposant public a des faiblesses
>> notoires que
>> n'a pas RSA avec exposant public al�atoire).
>>
>
> je n'ai pas une g�n�ralit� de 65537, je l'ai
> indiqu� comme cons�quence
> � l'hypoth�se (non confirm�e par le PO) du traitement par
> une cl�
> *publique*, si le PO avait utilis� un exposant priv�
> "long" (de l'ordre
> de 2048 bits) pour son calcul, il n'aurait pas mis 74 sec pour traiter
> ceci relativisant �galement la port�e de la dite comparaison.
>
> Sylvain.
"je n'ai pas une g�n�ralit� de 65537, je l'ai
indiqu� comme cons�quence
� l'hypoth�se (non confirm�e par le PO) du traitement par
une cl�
*publique*, si le PO avait utilis� un exposant priv�
"long" (de l'ordre
de 2048 bits) pour son calcul, il n'aurait pas mis 74 sec pour traiter
ceci relativisant �galement la port�e de la dite comparaison."
j'ai t�l�charg� un certificat d'une pki taille de la cl� 2048 bits
Sylvain SF
>
> � Al�atoire �, ici, signifie en particulier que la clef publique et
> la clef secr�te font toutes les deux essentiellement 2048 bits.
c'est un jeu ou tu sais (pense savoir) de quoi tu parles ??
le terme "cl� secr�te" n'a aucun sens ici, c'est une cl�
priv�e.
l'exposant publique ('e' habituellement) doit satisfaire
GCD(p - 1, e) == 1 cette condition est d'autant plus dure
� satisfaire que e est grand, � moins que e ne soit premier
mais tu n'incluais pas cette hypoth�se.
> C'est la
> la bonne fa�on d'utiliser RSA quand on veut que les preuves de s�curit�
> s'appuyant sur la difficult� du probl�me RSA standard s'appliquent.
j'ai juste quelque doutes sur ce que tu pourrais penser �tre
"une bonne fa�on" ...
je vois bien un "probl�me RSA standard" r�sultant du choix de
p et q - qui eux sont de tailles comparables - mais moins
du choix de e (on �vitera quand m�me de choisir 1 pour donner
en clair ce que l'on croyait chiffr�), peux-tu d�tailler ton
affirmation ?
Sylvain.
Mehdi Tibouchi
>
> c'est un jeu ou tu sais (pense savoir) de quoi tu parles ??
Non, oui.
> l'exposant publique ('e' habituellement) doit satisfaire
> GCD(p - 1, e) == 1 cette condition est d'autant plus dure
> � satisfaire que e est grand, � moins que e ne soit premier
> mais tu n'incluais pas cette hypoth�se.
L'exposant e est choisi al�atoire parmi les nombres _premiers � phi(N)_
entre 2 et phi(N). Ce n'est pas une condition compliqu�e � r�aliser, et
elle n'est pas sp�cialement plus dure � satisfaire pour e grand. Ce n'est
pas elle qui va prendre le plus de temps pendant la g�n�ration de clef.
> je vois bien un "probl�me RSA standard" r�sultant du choix de p et q -
> qui eux sont de tailles comparables - mais moins du choix de e (on
> �vitera quand m�me de choisir 1 pour donner en clair ce que l'on
> croyait chiffr�), peux-tu d�tailler ton affirmation ?
Le probl�me RSA pour e (ou d) petit est, selon toute vraisemblance, plus
simple � r�soudre que RSA pour e et d al�atoires. Les sch�mas de
chiffrement ou de signature dont la s�curit� prouv�e repose sur la
difficult� du probl�me RSA standard supposent en g�n�ral e distribu�
al�atoirement pour que la r�duction fonctionne (cf. par exemple
les papiers de Hohenberger et Waters cette ann�e).
remy
> Sylvain SF wrote in message <4a35924c$0$12637$ba4a...@news.orange.fr>:
>> c'est un jeu ou tu sais (pense savoir) de quoi tu parles ??
>
> Non, oui.
>
>> l'exposant publique ('e' habituellement) doit satisfaire
>> GCD(p - 1, e) == 1 cette condition est d'autant plus dure
>> � satisfaire que e est grand, � moins que e ne soit premier
>> mais tu n'incluais pas cette hypoth�se.
>
> L'exposant e est choisi al�atoire parmi les nombres _premiers � phi(N)_
> entre 2 et phi(N).
oui disons un nombre premier
Ce n'est pas une condition compliqu�e � r�aliser,
non juste premier cela fera l'affaire
> et elle n'est pas sp�cialement plus dure � satisfaire pour e grand. Ce n'est
> pas elle qui va prendre le plus de temps pendant la g�n�ration de clef.
avec un petit test tatitique c'est jouable
>> je vois bien un "probl�me RSA standard" r�sultant du choix de p et q -
>> qui eux sont de tailles comparables - mais moins du choix de e (on
>> �vitera quand m�me de choisir 1 pour donner en clair ce que l'on
>> croyait chiffr�), peux-tu d�tailler ton affirmation ?
>
> Le probl�me RSA pour e (ou d) petit est, selon toute vraisemblance, plus
> simple � r�soudre que RSA pour e et d al�atoires. Les sch�mas de
> chiffrement ou de signature dont la s�curit� prouv�e repose sur la
> difficult� du probl�me RSA standard supposent en g�n�ral e distribu�
> al�atoirement pour que la r�duction fonctionne (cf. par exemple
> les papiers de Hohenberger et Waters cette ann�e).
bien � partir du moment o� tu en as que 2 il est difficile de dire
autre chose que "il sont pris au hasard "
mais bon j'ai peut �tre pas tout compris hein
moi les grands mots et les trucs qui font s�rieux parsem�s d'arguments
d'autorit� je l'ai comprend pas toujours j'aime bien les trucs
accessibles et simples
remy
Sylvain SF
>
> L'exposant e est choisi al�atoire parmi les nombres _premiers � phi(N)_
> entre 2 et phi(N). Ce n'est pas une condition compliqu�e � r�aliser, et
> elle n'est pas sp�cialement plus dure � satisfaire pour e grand. Ce n'est
> pas elle qui va prendre le plus de temps pendant la g�n�ration de clef.
ce n'est pas dur, mais c'est loin d'�tre appliqu� "dans la vraie vie".
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.
> Le probl�me RSA pour e (ou d) petit est, selon toute vraisemblance, plus
> simple � r�soudre que RSA pour e et d al�atoires. Les sch�mas de
> chiffrement ou de signature dont la s�curit� prouv�e repose sur la
> difficult� du probl�me RSA standard supposent en g�n�ral e distribu�
> al�atoirement pour que la r�duction fonctionne (cf. par exemple
> les papiers de Hohenberger et Waters cette ann�e).
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.
parles-tu de "Realizing Hash-n-Sign Signatures under Std Assumptions" ?
Sylvain.
Erwan David
> Mehdi Tibouchi a �crit :
>>
>> L'exposant e est choisi al�atoire parmi les nombres _premiers � phi(N)_
>> entre 2 et phi(N). Ce n'est pas une condition compliqu�e � r�aliser, et
>> elle n'est pas sp�cialement plus dure � satisfaire pour e grand. Ce n'est
>> pas elle qui va prendre le plus de temps pendant la g�n�ration de clef.
>
> ce n'est pas dur, mais c'est loin d'�tre appliqu� "dans la vraie vie".
>
> 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.
Dans la vraie vie, e=3, 17 ou 65537
parceque pour aller vite il ne faut pas qu'il soit trop grand, quand il
est premeier on est s�r qu'il convient, et moins il a de bits � 1 plus
vite vont les op�rations sur clef publique.
Je pense que tu confonds avec d qui se d�duit de e, p et q.
--
Le travail n'est pas une bonne chose. Si �a l'�tait,
les riches l'auraient accapar�
Thomas Pornin
> Dans la vraie vie, e=3, 17 ou 65537
Et toujours dans la vraie vie, choisir un e qui ne tient pas sur 32
bits, c'est chercher les ennuis. Par exemple, la couche cryptographique
interne � Windows, quand elle manipule une cl� publique RSA, affecte
joyeusement un mot de 32 bits pour e, pas plus.
--Thomas Pornin
Erwan David
Sylvain SF
>
> la couche cryptographique interne � Windows
quelle couche (BaseCSP, EnhCSP, CNG, ...) de quel windows ?
un XP SP3 avec ses CSP par d�faut g�re en effet tr�s mal les
exp. publics longs (stockage des certs n'importe o� et �chec de
v�rification).
SF.
Thomas Pornin
> quelle couche (BaseCSP, EnhCSP, CNG, ...) de quel windows ?
Les CSP. La doc que j'ai sous la main (le "platform SDK") couvre jusqu'�
Windows Server 2003 R2 et tous les CSP d�crits (Base, Strong, Enhanced,
AES, RSA/Schannel) utilisent le m�me format pour exporter ou importer
une cl� publique ; ce format contient une structure nomm�e "RSAPUBKEY",
laquelle a un champ de 32 bits pour l'exposant publique.
Dans un genre proche, ces m�mes CSP n'aiment pas quand la longueur de la
cl� n'est pas un multiple de 8. Si on veut s'en servir pour g�rer une
cl� _priv�e_ RSA, alors des restrictions additionnelles s'appliquent :
taille multiple de 16, exactement deux facteurs premiers, et la taille
de chaque facteur doit �tre pr�cis�ment la moiti� de celle du module.
--Thomas Pornin
Sylvain SF
>
> Les CSP. La doc que j'ai sous la main (le "platform SDK") couvre jusqu'�
> Windows Server 2003 R2 et tous les CSP d�crits (Base, Strong, Enhanced,
> AES, RSA/Schannel) utilisent le m�me format pour exporter ou importer
> une cl� publique ; ce format contient une structure nomm�e "RSAPUBKEY",
> laquelle a un champ de 32 bits pour l'exposant publique.
ok, merci pour la (mauvaise) nouvelle. j'�plucherais la doc CNG �
temps perdu.
> Dans un genre proche, ces m�mes CSP n'aiment pas quand la longueur de la
> cl� n'est pas un multiple de 8. Si on veut s'en servir pour g�rer une
> cl� _priv�e_ RSA, alors des restrictions additionnelles s'appliquent :
> taille multiple de 16, exactement deux facteurs premiers, et la taille
> de chaque facteur doit �tre pr�cis�ment la moiti� de celle du module.
oui, d�j� observ� son aversion pour des p / q de longueur dissemblable.
Sylvain.
Erwan David
>
> Dans un genre proche, ces m�mes CSP n'aiment pas quand la longueur de la
> cl� n'est pas un multiple de 8. Si on veut s'en servir pour g�rer une
> cl� _priv�e_ RSA, alors des restrictions additionnelles s'appliquent :
> taille multiple de 16, exactement deux facteurs premiers, et la taille
> de chaque facteur doit �tre pr�cis�ment la moiti� de celle du module.
�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).
Mehdi Tibouchi
<m2ski04...@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�?
Mehdi Tibouchi
>
> 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
Il suffit de ne pas l'utiliser... Mais les contraintes restent l�.
remy
tiens justement j'�tais tomb� sur
http://ljk.imag.fr/membres/Jean-Guillaume.Dumas/Enseignements/TAI/documents/
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
remy
http://ljk.imag.fr/membres/Jean-Guillaume.Dumas/Enseignements/TAI/documents/
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
Thomas Pornin
> 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
Thomas Pornin
> 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
> According to Sylvain SF <syl...@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 ?!...
Sylvain.
Thomas Pornin
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