RSA鍵の要素と暗号化

普段何気なく使っている（？）RSA鍵と暗号化アルゴリズムについての覚書。
なお、数学的な素養は皆無に等しいため、難しいこと（数式の解説）はナシ。中ではこういう計算をしているんだなという程度。

RSAの公開鍵と秘密鍵が具体的にどういう要素からなり、どうやって作られ、どのように暗号・複合に使われるのかをまとめる。

## 鍵生成のステップ（オリジナル）
1. 大きな（いわゆる鍵長の1/2程度のビット数で）素数を2つ生成する（$p$と$q$とする）
2. 以下を算出する
    + $n = p \times q$
    + $\phi = (p -1) \times (q - 1)$
3. 公開指数$e$を決定する（$1 < e < \phi$であり、$\phi$との最大公約数が1である数、つまり互いに素である）
4. 秘密指数$d$を決定する（$1 < d < \phi$であり、$e \times d \equiv 1 (mod \quad \phi)$を満たす、つまり$(e \times d) \div \phi$の余りが$1$）

つまり、最初の$p$と$q$を決めれば、あとは導出できるということになる。こうして決められた$n$と$e$が公開鍵であり、$d$、$p$、$q$が秘密鍵（知られてはいけない情報）ということになる。

ここで出てきた数値の意味は以下のようになる。

| 数値 | 呼名 | 使い道|
|:-:|:-:|:-:|
| $n$  | modulus（法）  | 暗号・複合の両方で使用する |
| $e$  | public exponent（公開指数）  |暗号化（または署名検証）で使用する|
| $d$  | private exponent（秘密指数） |複合化（または署名）で使用する|

## 暗号・複合のアルゴリズム
これは式で書くととてもシンプルで、元データに対し、公開指数（$e$）・秘密指数（$d$）でべき乗し、さらにmodulus（$n$）の剰余をとる。

式にすると次のようになる（元のデータを$m$とする）。
$c = m^e \quad mod \quad n$
$m = c^d \quad mod \quad n$
署名の場合は逆に秘密鍵で署名し、公開鍵で複合する。つまり指数の部分が逆になる（$d$で署名して$e$で複合）。

ここまでをJavaで簡単に実験してみる。$p$と$q$および暗号化対象データを引数で与えて、残りは適当に決定する。パラメタを含む各種データは、必要な演算メソッドがある`BigInteger`のインスタンスとする。

```java:SimpleRSATest.java
import java.math.BigInteger;

public class SimpleRSATest {
	public static void main(String[] args) {
		BigInteger p = new BigInteger(args[0]);
		BigInteger q = new BigInteger(args[1]);
		BigInteger m = new BigInteger(args[2]);

		//step 2. compute modulus and phi
		BigInteger n = p.multiply(q);
		BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
		System.out.println("modulus: " + n);
		System.out.println("phi: " + phi	);

		//step 3. determine public exponent
		System.out.println(System.currentTimeMillis() + " searching for public exponent ... ");
		BigInteger e = new BigInteger("2");
		while(! e.equals(phi)) {
			if(e.gcd(phi).equals(BigInteger.ONE)) {
				break;
			} else {
				e = e.add(BigInteger.ONE);
			}
		}
		System.out.println(System.currentTimeMillis() + " DONE! " + e);

		//step 4. determine private exponent
		System.out.println(System.currentTimeMillis() + " searching for private exponent ... ");
		BigInteger d = new BigInteger("2");
		while(! d.equals(phi)) {
			if(d.multiply(e).mod(phi).equals(BigInteger.ONE)) {
				break;
			} else {
				d = d.add(BigInteger.ONE);
			}
		}
		System.out.println(System.currentTimeMillis() + " DONE! " + d);

		//try it!
		System.out.println(System.currentTimeMillis() + " encrypting ... ");
		BigInteger enc = encrypt(m, e, n);
		System.out.println(System.currentTimeMillis() + " DONE! ");

		System.out.println(System.currentTimeMillis() + " decrypting ... ");
		BigInteger dec = encrypt(enc, d, n);
		System.out.println(System.currentTimeMillis() + " DONE! ");

		System.out.println(m + " -> " + enc);
		System.out.println(enc + " -> " + dec);
	}

	private static BigInteger encrypt(BigInteger msg, BigInteger exp, BigInteger mod) {
		return msg.modPow(exp, mod);
	}

}
```

`BigInteger`の`modPow()`メソッドを使えば、暗号化は1行で済む。暗号・複合ともアルゴリズムは同じで、渡すパラメタが異なるだけ（秘密指数を渡すか公開指数を渡すか）。

すぐに思い浮かぶ小さな素数（3,5）を使い、鍵長（$n = 15$なので4 bit）と比べて大きなデータを食わせてみると、、、

