Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 07-02-2020 12: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

#2 08-02-2020 11:40:33

LEG
Membre
Inscription : 19-09-2012
Messages : 690

Re : La cryptographie moderne est trop !

Et combien pour un RSA de 2^64 bits; 2^128 ; 2^256...on serra toujours limité par la mémoire, même pour un ordinateur quantique  ...Donc pas de souci...

Hors ligne

#3 21-06-2020 14: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 18: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.

for J in range(D):
    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 09: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 16: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 18: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 20: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 18-07-2020 23: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 14: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 16: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

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
deux plus quatre-vingt onze
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums