Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 Re : Cryptographie » [Résolu] Unicité des clés privées RSA pour une même clé publique » 01-02-2010 09:52:26
Merci pour l'info,
J'avais bien pensé à Wikipedia mais en Français :-(
Pour la petite démonstration (avec en plus un exemple sur des petits nombres, c'est on ne peut plus clair.
Je n'ai pas trouvé (pas longtemps cherché non plus, j'avoue) comment on mettait le post "résolu" mais je considère qu'il l'est.
Merci encore et sans doute à bientôt.
#2 Re : Cryptographie » [Résolu] Unicité des clés privées RSA pour une même clé publique » 28-01-2010 14:34:16
C'est marrant le vouvoiement en viendrait presque à me choquer :-)
Dans l'exemple que je donnais, (e * d - 1) est divisible par (p-1) et (q-1) pour les deux valeurs de d.
Le PGCD de (p-1) et (q-1) dans l'exemple donné est 2.
Cette nouvelle formule (Carmichael) m'explique déjà d'où vient le deuxième nombre d que j'avais (c'était une valeur générée par un autre système que celui sur lequel je travaille).
En effet, le premier d est calculé par d = inv(e) mod phi (= formule la plus répandue sur Internet)
Le second d correspond bien à d = inv(e) mod (phi / 2) (formule de Carmichael).
Donc rien que pour ça, un grand merci.
Maintenant, si on y réfléchit un peu, ce facteur de 2 est systématique :
p est un nombre premier donc il est forcément impair
donc p-1 est un nombre pair donc multiple de 2.
Même raisonnement pour q.
- Cela veut-il dire qu'il existe systématiquement au moins deux valeurs de d qui correspondent au couple (n,e) ? (je n'ai pas les compétences mathématiques pour continuer le raisonnement) ou bien c'est un cas particulier ?
- y-a-t-il autant de valeurs de d possibles que de facteurs communs entre (p-1) et (q-1) ?
En tout cas, encore merci.
Cdt,
HappyMadMan
#3 Cryptographie » [Résolu] Unicité des clés privées RSA pour une même clé publique » 27-01-2010 10:29:55
- HappyMadMan
- Réponses : 4
Bonjour,
Je me suis aperçu d’un phénomène « étrange » avec l’algorithme RSA.
Peut-être pourrez-vous me confirmer mon hypothèse et m’expliquer :
Jusque là, j’ai toujours pensé que pour déchiffrer un message chiffré par un couple (n, e), il n’y avait qu’un seul couple (n, d) possible.
Or, lors de tests pour une application, je me suis retrouvé plusieurs fois dans le cas où des « d » différents permettaient des déchiffrements.
Le seul point est que la relation ed = 1 mod (phi) n’est pas toujours vérifiée.
(phi = indicatrice d'Euler = (p-1)(q-1) )
Vous trouverez un exemple (avec une clé de 1024 bits) à la fin de ce message.
Mon hypothèse est donc la suivante :
Pour un couple (n, e) donné, la décomposition CRT (p, q, dp, dq, u) est unique mais il existe potentiellement plusieurs couples (n, d) qui correspondent (permettent la signature ou le déchiffrement).
Pouvez-vous me confirmer cette hypothèse et éventuellement m’expliquer le pourquoi de la chose ?
Merci d’avance
Exemple :
CLEAR MODULUS : AFE44E58D16ADA77916B2E3794B00EF51A2A65DE686322E0B0D718638C3C1737CEE5221A44E1961CA77127151D44097F89366C1FCB63E6C8832991CC839A0075680EBDBBEA908F0F4FF5C5175258F3ED64DA96FE7A7A516EE101340B3FF1178B9BB28149D748709BFFF99B9B3515C0A410B708B36255F9528C95AD859C324927
MODULUS LENGTH (bits) : 1024
CLEAR PUBLIC EXPONENT : 00000003
CLEAR PRIVATE EXPONENT :
(where e * d = 1 mod phi)
7542DEE5E0F1E6FA60F21ECFB8755F4E1171993EF042174075E4BAED08280F7A89EE16BC2DEBB9686FA0C4B8BE2D5BAA5B799D6A8797EF3057710BDDAD1155A27FAC3C4AD12AF0E56F9DAEF3D1831E47EF9A3B8E99E54A2885F609D6CD5565066F185A64CE0BB5208270AFEFF11A65CEC411CE6669C0509EB86BFB6009E79D5B
(where e *d != 1 mod phi)
1D50B7B9783C79BE983C87B3EE1D57D3845C664FBC1085D01D792EBB420A03DEA27B85AF0B7AEE5A1BE8312E2F8B56EA96DE675AA1E5FBCC15DC42F76B4455689FEB0F12B44ABC395BE76BBCF460C791FBE68EE3A679528A217D8275B35559419BC616993382ED48209C2BFBFC469973B10473999A701427AE1AFED80279E757
P PARAMETER : D9EEFA86B40B8BA53DA69D2E059E692A2FD47B13C83D31D8FFEE57ACF993DBF693D125758026212F452CD0C115957AADBACA0C9955ED7348DFE11FB01E11FEF5
Q PARAMETER : CE9D68C4FCC49A11EAE2A17B9275DD574D9EC294CB6530591821CD9C125D240B613CD43D2210BFBBF723C2F235D8AD402FD246806DC80D1B981294C56F44DE2B
DP PARAMETER : 9149FC59CD5D07C37E6F137403BEF0C6CA8DA762857E213B55498FC8A66292A4628B6E4E556EC0CA2E1DE080B90E51C927315DBB8E9E4CDB3FEB6A75696154A3
DQ PARAMETER : 89BE45D8A88311614741C0FD0C4E938F891481B88798CAE610168912B6E8C2B240D33828C1607FD2A4C281F6CE9073801FE184559E855E126561B8839F833EC7
U PARAMETER : 1491B440A4CD8DFDD76F343E719DD7D3B09307718CFEF993529CD868CC3CF0F1F1EF4298861E8EBFC87EDF072C3ADC10CE0B191382F405D4347B5C40E04AD1C5
Pages : 1