如何解决C++编写RSA密钥生成代码时出现的浮点异常core dumped问题

直接崩溃原因 #

你的floating point exception核心转储是除以零导致的，问题出在getE函数返回了0，后续getPrivateKey中执行(k*(n_)+1)/e_时触发除零异常。

代码中的核心错误点 #

• isPrime质数判定函数完全错误 #

  1. 没有处理number <= 1的边界情况，这类输入会导致函数没有返回值，触发未定义行为
  2. 循环逻辑错误：只要第一个除数2不整除输入值，就直接返回true，导致9、15这类非质数会被判定为质数，比如9%2=1就直接返回真，完全不符合质数判定逻辑
  3. 循环边界可以优化到sqrt(number)，不用到number/2，效率更高
     修复后的参考代码：

  bool isPrime(int number) {
    if (number <= 1) return false;
    if (number == 2) return true;
    if (number % 2 == 0) return false;
    for(int i = 3; i <= sqrt(number); i += 2) {
      if(number % i == 0) {
        return false;
      }
    }
    return true;
  }
  

• getE公钥指数生成函数逻辑完全错误 #

  1. RSA要求公钥e满足三个条件：1 < e < 欧拉函数v、e和v互质，你当前的判断条件完全不符合要求，还会大概率返回0或者不符合要求的值
  2. 你写的e/n_ == 0是无意义的整数除法判定，对你的需求没有任何帮助
     你需要先实现一个求最大公约数的gcd函数，再改造getE：

  int gcd(int a, int b) {
    while(b) {
      int temp = b;
      b = a % b;
      a = temp;
    }
    return a;
  }
  
  // 注意这里要传v（欧拉函数值）不是n
  int getE(int v){
    int e;
    do{
      e = rand() % (v-2) + 2; // 保证e在2到v-1之间
    } while(gcd(e, v) != 1); // 直到e和v互质
    return e;
  }
  

• getPrivateKey私钥生成逻辑完全错误 #

  RSA私钥d要求满足e*d ≡ 1 mod v，也就是d是e在模v下的乘法逆元，你当前的随机取k再除法的逻辑完全不符合要求，建议用扩展欧几里得算法求逆元，参考实现：

  int extGcd(int a, int b, int &x, int &y) {
    if (b == 0) {
      x = 1;
      y = 0;
      return a;
    }
    int g = extGcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
  }
  
  int modInv(int a, int m) {
    int x, y;
    int g = extGcd(a, m, x, y);
    if (g != 1) return -1; // 不存在逆元
    return (x % m + m) % m; // 保证返回正数
  }
  
  int getPrivateKey(int e, int v){
    int d = modInv(e, v);
    cout << "private key: " << d << endl;
    return d;
  }
  

• 其他次要问题 #

  1. 缺少<iostream>头文件，你用到了cout但没有引入对应头文件，部分编译器会报错
  2. getVscomposta、getNpri函数当前完全没有生效，你可以后续根据需求调整
  3. 主函数调用getE的时候要传v不是n，修改为int e = getE(v);

内容的提问来源于stack exchange，提问作者Elia Todescato