Understanding Public Key Cryptography to understand JSON Object Signing and Encryption (JOSE)

Igor Rendulic -

An essential algorithm for Public Key Cryptography is a a trap door function: a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction.

There are two flavors of public key cryptography. One is RSA and the second is Elliptic curve cryptography. These are basically the two competing algorithms.

RSA

is the most popular public key cryptography system. It has a public key and a private key. The idea behind RSA is that factoring is slow while multiplication is fast.

Factoring (called "Factorising" in the UK) is the process of finding the factors: (2 x 3 = 6, 2 is a factor and 3 is a factor).  

Prime numbers are fundamental piece of math for RSA. Another thing we need is a bit of modular arithmetic.  It's also an algorithm of choice for HTTPS connections.

How to create RSA key

  1. Choose  2 very large prime numbers (p and q)  => example: p = 2, q = 7
  2. Find the product of those 2 numbers (N = p*q) => example: N = 2*7 = 14
  3. Use Euler Totient (p - 1)*(q-1) = T => T = (p-1)(q-1) = (2-1)(7-1) = 6
  4. Take two numbers (e and d) where (e*d) mod T = 1 => (e*d)  mod 6 = 1
  • e must be less than 6, must be co-prime of 6 and 14 => e = 5
  • d must be less than 6, find multiples of 5, then mod(multiple, 6), pick any product with mod = 1 => e.g. d = 11
  1. Public N and e numbers. This is your public key => (5, 14)
  2. Keep N and d secret. This is your private key.  => (11, 14)

How to encrypt

Let's say B letter is number 2. (e.g. A= 1, B=2, ...)
Encryption value: $ 2^5 mod 14 = 4 $ where 2 is the secret message, 5 is first part of public key, 14 is the second part of public key.

4 is the letter "D". This is our encrypted message.  

How to decrypt

Private key is (11, 14)
Secret message is "D", number 4.

Decrypted value is: $ 4^11 mod 14 $ (11 is first part of private key, 14 is the second part of private key, 4 is letter D).
$ 4^11 = 4,194,304 mod 14 = 2.000000000000002 $

2 is the decrypted message or letter "A".

RSA numbers

Security of RSA is in the difficulty to find the two prime numbers (factors).

RSA - name of the algorithm
e.g. 100 - number of decimal digits (330 bits)

RSA-100 (factors where found, thus cracked)
RSA-280 and beyond (not yet cracked)

Diffie-Hellman Key Exchange

Another algorithm based on prime numbers is secure exchange of cryptographic keys.

Simple Diffie-Hellman algorithm in Python

The goals of the algorithm is for both parties (Alice and Bob) to come to an agreement of the same cryptographic key (same large number) in secure manner (meaning even if someone sees everything that is exchanged between Alice and Bob they still can't guess the agreed upon cryptographic key).  

Check this link for the code explanation of the algorithm

sharedPrime = 23    # p
sharedBase = 5      # g
 
aliceSecret = 6     # a
bobSecret = 15      # b
 
# Alice Sends Bob A = g^a mod p
A = (sharedBase**aliceSecret) % sharedPrime
print( "\n  Alice Sends Over Public Chanel: " , A )
 
# Bob Sends Alice B = g^b mod p
B = (sharedBase ** bobSecret) % sharedPrime
print( "   Bob Sends Over Public Chanel: ", B )
 
print( "\n------------\n" )
print( "Privately Calculated Shared Secret:" )
# Alice Computes Shared Secret: s = B^a mod p
aliceSharedSecret = (B ** aliceSecret) % sharedPrime
print( "    Alice Shared Secret: ", aliceSharedSecret )
 
# Bob Computes Shared Secret: s = A^b mod p
bobSharedSecret = (A**bobSecret) % sharedPrime
print( "    Bob Shared Secret: ", bobSharedSecret )

Key Exchange Problems

Alice doesn't prove to Bob that she is really Alice (also vice-a-versa). Simple Diffie-Hellman doesn't cover that scenario. We'd like to ensure no one can impersonate Alice nor Bob. So Alice and Bob in key exchanges sign their messages before sending to each other.

In case RSA gets compromised Diffie-Hellman uses ephemeral keys (unique for each session) ensuring perfect forward secrecy.

RSA is used only to sign the exchange messages between Alice and Bob to derive short lived shared secrets which are used only per session basis. RSA is too slow for encryption anyways.

Algorithms such as AES are used to encrypt messages after ECDHE-RSA is done.

RSA Future

RSA algorithms depend on the difficulty of factoring. Specialized algorithms like Quadratic Sieve and the General Number Field Sieve were create to tackle the problem of prime factorization and have been moderately successful. As the resources available to decrypt numbers increase, the size of the keys need to grow even faster. This is not a sustainable situation for mobile and low-powered devices that have limited computational power. The gap between factoring and multiplying is not sustainable in the long term.

Elliptic curves

Beyond factoring for a better Trapdoor.

$ y^2 = x^3 +  Ax + B $

With Elliptic Curves Mathematics are simpler to compute for the same level of security. There is a strong tendency to use elliptic curves.

Play with the elliptic curve visualization tool: https://www.desmos.com/calculator/ialhd71we3

Different types of elliptic curves provide different level of security (cryptographic strength).

Elliptic curve cryptography (ECC) provides several groups of algorithms:

  • ECC Digital Signature, like ECDSA (for classical curves) and EdDSA (for twisted Edwards curves with it's variants: Ed25519 and Ed448).
  • ECC encryption algorithms for hybrid encryption schemes like ECIES integration encryption scheme and EEECC (EC-based ElGamal)
  • ECC key agreement algorithms like ECDH, X25519 and FHMQV.

All these algorithms use a curve (like secp256k1, curve25519, NIST p521, p256 or p384). List of elliptic curves considered safe by researchers (mainly Daniel J. Bernstein): Elliptic curves and their safety.

Cryptography Glossary

Resources