How to transform between the two styles of public key format, one “BEGIN RSA PUBLIC KEY”, the other is “BEGIN PUBLIC KEY”

opensslpkcs#1public-keyssh-keysx509

How can I transform between the two styles of public key format,
one format is:

-----BEGIN PUBLIC KEY-----
...
-----END PUBLIC KEY-----

the other format is:

-----BEGIN RSA PUBLIC KEY-----
...
-----END RSA PUBLIC KEY-----

for example I generated id_rsa/id_rsa.pub pair using ssh-keygen command,
I calculated the public key from id_rsa using:

openssl rsa -in id_rsa -pubout -out pub2

then again I calculated the public key from id_rsa.pub using :

ssh-keygen -f id_rsa.pub -e -m pem > pub1

the content is pub1 is :

and the content of pub2 is :

According to my understanding, pub1 and pub2 contain the same public key information, but they are in different format, I wonder how can I transform between the two format? Can anyone show me some concise introduction on the tow formats?

Best Answer

I wanted to help explain what's going on here.

An RSA "Public Key" consists of two numbers:

the modulus (e.g. a 2,048 bit number)
the exponent (usually 65,537)

Using your RSA public key as an example, the two numbers are:

Modulus: 297,056,429,939,040,947,991,047,334,197,581,225,628,107,021,573,849,359,042,679,698,093,131,908,015,712,695,688,944,173,317,630,555,849,768,647,118,986,535,684,992,447,654,339,728,777,985,990,170,679,511,111,819,558,063,246,667,855,023,730,127,805,401,069,042,322,764,200,545,883,378,826,983,730,553,730,138,478,384,327,116,513,143,842,816,383,440,639,376,515,039,682,874,046,227,217,032,079,079,790,098,143,158,087,443,017,552,531,393,264,852,461,292,775,129,262,080,851,633,535,934,010,704,122,673,027,067,442,627,059,982,393,297,716,922,243,940,155,855,127,430,302,323,883,824,137,412,883,916,794,359,982,603,439,112,095,116,831,297,809,626,059,569,444,750,808,699,678,211,904,501,083,183,234,323,797,142,810,155,862,553,705,570,600,021,649,944,369,726,123,996,534,870,137,000,784,980,673,984,909,570,977,377,882,585,701
Exponent: 65,537

The question then becomes how do we want to store these numbers in a computer. First we convert both to hexadecimal:

Modulus: EB506399F5C612F5A67A09C1192B92FAB53DB28520D859CE0EF6B7D83D40AA1C1DCE2C0720D15A0F531595CAD81BA5D129F91CC6769719F1435872C4BCD0521150A0263B470066489B918BFCA03CE8A0E9FC2C0314C4B096EA30717C03C28CA29E678E63D78ACA1E9A63BDB1261EE7A0B041AB53746D68B57B68BEF37B71382838C95DA8557841A3CA58109F0B4F77A5E929B1A25DC2D6814C55DC0F81CD2F4E5DB95EE70C706FC02C4FCA358EA9A82D8043A47611195580F89458E3DAB5592DEFE06CDE1E516A6C61ED78C13977AE9660A9192CA75CD72967FD3AFAFA1F1A2FF6325A5064D847028F1E6B2329E8572F36E708A549DDA355FC74A32FDD8DBA65
Exponent: 010001

RSA invented the first format

RSA invented a format first:

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

They chose to use the DER flavor of the ASN.1 binary encoding standard to represent the two numbers [1]:

SEQUENCE (2 elements)
   INTEGER (2048 bit): EB506399F5C612F5A67A09C1192B92FAB53DB28520D859CE0EF6B7D83D40AA1C1DCE2C0720D15A0F531595CAD81BA5D129F91CC6769719F1435872C4BCD0521150A0263B470066489B918BFCA03CE8A0E9FC2C0314C4B096EA30717C03C28CA29E678E63D78ACA1E9A63BDB1261EE7A0B041AB53746D68B57B68BEF37B71382838C95DA8557841A3CA58109F0B4F77A5E929B1A25DC2D6814C55DC0F81CD2F4E5DB95EE70C706FC02C4FCA358EA9A82D8043A47611195580F89458E3DAB5592DEFE06CDE1E516A6C61ED78C13977AE9660A9192CA75CD72967FD3AFAFA1F1A2FF6325A5064D847028F1E6B2329E8572F36E708A549DDA355FC74A32FDD8DBA65
   INTEGER (24 bit): 010001

