Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 07-02-2020 13:42:13
- Rossignol
- Membre
- Inscription : 19-06-2015
- Messages : 290
La cryptographie moderne est trop !
Bonjour à tous,
Un peu de lecture pour ceux qui sont intéressés par la cryptographie moderne.
Jean-Philippe Aumasson a publié récemment un papier assez surprenant sur la robustesse des chiffres symétriques modernes. D'après lui, on pourrait diminuer le nombre de tours de ces algorithmes pour augmenter leur vitesse d'exécution, sans perdre en sécurité.
Malgré de très bons arguments, il y a peu de chance qu'il soit suivi dans cette voie ! Il est bien connu que les cryptologues sont paranoïaques.
La grande question du moment, c'est l'impact des ordinateurs quantiques en cryptographie. Ce papier, pas trop technique, fait le point sur la situation.
A retenir : si vous chiffrez des données en AES avec une clé de 256 bits, vous êtes sauf même en cas d'apparition d'un ordinateur quantique.
Par contre, les chiffres à clé publique sont tous vulnérables.
D'après ce papier récent, il faudrait 8 heures à un ordinateur quantique pour factoriser un entier RSA de 2048 bits.
Pas de panique, un ordinateur quantique avec 20 millions de qubits, c'est de la science-fiction !
@+
Hors ligne
#3 21-06-2020 15:58:56
- gilles06270
- Membre
- Inscription : 21-06-2020
- Messages : 15
Re : La cryptographie moderne est trop !
Bonjour,
Je me suis mis récemment a la cryptographie sur les courbes elliptiques et j'ai un problème de compréhension et d’exécution concernant l'encodage et surtout le décodage d'un caractère sur une courbe elliptique de type Weierstrass de la forme y2(modP)=(x3+ax+b)(modP).
J'utilise l’échange de clefs par la méthode Massey-Omura sur une courbe elliptique avec (a=-1, b=188, P=751, N=727 et G[x,y]=[161,1]
En fait j'ai trouve la façon d'encoder un caractère ASCII sur la courbe ou j'obtiens bien un point appartenant a celle-ci, mais je n'arrive pas a retrouver le caractère ASCII a partir de ce même point.
Est-ce que quelqu'un peut m'aider a comprendre et aussi savoir si je suis bien au bon endroit pour poser ma question ?
Voila mon code Python pour encoder un caractère sur une courbe elliptique:
dm: caractère ascii a encoder
curve: courbe elliptique de reference
P = curve.P
zz = int((P+1)/2)
ww = int((P+1)/4)
D = 100
for J in range(1,D-1):
if enc: # Encode
X = (int(dm) + J)%P
Y2 = self.curve_result(curve, X)
if Y2 == pow(Y2,zz,P):
Y = pow(Y2,ww,P)
point = [X, Y]
if self.is_on_Curve(curve, point):
print('--> Point %s is on curve'%point)
return(point)
J'ai essayé plusieurs manières pour retrouver la valeur ascii a partir du point, mais sans résultat et de plus je n'arrive pas a trouver de documentation sur le sujet.
Est-ce que quelqu'un peut me renseigner ?
Merci a vous tous
Hors ligne
#4 21-06-2020 19:57:07
- Rossignol
- Membre
- Inscription : 19-06-2015
- Messages : 290
Re : La cryptographie moderne est trop !
Bonjour gilles06270,
Dans le chiffrement de Massey-Omura la méthode qui permet d'associer à un message (un entier) un point de la courbe elliptique est cruciale. La méthode généralement utilisée est de compléter le nombre-message avec deux chiffres. Par exemple si le message est le caractère A de code ASCII 65, on cherche s'il existe un point de la courbe d'abscisse 6500, ou bien 6501, ou bien 6502 ...etc. On prend le premier qui marche.
if enc: # Encode
X = D*int(dm) + J # pas de modulo P
Y2 = self.curve_result(curve, X)
...
On peut simplifier en prenant D = 10. On a une chance sur deux de tomber sur un résidu quadratique. Si les dix essais échouent, c’est vraiment pas de bol !
Attention, pas de modulo P pour le calcul de X sinon ce n'est pas bijectif. Le plus grand code ASCII étant 127, il faut donc $P>12799$.
Pour retrouver le message à partir du point, il suffit de faire la division entière de l'abscisse du point par D.
@+
Hors ligne
#5 22-06-2020 10:06:01
- gilles06270
- Membre
- Inscription : 21-06-2020
- Messages : 15
Re : La cryptographie moderne est trop !
Merci Rossignol,
Effectivement mon erreur était que je considérais sur le calcul de x le modulo P. C'est vrai ce n'est pas bijectif, voila donc pourquoi je ne trouvais plus mon message.
Encore Merci
A+
Hors ligne
#6 28-06-2020 17:46:29
- gilles06270
- Membre
- Inscription : 21-06-2020
- Messages : 15
Re : La cryptographie moderne est trop !
Bonjour Rossignol,
Je reviens tj sur Massey-Omura, car je bute tj sur le décodage de mon point sur la courbe.
Voila j'utilise la courbe elliptique suivante: y2(modP)=(x3+ax+b)(modP) avec les parametres suivants: (a=-1, b=188, P=751, N=727 et G[x,y]=[161,1])
J'utilise les paramètres suivants:
eA(clef privee de A) = 134,
eB(clef privee de B) = 68,
dA(clef Public de A) = 241,
dB(celf public de B) = 497
avec 1< eA < P-1 et d’après massey-omura dA = eA**-1(moduloP), soit dA= euclide_etendu(eA, P) ...
Soit le message M a envoyer de A vers B, character ascii "A"(65), son point correspondant sur la courbe elliptique est: [65001,703]
Si A veut envoyer M a B, il envoie d'abord eA.M (eA.M étant le produit scalaire de eA et M sur la courbe) a B, ensuite B lui renvoie eB.eA.M
Et pour finir A renvoie dA.eB.eA.M a B
B peut enfin décoder le message dA.eB.eA.M (sachant que dA.eA ≡ 1 (modN))
Je trouve les points suivants:
eA.M = [465,181]
eB.eA.M= [599,380]
dA.eB.eA.M=[246,698]
# Encode d'un point sur la courbe
P = curve.P
zz = int((P+1)/2)
ww = int((P+1)/4)
D = 100
for J in range(1,D-1):
X = (D*int(car) + J)
Y2 = self.curve_result(curve, X)
if Y2 == pow(Y2,zz,P):
Y = pow(Y2,ww,P)
Pm = [X, Y]
if self.is_on_Curve(curve, Pm):
print('--> Point %s is on curve'%Pm)
break
eXM = self.scalar_mult(curve, Key, Pm)
dA.eB.eA.M=[246,698]
eBm1 = inverse(eB,P)
Pour retrouver le point [65001,703] cela devrait être M = scalar_mult(curve, ebm1, [246,698]) si je ne me trompe pas.
En partant du point [246,698] je n'arrive pas a retrouver mon point d’origine [65001,703].
Je ne comprends pas ou est mon erreur, si on peut me mettre sur la voie et m'eclairer.
Merci d'avance
Hors ligne
#7 30-06-2020 19:41:40
- Rossignol
- Membre
- Inscription : 19-06-2015
- Messages : 290
Re : La cryptographie moderne est trop !
Le problème vient du fait que le module $P$ est trop petit.
La racine carrée $Y$ est "rabotée" modulo $P$ et au bout du compte tu ne peux pas retomber sur $6501$ qui est plus grand que $P = 751$.
Comme je le disais dans mon message précédent, il faut $P>12799$ si on veut des messages entre $0$ et $127$.
Python peut calculer sans problème avec des entiers de taille quelconque (dans la limite de la mémoire disponible).
Tu utilises l'algorithme d'Euclide étendu (Bézout) pour calculer l'inverse modulo $P$. Tu peux plus simplement utiliser une puissance modulaire : $n^{-1}\equiv n^{P-2} \pmod{P}$ si $n$ est premier avec $P$, d'après le petit théorème de Fermat.
@+
Hors ligne
#8 30-06-2020 21:20:58
- gilles06270
- Membre
- Inscription : 21-06-2020
- Messages : 15
Re : La cryptographie moderne est trop !
Je vois ce que tu veux dire. Je vais essayer, merci pour ton explication.
A+
Hors ligne
#9 19-07-2020 00:47:59
- gilles06270
- Membre
- Inscription : 21-06-2020
- Messages : 15
Re : La cryptographie moderne est trop !
Rossignol, j'ai une question sur les courbes elliptiques.
Je me trouve confronte a un problème de compréhension qui m’échappe.
J'ai réussi a implémenter un encodage Koblitz sur courbe elliptique, tout fonctionne bien, MAIS uniquement avec certaines courbes comme la "secp128r1" et la "secp128r2".
Avec les autres toujours de type "weierstrass" comme la "secp256k1" mon programme loupe sur l'encodage des caractères sur la courbe et je n'arrive pas a trouver un point correspondant.
Est-ce que quelqu'un peut m'expliquer pourquoi ?
Merci de votre aide
Hors ligne
#10 07-08-2020 15:39:39
- gilles06270
- Membre
- Inscription : 21-06-2020
- Messages : 15
Re : La cryptographie moderne est trop !
Bonjour,
J'ai trouve mon erreur sur mon pb precedent, c’était une mauvaise implémentation dans le calcul du "square root". Tout fonctionne normalement maintenant.
Par contre j'ai implémenté su "Massey Omura" sur la courbe elliptique "secp128r1" et je voudrais comprendre pourquoi je n'ai pas la condition (eA*dA)%P = 1 sur la courbe elliptique. En fait cette condition est verifiee avec le produit algebrique, mais pas sur le produit scalaire.
Soit:
Soit la courbe elliptique "secp128r1" ayant comme modulo P:
P = 340282366762482138434845932244680310783
Soit eA = Prime Number (tel que le pgcd(eA, P) = 1)
j'ai : eA = 222729849860841252646895880209163383018
Je calcule: dA = eA-1(modulo P)
j'obtiens: dA = 25499995906950683222942502412533395996
On a bien la vérification: (eA*dA)%P = 1 (multiplication algébrique) (1)
Maintenant j'encode le caractère M ("113") sur la courbe au point initial G, donc je fais la multiplication scalaire Pm:
(scalaire_mult retourne un point egal a k*point calcule en utilisant l'algorithme "double" et "point_add")
Soit M= 113 (message ascii a envoyer)
Pm = scalar_mult(M, curve.G) (avec curve.G = [29408993404948928992877151431649155974, 275621562871047521857442314737465260675])
j'obtiens donc: Pm = [11304, 47308684804953685417912176806684238791] qui est bien un point de la courbe.
Je calcule eA.M (produit scalaire):
eAM = scalar_mult(eA, Pm)
eAM = [329789671570620376869107999552285827632, 18576016706169931541565139651176012108]
d'apres (1) et Massey-Omura je devrais aussi avoir: Pm = scalar_mult(dA, eAM) (puisque dA = (eA-1)%P)
Je m'attendais a retrouver Pm, or je n'ai pas cela, j'obtiens:
Pm = [86073600083364677830412384662030830277, 75033663402156624835667966858367557632]
Est-ce a dire que Pm = (dA*eA*Pm)%P n'est pas vérifié avec un produit scalaire ?
Hors ligne
#11 16-08-2020 17:50:40
- gilles06270
- Membre
- Inscription : 21-06-2020
- Messages : 15
Re : La cryptographie moderne est trop !
Bonjour,
Désolé de vous avoir déranger, mais je viens de trouver mon erreur. Elle venait en fait dans le calcul de dA qui est l'inverse de eA. Le modulo utilise pour le calcul n’était pas le bon.
Tout fonctionne correctement maintenant
Encore Merci
Hors ligne
Pages : 1