背景

ちょっとした RSA 秘密鍵を、本来的なその変数である素数p, qと、公開乗数eを指定して自動で作成したいと思いたち、それを行なうスクリプトを記述した。

その際に、 Ruby は

整数(Integer)がデフォルトで任意精度
OpenSSL が標準ライブラリに含まれるので、 DER まわりの処理が他のライブラリを必要としない

で、親和性が高かったので、これを用いた。

スクリプト本体

create-rsa-private.rb


#!/usr/bin/env ruby

require 'openssl'

prime1 = ARGV[0].to_i
prime2 = ARGV[1].to_i
e = (ARGV[2] || 0x10001).to_i

# 以上から、 rsa の key を作る。

n = prime1 * prime2

module ExtendedEuclid
  # args: a, b
  # return: [gcd(a,b), x, y]
  #         s.t. x*a + y*b = gcd(a,b)
  def self.call(a, b)
    return [a, 1, 0] if b == 0

    # a = q*b + r
    # <=> r = a - q*b
    q, r = a.divmod(b)

    # s*b + t*r == gcd
    gcd, s, t = call(b, r)
    # s*b + t*(a- q*b) == gcd
    # t*a + (s - t*q)*b == gcd

    [gcd, t, s - t*q]
  end
end

carmichael = (prime1 - 1).lcm(prime2 - 1)
gcd, _, d = ExtendedEuclid.call(carmichael, e)
raise "e and lcm(p-1, q-1) not coprime" unless gcd == 1
d = d % carmichael

exp1 = d % (prime1 - 1)
exp2 = d % (prime2 - 1)

gcd, _, prime2_inv = ExtendedEuclid.call(prime1, prime2)
raise "p and q not coprime" unless gcd == 1
prime2_inv = prime2_inv % prime1

priv_key = OpenSSL::ASN1::Sequence.new(
  [0, n, e, d, prime1, prime2, exp1, exp2, prime2_inv].map(&OpenSSL::ASN1::Integer.method(:new))
)

print(priv_key.to_der)

利用法

# 生成されるのは der なので
$ ./create-rsa-private.rb 103 131 > private.der

# pem が良い場合は openssl で変換する
$ openssl rsa -in ./private.der -inform DER > private.pem

# RSA 秘密鍵として適格か確認
$ openssl rsa -in ./private.pem -text -noout -check
Private-Key: (14 bit)
modulus: 13231 (0x33af)
publicExponent: 65537 (0x10001)
privateExponent: 673 (0x2a1)
prime1: 101 (0x65)
prime2: 131 (0x83)
exponent1: 73 (0x49)
exponent2: 23 (0x17)
coefficient: 64 (0x40)
RSA key ok

補足

RSA 秘密鍵の定義

の ASN1 に定義が書いてあり、それをそのまま計算すれば良い。具体的には、

version:         0
modulus:         n == p * q
publicExponent:  e == 65537  (==0x10001)
privateExponent: d == e^-1 mod LCM(p-1, q-1)
prime1:          p
prime2:          q
exponent1:       d mod (p-1)
exponent2:       d mod (q-1)
coefficient:     q^(-1) mod p

な ASN1 の SEQUENCE であれば良い。

素数以外をつっこみたいとき

上で記述した秘密鍵の定義上、p と q が互いに素であって、かつ lcm(p-1, q-1) と e が互いに素であれば、例えば「合成数をベースにしてしまった RSA 秘密鍵」も割と問題なく作れたりする。

擬素数をつっこんで RSA がそのときどのように動作するのか調べたいときにも使える。(自分はむしろこっちがやりたくてこのスクリプトを書いていた)