So What’s In A Public Key?

So What’s In An RSA Public and a Private Key?

You have probably viewed a digital certificate, and one which contains the key pair (the public and private keys) and also the distributed version (with just the public key). You should never distribute the one with the private key, as this could allow someone to break encryption tunnels, or pretend to be the entity who has had their private key stolen. The Lenovo hack a few years ago was a good example of this, and where the key pair was distributed with the software, and where it took someone just a few minutes to crack the password on it. After that, anyone could crack the tunnelled communication to Google (as there was a back-door in the communications).

But what is actually on a key? Well, let’s look at an RSA key [here].

RSA is an asymmetric encryption algorithm, which uses two keys, one to encrypt and the other to decrypt. It was created in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman, and is still one of the most widely used encryption methods. Basically, we have a modulus N and which is the multiplication of two prime numbers: P and Q. We select a value of E, and our encryption key (the public key) is (E,N). After this, we determine the decryption key (D), and our private key becomes (D,N). Here is RSA is 12 lines of Python code [link].

A typical application is in authenticating a sender, where the senders private key is used to encrypt a message, and then is decrypted by the receiver with the senders public key (which is known to anyone who wants it). It is also typically used for encrypting disks/files (and where we can use an AES key, and which is protected by the private key), such as for EFS. In this example, we use a range of key sizes from 512-bits (which is seen to be insecure) right up to 4,096 bits. We could go up to 16,384 bits, but it would take a long time to generate the keys:

SEQUENCE                  // PublicKeyInfo
+- SEQUENCE               // AlgorithmIdentifier
   +- OID                 // 1.2.840.113549.1.1.1
   +- NULL                // Optional Parameters
+- BITSTRING              // PublicKey
   +- SEQUENCE            // RSAPublicKey
      +- INTEGER(N)       // N
      +- INTEGER(E)       // E

A public key has the format:

SEQUENCE                  // PublicKeyInfo
+- SEQUENCE               // AlgorithmIdentifier
   +- OID                 // 1.2.840.113549.1.1.1
   +- NULL                // Optional Parameters
+- BITSTRING              // PublicKey
   +- SEQUENCE            // RSAPublicKey
      +- INTEGER(N)       // N
      +- INTEGER(E)       // E

and for the key pair (the public and the private key):

SEQUENCE                  // PrivateKeyInfo
+- INTEGER                // Version - 0 (v1998)
+- SEQUENCE               // AlgorithmIdentifier
   +- OID                 // 1.2.840.113549.1.1.1
   +- NULL                // Optional Parameters
+- OCTETSTRING            // PrivateKey
   +- SEQUENCE            // RSAPrivateKey
      +- INTEGER(0)       // Version - v1998(0)
      +- INTEGER(N)       // N
      +- INTEGER(E)       // E
      +- INTEGER(D)       // D
      +- INTEGER(P)       // P
      +- INTEGER(Q)       // Q
      +- INTEGER(DP)      // d mod p-1
      +- INTEGER(DQ)      // d mod q-1
      +- INTEGER(Inv Q)   // INV(q) mod p

Code used

I have integrated the library from Here

[HttpPost]
        public ActionResult rsa3(hashing h, FormCollection form)
        {
            h.message = form["message"];

          int [] val = {512,1024,2048,3072,4096,6144,8192,10240,16384};
     

            RSACryptoServiceProvider csp = new RSACryptoServiceProvider(val[0]);
            string str = csp.ToXmlString(true).Replace("><", ">\r\n<");
            string str2= csp.ToXmlString(false).Replace("><", ">\r\n<");
            try
            {
                RSAx rsax = new RSAx(str, val[0]);
                rsax.RSAxHashAlgorithm = RSAxParameters.RSAxHashAlgorithm.SHA1;
                byte[] CT = rsax.Encrypt(Encoding.UTF8.GetBytes(h.message), false, false);
                string str3 = Convert.ToBase64String(CT);
                ViewData["encrypted"] = str3;

                rsax = new RSAx(str, val[0]);
                rsax.RSAxHashAlgorithm = RSAxParameters.RSAxHashAlgorithm.SHA1;
                byte[] PT = rsax.Decrypt(Convert.FromBase64String(str3), true, false);
                string str4 = Encoding.UTF8.GetString(PT);
                ViewData["decrypted"] = str4;
            }
            catch (Exception ex)
            {
                string msg = ex.Message;
            }

            ViewData["tbPublic"] = str;
            ViewData["tbPrivate"] = str2;
            
            
            return PartialView("ParticalRSA3Keys");

        }

And so here is what a key pair looks like:

<RSAKeyValue>
<Modulus>zmZEKAEtOVb7hzlug8YuyMgmuQIZV39ogi2AntgqxW3qlDzQ9ivHAgViB79ZrJ6RTzb7VMc3KVHuJvtt1sGx5w==</Modulus>
<Exponent>AQAB</Exponent>
<P>/NU7g4s8UIdtNdIUNH/CfHbFb6rSRYaGggHvqoaeFZU=</P>
<Q>0PwiU0BRFlOEMNFxamZAQl4IMVYAC40Inm1q8qrpkos=</Q>
<DP>xVpcfi2tAt7zLFOzWddwJF9BdgzM3WBIliqUvXMe6pE=</DP>
<DQ>CxZlZ89QvgN+Tuy9vKxiGmNMwflTFUnNPEKH2woQTFM=</DQ>
<InverseQ>vPSg56IzBeGW4ztA32/T9dmgprpZ1oN5sYkjOZIsGWE=</InverseQ>
<D>yB6h4MPbTGhI8sC9painPefKm8EsPwj6lJV3ywu+1LJRZKR7nIz4n4shSPksXltBBY1WlmayG9FIUs3q3vjZ+Q==</D>
</RSAKeyValue>

The value of “AQAB” is 0x10001 and which is 65,537 (which is the value that we typically use for E). The values of P and Q are the prime numbers and should be kept secret. D is the decryption key, and should also be kept secret. The Modulus (N) is P times Q.