RSA鍵を作る

最近暗号系をいろいろ実装してみている中で PKCS #1 の RSA も必要になってきたので実装してみた。中身がわからないと使いにくいタイプ。

RSA は公開鍵暗号という形で秘密鍵、公開鍵の2つの鍵を使う。AESなどの共通鍵暗号とは違うところ。

公開鍵で暗号化、秘密鍵で復号ができるのがひとつめ。

秘密鍵で署名。公開鍵で検証。これが2つめ。 

公開鍵暗号共通の特徴ではなくRSAの特徴のようなので注意。

アルゴリズム的にはガロア体と同じようなものを作って2つの状態を行き来してる感じがした。

何に使えるのか。ひととおりバイト列の暗号化などにも使えるが、速さが出ないので署名用途の方が主流で暗号化も一部用途に限定して使う場合が多い。

秘密鍵と公開鍵の中身を見ていく。

RSAは大きい数の因数分解が難しいというところから作られているので2つの素数から鍵を作る。

素数(prime)2つ(pとq)を決める。2048ビットのRSAだと1024ビットくらいの素数を2つ。今なら3072ビットくらいが最低ラインになってきているので1536ビットくらいの素数を2つ。

Java で作るのでいろいろ省略できるところは省略する。

乱数はjava.math.SecureRandom っぽいところから。安全かどうかは不明。他の要素があればいろいろ混ぜるとより安全かも。普通のRandomは安全ではない。

SecureRandom srnd = SecureRandom.getInstanceStorong();

BigInteger p = BigInteger.probablePrime( len / 2, srnd );

BigInteger q = BigInteger.probablePrime( len / 2, srnd );

これで素数2つを作ってくれるのでおまかせ。素数ではない場合もあるらしい。

modulus 素数2つを掛けたもの 変数名は n など。

BigInteger n = p.multiply(q); // n = p * q

nをpとqに素因数分解するのが難しい。

次はeとdという指数(exponent)を決めていく。

eは公開指数(public exponent)、dは秘密指数(private exponent)。

e * d = 1 mod (p - 1)(q - 1) が成り立つ範囲のeとd。

e はほぼ固定値が使われていてフェルマーなんとかの 65537 ( 0x10001 ) が使われることが多い。

eの条件は、3からn-1の値、p,qと互いに素である数である。素数ではなくてもいいが奇数であること(p-1, q-1が偶数なので)。 ( 2^16 + 1 ～ 2^256 - 1 ) ぐらいが最適っぽい。

BigInteger e = BigInteger.probablePrime(17,srnd); ぐらいでいいんじゃないのかな

e が決まると上の式からdも自動的に決まる。成立しない場合は e, p, qを作り直す。

計算する場合はp-1, q-1 の最小公倍数(lambda(n))を出す必要があるらしいのでこんなかんじ。

BigInteger d = e.modInverse(lambda); // e * d = 1 (mod lambda)

lambda は p-1, q-1の最小公倍数 lambda = LCM(p-1, q-1)

最小公倍数は最大公約数から

最小公倍数 LCM(a, b) = ab / GCD(a,b);

最大公約数 GCD(a, b) = a != 0 ? GCD(b % a, a) : b;

こんなかんじ。

n と e が公開鍵、n と d が秘密鍵(最小の場合)として使われる。

OpenSSLで生成される秘密鍵にはp, qなどの要素も保存されている。

• modulus = n
• publicExponent = e
  
• privateExponent = d
  
• prime1 = p
• prime2 = q
• exponent1 = e.modInverse(p - 1) = d.mod(p - 1)
  
• exponent2 = e.modInverse(q - 1) = d.mod(q - 1)
• coefficient = q.modInverse(p)
  

各要素の使い方は省略.

メッセージ M (長さは鍵長 - 数バイトまで)、暗号文 C で簡単な計算方法

公開鍵で暗号化 C = M.modPow(e, n)

秘密鍵で復号 M = C.modPow(d, n)

秘密鍵で署名 S = Hash(M).modPow(d, n)

公開鍵で署名検証 Hash(M) = S.modPow(e, n)

HashはSHAなどJava では MessageDigest系。Paddingなどもあるので実際はちょっと違う。