The final binary encoding in ASN.1 is:

30 82 01 0A      ;sequence (0x10A bytes long)
   02 82 01 01   ;integer (0x101 bytes long)
      00 EB506399F5C612F5A67A09C1192B92FAB53DB28520D859CE0EF6B7D83D40AA1C1DCE2C0720D15A0F531595CAD81BA5D129F91CC6769719F1435872C4BCD0521150A0263B470066489B918BFCA03CE8A0E9FC2C0314C4B096EA30717C03C28CA29E678E63D78ACA1E9A63BDB1261EE7A0B041AB53746D68B57B68BEF37B71382838C95DA8557841A3CA58109F0B4F77A5E929B1A25DC2D6814C55DC0F81CD2F4E5DB95EE70C706FC02C4FCA358EA9A82D8043A47611195580F89458E3DAB5592DEFE06CDE1E516A6C61ED78C13977AE9660A9192CA75CD72967FD3AFAFA1F1A2FF6325A5064D847028F1E6B2329E8572F36E708A549DDA355FC74A32FDD8DBA65
   02 03         ;integer (3 bytes long)
      010001

If you then run all those bytes together and Base64 encode it, you get:

MIIBCgKCAQEA61BjmfXGEvWmegnBGSuS+rU9soUg2FnODva32D1AqhwdziwHINFa
D1MVlcrYG6XRKfkcxnaXGfFDWHLEvNBSEVCgJjtHAGZIm5GL/KA86KDp/CwDFMSw
luowcXwDwoyinmeOY9eKyh6aY72xJh7noLBBq1N0bWi1e2i+83txOCg4yV2oVXhB
o8pYEJ8LT3el6Smxol3C1oFMVdwPgc0vTl25XucMcG/ALE/KNY6pqC2AQ6R2ERlV
gPiUWOPatVkt7+Bs3h5Ramxh7XjBOXeulmCpGSynXNcpZ/06+vofGi/2MlpQZNhH
Ao8eayMp6FcvNucIpUndo1X8dKMv3Y26ZQIDAQAB

RSA labs then said add a header and trailer:

Five hyphens, and the words BEGIN RSA PUBLIC KEY. That is your PEM DER ASN.1 PKCS#1 RSA Public key

PEM: synonym for base64
DER: a flavor of ASN.1 encoding
ASN.1: the binary encoding scheme used
PKCS#1: The formal specification that dictates representing a public key as structure that consists of modulus followed by an exponent
RSA public key: the public key algorithm being used

Not just RSA

After that, other forms of public key cryptography came along:

Diffie-Hellman
Ellicptic Curve

When it came time to create a standard for how to represent the parameters of those encryption algorithms, people adopted a lot of the same ideas that RSA originally defined:

use ASN.1 binary encoding
base64 it
wrap it with five hyphens
and the words BEGIN PUBLIC KEY

But rather than using:

-----BEGIN RSA PUBLIC KEY-----
-----BEGIN DH PUBLIC KEY-----
-----BEGIN EC PUBLIC KEY-----

They decided instead to include the Object Identifier (OID) of what is to follow. In the case of an RSA public key, that is:

RSA PKCS#1: 1.2.840.113549.1.1.1

So for RSA public key it was essentially:

public struct RSAPublicKey {
   INTEGER modulus,
   INTEGER publicExponent 
}

Now they created SubjectPublicKeyInfo which is basically:

public struct SubjectPublicKeyInfo {
   AlgorithmIdentifier algorithm,
   RSAPublicKey subjectPublicKey
}

In actual DER ASN.1 definition is:

