Recherche
Recherche

Pourquoi le décryptage RSA Encryption est-il incorrect lorsque je modifie le message à l'aide de JavaScript?

Edison Pebojot Publié le Dev
7
Edison pebojot

RSA est un algorithme de chiffrement basé sur la factorisation de grands entiers. En RSA, deux grands nombres premiers et une valeur supplémentaire sont générés comme clé publique. N'importe qui peut utiliser la clé publique pour crypter un message, mais seuls ceux avec les facteurs premiers peuvent décoder le message. Il y a trois phases dans le processus:

  1. génération de clé - La clé publique et la clé privée sont générées. La méthode de construction des clés générées doit être secrète.
  2. cryptage - Le message peut être crypté via une clé publique
  3. déchiffrement - Seule la clé privée peut être utilisée pour déchiffrer le message

Le processus de cryptage est comme indiqué:

m - message:
m^e % n = c
c - encrypted message

Le processus de décryptage est comme indiqué:

c^d % n = m

C'est la mise en œuvre du calcul de d :

function modInverse(e, phi) {
   var m0 = phi, t, q;
   var x0 = 0, x1 = 1;
  if (phi == 1)
      return 0;

  while (e > 1) {
  // q is quotient
  q = Math.floor(e / phi);

  t = phi;

  // phi is remainder now, process same as
  // Euclid's algo
  phi = e % phi, e = t;

  t = x0;

  x0 = x1 - q * x0;

  x1 = t;
}

// Make x1 positive
if (x1 < 0)
   x1 += m0;

   return x1;

 }
 modInverse(7, 40) // 23

Des paires de clés d'une clé publique et d'une clé privée doivent également être générées. Prenons 5 et 11 comme nombres premiers:

 function modInverse(e, phi) {
     var m0 = phi, t, q;
     var x0 = 0, x1 = 1;
     if (phi == 1)
         return 0;

     while (e > 1) {
       // q is quotient
       q = Math.floor(e / phi);

       t = phi;

      // phi is remainder now, process same as
      // Euclid's algo
      phi = e % phi, e = t;

      t = x0;

      x0 = x1 - q * x0;

      x1 = t;
     }

    // Make x1 positive
    if (x1 < 0)
       x1 += m0;

       return x1;

    }

    function isPrime(n){
       var prime_numbers=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
       for(let i of prime_numbers){
        if(n===i){
          return true
        }
      }
    }

   function RSAKeyPair(p, q) {
       // Need to check that they are primes
       if (!(isPrime(p) && isPrime(q)))
           return;
       // Need to check that they're not the same
       if (p == q)
           return;

           var n = p * q,
           phi = (p - 1) * (q - 1),
           e = 3,
           d = modInverse(e, phi);


          // Public key: [e,n], Private key: [d,n]
          return [[e, n], [d, n]]

        }

RSAKeyPair (5,11) // Clé publique: [3,55], Clé privée: [27,55]

Terminé: cryptage et décryptage

function modInverse(e, phi) {
    var m0 = phi, t, q;
    var x0 = 0, x1 = 1;
    if (phi == 1) {
        return 0;
    }

    while (e > 1) {
        // q is quotient
        q = Math.floor(e / phi);

        t = phi;

        // phi is remainder now, process same as
        // Euclid's algo
        phi = e % phi // 3 % 40
        e = t; // e = 40
        t = x0; // t = 0
        x0 = x1 - q * x0; // 1-0|13|3 x 0
        x1 = t; // 0
    }

        // Make x1 positive
        if (x1 < 0) {
            x1 += m0;
        }

        return x1;

    }

function isPrime(n){
    var prime_numbers=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
    for(let i of prime_numbers){
        if(n===i){
            return true
        }
    }
}

function RSAKeyPair(p, q) {
    // Need to check that they are primes
    if (!(isPrime(p) && isPrime(q))) {
        return;
    }
// Need to check that they're not the same
if (p==q) {
    return;
}

var n = p * q,
    phi = (p-1)*(q-1),
    e = 3,
    d = modInverse(e,phi);



// Public key: [e,n], Private key: [d,n]
return [[e,n], [d,n]]

}

RSAKeyPair(5,11)

