Scribd Logo
Importer

Bienvenue sur Scribd !

  • 60 vues

    RSA

    Transféré par

    Rami ben salem
    L'algorithme RSA est décrit, expliquant la création des clés publiques et privées à partir de nombres premiers, le chiffrement et déchiffrement de messages via des exponentiations modulaires, avec un exemple numérique. Le document présente également l'alphabet de substitution et donne des instructions pour chiffrer puis déchiffrer manuellement un texte avec l'algorithme RSA.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PPTX, PDF, TXT ou lisez en ligne sur Scribd

    RSA

    Transféré par

    Rami ben salem
    60 vues9 pages
    L'algorithme RSA est décrit, expliquant la création des clés publiques et privées à partir de nombres premiers, le chiffrement et déchiffrement de messages via des exponentiations modulaires, avec un exemple numérique. Le document présente également l'alphabet de substitution et donne des instructions pour chiffrer puis déchiffrer manuellement un texte avec l'algorithme RSA.

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PPTX, PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    L'algorithme RSA est décrit, expliquant la création des clés publiques et privées à partir de nombres premiers, le chiffrement et déchiffrement de messages via des exponentiations modulaires, avec un exemple numérique. Le document présente également l'alphabet de substitution et donne des instructions pour chiffrer puis déchiffrer manuellement un texte avec l'algorithme RSA.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PPTX, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pptx, pdf ou txt
    60 vues9 pages

    RSA

    Transféré par

    Rami ben salem
    L'algorithme RSA est décrit, expliquant la création des clés publiques et privées à partir de nombres premiers, le chiffrement et déchiffrement de messages via des exponentiations modulaires, avec un exemple numérique. Le document présente également l'alphabet de substitution et donne des instructions pour chiffrer puis déchiffrer manuellement un texte avec l'algorithme RSA.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PPTX, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pptx, pdf ou txt
    sur 9

    RSA

    Chiffrement RSA

    • Le chiffrement RSA (nommé par les initiales de ses trois inventeurs) est un
    algorithme de cryptographie asymétrique, très utilisé dans le commerce
    électronique, et plus généralement pour échanger des données
    confidentielles sur Internet. Cet algorithme a été décrit en 1977 par Ronald
    Rivest, Adi Shamir et Leonard Adleman. RSA a été breveté par le
    Massachusetts Institute of Technology (MIT) en 1983 aux États-Unis. Le
    brevet a expiré le 21 septembre 2000.
    Principe

    • Le chiffrement RSA est asymétrique : il utilise une paire de clés (des nombres entiers) composée d'une
    clé publique pour chiffrer et d'une clé privée pour déchiffrer des données confidentielles. Les deux clés
    sont créées par une personne, qui souhaite que lui soient envoyées des données confidentielles. Cette
    personne rend la clé publique accessible. Cette clé est utilisée par ses correspondants pour chiffrer les
    données qui lui sont envoyées. La clé privée est quant à elle réservée à son créateur, et lui permet de
    déchiffrer ces données. La clé privée peut aussi être utilisée par cette personne pour signer une
    donnée qu'elle envoie, la clé publique permettant à n'importe lequel de ses correspondants de vérifier
    la signature.
    • Une condition indispensable est qu'il soit « calculatoirement impossible » de déchiffrer à l'aide de la
    seule clé publique, en particulier de reconstituer la clé privée à partir de la clé publique, c'est-à-dire
    que les moyens de calcul disponibles et les méthodes connues au moment de l'échange (et le temps
    que le secret doit être conservé) ne le permettent pas.
    • Le chiffrement RSA est souvent utilisé pour communiquer une clé de chiffrement symétrique, qui
    permet alors de poursuivre l'échange de façon confidentielle.
    Création des clés
    L'étape de création des clés est à la charge du récepteur. Elle n'intervient pas à chaque chiffrement car les clés
    peuvent être réutilisées, la difficulté première est que l’emetteur soit bien certain que la clé publique qu'il
    détient est celle du recepteur. Le renouvellement des clés n'intervient que si la clé privée est compromise, ou
    par précaution au bout d'un certain temps (qui peut se compter en années).
    • Choisir « p » et « q », deux nombres premiers distincts ;
    • calculer leur produit « n = pq », appelé module de chiffrement ;
    • calculer « φ(n) = (p - 1)(q -1) »;
    • choisir un entier naturel « e » premier avec « φ(n) » et strictement inférieur à « φ(n) », appelé exposant de
    chiffrement ;
    • calculer l'entier naturel d, inverse de e modulo « φ(n) », et strictement inférieur à « φ(n) », appelé exposant de
    déchiffrement ;
    Comme e est premier avec « φ(n) », d'après le théorème de Bachet-Bézout il existe deux entiers d et k tels que
    « ed + kφ(n) = 1 », c'est-à-dire que « ed ≡ 1 ( mod φ(n) ) » : « e » est bien inversible modulo « φ(n) ».
    Le couple « (n,e) » est la clé publique du chiffrement, alors que le couple « (n,d) » est sa clé privée.
    Chiffrement du message

    • Si « M » est un entier naturel strictement inférieur à « n » représentant un


    message, alors le message chiffré sera représenté par:

    C =Me mod(n)
    Déchiffrement du message

    • Pour déchiffrer « C », on utilise « d », l'inverse de « e » modulo ((p-1)(q-1)), et


    on retrouve le message clair « M » par:

    M =Cd mod(n)
    Exemple
    Un exemple avec de petits nombres premiers (en pratique il faut de très grands nombres premiers) :

    1. on choisit deux nombres premiers p = 3, q = 11 ;


    2. leur produit n = 3 x 11 = 33 est le module de chiffrement ;
    3. φ(n) = (3-1) x (11-1) = 2 x 10 = 20 ;
    4. on choisit e= 3 (premier avec 20) comme exposant de chiffrement ;
    5. l'inverse de 3 modulo 20 est d =7 (ed = 3 x 7 = 1 mod 20), l'exposant de déchiffrement.
    La clé publique est (n,e) = (33,3), et sa clé privée est (n,d) = (33,7).
    Chiffrement de M = 4 avec la clé publique : 43 = 64 mod (33) = 31,
    le chiffré est C = 31
    Déchiffrement de C = 31 avec la clé privée : 317 = 27512 614 111 mod (33) = 4,
    Le message intial M = 4.
    l'algorithme d'Euclide étendu
    ########## On cherche l'inverse de b (mod n) ##############
    n0 := n
    b0 := b
    t0 := 0
    t := 1
    q := nombre entier immédiatement inférieur ou égal à n0/b0
    r := n0 - q * b0
    Tant que r > 0 faire
    Début
    temp := t0 - q * t
    Si temp >= 0 alors temp := temp mod n, sinon temp := n - ((-temp)
    mod n) fin si
    t0 := t
    t := temp
    n0 := b0
    b0 := r
    q := nombre entier immédiatement inférieur ou égal à n0 / b0
    r := n0 - q * b0
    Fin
    Si b0 != 1 alors b n'a pas d'inverse modulo n, sinon b-1 mod n = t
    Exercice
    • Chiffrer et déchiffrer a la main le texte suivant avec l’algorithme RSA (si votre calculatrice n’y arrive pas
    utilisez vos ordinateurs):
    p=47 n=?
    q=59 φ(n)=?
    e=335 d=? ( e.d + k.φ(n) = 1) (e.d=1 mod φ (n) )

    • Texte: ceci est un algorithme asymetrique


    • alphabet: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
    a b c d e f g h i j k l m n o p q r s t u v w x y z
    28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

    • Résultat:?
    • Rq: Si le texte est simplement codé en entier puis chiffrer nous nous retrouverons dans le cas d’un
    chiffrement par substitution monoalphabétique, qu’on pourra casser par simple analyse de fréquence, pour
    éviter cela, nous allon regrouper les entier par bloc de taille supérieure et dont les valeurs ne doivent pas
    dépassés “n”
    • Mohamed ⇒ 13 42 35 28 40 32 31 ⇒ 013 423 528 403 231 (on ajoute des “0” au debut si le nombre de caractère
    n'ai pas divisible par la taille du bloc)

    Vous aimerez peut-être aussi