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).

Répondre

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)?
soixante treize moins vingt deux
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.

Retour

Résumé de la discussion (messages les plus récents en premier)

gilles06270
07-08-2020 14:39:39

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 ?

gilles06270
18-07-2020 23:47:59

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

gilles06270
30-06-2020 20:20:58

Je vois ce que tu veux dire. Je vais essayer, merci pour ton explication.

A+

Rossignol
30-06-2020 18:41:40

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.

@+

gilles06270
28-06-2020 16:46:29

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

gilles06270
22-06-2020 09:06:01

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+

Rossignol
21-06-2020 18:57:07

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.

@+

gilles06270
21-06-2020 14:58:56

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

LEG
08-02-2020 11:40:33

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...

Rossignol
07-02-2020 12:42:13

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 !

@+

Pied de page des forums