Generate public key from numbers

Question 1

The private and public keys you are familiar with are in a format called PEM. PEM refers to the header and footer wrapping base64 encoded data.

The encoded binary data is in the DER (Distinguished Encoding Rules) format of ASN.1 (Abstract Syntax Notation One).

Here's a javascript ASN.1 decoder. http://lapo.it/asn1js/

The public and private keys contain the modulus and either the public or private exponent respectively.

Question 2

The following code came from a couple authors (listed in the comments), compiled on Ohloh Code (http://code.ohloh.net/file?fid=gxO4OHIDEgc0cAHG4K2iptOVOUY&cid=b0rvFixqcq4&s=&fp=285256&mp=&projSelected=true#L0). All credit due to them for their hard work. But the compilation did the trick for me. Add this as a .js library and then you can call it from your main routine like this:

publicPem = publicPEM();
privatePemUnencrypted = privatePEM(); //you will probably want to encrypt this

The output is in PEM format.

Codez:

//From git://github.com/titanous/pem-js.gitmaster

var ASNIntValue, ASNLength, int2hex;
function privatePEM() {
  var encoded;
  encoded = '020100';
  encoded += ASNIntValue(this.n, true);
  encoded += ASNIntValue(this.e, false);
  encoded += ASNIntValue(this.d, false);
  encoded += ASNIntValue(this.p, true);
  encoded += ASNIntValue(this.q, true);
  encoded += ASNIntValue(this.dmp1, true);
  encoded += ASNIntValue(this.dmq1, false);
  encoded += ASNIntValue(this.coeff, false);
  encoded = '30' + ASNLength(encoded) + encoded;
  return "-----BEGIN RSA PRIVATE KEY-----\n" + encode64(chars_from_hex(encoded)) + "\n-----END RSA PRIVATE KEY-----";
};

function publicPEM() {
  var encoded;
  encoded = ASNIntValue(this.n, true);
  encoded += ASNIntValue(this.e, false);
  encoded = '30' + ASNLength(encoded) + encoded;
  encoded = '03' + ASNLength(encoded, 1) + '00' + encoded;
  encoded = '300d06092a864886f70d0101010500' + encoded;
  encoded = '30' + ASNLength(encoded) + encoded;
  return "-----BEGIN PUBLIC KEY-----\n" + encode64(chars_from_hex(encoded)) + "\n-----END PUBLIC KEY-----";
};

RSAKey.prototype.parsePEM = function(pem) {
  pem = ASN1.decode(Base64.unarmor(pem)).sub;
  return this.setPrivateEx(pem[1].content(), pem[2].content(), pem[3].content(), pem[4].content(), pem[5].content(), pem[6].content(), pem[7].content(), pem[8].content());
};

ASNIntValue = function(integer, nullPrefixed) {
  integer = int2hex(integer);
  if (nullPrefixed) {
    integer = '00' + integer;
  }
  return '02' + ASNLength(integer) + integer;
};

ASNLength = function(content, extra) {
  var length;
  if (!(typeof extra !== "undefined" && extra !== null)) {
    extra = 0;
  }
  length = (content.length / 2) + extra;
  if (length > 127) {
    length = int2hex(length);
    return int2hex(0x80 + length.length / 2) + length;
  } else {
    return int2hex(length);
  }
};

int2hex = function(integer) {
  integer = integer.toString(16);
  if (integer.length % 2 !== 0) {
    integer = '0' + integer;
  }
  return integer;
};

/* CryptoMX Tools - Base64 encoder/decoder
 * http://www.java2s.com/Code/JavaScriptDemo/Base64EncodingDecoding.htm
 *
 * Copyright (C) 2004 - 2006 Derek Buitenhuis
 * Modified February 2009 by TimStamp.co.uk
 * GPL v2 Licensed
 */
function encode64(a){a=a.replace(/\0*$/g,"");var b="",d,e,g="",h,i,f="",c=0;do{d=a.charCodeAt(c++);e=a.charCodeAt(c++);g=a.charCodeAt(c++);h=d>>2;d=(d&3)<<4|e>>4;i=(e&15)<<2|g>>6;f=g&63;if(isNaN(e))i=f=64;else if(isNaN(g))f=64;b=b+"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=".charAt(h)+"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=".charAt(d)+"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=".charAt(i)+"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=".charAt(f)}while(c<
a.length);a="";b=b.split("");for(c=0;c<b.length;c++){if(c%64==0&&c>0)a+="\n";a+=b[c]}b.join();b=a%4;for(c=0;c<b;c++)a+="=";return a}
function decode64(a){var b="",d,e,g="",h,i="",f=0;a=a.replace(/[^A-Za-z0-9\+\/\=\/n]/g,"");do{d="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=".indexOf(a.charAt(f++));e="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=".indexOf(a.charAt(f++));h="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=".indexOf(a.charAt(f++));i="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=".indexOf(a.charAt(f++));d=d<<2|e>>4;e=(e&15)<<4|h>>2;g=(h&3)<<
6|i;b+=String.fromCharCode(d);if(h!=64)b+=String.fromCharCode(e);if(i!=64)b+=String.fromCharCode(g)}while(f<a.length);return b=b.replace(/\0*$/g,"")};

/* JavaScript ASCII Converter
 * http://www.vortex.prodigynet.co.uk/misc/ascii_conv.html
 *
 * TPO 2001/2004
 * Modified Feb 2009 by Tim Stamp (timstamp.co.uk)
 * License Unknown
 */
function chars_from_hex(a){var c="";a=a.replace(/^(0x)?/g,"");a=a.replace(/[^A-Fa-f0-9]/g,"");a=a.split("");for(var b=0;b<a.length;b+=2)c+=String.fromCharCode(parseInt(a[b]+""+a[b+1],16));return c};

Question 3

Using the link suggested by @borkencode (http://lapo.it/asn1js/) I have been able to successfully extract all the components of the public key, and also the relevant components from private keys.

Code to test extraction of numerical portions of keys

// copy and paste into console whilst on `http://lapo.it/asn1js/`
// so that dependancies are met
var getParts, pri, pub;

getParts = function(key) {
  var end, current, output, crypt, slice, sa, so, start, tree, _i, _len;

  // strip out the BEGIN/END tags from the input keys
  crypt = key.replace(/^-.+/mg, '');

  // decode the input text into ASN1 object
  tree = ASN1.decode(Base64.decode(crypt));


  // set root object based on type of key
  if (key.match(/PUBLIC KEY-/)) {
    root = tree.sub[1].sub[0].sub;
  } else if (key.match(/PRIVATE KEY-/)) {
    root = tree.sub;
  } else {
    console.error("Not happening");
    return;
  }

  // initialize empty array to populate with results
  output = [];

  // loop through the root ASN1 object
  for (_i = 0, _len = root.length; _i < _len; _i++) {

    // get the current object
    current = root[_i];

    // set the start and end positions in the stream
    start = current.stream.pos + current.header;
    end = start + current.length;

    // cut the required compnent out of the stream
    slice = current.stream.enc.slice(start, end);

    // format the slice in HEX, joining as string
    // and replacing leading `00`s
    str = slice.map(function(i) {
      return ("0" + i.toString(16)).replace(/.(..)/, "$1");
    }).join('').replace(/^(00)+/, '');

    // add to output array
    output.push(str);

  }

  // send the results!
  return output;

};

pri = "-----BEGIN RSA PRIVATE KEY-----\n"+
"MIIBOgIBAAJBAMpZrx0gTluJEu6+fop1e60lwbnlBD6kHvoRx85GBhUgD8SQknjc\n"+
"LcU2qqM/pV9ZX8MV8x49h2mzrmRyH7kDmpcCAwEAAQJAYf2GYMt5Rrids4IKk5CL\n"+
"IPFs3FH8eT1PRvh/UvP0FBwDMZu/Q4m+3PNTM3ARQhFuCvWgCalMmZkyVx0HYRLe\n"+
"4QIhAOaaQm+b/bSoHqolvVTcyfBL09rrLFZhgGkETX3R6cVRAiEA4KLdUm97YBxP\n"+
"T6/jkn/P7K8SUWEO9o9u8Bif1UKQB2cCIETqoSQ92EqfW9q5wKWV/nvkDYKFehCu\n"+
"vvOjp40MqPKhAiA2sPBZpbLQD5Rvvk8V1/Bzm5xGG+9csEc+RYCEl5QheQIhAKgi\n"+
"Xb3zY9lqtpX/mgTIrW6RPB3GocviJOibqtpfNxRU\n"+
"-----END RSA PRIVATE KEY-----";

pub = "-----BEGIN PUBLIC KEY-----\n"+
"MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAMpZrx0gTluJEu6+fop1e60lwbnlBD6k\n"+
"HvoRx85GBhUgD8SQknjcLcU2qqM/pV9ZX8MV8x49h2mzrmRyH7kDmpcCAwEAAQ==\n"+
"-----END PUBLIC KEY-----";

console.dir(getParts(pri));
console.dir(getParts(pub));

Output to console:

0: ""
1: "ca59af1d204e5b8912eebe7...d8769b3ae64721fb9039a97"
2: "010001"
3: "61fd8660cb7946b89db3820...94c999932571d076112dee1"
4: "e69a426f9bfdb4a81eaa25b...c56618069044d7dd1e9c551"
5: "e0a2dd526f7b601c4f4fafe...ef68f6ef0189fd542900767"
6: "44eaa1243dd84a9f5bdab9c...a10aebef3a3a78d0ca8f2a1"
7: "36b0f059a5b2d00f946fbe4...f5cb0473e45808497942179"
8: "a8225dbdf363d96ab695ff9...1cbe224e89baada5f371454"
------------------------------------------------------
0: "ca59af1d204e5b8912eebe7...d8769b3ae64721fb9039a97"
1: "010001"

I have tested the values, using them as inputs to encrypt, and decrypt messages with my javascript library. What I really want to be able to do now, is to create the .pem and .pub files by going the other way, from numbers, to formatted text.

The closest I have found so far, is a PHP function, which I might translate to javascript. Details here: http://pumka.net/2009/12/19/reading-writing-and-converting-rsa-keys-in-pem-der-publickeyblob-and-privatekeyblob-formats/

//Encode key sequence
$modulus = new ASNValue(ASNValue::TAG_INTEGER);
$modulus->SetIntBuffer($Modulus);
$publicExponent = new ASNValue(ASNValue::TAG_INTEGER);
$publicExponent->SetInt($PublicExponent);
$keySequenceItems = array($modulus, $publicExponent);
$keySequence = new ASNValue(ASNValue::TAG_SEQUENCE);
$keySequence->SetSequence($keySequenceItems);
//Encode bit string
$bitStringValue = $keySequence->Encode();
$bitStringValue = chr(0x00) . $bitStringValue; //Add unused bits byte
$bitString = new ASNValue(ASNValue::TAG_BITSTRING);
$bitString->Value = $bitStringValue;
//Encode body
$bodyValue = "\x30\x0d\x06\x09\x2a\x86\x48\x86\xf7\x0d\x01\x01\x01\x05\x00" . $bitString->Encode();
$body = new ASNValue(ASNValue::TAG_SEQUENCE);
$body->Value = $bodyValue;
//Get DER encoded public key:
$PublicDER = $body->Encode();

Question 4

For answer to your question, please have a look at the RSA algorithm for the actual formulae . For the complexity part, its better to leave the transformation to the JS

In case it helps, I used this code for my application and it worked wonders :)