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ビットを正確に超える整数を表すことはできません。ほとんどの場合、 bcmathやgmpなどのPHP多倍長ライブラリを使用する必要があります。これはまだ高速ではありませんが、少なくとも正しい結果が得られます。

于 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 から 1 までを実行して、$decryptmodded によって 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 に答える