0

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.

Maarten Bodewes
  • 90,524
  • 13
  • 150
  • 263
ahjohnston25
  • 1,915
  • 15
  • 36
  • Have a look at http://www.ietf.org/rfc/rfc3447.txt. Appendix A gives a format for the public and private keys as ASN.1 structures. – Henry Sep 25 '13 at 07:51
  • I looked through the RFC as well as RFC2315, but all I could find is that I should use PKCS#1 v1.5, but it didn't specify how I go about implementing this. – ahjohnston25 Sep 25 '13 at 13:35
  • You would typically use ASN.1 DER Encoding (DER = Distinguished encoding rules). See for example http://luca.ntop.org/Teaching/Appunti/asn1.html – Henry Sep 25 '13 at 13:57
  • Your example seems to be OpenPGP Format, see http://tools.ietf.org/html/rfc4880 – Henry Sep 25 '13 at 14:22
  • @Henry why do you think that? It clearly contains a PKCS#1 public key: {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) rsaEncryption(1)} is the embedded OID... – Maarten Bodewes Sep 25 '13 at 21:25
  • @owlstead oops, you are right. I made a mistake when I dumped the data and did not recognize the DER encoding. – Henry Sep 26 '13 at 13:55

2 Answers2

3

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
}
Henry
  • 42,982
  • 7
  • 68
  • 84
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).

Maarten Bodewes
  • 90,524
  • 13
  • 150
  • 263
  • I think, the implementation is not so difficult in this case. The AlgorithmIdentifier is a constant, and the overall structure is also the same in every case. Basically just the values for n and e need to be inserted and the length fields need to be adjusted. – Henry Sep 26 '13 at 14:38
  • True, public key structures are one of the simpler structures around. But still you need to know the correct formatting. To play around with the structure, it may be a good idea to use the ASN.1 editor from Liping Dai. On a GNU system you could also use `openssl asn1parse` to look into the structure. It's also not hard to find pages that do the base64 decoding and ASN.1 parsing on the net using JavaScript in the browser. – Maarten Bodewes Sep 26 '13 at 15:10
  • Note that `PublicKey.getEncoded()` is actually X.509 SubjectPublicKeyInfo _containing_ PKCS1. SPKI is commonly used (and X.509 _cert containing_ SPKI even more) but if you really need 'raw' PKCS1 you can extract it from SPKI as shown in Henry's answer. – dave_thompson_085 Nov 01 '16 at 13:14
  • @dave_thompson_085 This code above actually returns a SubjectPublicKeyInfo indeed and is wrong (but I cannot delete it because it is an accepted answer. Just shows you that I wasn't that good in 2013 I guess. Then again, it seems that the question actually asked for a SubjectPublicKeyInfo, not PKCS#1 only .... – Maarten Bodewes Nov 01 '16 at 17:34