background

I wanted to automatically create a small RSA private key by specifying its original variables, the prime numbers p and q, and the public multiplier e, and wrote a script to do that.

At that time, Ruby

Integer is arbitrary precision by default
OpenSSL is included in the standard library, so processing around DER does not require other libraries.

And since it had a high affinity, I used this.

Script body

`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

#From the above, create the key for rsa.

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)

Usage

#Because it is der that is generated
$ ./create-rsa-private.rb 103 131 > private.der

#If pem is good, convert with openssl
$ openssl rsa -in ./private.der -inform DER > private.pem

#Check if it is eligible as an RSA private key
$ 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

Supplement

RSA private key definition

https://tools.ietf.org/html/rfc3447

The definition is written in ASN1 of, and you can calculate it as it is. In particular,

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

Any ASN1 SEQUENCE will do.

When you want to play something other than prime numbers

In the definition of the private key described above, if p and q are relatively prime, and lcm (p-1, q-1) and e are relatively prime, for example," You can also create an "RSA private key that has been based on composite numbers" without any problems.

It can also be used when you want to dig into pseudoprimes and see how RSA works then. (I was writing this script because I wanted to do it)

A ruby ​​script that creates an rsa private key that can be used with OpenSSL from any two prime numbers