Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Répondre
Résumé de la discussion (messages les plus récents en premier)
- HappyMadMan
- 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.
- Centron
- 29-01-2010 14:22:22
Salutations à HappyMadMan
Effectivement le facteur 2 peut produire d'autrs valeurs pour d.
Mais pas toujours.Voici un exemple très simple :
p = 23 q = 31 n=313 phi = 660 lambda = 330
e premier avec phi, je choisis e = 7
Alors 7*d = 1 mod 660 donne d = 283
mais 7*d = 1 mod 330 donne la même valeur 283.
Le système RSA admet l'utilisation de la fonction Lambda(n).
Voir à ce sujet le Wikipedia américain à :
<http://en.wikipedia.org/wiki/rsa>
Carmichael est un mathématicien américain actif au début du siècle précédent, il travaillait sur la théorie des nombres.
Je suppose que c'est lui qui a découvert les nombres de Carmichael,
nombres commposés mais qui dans Fermat se comportent comme des
nombres premiers tel que 561 = 3*11*17.
Cordialement
Centron
- HappyMadMan
- 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
- Centron
- 27-01-2010 20:23:02
Salutation à HappyMadMan
Ce que vous constatez peut se produire lorsque les quantités (p - 1) et (q - 1)
ont un facteur commun important.
Regardez si (e * d - 1) est divisible séparément par (p - 1) et (q - 1)
Il existe une autre indicatrice : lambda(n) = (p-1)*(q-1)/f où f est le facteur
commun de (p-1) et (q-1).
On l'appelle parfois fonction de Carmichael.
Cordialement
Centron
- HappyMadMan
- 27-01-2010 10:29:55
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