NOMBRES – Curiosités, Théorie et Usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 25/01/2024

Orientation générale        DicoMot Math          Atlas                   Actualités                       M'écrire

Barre de recherche          DicoCulture              Index alphabétique        Références      Brèves de Maths 

            

CODAGE

 

Débutants

Général

Cryptologie

 

Glossaire

Chiffre

 

 

INDEX

 

Cryptologie

 

Théorie des nombres

 

Cryptologie

Décalage lettres

Clé publique

RSA

Codage

Bureau 47

Nombres RSA

Message

Sécurité

Pig Pen

Übchi

LLL

Nombres

 

Sommaire de cette page

>>> Bases

>>> Exemple

>>> Théorie

>>> Extension

 

 

 

 

CHIFFREMENT RSA

ou codage ou cryptage RSA

 

Chiffrement à clé asymétrique.

Pourquoi c'est sûr? Pour deux raisons au moins:

*    Utilisation d'une fonction non réversible qui repose sur les propriétés de l'arithmétique modulaire

*    Difficulté à factoriser les grands nombres

Voir principes en Clé publique / Historique

 

Inventeurs

 

R

S

A

Ronald Rivest

É.-U. né en 1947

Adi Shamir

Israël né en 1952

Leonard Adleman

É.-U. né en 1945

    

 

 

BASES

 

*    Tu veux me transmettre la valeur x.

*    Je te transmets sans précaution la clé publique (e et n).

*    Tu t'en sers pour crypter le message.

*    Tu me le transmets: y

*    Je suis le seul à pouvoir décrypter car j'ai la clé privée.
 

*    x est la valeur que tu veux coder (tu découpes le message de façon que x < n).

*    e et n sont les deux éléments de la clé publique.

*    Tu enfouis x dans un calcul qui donne y.

*    y est la valeur transmise.

*    Je calcule z

en utilisant ma clé privé d.

*    Après ce tour de passe-passe mathématique, il se trouve que z est égal à x.

 

En effet

 

z =  y d    mod n

(x e mod f) d    mod n

x ed   mod n
x 1   mod n
x

 

 Voici le calcul

 

*    La justification précise est un peu plus compliquée.

*    Tout tient dans le choix de e et f.

*    Voir l'exemple ci-dessous.

Voir Théorie du modulo

 

EXEMPLE

Ma sauce à moi      (préparation des clés)

*    Deux nombres premiers tenus secrets

p et q

3 et 7

*    Son produit n est diffusé

n = p.q

n = 21

*    On calcule f

f = (p – 1) (q – 1)

f = 2x6 = 12

*    Un nombre e est, lui aussi, diffusé

e premier avec f

e = 5

*    Je calcule d, inverse de e mod f

e.d = 1 mod f

5d = 1 mod 12

5x5 = 1 mod 12

d = 5

Préparation du message

*    Le message est converti en chiffres

*    On va coder chaque chiffre

x1 … xi

avec xi < n

x = 2, par exemple

Codage du message

*    Chaque x est codé par y

y = x e mod n

y = 2 5 mod 21

y = 32 mod 21

y = 11

*    Les valeurs de y sont transmises

y est transmis

11 est transmis

Déchiffrage

*    Je calcule z

z = y d mod n

 

z = 11 5 mod 21

z = 11 x121x121 mod 21

z = 11 x 16 x 16 mod 21

z = 11 x 256 mod 21

z = 11 x     4 mod 21

z = 44 mod 21

z =   2 mod 21

*    Car en fait

z = x mod n

z =   2 mod 21

 

 

THÉORIE

 

Quelques rappels théoriques

 

*    La fonction phi (n) :   est la quantité d'entiers strictement positifs inférieurs à n et premier avec n.

 

Théorème de Fermat-Euler

 

Si a est premier avec m, alors

 

 

La notation ci-dessus est la plus formelle; on peut se permettre  de simplifier lorsqu'il n'y a pas confusion. Ce sera le cas ci-dessous.

 

*    La démonstration ci-dessous est valable pour le cas général où x est premier avec n. On peut montrer que le procédé reste valable même dans les autres cas.

 

RSA - Raisonnement

 

*    Il s'agit de prouver le raisonnement suivant:

z =

y d     mod n

x ed   mod n
x

 

 

Quelques calculs préalables

 

 

*       On se souvient que

f =

(p – 1) (q – 1)

*       C'est l'indicateur d'Euler ou fonction phi de n

f =

 (n)

*       On a également

e.d=

=

1 mod f

1 mod  (n)

*       Ce qui veut dire que e.d – 1 est un multiple de phi

e.d – 1 =

k .  (n)

Expression de z

 

 

*       Si on revient à z

z =

y d mod n

(x e ) d mod n

x e . d mod n

*       On ajoute un facteur en x que l'on retire dans l'exposant

z =

x . x e . d - 1 mod n

*       On connaît la valeur de cet exposant

z =

*       Il est temps d'appliquer le théorème de Fermat-Euler

z =

x . (1) mod n

x . mod n

*       Or on a choisit x < n

z =

x

 

 

Extension

 

Merci à Pierre Noël pour cette démonstration

 

 

 

 

Suite

*    Nombres RSA

*    Algorithme LLL

*    Voir haut de page

Voir

*    Autocodes

*    Cadenas

*    Clés de cryptage

*    Codage décimal

*    Codage des lettres

*    Codage RSA

*    Code barre

*    Code ISBN des livres

*    Cryptogrammes

*    Message chiffré

*    Théorie des nombres

Livres

*      Le vol du frelon – Ken Follet – Robert Laffont – 2003 – page 92

*      La conjecture de Fermat – Jean d'Aillon – JC Lattès – 2006

*    Dossier Pour La Science spécial "La cryptographie -  l'art du secret" - juillet 2002

Cette page

http://villemin.gerard.free.fr/Crypto/RSA.htm