for (let i in RSAKeyPair(5,11)){
    var encrypted_message;
const encryption=c=>{
    var m = 2,e = c[0], n = c[1], Encrypted_Message = m ** e % n
    console.log("Encryption: " + Encrypted_Message)
    encrypted_message=Encrypted_Message
}
const decryption=c=>{
   var d = c[0], n = c[1], Decrypted_Message = encrypted_message ** d % n
   console.log("Decryption: " + Decrypted_Message)
}
   i=="0"?encryption(RSAKeyPair(5, 11)[0]) : i == "1" ? decryption(RSAKeyPair(5, 11)[1]) : false

}

Exécuter:

    
function modInverse(e, phi) {
    var m0 = phi, t, q;
    var x0 = 0, x1 = 1;
if (phi == 1) {
    return 0;
}

while (e > 1) {
    // q is quotient
    q = Math.floor(e / phi);

    t = phi;

    // phi is remainder now, process same as
    // Euclid's algo
    phi = e % phi // 3 % 40
    e = t; // e = 40
    t = x0; // t = 0
    x0 = x1 - q * x0; // 1-0|13|3 x 0
    x1 = t; // 0
}

// Make x1 positive
if (x1 < 0) {
    x1 += m0;
}

return x1;

}

function isPrime(n){
    var prime_numbers=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
    for(let i of prime_numbers){
        if(n===i){
            return true
        }
    }
}

function RSAKeyPair(p, q) {
    // Need to check that they are primes
    if (!(isPrime(p) && isPrime(q))) {
        return;
    }
// Need to check that they're not the same
if (p==q) {
    return;
}

var n = p * q,
    phi = (p-1)*(q-1),
    e = 3,
    d = modInverse(e,phi);



// Public key: [e,n], Private key: [d,n]
return [[e,n], [d,n]]

}

RSAKeyPair(5,11)

for (let i in RSAKeyPair(5,11)){
    var encrypted_message;
const encryption=c=>{
    var m=2,e=c[0],n=c[1],Encrypted_Message=m**e%n
    console.log("Encryption: "+Encrypted_Message)
    encrypted_message=Encrypted_Message
}
const decryption=c=>{
   var d=c[0],n=c[1],Decrypted_Message=encrypted_message**d % n
   console.log("Decryption: "+Decrypted_Message)
}
i=="0"?encryption(RSAKeyPair(5,11)[0]):i=="1"?decryption(RSAKeyPair(5,11)[1]):false

}

Cela crypte le message 2, et le destinataire peut le décrypter en 2. Cependant, lorsque je change le message 2 en 3:

function modInverse(e, phi) {
    var m0 = phi, t, q;
    var x0 = 0, x1 = 1;
    if (phi == 1) {
        return 0;
    }

    while (e > 1) {
        // q is quotient
        q = Math.floor(e / phi);

        t = phi;

        // phi is remainder now, process same as
        // Euclid's algo
        phi = e % phi // 3 % 40
        e = t; // e = 40
        t = x0; // t = 0
        x0 = x1 - q * x0; // 1-0|13|3 x 0
        x1 = t; // 0
    }

    // Make x1 positive
    if (x1 < 0) {
        x1 += m0;
    }

    return x1;

}

function isPrime(n) {
    var prime_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    for (let i of prime_numbers) {
        if (n === i) {
            return true
        }
    }
}

function RSAKeyPair(p, q) {
    // Need to check that they are primes
    if (!(isPrime(p) && isPrime(q))) {
        return;
    }
    // Need to check that they're not the same
    if (p == q) {
        return;
    }

    var n = p * q,
        phi = (p - 1) * (q - 1),
        e = 3,
        d = modInverse(e, phi);



    // Public key: [e,n], Private key: [d,n]
    return [[e, n], [d, n]]

}

RSAKeyPair(5, 11)

for (let i in RSAKeyPair(5, 11)) {
    var encrypted_message;
    const encryption = c => {
        var m = 3, e = c[0], n = c[1], Encrypted_Message = m ** e % n
        console.log("Encryption: " + Encrypted_Message)
        encrypted_message = Encrypted_Message
    }
    const decryption = c => {
        var d = c[0], n = c[1], Decrypted_Message = encrypted_message ** d % n
        console.log("Decryption: " + Decrypted_Message)
    }
    i == "0" ? encryption(RSAKeyPair(5, 11)[0]) : i == "1" ? decryption(RSAKeyPair(5, 11)[1]) : false

}

Cela donne un résultat différent. J'espère que 3 devrait être la réponse, qu'est-ce qui ne va pas?

