Converting RSA keys into SubjectPublicKeyInfo Form

Question

WARNING: the initial question was about PKCS#1 encoded keys, while the actual example in the question requires SubjectPublicKeyInfo (X.509) encoded keys.

---

I'm currently working on implementing the RSA algorithm from scratch in java, particularly on key generation. Right now I have code working that will give me three BigIntegers n, e, and d.

From what I can see online an RSA key (much like a PGP Signature) is usually a mix of characters and not just very long numbers; apparently this is because the keys are encrypted/translated (I'm not quite sure) into PKCS#1.

How would I go about doing this myself? Further, is PKCS#1 SubjectPublicKeyInfo what I want to be displaying the keys in or is there a more updated format?

EDIT: For clarity, here's an example of what I'm looking for:

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0
FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/
3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB
-----END PUBLIC KEY-----

And I currently have:

Public Key (n,e): (25130290470670502980544427869200613840944965290040433220698179071215137002904823499373962164071905921326803837460733139500455896910114421141830335882737678919237073090149470600927019562678483947908156329730770276498955439764614844798829603416304775442087438623389826719642285111749464396302305124179886483673046650125158307930593778247437940929550491287419436361905923356252487704851166279431792122641372330876814779543893241235355988829436458897455503500810769146739895787437926366072829812130032509796362669335922016603663923790043992999351304972183762844549989472560311169566110061553119311399708581940621713200371,65537)

I don't know how I can covert this huge number into a standard-form key.

Answer 1

The best way to do this is to use the Java API. Simply create an RSAPublicKey and call getEncoded(). Otherwise you could use the Bouncy Castle libraries and construct the public key using the Bouncy internal ASN.1 encoding structures (possibly "stealing" the implementation from the Bouncy Castle JCE implementation, they have to implement getEncoded() as well).

Finally, you can simply look up the PKCS#1 RSA standard and implement the ASN.1 structure. If you do this then you will have to learn at least a subset of ASN.1 and DER encoding rules. Note that if you want to implement a complete ASN.1 parser + BER/DER encoder/decoder from scratch, you will need a couple of months implementation time and several years of experience.

Note that getEncoded() simply contains the binary DER encoded ASN.1 structure. You need to convert to base 64 and add the beginning and starting lines to create the PEM structure you have shown us. This is also sometimes called an "ASCII armor" as it shields the binary code against corruption when you send the structure e.g. by mail (PEM means Privacy Enhanced Mail).

Answer 2

To decode the example

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0
FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/
3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB
-----END PUBLIC KEY-----

first remove the base64 encoding, which gives:

00000000  30 81 9f 30 0d 06 09 2a  86 48 86 f7 0d 01 01 01  |0..0...*.H......|
00000010  05 00 03 81 8d 00 30 81  89 02 81 81 00 aa 18 ab  |......0.........|
00000020  a4 3b 50 de ef 38 59 8f  af 87 d2 ab 63 4e 45 71  |.;P..8Y.....cNEq|
00000030  c1 30 a9 bc a7 b8 78 26  74 14 fa ab 8b 47 1b d8  |.0....x&t....G..|
00000040  96 5f 5c 9f c3 81 84 85  ea f5 29 c2 62 46 f3 05  |._\.......).bF..|
00000050  50 64 a8 de 19 c8 c3 38  be 54 96 cb ae b0 59 dc  |Pd.....8.T....Y.|
00000060  0b 35 81 43 b4 4a 35 44  9e b2 64 11 31 21 a4 55  |.5.C.J5D..d.1!.U|
00000070  bd 7f de 3f ac 91 9e 94  b5 6f b9 bb 4f 65 1c db  |...?.....o..Oe..|
00000080  23 ea d4 39 d6 cd 52 3e  b0 81 91 e7 5b 35 fd 13  |#..9..R>....[5..|
00000090  a7 41 9b 30 90 f2 47 87  bd 4f 4e 19 67 02 03 01  |.A.0..G..ON.g...|
000000a0  00 01                                             |..|
000000a2

Now we have:

30 81 9f <- a SEQUENCE with 9f bytes
   30 0d <- a SEQUENCE with 0d bytes
      06 09 2a 86 48 86 f7 0d 01 01 01  <- OID 1.2.840.113549.1.1.1
      05 00  <- NULL
   03 81 8d 00  <- BIT STRING with 8d bytes (0 unused bits in last byte)

The contents of the BIT STRING is the public key, again DER encoded

30 81 89  <- SEQUENCE with 89 bytes
   02 81 81  <- INTEGER with 81 bytes, this is n
      00 aa 18 ... 4e 19 67
   02 03   <- INTEGER with 3 bytes, this is e
      01 00 01   <- 2^16+1

So the whole structure is a

SubjectPublicKeyInfo ::= SEQUENCE {
  algorithm AlgorithmIdentifier,
  publicKey BIT STRING }

where an AlgorithmIdentifier is

AlgorithmIdentifier ::= SEQUENCE {
    algorithm OBJECT IDENTIFIER,
    parameters ANY DEFINED BY algorithm OPTIONAL }

and the public key is

RSAPublicKey ::= SEQUENCE {
    modulus           INTEGER,  -- n
    publicExponent    INTEGER   -- e
}