OpenSSLで作ることが多いRSA鍵をJavaでざっくり作ってみた。Javaでもcrypto系のもので作ることはできるけれど手作り系。
一般的にTLSなどで使われるのは秘密鍵、公開鍵入り証明書の組み。今回は秘密鍵の計算部分。
セキュリティ的なところは保証しない。

PKCS #1 / RFC 8017

RSAの方式はPKCS #1にいろいろあるのでRFC 8017でも見ることができる。
基本的なフォーマットはASN.1 (ITU-T X.680系)のDER。BASE64っぽいのはPEMという形。
さらにPKCS #8でも秘密鍵をくるむことができるのでどの形式なのか特定するのが厄介。
ASN.1のデータをバイナリにしたり読みやすくするのは*ER という名前が付いている。
バイナリで一般的なのがDERという形式。BER,CERというのもあったが厳格に型を決めていったのがDER。
RSAでは古めのCERもデコードはできた方がいいくらいで使われることがある想定だったかな。
テキストではプレーンっぽいもののほか、XML(XER)やJSON(JER)にもできるらしい。

PKCS #1 DER
PKCS #8 暗号化ができる
SSH
他いろいろ

証明書などを含む形式は PKCS #12 もある。

今回は数値を計算するだけなのでASN.1までは進まない。ASN.1以降のものは他にいろいろあるので略。

RSAは大きい素数(prime)2つを掛け合わせた数が素因数分解が難しいというのと他いろいろとを組み合わせた暗号方式。
長さは素数2つを掛け合わせた数(modulus)のビット数というのが一般的かな。現在は2048bit以上3072bitくらいが目安。
同じbit数くらいの値を暗号化することができたりする。解読耐性を上げるために長すぎることになってしまっている気がするので他の方式に置き換わっていくのだろう。
JavaではBigInteger を使うと大きい数を扱うことができる。RSAの計算に必要なものも割とそろっているのでそのまま使ってもいい。

PKCS #1で必要なものは中国余剰定理が使える形で素数も保存されている。

秘密鍵 (RFC 8017 A.1.2. RSA Private Key Syntax)

RSAPrivateKey ::= SEQUENCE {
             version           Version,
             modulus           INTEGER,  -- n
             publicExponent    INTEGER,  -- e
             privateExponent   INTEGER,  -- d
             prime1            INTEGER,  -- p
             prime2            INTEGER,  -- q
             exponent1         INTEGER,  -- d mod (p-1)
             exponent2         INTEGER,  -- d mod (q-1)
             coefficient       INTEGER,  -- (inverse of q) mod p
             otherPrimeInfos   OtherPrimeInfos OPTIONAL
         }

だいたいこのような感じの構成になっている。長い名前(publicExponentなど)と変数名などで使われる名前(eなど)の2種類がある。この形のASN.1で書き出せばPKCS #1形式、やや肉付けをするとPKCS #8形式になる。

JavaのRSA秘密鍵

RSAPrivateKey, RSAPrivateKeySpec (n, d)
RSAPrivateCrtKey, RSAPrivateCrtKeySpec (n, e, d, p, q, dP, dQ, qInv)
RSAMultiPrimePrivateCrtKey, RSAMultiPrimeCrtKeySpec (otherPrimeInfos OPTIONALを含む)

の3種類があり、今回はRSAPrivateCrtKeySpec を使う。MultiPrimeCrtKeyは素数が3つ以上になるがあまり使われないので略。

秘密鍵の最小構成は、RSAPrivateKey のmodulus(n)とprivateExponent(d)。公開鍵はmodulus(n)とpublicExponent(e)のみで他は公開してはいけない。その他は秘密鍵の高速化などで使われるのでSSH鍵などでは保存していない場合がある。RSAPrivateCrtKeySpec はnとeを持っているので公開鍵を作ることもできる。

RSAPrivateCrtKeySpec を作ってから RSAPrivateCrtKey に変換するとJavaで一般的に使える形式になるので作っていく。

毎回同じにならないよう乱数を使うが、普通のRandomはランダムではないのでSecureRandom.getInstanceStorong() で乱数のもとを作る方がいい。

SecureRandom srnd = SecureRandom.getInstanceStorong();

まずはprime1, prime2 の素数から作る。

int len = 3072; // bit

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

probablePrimeはほぼ素数を作ってくれるのでそのまま使う。素数は全体の長さの半分くらいで作る。場合によっては2つの値が近すぎたりしないような判定も必要。pとqが決まれば他の値もほぼ自動的に決まる。

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

n は pとqを掛けた値。長さは1ビット減ったりするので再計算するなどしてもいいのかどうか。
nからpとqを出すことは難しい。

次は eとdを決めていく。eはフェルマーのなんとかで65537 (0x10001)で固定されている場合が多いが他の値にすることもできる。

e * d = 1 mod (p-1)(q-1) だったか e * d = 1 mod LCM(p-1,q-1) が成り立つこと。

eは 3からn-1 の範囲。p-1, q-1と互いに素である数。素数でなくてもいいが、奇数であること(p-1,q-1が偶数なので)。(2^16+1 ～ 2^256 - 1)ぐらいが最適っぽいので17ビット程度の素数で指定してみることにする。

BigInteger e = BigInteger.probablePrime( 17, srnd );

e が決まると上の式e * d = 1 mod (p-1)(q-1)から dも自動的に決まる。ここまでで各条件が成立しない場合は p, q, e から作り直す。

(GCD(e,p-1) == 1 && GCD(e,q-1) == 1)

GCDは最大公約数。これが成立しないとこの後の計算もできなくなる。

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

これでp,q,eからdが決まる。lambda は p-1,q-1の最小公倍数。

lambda = LCM(p-1,q-1)

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

BigInteger LCM(BigInteger a, BigInteger b) {
    return a.divide(GCD(a,b)).multiply(b); // = a * b / GCD(a,b)
}

BigInteger GCD(BigInteger a, BigInteger b) {
    return a.equals(BigInteger.ZERO) ? b : GCD(b.mod(a), a); 
}

再帰をループに変えると

BigInteger GCD(BigInteger a, BigInteger b) {
    while (!a.equals(BigInteger.ZERO) {
        BigInteger m = b.mod(a);
        b = a;
        a = m;
    }
    return b;
}

最小公倍数 LCM(a,b) = ab / GCD(a,b)
最大公約数 GCD(a,b) = a != o ? GCD(b % a, a) : b

GCDはBigInteger のメソッドにもあるので a.gcd(b) としてもいい。

e.modInverse(m) はmodInverse(e,m)とするとこんな感じらしい。

BigInteger modInverse(BigInteger a, BigInteger m) {
    if (BigInteger.ONE.equals(a)) {
        return BigInteger.ZERO;
    }
    BigInteger m0 = m;
    BigInteger y = BigInteger.ZERO;
    BigInteger x = BigInteger.ONE;

    while (a.compareTo(BigInteger.ONE) > 0) {
        BigInteger q = a.divide(m); // q = a / m
        BigInteger t = m;
        m = a.mod(m);
        a = t;
        t = y;
        y = x.subtract(q.multiply(y));
        x = t;
    }

    if ( x.compareTo(BigInteger.ZERO) < 0) {
        x = x.add(m0);
    }
    return x;
}

というわけで最終的にnとeが公開鍵、nとdが秘密鍵(最小構成)として使われる。

dPとdQ,qInv もここまでの値から計算できる。

BigInteger dP = e.modInverse(p-1) = d.mod(p-1);
BigInteger dQ = e.modInverse(q-1) = d.mod(q-1);

dP, dQはeとdどちらを使っても計算できるらしいがpとqは公開鍵側では使えないので使えるのは秘密鍵側のみ。

BigInteger qInv = q.modInverse(p);

qInvもpとqから計算するだけ。これらの値は中国余剰定理で使うと半分程度の計算量で済むらしい。

ここまででRSA暗号に必要な要素はひととおりそろったことになる。

RSAPrivateCrtKeySpec に入れてからRSAPrivateCrtKeyなどに変換して問題なく使えることを確認してみよう。

KeyFactory factory = KeyFactory.getInstance("RSA");
RSAPrivateCrtKeySpec privateSpec = new RSAPrivateCrtKeySpec(n,e,d,p,q,dP,dQ,qInv);
RSAPrivateCrtKey privateKey = factory.generatePrivate(privateSpec);

ASN.1で符号化したり、暗号化、復号、署名などの方法は適度にありそうなので略。
ASN.1のJavaライブラリもGitHubに公開しているので使えばいいかもしれない。

SEQUENCE s = new SEQUENCE();
s.add(0); // Version
s.add(n); // modulus
s.add(e); // publicExponent
s.add(d); // privateExponent
s.add(p); // prime1
s.add(q); // prime2
s.add(dP); // exponent1
s.add(dQ); // exponent2
s.add(qInv); // coefficient
byte[] asn1 = s.encodeAll();

PKCS #1形式

RSA鍵を作る

PKCS #1 / RFC 8017

JavaのRSA秘密鍵