Why RSA Encryption decryption is wrong when I change the message using JavaScript?

user_10233884 0
Viewed 355

RSA is an encryption algorithm based on factoring large integers. In RSA, two large prime numbers and a supplementary value are generated as public key. Anyone can use the public key to encrypt a message, but only those with the prime factors can decode the message. There are three phases in the process:

  1. key generation - The public key and private key are generated. The construction method of the keys generated should be secret.
  2. encryption - The message can be encrypted via public key
  3. decryption - Only the private key can be used to decrypt the message

Encryption process is as shown:

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

Decryption process is as shown:

c^d % n = m

This is the implementation of calculating 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

Key pairs of a public key and a private key also need to be generated. Let’s pick 5 and 11 as the primes:

 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) //Public key: [3,55], Private key: [27,55]

Complete: Encryption and Decryption

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

}

Run it:

    
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

}

This encrypts the message 2, and the receiver can decrypt that back to 2. However, when I change the message 2 to 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

}

It gives different result. I expect 3 should be the answer, what is wrong?

rsa encryption javascript
1 Answers

The posted example uses p = 5 and q = 11 and determines for the modulus N = 55, the public exponent e = 3 and the private exponent d = 27 (returned by RSAKeyPair(5, 11)). This corresponds to a valid key pair.

Although small values are used, the intermediate results can be quite large.

With the plaintext m = 3 the ciphertext c = me mod 55 = 27 results for the encyrption. The value 33 = 27 is obviously uncritical.

For decryption, however, the decrypted data is m = cd mod 55 = 2727 mod 55. The value 2727 (approx. 4.4 * 1038) is critical, since it is above the maximum (safe) integer possible for JavaScript Number.MAX_SAFE_INTEGER = 253 - 1 = 9,007,199,254,740,991. This generally results in a wrong plaintext during decryption.

The problem can be solved by using BigInt for larger numbers:

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));
}

Of course this applies in general, i.e. not only to encryption and decryption, but also to the key generation, as soon as the values (including intermediate results) become accordingly large.

Edit: As mentioned in the comment, there are more efficient implementations for modular exponentiation than the direct one (= exponentiate, then taking the result modulo). For this, also existing libraries can be used, e.g. bigint-mod-arith, which applies the right-to-left binary method for modular exponentiation.

user_90140970
Related