PHP での RSA アルゴリズムの実装

/*
* RSA アルゴリズムの実装
* (C) Copyright 2004 Edsko de Vries, Ireland
*
* Licensed under the GNU Public License (GPL) )
*
* この実装は [3]
* (Java/PHP の相互運用性がテスト済み) に対して検証されています。
*
* 参照:
* [1] "応用暗号化"、Bruce Schneier、John Wiley & Sons、1996
* [2] "Prime Number Hide-and-Seek"、Brian Raiter、Muppetlabs (オンライン)
* [3] "The Bouncy Castle Crypto Package"、 Legion of the Bouncy Castle、
* (Java 用オープンソース暗号ライブラリ、オンライン)
* [4] 「PKCS #1: RSA Encryption Standard」、RSA Laboratories テクニカル ノート、
* バージョン 1.5、改訂1993 年 11 月 1 日
*/

/*
* を目的とした関数この PHP モジュールのユーザーによって使用されます。
*
* 注:
* - $key と $modulus は (10 進数の) 文字列形式の数値である必要があります
* - $message は次のようになります。バイナリデータ
* - $keylength は 8 の倍数で、ビット単位である必要があります
* - rsa_encrypt/rsa_sign の場合、$message の長さは
* ($keylength / 8) を超えてはなりません - 11 ([4] で義務付けられている)。
* - rsa_encrypt と rsa_sign はメッセージにパディングを自動的に追加します。
* rsa_encrypt の場合、このパディングはランダムな値で構成されます。 rsa_sign の場合、
* パディングは適切な数の 0xFF 値で構成されます ([4] を参照)
* - rsa_decrypt と rsa_verify はメッセージ パディングを自動的に削除します。
* - デコード用のブロック (rsa_decrypt、rsa_verify)
* ($keylength / 8) バイトの長さである必要があります。
* - rsa_encrypt と rsa_verify は公開キーを期待します。 rsa_decrypt と rsa_sign
* は秘密鍵を必要とします。
*/

function rsa_encrypt( $message, $public_key, $modulus , $keylength)
{
$padded = add_PKCS1_padding($message, true, $keylength / 8);
$number = binary_to_number($padded);
$encrypted = pow_mod($number, $public_key, $modulus);
$result =number_to_binary($encrypted, $keylength / 8);

return $result;
}

関数 rsa_decrypt($message, $private_key, $modulus, $keylength)
{
$number = binary_to_number($message);
$decrypted = pow_mod($number, $private_key, $modulus);
$result =number_to_binary($decrypted, $keylength / 8);

returnremove_PKCS1_padding($result、 $keylength / 8);
}

function rsa_sign($message 、 $private_key、 $modulus、 $keylength)
{
$padded = add_PKCS1_padding( $message, false, $keylength / 8);
$number = binary_to_number($padded);
$signed = pow_mod($number, $private_key, $modulus);
$result =number_to_binary($signed, $keylength / 8);

    return $result;
}

function rsa_verify( $message, $public_key, $modulus , $keylength)
{
return rsa_decrypt( $message, $public_key, $modulus , $keylength);
}

/*
* 一部の定数
*/

define("BCCOMP_LARGER", 1);

/*
* 実際の実装。
* PHP での BCMath サポートが必要です (--enable-bcmath でコンパイル)
*/

//--
// (p ^ q) mod r を計算します
//
// [2]:
// (a) (p ^ q) mod r の前に (p ^ q) を計算することは避けてください。これは、典型的な RSA
// アプリケーションでは、(p ^ q) _WAY_ が大きすぎます。
// (つまり、__WAY__ が大きすぎて、コンピューターのメモリに収まりません。)
// (b) それでもかなり効率的です。
/ /
// p、q、r はすべて正であり、r はゼロ以外であると仮定します。
//
// $p 自体を $q 回乗算する、より単純なアルゴリズムに注意してください。 、
// すべてのステップで "mod $r" を適用することも有効ですが、これは O($q) ですが、この
// アルゴリズムは O(log $q) です。大きな違い。
//
// 私が見る限り、私が使用しているアルゴリズムは最適です。部分的な結果の計算には冗長性はありません
//。
//--
function pow_mod($p, $q, $r)
{
// $q から 2 のべき乗を抽出
$factors = array();
$div = $q;
$power_of_two = 0;
while(bccomp( $div, "0") = = BCCOMP_LARGER)
{
        $rem = bcmod($div, 2);
$div = bcdiv($div, 2);

if($rem) array_push($factors, $power_of_two);
$ power_of_two++;
}

// 各部分を使用して、各因子の部分結果を計算します
// 次の開始点としての結果。これは、
// 昇順に生成される 2 の因数に依存します。
$partial_results = 配列();
$part_res = $p;
$idx = 0;
foreach($factors as $factor)
{
while($idx < $factor)
{
$part_res = bcpow($part_res 、 "2");
$part_res = bcmod($part_res, $r);

$idx++;
}
        
array_pus($partial_results, $part_res);
}

// 最終結果の計算
$result = "1";
foreach($partial_results as $part_res)
{
$result = bcmul($result, $part_res);
$result = bcmod($result, $r);
}

return $result;
}

//--
// 復号化された文字列にパディングを追加する関数
// 知っておく必要がありますこれが秘密鍵または公開鍵の操作である場合 [4]
//--
function add_PKCS1_padding( $data、 $isPublicKey、 $blocksize )
{
$pad_length = $blocksize - 3 - strlen($data);

if($isPublicKey)
{
$block_type = " x02";

$padding = "";
        for($i = 0; $i $pad_length; >$i++) { $rnd

= mt_rand(1, 255) ; $padding
.= chr($rnd); } }
else

{ $ block_type

= "x01"; $padding
= str_repeat("xFF", $pad_length); }
return

"x00" . $block_type . $padding . "x00" . $data;}
//
--
// 復号化されたデータからパディングを削除しますstring// 詳細については、[4] を参照してください。//--


function Remove_PKCS1_padding(
<🎜) >$data, $blocksize){ assert
(
strlen($data) == $blocksize);    $data = substr($data, 1);

// ブロックタイプには対応できません0
if($data{0} == ' ')
die("ブロック タイプ 0 は実装されていません。") ;

// この場合、ブロック タイプは 1 または 2 でなければなりません
assert(($data{0} == "x01") || ($data{0} == "x02"));

// パディングを削除します
$offset = strpos($data, " ", 1);
return substr( $data、 $offset + 1);
}

//--
// バイナリ データを 10 進数に変換します
//--
関数 binary_to_number($data)
{
$base = "256";
$radix = "1 ";
    $result = "0";

for($i = strlen($data) - 1$i >0; >$i--) { $digit

= ord($data{$i}) ; $part_res
= bcmul($digit, $radix); $result
= bcadd($result, $part_res); $radix
= bcmul ($radix, $base); }
return

$result;}
//
--
// 数値をバイナリ形式に変換します//--

functionnumber_to_binary (
$number, $blocksize){ $base

= "256"; $result
= ""; $div

= $number;    その間($div > 0)
{
$mod = bcmod ($div, $base);
$div = bcdiv($div, $base);

$result = chr($mod) . $result;
}

return str_pad($result、 $blocksize、 "x00", STR_PAD_LEFT);
}
?>