为什么我使用JavaScript更改消息时RSA加密解密是错误的？

Question

RSA是一种基于大整数因式分解的加密算法。在 RSA 中，生成两个大质数和一个补充值作为 public 密钥。任何人都可以使用 public 密钥来加密消息，但只有那些拥有质因数的人才能解码消息。该过程分为三个阶段：

密钥生成 - 生成了public密钥和私钥。按键构造方法生成的应该是秘密的。
加密 - 消息可以通过public密钥
解密 - 只有私钥才能解密留言

加密过程如图：

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

解密过程如图：

c^d % n = m

这是计算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

还需要生成public密钥和私钥的密钥对。让我们选择 5 和 11 作为质数：

 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密钥：[3,55]，私钥：[27,55]

完成：加密与解密

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

}

运行它：

    
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

}

这会加密消息 2，接收方可以将其解密回 2。但是，当我将消息 2 更改为 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

}

它给出了不同的结果。我认为 3 应该是答案，有什么问题吗？

Answer 1

发布的示例使用 p = 5 和 q = 11 并确定 modulus N = 55，public 指数 e = 3 和私有指数 d = 27（由返回RSAKeyPair(5, 11))。这对应于一个有效的密钥对。

虽然使用的值很小，但中间结果可能会很大。

明文m = 3 密文c = m^e mod 55 = 27 加密结果。值 3³ = 27 显然是不重要的。

解密，然而，解密后的数据为m = c^d mod 55 = 27²⁷ mod 55. 值 27²⁷（大约 4.4 * 10³⁸）很关键，因为它高于可能的最大（安全）整数对于 JavaScript Number.MAX_SAFE_INTEGER = 2⁵³ - 1 = 9,007,199,254,740,991。这通常会导致解密时出现错误的明文。

这个问题可以通过使用BigInt来解决更大的数字：

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

当然这适用于一般情况，即不仅适用于加密和解密，而且适用于密钥生成，只要值（包括中间结果）相应地变大。

编辑： 正如评论中提到的，mod 方求幂比直接求幂（= 求幂，然后取结果 mod乌洛）。为此，也可以使用现有的库，例如bigint-mod-arith, which applies the right-to-left binary mod 平方幂的方法。

为什么我使用JavaScript更改消息时RSA加密解密是错误的？

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

javascript

encryption

rsa