Understanding Public/Private Key Encryption

Public key cryptography, or asymmetric cryptography is a very important piece of communications and the internet is dependent on it to keep all of the data exchanged between servers safe from attackers.

If you enter your credit card information in a website, without encryption, anyone could “sniff” your traffic and grab your data. But with encryption, the data gets scrambled so that only you and the person you want to be exchanging information with are able to read the info.

The general concept behind the way public key cryptography works is that when Alice wants to give Bob information, she asks him for his public key. Then she uses that key to encrypt the data she wants to give him. Then she sends the data to him, and since it is encrypted, anyone who intercepts the data will be unable to read it. Then once Bob gets the data, he can use his private key, which only he possesses and is mathematically bound to his public key to decrypt it. If a message is encrypted with a public key, only it’s bound private key can decrypt it and get the information out.
Now Bob can do the same to Alice. He can ask her for her private key, ecrypt the message he wants to send with it, send the encrypted data, and once she gets it she can use her private key to decrypt it and get the original message.

I am using JSEncrypt to generate the keys

var jsencrypt = new JSEncrypt();
var publicKey = jsencrypt.getPublicKey();
var privateKey = jsencrypt.getPublicKey();
console.log(publicKey);
console.log(privateKey);

The keys look something like:

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDDs09T2uaB/tM1l8x0Gr4KSjxM
ruIf19/Yx2BYRPGxCsywLtbUFonEi9KLL9N6oeu+TmqOVxdWK0Hd1s0zq/vtefcK
XzPEkNaHP73pmdb3m10Nl6keDp85qvZzGwr9/wg8Y+wN8or1ukhbDqZwKRxmkI8H
dEbZDkWu2JCK3O3lKQIDAQAB
-----END PUBLIC KEY-----
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQDDs09T2uaB/tM1l8x0Gr4KSjxMruIf19/Yx2BYRPGxCsywLtbU
FonEi9KLL9N6oeu+TmqOVxdWK0Hd1s0zq/vtefcKXzPEkNaHP73pmdb3m10Nl6ke
Dp85qvZzGwr9/wg8Y+wN8or1ukhbDqZwKRxmkI8HdEbZDkWu2JCK3O3lKQIDAQAB
AoGAN3eIAV1mveuK04LNyQ6XVHVL9/QNVTcrU9bWoM4Rrrs/3qO38e7dZ1618wtA
Jl7kYVD6dJOMorip94VdLcsOIPXcdLUBA/jOKOnD7Igt66M5krZB/XeD+wUDi/lH
YBaW12ADORSbXC+p0mYB85WPPEOn3HffgI0sHM/ets5jPG0CQQD/FD1Ru0k+2RQw
FVClMUuTXpu2usEH2JOboBjHJyaIMV9WggIhiDJW8Z/RzUoid/yf1fkNA151+YJB
pB2xmbcnAkEAxGgwVOD6FtmNIz64Z5imi0OlG8jBliTCIkQUAC/0UvrHn5rm5ZvX
pa9gSvhNKOEOkUDjvPJMGVtEAV5Bk1OzLwJASUT+DCEY/AWM5/bncFwFknJFlip0
0hUi6TwGggY76jkMYqP7irg9hX3oY3JtjhMbLKpg3J0QICEoikRjByXZVwJAeMM3
NHlATFxnk4w1Bj2t6WMmWfcOUKs5UqhZQ+Q4be0UYOZ1oig4Z/91TaNujfwTYOxt
GvhAIjcjkVPLLjMAsQJBAKHJKfDP0KL4NE/ctvNEbc+ABPf7nfAnH6WliEhowLem
zifw4KUdaiNXf/wiwQXsi/KrzlsJzqDUcQTlUvy2Slc=
-----END RSA PRIVATE KEY-----

All the keys are are just a bunch of big numbers concatenated, encoded in base 64, then encoded with ASN1. If you decode the keys you get something like:

Decoding a public key with ASN1 gets you something like this:

SEQUENCE(2 elem)
    SEQUENCE(2 elem)
    OBJECT IDENTIFIER 1.2.840.113549.1.1.1 rsaEncryption (PKCS #1)
    NULL
  BIT STRING (1 elem)
    SEQUENCE (2 elem)
      INTEGER (1024 bit) 137425514862869046261755236501454065230900195755940639685658196880961…
      INTEGER 65537

And the private key looks something like this:

SEQUENCE(9 elem)
  INTEGER 0
  INTEGER (1024 bit) 137425514862869046261755236501454065230900195755940639685658196880961…
  INTEGER 65537
  INTEGER (1022 bit) 389501951352334182875643303479638869900052052453819580109114089302815…
  INTEGER (512 bit) 1335957442284695206214296103394444984466074215569936883828396830431418…
  INTEGER (512 bit) 1028666861033013309483810613826376398410952873585139276208798388843758…
  INTEGER (511 bit) 3837435166548573669375181065108324584978538399393329239676758217933602…
  INTEGER (511 bit) 6324848533223416439409742968818783793943536779832273719289827101766650…
  INTEGER (512 bit) 8473409693078757515953958638775272579977963984606682293454406310562873…

And you can see how they match up with the various values used in the calculations

> jsencrypt.getKey().n.toString()
"1374255148628690462617552365014540652309001957...
> jsencrypt.getKey().e.toString()
"65537"
> jsencrypt.getKey().d.toString()
"3895019513523341828756433034796388699000520524538...
> jsencrypt.getKey().p.toString()
"13359574422846952062142961033944449844660742155699...

> jsencrypt.getKey().q.toString()
"102866686103301330948381061382637639841095287358...
> jsencrypt.getKey().dmp1.toString()
"383743516654857366937518106510832458497853839939...
> jsencrypt.getKey().dmq1.toString()
"6324848533223416439409742968818783793943536779832...
> jsencrypt.getKey().coeff.toString()
"8473409693078757515953958638775272579977963984606...

The steps for the algorithm go something like:

  • Create 2 prime numbers q and p
  • Calculate the modulus n where n = p * q (this is where the security happens; given p and q you can easily find n but its very difficult given n to find p and q)
  • Calculate the totient λ(n) of q and p where λ(n) = lcm(λ(p), λ(q)) = lcm(p − 1, q − 1)
  • Choose the public exponent e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1. It is usually set as the value 65,537
  • Calculate the private exponent d where d ≡ e−1 (mod λ(n))

Now all those numbers are mathematically bound to eachother and can be used to encrypt and decrypt messages. The formula to encrypt is

F(m,e) = memod(n) = c

And to decrypt the formula is

F(c,d) = cdmod(n) = m

Where m is the message, and c is the encrypted message cypher text.

So you can see how when you have the public key, (e, n), you can encrypt a message that can only be unencrypted with the private key (d, n)

This is a very basic overview of how public key cryptography works. In reality it is much more complex as there are vulnerabilities with it that need protection against, such as adding padding to prevent plain-text attacks. But it is very useful to have a basic understanding of how it works since we use it so much on a day to day basis.

Leave a Reply

Your email address will not be published. Required fields are marked *