0

嗨，我需要在 php 中自己实现 RSA 算法。我唯一有问题的是计算私钥的部分。我的函数的工作方式是获取一个随机数并检查它是否适合私钥公式。这很好用，但是唯一的问题是当使用非常大的数字时，它需要很长时间并且页面超时。我想知道，有没有更好的方法可以实现这一点而不必继续生成随机数？这是所需的代码：

$decrypt = rand(1,($phi-1));
while(!private($decrypt, $encrypt, $phi)){
$decrypt = rand(1,($phi-1));
}

...

function private($decrypt, $encrypt, $phi) {

 if(($decrypt * $encrypt) % ($phi) == 1){
 Return true;
 }
 else{
 Return false;
 }
}
4

2 回答 2

1

这种方法行不通。PHP 数字类型是双精度浮点数，因此不能精确表示超过 53 位的整数。您很可能需要使用 PHP 多精度库，例如bcmath或gmp。这仍然不会很快，但它至少会给出正确的结果。

于 2012-11-14T23:42:30.340 回答
0

选项1：

您最好按顺序执行此操作。您的 rand() 可以找到以前使用过的数字。假设你的最大值是 10，要求的数字是 8 或 4，使用 rand() 你可以得到 3,5,9,10,3,6,2,7,3,6,9,10,1,3, 5,6,3,7,8 在找到答案之前。如果您按顺序运行，您最多可以调用 10 次来获取它。

但是，您需要一个随机数，因此您可能应该从一个随机数开始，然后按顺序增加，直到获得命中 - 这样您可以得到 8 个，也可以得到 4 个，具体取决于您的起点。

选项 2：

在那之后，还有其他数学方法可以解决。从一个随机数开始，计算模数是多少，以及与 1 的差值（如果为负，则添加$phi）。然后你可以从 1 运行$decrypt到找出修改后的数字与 1 有什么不同，然后添加它来加密你的响应。

$decrypt = 7
$encrypt = 9
$phi = 3
($decrypt * $encrypt) % ($phi) = 0
$differenceInMod = 1 - ($decrypt * $encrypt) % ($phi) = 1;
if ($differenceInMod < 0) {
    $differenceInMod+=$phi;
}
for($i = 1; $i<$decrypt; $i++) {
   if (($decrypt * $i) % ($phi) == $differenceInMod) {
      $validEncrypt = $encrypt + $i;
      break;
   }
}

可能没有比直接顺序更快（选项 1） - 但数字更小，你有限制。

于 2012-11-15T00:31:24.373 回答