SubjectPublicKeyInfo  ::=  SEQUENCE  {
    algorithm  ::=  SEQUENCE  {
        algorithm               OBJECT IDENTIFIER, -- 1.2.840.113549.1.1.1 rsaEncryption (PKCS#1 1)
        parameters              ANY DEFINED BY algorithm OPTIONAL  },
    subjectPublicKey     BIT STRING {
        RSAPublicKey ::= SEQUENCE {
            modulus            INTEGER,    -- n
            publicExponent     INTEGER     -- e
        }
}

That gives you an ASN.1 of:

SEQUENCE (2 elements)
   SEQUENCE (2 elements)
      OBJECT IDENTIFIER 1.2.840.113549.1.1.1
      NULL
   BIT STRING (1 element)
      SEQUENCE (2 elements)
         INTEGER (2048 bit): EB506399F5C612F5A67A09C1192B92FAB53DB28520D859CE0EF6B7D83D40AA1C1DCE2C0720D15A0F531595CAD81BA5D129F91CC6769719F1435872C4BCD0521150A0263B470066489B918BFCA03CE8A0E9FC2C0314C4B096EA30717C03C28CA29E678E63D78ACA1E9A63BDB1261EE7A0B041AB53746D68B57B68BEF37B71382838C95DA8557841A3CA58109F0B4F77A5E929B1A25DC2D6814C55DC0F81CD2F4E5DB95EE70C706FC02C4FCA358EA9A82D8043A47611195580F89458E3DAB5592DEFE06CDE1E516A6C61ED78C13977AE9660A9192CA75CD72967FD3AFAFA1F1A2FF6325A5064D847028F1E6B2329E8572F36E708A549DDA355FC74A32FDD8DBA65
         INTEGER (24 bit): 010001

The final binary encoding in ASN.1 is:

30 82 01 22          ;SEQUENCE (0x122 bytes = 290 bytes)
|  30 0D             ;SEQUENCE (0x0d bytes = 13 bytes) 
|  |  06 09          ;OBJECT IDENTIFIER (0x09 = 9 bytes)
|  |  2A 86 48 86   
|  |  F7 0D 01 01 01 ;hex encoding of 1.2.840.113549.1.1
|  |  05 00          ;NULL (0 bytes)
|  03 82 01 0F 00    ;BIT STRING  (0x10f = 271 bytes)
|  |  30 82 01 0A       ;SEQUENCE (0x10a = 266 bytes)
|  |  |  02 82 01 01    ;INTEGER  (0x101 = 257 bytes)
|  |  |  |  00             ;leading zero of INTEGER
|  |  |  |  EB 50 63 99 F5 C6 12 F5  A6 7A 09 C1 19 2B 92 FA 
|  |  |  |  B5 3D B2 85 20 D8 59 CE  0E F6 B7 D8 3D 40 AA 1C 
|  |  |  |  1D CE 2C 07 20 D1 5A 0F  53 15 95 CA D8 1B A5 D1 
|  |  |  |  29 F9 1C C6 76 97 19 F1  43 58 72 C4 BC D0 52 11 
|  |  |  |  50 A0 26 3B 47 00 66 48  9B 91 8B FC A0 3C E8 A0
|  |  |  |  E9 FC 2C 03 14 C4 B0 96  EA 30 71 7C 03 C2 8C A2  
|  |  |  |  9E 67 8E 63 D7 8A CA 1E  9A 63 BD B1 26 1E E7 A0  
|  |  |  |  B0 41 AB 53 74 6D 68 B5  7B 68 BE F3 7B 71 38 28
|  |  |  |  38 C9 5D A8 55 78 41 A3  CA 58 10 9F 0B 4F 77 A5
|  |  |  |  E9 29 B1 A2 5D C2 D6 81  4C 55 DC 0F 81 CD 2F 4E 
|  |  |  |  5D B9 5E E7 0C 70 6F C0  2C 4F CA 35 8E A9 A8 2D 
|  |  |  |  80 43 A4 76 11 19 55 80  F8 94 58 E3 DA B5 59 2D
|  |  |  |  EF E0 6C DE 1E 51 6A 6C  61 ED 78 C1 39 77 AE 96 
|  |  |  |  60 A9 19 2C A7 5C D7 29  67 FD 3A FA FA 1F 1A 2F 
|  |  |  |  F6 32 5A 50 64 D8 47 02  8F 1E 6B 23 29 E8 57 2F 
|  |  |  |  36 E7 08 A5 49 DD A3 55  FC 74 A3 2F DD 8D BA 65
|  |  |  02 03          ;INTEGER (03 = 3 bytes)
|  |  |  |  010001

And as before, you take all those bytes, Base64 encode them, you end up with your second example:

MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA61BjmfXGEvWmegnBGSuS
+rU9soUg2FnODva32D1AqhwdziwHINFaD1MVlcrYG6XRKfkcxnaXGfFDWHLEvNBS
EVCgJjtHAGZIm5GL/KA86KDp/CwDFMSwluowcXwDwoyinmeOY9eKyh6aY72xJh7n
oLBBq1N0bWi1e2i+83txOCg4yV2oVXhBo8pYEJ8LT3el6Smxol3C1oFMVdwPgc0v
Tl25XucMcG/ALE/KNY6pqC2AQ6R2ERlVgPiUWOPatVkt7+Bs3h5Ramxh7XjBOXeu
lmCpGSynXNcpZ/06+vofGi/2MlpQZNhHAo8eayMp6FcvNucIpUndo1X8dKMv3Y26
ZQIDAQAB

Add the slightly different header and trailer, and you get:

And this is your X.509 SubjectPublicKeyInfo/OpenSSL PEM public key [2].

Do it right, or hack it

Now that you know that the encoding isn't magic, you can write all the pieces needed to parse out the RSA modulus and exponent. Or you can recognize that the first 24 bytes are just added new stuff on top of the original PKCS#1 standard

30 82 01 22          ;SEQUENCE (0x122 bytes = 290 bytes)
|  30 0D             ;SEQUENCE (0x0d bytes = 13 bytes) 
|  |  06 09          ;OBJECT IDENTIFIER (0x09 = 9 bytes)
|  |  2A 86 48 86   
|  |  F7 0D 01 01 01 ;hex encoding of 1.2.840.113549.1.1
|  |  05 00          ;NULL (0 bytes)
|  03 82 01 0F 00    ;BIT STRING  (0x10f = 271 bytes)
|  |  ...

Those first 24-bytes are "new" stuff added:

30 82 01 22 30 0D 06 09 2A 86 48 86 F7 0D 01 01 01 05 00 03 82 01 0F 00

And due to an extraordinary coincidence of fortune and good luck:

24 bytes happens to correspond exactly to 32 base64 encoded characters

Because in Base64: 3-bytes becomes four characters:

30 82 01  22 30 0D  06 09 2A  86 48 86  F7 0D 01  01 01 05  00 03 82  01 0F 00
\______/  \______/  \______/  \______/  \______/  \______/  \______/  \______/
    |         |         |         |         |         |         |         |
  MIIB      IjAN      Bgkq      hkiG      9w0B      AQEF      AAOC      AQ8A

That means if you take your second X.509 public key, the first 32 characters corresponds only to newly added stuff:

If you remove the first 32 characters, and change it to BEGIN RSA PUBLIC KEY:

You have exactly what you wanted - the older RSA PUBLIC KEY format.

Related Solutions

Php – Converting an OpenSSL generated RSA public key to OpenSSH format (PHP)

Ok, I have just solved my own problem by taking a closer look at the C implementation references from Convert pem key to ssh-rsa format (which I did before but apparently I missed some important stuff). I needed to AND the first character of N and e with 0x80 and if it matches add another NULL character at the beginning of the number and increase the size by 1 respectively.

I am not sure why this is done (I didn't find any reference to this in on-line searching I did) but it works.

I've only done basic tests on this but it seems to work well, and here my code:

<?php

$privKey = openssl_pkey_get_private($rsaKey);
$pubKey = sshEncodePublicKey($privKey);

echo "PHP generated RSA public key:\n$pubKey\n\n";

function sshEncodePublicKey($privKey)
{
    $keyInfo = openssl_pkey_get_details($privKey);

    $buffer  = pack("N", 7) . "ssh-rsa" . 
               sshEncodeBuffer($keyInfo['rsa']['e']) . 
               sshEncodeBuffer($keyInfo['rsa']['n']);

    return "ssh-rsa " . base64_encode($buffer); 
}

function sshEncodeBuffer($buffer)
{
    $len = strlen($buffer);
    if (ord($buffer[0]) & 0x80) {
        $len++;
        $buffer = "\x00" . $buffer;
    }

    return pack("Na*", $len, $buffer);
}
?>

C# RSA Public Key Output Not Correct

Unfortunately, the code in the answer you referenced isn't really correct - it exports a private key PEM format, but with only the public key fields correctly set, this is not the same as exporting an RSA public key in standard format.

I actually wrote the code in the other answer to that question, and at the time wrote a mode for exporting the public key in the standard format, but didn't include it in that answer as it wasn't required. Here it is:

private static void ExportPublicKey(RSACryptoServiceProvider csp, TextWriter outputStream)
{
    var parameters = csp.ExportParameters(false);
    using (var stream = new MemoryStream())
    {
        var writer = new BinaryWriter(stream);
        writer.Write((byte)0x30); // SEQUENCE
        using (var innerStream = new MemoryStream())
        {
            var innerWriter = new BinaryWriter(innerStream);
            innerWriter.Write((byte)0x30); // SEQUENCE
            EncodeLength(innerWriter, 13);
            innerWriter.Write((byte)0x06); // OBJECT IDENTIFIER
            var rsaEncryptionOid = new byte[] { 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x01, 0x01, 0x01 };
            EncodeLength(innerWriter, rsaEncryptionOid.Length);
            innerWriter.Write(rsaEncryptionOid);
            innerWriter.Write((byte)0x05); // NULL
            EncodeLength(innerWriter, 0);
            innerWriter.Write((byte)0x03); // BIT STRING
            using (var bitStringStream = new MemoryStream())
            {
                var bitStringWriter = new BinaryWriter(bitStringStream);
                bitStringWriter.Write((byte)0x00); // # of unused bits
                bitStringWriter.Write((byte)0x30); // SEQUENCE
                using (var paramsStream = new MemoryStream())
                {
                    var paramsWriter = new BinaryWriter(paramsStream);
                    EncodeIntegerBigEndian(paramsWriter, parameters.Modulus); // Modulus
                    EncodeIntegerBigEndian(paramsWriter, parameters.Exponent); // Exponent
                    var paramsLength = (int)paramsStream.Length;
                    EncodeLength(bitStringWriter, paramsLength);
                    bitStringWriter.Write(paramsStream.GetBuffer(), 0, paramsLength);
                }
                var bitStringLength = (int)bitStringStream.Length;
                EncodeLength(innerWriter, bitStringLength);
                innerWriter.Write(bitStringStream.GetBuffer(), 0, bitStringLength);
            }
            var length = (int)innerStream.Length;
            EncodeLength(writer, length);
            writer.Write(innerStream.GetBuffer(), 0, length);
        }

        var base64 = Convert.ToBase64String(stream.GetBuffer(), 0, (int)stream.Length).ToCharArray();
        outputStream.WriteLine("-----BEGIN PUBLIC KEY-----");
        for (var i = 0; i < base64.Length; i += 64)
        {
            outputStream.WriteLine(base64, i, Math.Min(64, base64.Length - i));
        }
        outputStream.WriteLine("-----END PUBLIC KEY-----");
    }
}

private static void EncodeLength(BinaryWriter stream, int length)
{
    if (length < 0) throw new ArgumentOutOfRangeException("length", "Length must be non-negative");
    if (length < 0x80)
    {
        // Short form
        stream.Write((byte)length);
    }
    else
    {
        // Long form
        var temp = length;
        var bytesRequired = 0;
        while (temp > 0)
        {
            temp >>= 8;
            bytesRequired++;
        }
        stream.Write((byte)(bytesRequired | 0x80));
        for (var i = bytesRequired - 1; i >= 0; i--)
        {
            stream.Write((byte)(length >> (8 * i) & 0xff));
        }
    }
}

private static void EncodeIntegerBigEndian(BinaryWriter stream, byte[] value, bool forceUnsigned = true)
{
    stream.Write((byte)0x02); // INTEGER
    var prefixZeros = 0;
    for (var i = 0; i < value.Length; i++)
    {
        if (value[i] != 0) break;
        prefixZeros++;
    }
    if (value.Length - prefixZeros == 0)
    {
        EncodeLength(stream, 1);
        stream.Write((byte)0);
    }
    else
    {
        if (forceUnsigned && value[prefixZeros] > 0x7f)
        {
            // Add a prefix zero to force unsigned if the MSB is 1
            EncodeLength(stream, value.Length - prefixZeros + 1);
            stream.Write((byte)0);
        }
        else
        {
            EncodeLength(stream, value.Length - prefixZeros);
        }
        for (var i = prefixZeros; i < value.Length; i++)
        {
            stream.Write(value[i]);
        }
    }
}