```text:実行結果
# java SimpleRSATest 3 5 14
modulus: 15
phi: 8
1550660446376 searching for public exponent ...
1550660446376 DONE! 3
1550660446377 searching for private exponent ...
1550660446377 DONE! 3
1550660446377 encrypting ...
1550660446378 DONE! 3
1550660446378 decrypting ...
1550660446378 DONE! 3
14 -> 14
14 -> 14
```

なんと、暗号化しても同じ数値になってしまった。というわけで、短い鍵長では解読されやすくなるどころか、小さなデータしか暗号化できない（当然13までは普通に使える）。

pとqを自動生成（`BigInteger.probablePrime()`）してビット数と暗号化対象を引数指定するように変更する。

```java:SimpleRSATest.java
		int bit = Integer.parseInt(args[0]);
		BigInteger p = BigInteger.probablePrime(bit, new Random());
		BigInteger q = BigInteger.probablePrime(bit, new Random());
		BigInteger m = new BigInteger(args[1]);
```

ここでbit数を変えながら秘密指数を決定するのにかかる時間をまとめた。

| bit | msec | private exponent|
|:-:|:-:|:-:|
| 8 bit  |  15  |17405|
| 12 bit  | 779  |9667147|
| 13 bit |1,870|23623421|
|14 bit |2,441|41887793|
|15 bit |12,006|220559501|
|16 bit |23,652|507694169|

![image.png](https://qiita-image-store.s3.amazonaws.com/0/232587/a3a446c0-4db6-8949-3ec9-2b00dd689dee.png)

文字通り指数関数的に時間が伸びていっているのがわかる。2019年現在で、2048 bit以上の鍵長が安全とされているので、このプログラムに渡す引数でいえば1024 bitの2つの素数が必要となる。単純計算（上記実測での単回帰予測）でも40分以上かかることになる（実際にはもっとかかる）。

これでは使い物にならないということで、実際には以下のような手続きでこれらのパラメータが決められる。

## 鍵生成のステップ（実際）
1. $e$を選択する（3,5,17,257,65537から選ぶ。OpenSSLでは65537を採用している。これはフェルマー数といわれ$F_x=2^{2^x} + 1$で表される。このうち$F_0$から$F_4$は素数でそれ以降は素数ではないということが知られている、らしい。なぜこのような数値を好んで使うかといえば、ビットで表現したときに"10000000000000001"のように二つの"1"に"0"が挟まれるような並びとなり、コンピュータにとって計算しやすいから。
1. $p \quad mod \quad e \neq 1$となるような$p$を決める（必要な鍵長$\frac{k}{2}$ bit）
1. 同様に$q \quad mod \quad e \neq 1$となるような$q$を決める（$k - \frac{k}{2}$ bit）
1. $n$と$\phi$を算出する（計算方法は同じ）
1. $d$を$e$と$n$のモジュラー逆数から算出する

Javaでやってみる。

```java:RefinedRSATest.java
import java.math.BigInteger;
import java.util.Random;

public class RefinedRSATest {

	public static void main(String[] args) {
        //step 1. select e
		BigInteger e = new BigInteger(args[0]);
		int bit = Integer.parseInt(args[1]);
		BigInteger m = new BigInteger(args[2]);
		Random r = new Random();

		//step 2. compute p where p mod e != 1
		BigInteger p;
		System.out.println(System.currentTimeMillis() + " searching for p ... ");
		while(true) {
			p = BigInteger.probablePrime(bit / 2, r);
			if(! p.mod(e).equals(BigInteger.ONE)) {
				break;
			}
		}
		System.out.println(System.currentTimeMillis() + " DONE! " + p);

		//step 3. compute q where q mod e != 1
		BigInteger q;
		System.out.println(System.currentTimeMillis() + " searching for q ... ");
		while(true) {
			q = BigInteger.probablePrime(bit - (bit / 2), r);
			if(! q.mod(e).equals(BigInteger.ONE)) {
				break;
			}
		}
		System.out.println(System.currentTimeMillis() + " DONE! " + q);

		//step 4. compute modulus and phi
		BigInteger n = p.multiply(q);
		BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

		//step 5. compute d from e and phi
		BigInteger d = e.modInverse(phi);

		//try it!
		System.out.println(System.currentTimeMillis() + " encrypting ... ");
		BigInteger enc = encrypt(m, e, n);
		System.out.println(System.currentTimeMillis() + " DONE! ");

		System.out.println(System.currentTimeMillis() + " decrypting ... ");
		BigInteger dec = encrypt(enc, d, n);
		System.out.println(System.currentTimeMillis() + " DONE! ");

		System.out.println(m + " -> " + enc);
		System.out.println(enc + " -> " + dec);

	}
	private static BigInteger encrypt(BigInteger msg, BigInteger exp, BigInteger mod) {
		return msg.modPow(exp, mod);
	}
}
```

実際に動かしてみると、さっきとは比較にならないほど速い。鍵長を2048 bitにしてもミリ秒単位で鍵生成と暗号・複合デモが完了した。ただし、AES256と同程度の強度であるといわれる15360 bitにするとさすがに時間がかかる（素数の生成に5分程度）。暗号・複合演算も、対象データが小さいにもかかわらず秒単位でかかる。
素数の選択が数打てば当たる作戦（`BigInteger.probablePrime()`）なのがネックになっている。`openssl genrsa 15360`では同じマシンで1分程度で鍵生成できた。

## CRT（Chinese Remainder Theorem）を使って計算を楽にする
暗号・複合は指数計算であるため、その指数（つまり公開指数や秘密指数）の桁数（=鍵長）が大きくなるほど、文字通り指数関数的に計算量が増える（ビット長$k^3$に比例）。
そこでCRT（Chinese Remainder Theorem）というアルゴリズム（とそれに付随するパラメタ）を使うことで、秘密指数を使った処理（公開鍵暗号の複合または署名）における計算量を少なくできる、らしい。
これは暗号鍵に3つのパラメタをあらかじめ計算して保存しておき、複合の演算に使うもの。
1. `dP = e.modInverse(p-1) = d.mod(p-1)`
2. `dQ = e.modInverse(q-1) = d.mod(q-1)`
3. `qInv = q.modInverse(p)`

複合時は以下の計算をする。
1. `m1 = c.modPow(dP, p)`
2. `m2 = c.modPow(dQ, q)`
3. `h = qInv.multiply(m1 - m2).mod(p)`
4. `m = m2.add(h.multiply(q))`

この辺の理屈はもう偉人の知恵と思うしかない。実装してみる。

```java:CRTRSATest.java
import java.math.BigInteger;
import java.util.Random;

public class CRTRSATest {

	public static void main(String[] args) {
        //step 1. select e
		BigInteger e = new BigInteger(args[0]);
		int bit = Integer.parseInt(args[1]);
		BigInteger m = new BigInteger(args[2]);
		Random r = new Random();

		//step 2. compute p where p mod e != 1
		BigInteger p;
		System.out.println(System.currentTimeMillis() + " searching for p ... ");
		while(true) {
			p = BigInteger.probablePrime(bit / 2, r);
			if(! p.mod(e).equals(BigInteger.ONE)) {
				break;
			}
		}
		System.out.println(System.currentTimeMillis() + " DONE! " + p);

		//step 3. compute q where q mod e != 1
		BigInteger q;
		System.out.println(System.currentTimeMillis() + " searching for q ... ");
		while(true) {
			q = BigInteger.probablePrime(bit - (bit / 2), r);
			if(! q.mod(e).equals(BigInteger.ONE)) {
				break;
			}
		}
		System.out.println(System.currentTimeMillis() + " DONE! " + q);

		//step 4. compute modulus and phi
		BigInteger n = p.multiply(q);
		BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

		//step 5. compute d from e and phi
		BigInteger d = e.modInverse(phi);

		//step 6. compute CRT parameters
		BigInteger dP = d.mod(p.subtract(BigInteger.ONE));
		BigInteger dQ = d.mod(q.subtract(BigInteger.ONE));
		BigInteger qInv = q.modInverse(p);

		//try it!
		System.out.println(System.currentTimeMillis() + " encrypting ... ");
		BigInteger enc = encrypt(m, e, n);
		System.out.println(System.currentTimeMillis() + " DONE! ");

		System.out.println(System.currentTimeMillis() + " decrypting ... ");
		BigInteger dec = encrypt(enc, d, n);
		System.out.println(System.currentTimeMillis() + " DONE! ");

		System.out.println(System.currentTimeMillis() + " decrypting with CRT... ");
		BigInteger dec2 = decryptWithCRT(enc, p, q, dP, dQ, qInv);
		System.out.println(System.currentTimeMillis() + " DONE! ");


		System.out.println(m + " -> " + enc);
		System.out.println(enc + " -> " + dec);
		System.out.println(enc + " -> " + dec2);

	}
	private static BigInteger encrypt(BigInteger msg, BigInteger exp, BigInteger mod) {
		return msg.modPow(exp, mod);
	}
	private static BigInteger decryptWithCRT(BigInteger c, BigInteger p, BigInteger q, BigInteger dP, BigInteger dQ, BigInteger qInv) {
		BigInteger m1 = c.modPow(dP, p);
		BigInteger m2 = c.modPow(dQ, q);
		BigInteger h = qInv.multiply(m1.subtract(m2)).mod(p);
		return m2.add(h.multiply(q));
	}
}
```

```text:実行結果
java CRTRSATest 3 2048 999999999999999999999
1550668984175 searching for p ...
1550668984312 DONE! 172295263676645622090142961433941938810968859634847885352718649283943335652307381531201219791947816388624709618558064722831544819543449413413862148548502398212198232129367664537071357097143783549628019289207554523026851174626782853999027976972520323381529997253896385528709711263051313039439139827764227680119
1550668984312 searching for q ...
1550668984374 DONE! 155009203774427232415058007184226622768823333917952587100167094700260097053746651573818380802922008472261364493832345544768795940502871573671874092856361700909726970886508496382455927192820287807940406629233619377446446141580086830778212683432723563860306993510142370287498036100502589223226967052825231792047
1550668984374 encrypting ...
1550668984374 DONE!
1550668984374 decrypting ...
1550668984390 DONE!
1550668984390 decrypting with CRT...
1550668984390 DONE!
999999999999999999999 -> 999999999999999999997000000000000000000002999999999999999999999
999999999999999999997000000000000000000002999999999999999999999 -> 999999999999999999999
999999999999999999997000000000000000000002999999999999999999999 -> 999999999999999999999
```

何回か実行してみたが、CRTを使わない複合に5 ms程度かかっているのに対し、CRTを使用すると1 ms以内で終了していた。対象データを大きく（第3引数を長く）してみたところ、この傾向はより顕著だった。
実際に公開鍵暗号化方式を使ってデータの暗号・複合をするケースはあまりない、というか共通鍵の交換時くらいしかないかもしれない。とはいえ、CPU時間を1/3程度にできるというのはかなり魅力的だといえる。

## OpenSSLでの確認
最後にOpenSSLでの鍵の内容を確認する。

```bash
openssl genrsa 512 | openssl rsa -text
```

```text:実行結果抜粋
modulus:
    00:bf:80:e8:d4:ef:e4:81:b2:e8:66:fa:9f:6f:2e:
    66:ef:80:5a:fd:be:5a:39:bc:6b:74:86:43:f0:c2:
    42:0b:f6:ce:83:d8:a8:40:e3:8d:8f:42:c1:b0:d9:
    d5:ca:32:9c:e6:99:3c:d7:1e:34:e3:e9:76:26:4e:
    7e:14:61:b8:1b
publicExponent: 65537 (0x10001)
privateExponent:
    18:71:6e:c6:87:1c:26:85:dc:6e:10:7d:3b:26:b4:
    12:cb:d2:51:62:f3:87:3d:0a:86:24:01:16:00:e5:
    87:3b:2f:57:de:5c:cb:08:3d:f0:4e:4d:a7:51:03:
    e5:95:3e:67:35:a1:a1:9e:fb:75:d3:49:c5:5a:8a:
    29:50:79:19
prime1:
    00:fd:09:8c:63:c4:5b:55:7f:ef:b8:20:f2:77:05:
    e5:35:ff:37:70:ef:84:13:02:b2:b6:ca:44:49:8c:
    da:56:9f
prime2:
    00:c1:be:eb:a1:a1:ce:6c:be:20:15:5b:2f:09:9b:
    e6:b2:44:53:0c:e6:34:c5:37:b5:27:35:78:3d:88:
    07:99:05
exponent1:
    00:e5:c5:60:e5:4b:6d:c0:82:ef:34:5d:3e:af:53:
    fc:22:7f:41:61:dd:2d:2a:72:1d:c4:9c:81:4b:e4:
    8a:73:73
exponent2:
    00:88:2a:92:98:aa:8b:d5:c9:59:eb:28:86:ca:8e:
    13:79:3e:a3:cf:f1:0b:2d:80:95:84:d5:03:88:db:
    4d:db:b1
coefficient:
    00:b8:3f:8c:5d:5d:0a:d7:fe:93:b9:1e:91:a8:a2:
    b5:7c:da:3a:32:72:0f:3b:a4:c6:9f:17:9e:db:1e:
    e3:40:7f
```

+ "prime1"と"prime2"が$p$および$q$に相当
+ "modulus"が$n$（`prime1*prime2`）
+ "publicExponent"が公開指数$e$で、前述の通り"65537"固定
+ "privateExponent"が秘密指数$d$
+ $\phi$は$d$の算出時にしか使わないので、鍵データに入っていない
+ "exponent1"、"exponent2"、"coefficient"がそれぞれ$dP$, $dQ$, $qInv$

## 参考資料
[RFC8017 PKCS #1: RSA Cryptography Specifications Version 2.2](https://tools.ietf.org/html/rfc8017)