ahjohnston25 - 2 months ago 18

Java Question

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

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).