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();

The keys look something like:

-----END PUBLIC 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)
  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 (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()
> jsencrypt.getKey().e.toString()
> jsencrypt.getKey().d.toString()
> jsencrypt.getKey().p.toString()

> jsencrypt.getKey().q.toString()
> jsencrypt.getKey().dmp1.toString()
> jsencrypt.getKey().dmq1.toString()
> jsencrypt.getKey().coeff.toString()

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 *