2021年9月19日
今回はほぼ趣味でRSA暗号を作成してみました。
数学が壊滅的に苦手なので細かく書いていきます。
目次
環境
この記事の作成環境は
xampp:3.2.4
PHP:7.4.6
エディタ:VisualStudioCode
で作成しました。
xamppをインストールした際の状況からiniファイルの一部を変更しており、具体的には
GMP関数という数学系関数を使用するため、extension=gmpのコメントアウトを外しています。
本記事の関数を実際に使用する際にはapacheを起動する前にコメントアウトを外してください。
extension=gmp
RSA暗号とは
RSA暗号（RSAあんごう）とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。
引用:Wikipedia
今回はWikipediaさんの記事内に書かれている暗号方式を参考にし、鍵生成、暗号化、復号の3つを作成しました。
鍵生成
生成するのは一つの秘密鍵と二つの公開鍵
素数:p,q
秘密鍵:d
公開鍵:n,e
p,q(ただしp≠q)の素数を用意し
n = pq とする
eをφ(n)未満の正の整数でφ(n)と互いに素な数とする
eは互いに素な数でφ(n)未満の数であればどんな数でも構わない。
どんな数でも構わないので、今回は0からφ(n)未満のランダムな数を選び、互いに素な数になるまで1減算し計算しました。素な数はかなりの高確率で見つかるので計算量の心配は大丈夫です。
φ(n)のφとはオイラーのφ関数といい、φ(n)は(p - 1)(q - 1)と同意義である。
互いに素な数とは二つ以上の整数の最大公約数が１であるときである。
dを、φ(n)を法としたeの逆数(de≡1 (mod φ(n)))とする
法とは「割る数」の事である。
逆数とはある数に掛け算した結果が1となる数である。
modとは剰余演算、モジュロとも呼ばれ、ある数値を別の数値(法)で除算し、余りを取得する演算である
// 鍵の生成
// 引数の素数は莫大な大きさの素数を使うことを推奨する
function rsa_key_generate(
$p // 素数１
,$q // 素数2
){
// 素数が一緒だとfalse
if($p === $q){
return false;
}
// 鍵生成
$n = (string)gmp_mul($p, $q); // mul-> 乗算
$n_ = gmp_mul( gmp_sub($p, '1'), gmp_sub($q, '1')); //sub-> 減算 (p-1)(q-1)
$rand = gmp_random_range( 0, gmp_sub($n_, '1')); // random_range-> ランダムな数 0 ~ (n')
// 互いに素な数が見つかるまで
while (true) {
$coprime_numbers = (string)gmp_gcd($rand, $n_); // gcd-> 最大公約数を返す
// 最大公約数が1なら互いに素な数
if ($coprime_numbers === '1') {
$e = (string)$rand;
break;
}
// 非互いに素な数減算し再計算
$rand = gmp_sub($rand, '1'); // rand--;
}
$d = (string)gmp_invert($e, $n_); // n'を法としたeの逆数
// 秘密鍵:d 公開鍵:n,e
return [$d, $n, $e];
}
暗号化
生成するのは暗号文b
平文:a
公開鍵:n,e
暗号文:b
aを平文空間Znの元とする。b = a^e mod n (nを法とする剰余)を計算し、bを出力する。
元(げん)とは,集合を構成する個々の数学的対象のことである。
つまりaを構成する複数の値全てにこの計算を実施し出力する事である。
// RSA暗号化
function rsa_encryption(
$a // 暗号化対象,平文
,$n // 公開鍵1
,$e // 公開鍵2
){
$b = [];
foreach ($a as $value) {
// aの一つをe乗する
$a_e = gmp_pow($value, $e); // pow-> べき乗
// e乗した値をnで割った余りを格納
$b[] = (string)gmp_div_r($a_e, $n); // div_r-> 剰余
}
return $b;
}
復号
生成するのは復号された文a'
暗号文:b
秘密鍵:d
公開鍵:n
復号文:a'
bを暗号文とするa' = b^d mod n を計算し、a'を出力する。ここで a' = aとなり、復号できる。
// RSA復号
function rsa_composite(
$b // 暗号文
,$d // 秘密鍵
,$n // 公開鍵n
){
$a = [];
foreach ($b as $value) {
// bの一つをd乗する
$b_d = gmp_pow($value, $d); // pow-> べき乗
// d乗した値をnで割った余りを格納
$a[] = (string)gmp_div_r($b_d, $n); // div_r-> 剰余
}
return $a;
}
文字列を数値配列に
生成するのは文字列を数値配列に
文字列:str
数値配列:ord_array
これを実行する理由は暗号化の際、文字列を構成する複数の値を計算するため文字一つ一つを数値に変換しなければなりません。なので文字列を分割し全て数値に変換しましょう。
// 平文を数値配列に変換
function convert_string_to_integer(
$str
){
// 初期配列
$ord_array = [];
// 文字列を全て数値配列に
for ($i = 0; $i < mb_strlen($str); $i++) {
// 一文字取得
$value = mb_substr($str, $i, 1);
// 文字を数値に
$ord_array[] = mb_ord($value);
}
return $ord_array;
}
数値配列を文字列に
生成するのは数値配列を文字列に
数値配列:int_array
文字列:chr
これを実行する理由は復号した際それはただの数値配列なのでそれを人が読めるよう文字列に変換しなければなりません。なので配列の数値を全て文字に変換し、文字列連結を繰り返して読めるようにしましょう。
// 数値配列を文字列に変換
function convert_integer_to_string(
$int_array
){
// 初期文字列
$chr = '';
// 配列の数値を全て文字列に変換
foreach ($int_array as $value) {
// 数値を文字列に
$chr .= mb_chr($value);
}
return $chr;
}
使用方法
全関数をコピー可能
AllFunction
// 鍵の生成
// 引数の素数は莫大な大きさの素数を使うことを推奨する
function rsa_key_generate(
$p // 素数１
,$q // 素数2
){
// 素数が一緒だとfalse
if($p === $q){
return false;
}
// 鍵生成
$n = (string)gmp_mul($p, $q); // mul-> 乗算
$n_ = gmp_mul( gmp_sub($p, '1'), gmp_sub($q, '1')); //sub-> 減算 (p-1)^(q-1)
$rand = gmp_random_range( 0, gmp_sub($n_, '1')); // random_range-> ランダムな数 0 ~ (n')
// 互いに素な数が見つかるまで
while (true) {
$coprime_numbers = (string)gmp_gcd($rand, $n_); // gcd-> 最大公約数を返す
// 最大公約数が1なら互いに素な数
if ($coprime_numbers === '1') {
$e = (string)$rand;
break;
}
// 非互いに素な数減算し再計算
$rand = gmp_sub($rand, '1'); // rand--;
}
$d = (string)gmp_invert($e, $n_); // n'を法としたeの逆数
// 秘密鍵:d 公開鍵:n,e
return [$d, $n, $e];
}
// ========================================================
// RSA暗号化
function rsa_encryption(
$a // 暗号化対象,平文
,$n // 公開鍵1
,$e // 公開鍵2
){
$b = [];
foreach ($a as $value) {
// aの一つをe乗する
$a_e = gmp_pow($value, $e); // pow-> べき乗
// e乗した値をnで割った余りを格納
$b[] = (string)gmp_div_r($a_e, $n); // div_r-> 剰余
}
return $b;
}
// ========================================================
// RSA復号
function rsa_composite(
$b // 暗号文
,$d // 秘密鍵
,$n // 公開鍵n
){
$a = [];
foreach ($b as $value) {
// bの一つをd乗する
$b_d = gmp_pow($value, $d); // pow-> べき乗
// d乗した値をnで割った余りを格納
$a[] = (string)gmp_div_r($b_d, $n); // div_r-> 剰余
}
return $a;
}
// ========================================================
// 平文を数値配列に変換
function convert_string_to_integer(
$str
){
// 初期配列
$ord_array = [];
// 文字列を全て数値配列に
for ($i = 0; $i < mb_strlen($str); $i++) {
// 一文字取得
$value= mb_substr($str, $i, 1);
// 文字を数値に
$ord_array[] = mb_ord($value);
}
return $ord_array;
}
// ========================================================
// 数値配列を文字列に変換
function convert_integer_to_string(
$int_array
){
// 初期文字列
$chr = '';
// 配列の数値を全て文字列に変換
foreach ($int_array as $value) {
// 数値を文字列に
$chr .= mb_chr($value);
}
return $chr;
}
暗号化と復号の使用例
SampleCode
// 平文
$a = [35501,12435,12391,12367,12428,12390,12354,12426,12364,12392,12358];
// 素数取得
$p = gmp_nextprime(512);
$q = gmp_nextprime(256);
// 鍵生成
$keys = rsa_key_generate($p, $q);
$d = $keys[0]; // 秘密鍵
$n = $keys[1]; // 公開鍵
$e = $keys[2]; // 公開鍵
// 暗号化
$b = rsa_encryption($a, $n, $e);
// 復号
$a_ = rsa_composite($b, $d, $n);
var_dump($a_);
留意すること
鍵の生成に使ったpとq
RSA暗号の鍵生成で使用する素数p,qは鍵を生成した後は安全に破棄すること。
pとqに使う素数は大きく
素数p,qは可能な限り大きな素数を使用すること、大きな素数であればあるほどセキュリティがより堅牢になる。また、小さすぎる数値だと公開鍵nの数値が小さくなり、その数値より大きなUnicodeなどの数値を扱えなくなる。
計算時間
暗号化や復号の際、べき乗をしているので計算量が莫大になり、使用者の端末のパフォーマンスに依存するが時間がかかる可能性があるので本格的に導入するとき以外にはそこそこの大きさの素数にするといいだろう。
キャストを行う理由
本記事のコードでは所々でキャストを行っているが、これはGMP関数を使用した際返り値がGMPオブジェクトという独自のクラスが帰ってきている為、そのオブジェクトを文字列に変換し、データを送りやすくするためである。
暗号文を送るときの配列
暗号文を送るとき、それは数値配列かと思うのでimplodeを使用して文字列にしてから送ると送りやすいかと思います。
素数を少し見つけやすく
留意する事では無いかもしれないが、大きな素数を探す際に便利な関数を紹介します。
gmp_nextprimeという次の素数を見つけるという関数を使用してもいいかもしれない。
使用関数一覧
| 関数名 | 簡易説明 |
|---|---|
| gmp_mul | 乗算 |
| gmp_sub | 減算 |
| gmp_random_range | ランダムな数 |
| gmp_gcd | 最大公約数 |
| gmp_invert | 法による逆 |
| gmp_pow | べき乗 |
| gmp_div_r | 剰余 |
| mb_strlen | 文字列の長さ |
| mb_substr | 文字列の一部 |
| mb_ord | 文字列のUnicode |
| mb_chr | Unicodeを文字列に |
| implode | 配列を,区切り等 |
| gmp_nextprime | 次の素数 |