Topaco

L'exemple affiché utilise p = 5 et q = 11 et détermine pour le module N = 55, l'exposant public e = 3 et l'exposant privé d = 27 (renvoyé par RSAKeyPair(5, 11)). Cela correspond à une paire de clés valide.

Bien que de petites valeurs soient utilisées, les résultats intermédiaires peuvent être assez importants.

Avec le texte clair m = 3, le texte chiffré c = m e mod 55 = 27 résultats pour le cryptage. La valeur 3 3 = 27 n'est évidemment pas critique.

Pour le décryptage, cependant, les données décryptées sont m = c d mod 55 = 27 27 mod 55. La valeur 27 27 (environ 4,4 * 10 38 ) est critique, car elle est supérieure à l'entier maximum (sûr) possible pour JavaScript Number.MAX_SAFE_INTEGER= 2 53 - 1 = 9 007 199 254 740 991. Cela entraîne généralement un mauvais texte en clair lors du décryptage.

Le problème peut être résolu en utilisant BigIntpour des nombres plus grands:

var e = 3;
var d = 27;
var N = 55;

// Encryption
var m = 3; // getRandomInt(N) // For arbitrary plaintexts uncomment getRandomInt(N)
var c = m ** e % N;
console.log("Plaintext            : " + m);
console.log("Ciphertext           : " + c);

// Decryption without BigInt
var dec = c ** d % N;
console.log("Result without BigInt: " + dec); // Wrong

// Decryption with BigInt
var dec = BigInt(c) ** BigInt(d) % BigInt(N);
console.log("Result with BigInt   : " + dec); // Correct

function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}

Bien entendu, cela s'applique en général, c'est-à-dire non seulement au cryptage et au décryptage, mais également à la génération de clé, dès que les valeurs (y compris les résultats intermédiaires) deviennent d'autant plus importantes.

Edit: Comme mentionné dans le commentaire, il existe des implémentations plus efficaces pour l'exponentiation modulaire que la directe (= exponentiate, puis en prenant le résultat modulo). Pour cela, des bibliothèques existantes peuvent également être utilisées, par exemple bigint-mod-arith , qui applique la méthode binaire de droite à gauche pour l'exponentiation modulaire.

Cet article est collecté sur Internet, veuillez indiquer la source lors de la réimpression.

En cas d'infraction, veuillez [email protected] Supprimer.

modifier le
0

laisse moi dire quelques mots

0commentaires
connexionAprès avoir participé à la revue

Articles connexes

TOP liste

  1. 1

    Impression de la longueur du chemin le plus court dans le labyrinthe

  2. 2

    Dans les modèles Hugo, comment vérifier la longueur du tableau de fichiers JSON?

  3. 3

    Vérifier la longueur du nombre à partir du message, puis utiliser la valeur dans l'instruction

  4. 4

    Aide de variable de débogage pprint jinja2

  5. 5

    Référencement des assemblys de structure .net 4.7 dans la solution .net core 2

  6. 6

    Algorithme: diviser de manière optimale une chaîne en 3 sous-chaînes

  7. 7

    Comment changer le navigateur par défaut en Microsoft Edge pour Jupyter Notebook sous Windows 10 ?

  8. 8

    Recherche de dicton Jinja2 à l'aide d'une clé variable

  9. 9

    mongo kafka connect source

  10. 10

    Laravel 8: Attempt to read property "id" on null

  11. 11

    Comment convertir une chaîne en tuple en utilisant `reads`?

  12. 12

    Comment obtenir l'intégration contextuelle d'une phrase dans une phrase à l'aide de BERT ?

  13. 13

    Microsoft.WebApplication.targets

  14. 14

    Pourquoi cette requête Java échoue-t-elle? renvoyer 0 quand il y a des résultats

  15. 15

    Exécuter la requête externe pour chaque date obtenue à partir de la requête interne

  16. 16

    comment convertir une chaîne en un tuple dateutil jour de la semaine sans utiliser eval

  17. 17

    Comment ajouter un texte dans un texte Python/Tkinter

  18. 18

    obtenir le nombre de marqueur affiché sur la carte

  19. 19

    How to display pagination links in a blade on Laravel 8?

  20. 20

    Comment exécuter un fichier python avec des droits d'administrateur dans pycharm

  21. 21

    Je ne peux pas transférer de stockage sur le serveur. Laravel

chaudétiquette

Archive