# A Primer on Public Key Encryption (PKE)
source: https://developer.mastercard.com/blog/a-primer-on-public-key-encryption/index.md

Authors: John Beric. Overview This blog post is the first in a three-part series on Public Key Encryption (PKE), the threat posed to it by Quantum Computing and how these threats will be addressed. In this post we will provide a primer on PKE that highlights the core principles for key generation and exchange (it is these mathematical principles that potentially make PKE vulnerable to Quantum attacks). We'll also walk through some examples. Setting the scene Cryptography pervades modern communications, it allows two parties to communicate confidentially, knowing that their communications have not been edited. Communications cryptography needs to be bootstrapped by the exchange between the two communicating parties (often known as Alice and Bob) of an initial compact piece of secret data (128 bits say) known as the cryptographic key. The power of modern cryptographic algorithms does the rest in that this initial exchange allows Gigabytes of data to be secured in subsequent transmissions over insecure channels like the Internet. The bootstrap problem - initialising a secure communication -- pre-1970s You and I want to communicate securely but we have not got a secret cryptographic key in place, what do we do? From the time of Caesar (around 55 BCE) to around 1970 CE the only way to perform the bootstrap was by use of an initial exchange mechanism that was physically secured. You and I would meet and whisper the secret to each other (in Caesar's case it was rotate the letters 3 letters forward: "a" becomes "d" etc.) or we would physically exchange a code book. Alternatively, we would use trusted couriers each carrying a part of a secret (my guess is this is what governments did) to exchange the key. It is clear, that establishing a Caesar channel by shouting to the whole world "rotate the message letters three letters forward" is not going to work! Pre-1970 the cryptographic instructions for protecting a message (encryption) allowed you to deduce the mechanism for revealing the message (decryption) so the initial set-up had to be done in secret somehow. The obvious rigidities of this system: No spontaneity. you couldn't just fire up a confidential conversation over an insecure data line with someone if you hadn't exchanged a prior secret in a trusted manner Expensive. if there is a network of n correspondents then n(n-1)/2 set up conversations/hardware installations are required for pairwise end to end secrecy. Being lazy we would say the cost scales as n squared, where n is the number of people in the community. Storing lots of secrets is also operationally a pain and a vulnerability, just think of the passwords you manage. Resilience/geographical reach depends on the ability to set-up and ensure the boot strapping is done securely. The bootstrap problem - the invention of public key cryptography During the 1970s, public key cryptography was invented, separating the twins of encryption/decryption. Knowing how to encrypt no longer automatically conferred the ability to decrypt. As a user I would publicly announce to the world how anyone could send me encrypted messages, all recipients of that announcement were equal, they could encrypt messages only I could read. Decryption of any intercepted messages sent to me required solving a mathematical problem beyond the capability of conventional computers. The piece of data I would broadcast is called a public key. Public key reduced rigidities: Spontaneity. Ask the person you want to secretly correspond with for their public key. They could email it or shout it out to you - it doesn't matter who overhears it, providing its ownership was corroborated. You could get the public key in the same way as you would get a telephone number by looking it up in a trusted directory (Certificate Authorities provide this service). Cost. The cost of a trusted directory scales with the number of entries n, not n squared. Imagine how much simpler life becomes if we only had one password and we didn't have to keep it secret. Today's public key algorithms run acceptably on all computing devices, IoT and upwards, we almost get them for free. Resilience comes automatically. If the information packet can reach its destination, it will be protected. Even if a malicious eavesdropper is permanently "camped" on the physical channel today, secure communication of time limited sensitive data is possible. Public key cryptography is clearly a better solution for key distribution than point to point exchange of secrets using trusted channels that in turn enable the use of untrusted channels like the internet. Public key cryptography as a technology underpins the security of the Internet, without public key technology pre-1970's methods of key distribution would create huge friction and greater operational costs. The proof point of public key; I can participate in a Zoom call with participants from all over the globe who I have never interacted with before, without any extra equipment/investment beyond my PC and an internet connection and our conversation is "end to end" private to us all. Any trusted channel bootstrapping process must compete with this. What is a public key? In one of the many ways of doing public key cryptography, the public key is simply a very big integer (whole number) that is used to define an instance of clock arithmetic. Each of us has a different big number as our public key, duplicates don't happen because of the huge number of choices available and the random nature by which each of us selects our public key. On a normal clock face, 12 defines the arithmetic. Whatever arithmetic you perform on a clock the answer is one of the digits from 1 to 12. \[e.g. 7 x 9 = 63 = 3 on a clock: the hour hand will move 63 hours, which is 5 full revolutions of 12 -the clock size - and will end up at 3 o'clock. The number of revolutions = 60/12 is thrown away\] For me to send a secret message to you I will use your public key (a big number) to perform some clock arithmetic on what I want to send to you secretly. How do we use a public key? In real world applications we don't use a small number like 12 as the modulus (or clock). We pick a very large prime number. When you use a prime number p as the modulus you can find a special number called a generator g so that gn mod p will give you all the values between 1 and p-1. This table will show it in action: given a prime number p of 7 and a generator g of 3: While it is easy to compute the value of gn mod p when we know n, it is very difficult to find the exponent n even if we know the other values. Using a brute force method for a prime number p of 7, we would have to try 6 different values (p-1). And in the real world, our prime number is going to be considerably bigger (typically over 600 digits). Before I show you how this all works in practice with a simple example, I need to call out some neat modular arithmetic rules that we're taking advantage of. The first is called the Modular Exponent Rule: (ab mod n) = (a mod n)b mod n Then we can combine this with the Exponent Power Rule to get the Modular Exponent Power Rule: (ab mod n)c mod n = (abc mod n) = (ac mod n)b mod n This provides the basis for how we exchange keys in public. Here's the process: Alice and Bob agree in public on values for a prime p and a generator g Alice picks a secret number a and Bob picks a secret number b Alice computes A = ga mod p and sends A to Bob Bob computes B = gb mod p and sends B to Alice When Alice gets B, she computes Ba mod p which is the same as (gb mod p)a mod p When Bob gets A, he computes Ab mod p which is the same as (ga mod p)b mod p Again, the Modular Exponent Rule tells us that: (ga mod p)b mod p = (gb mod p)a mod p So, Alice and Bob will end up with the same shared value to use as a key even though neither knows the other secret number and no eavesdropper can determine this value knowing only: g, p, A and B. This is referred to the Diffie-Hellman-Merkle method of key exchange. Using RSA to get around having to be online at the same time to exchange keys RSA (a popular public-key method) involves distributing a public key that anyone can use to encrypt a message to you, but which can only be decrypted using a separate private key. RSA's security relies on the difficulty of factoring large numbers, typically the product of two prime numbers e.g. 173 x 191 is 33,043. It gets exponentially harder when the prime numbers have 100, or more, digits. So, we start by choosing two primes and multiply them: n = pq. If we know p and q, we can use our friend the Modular Exponent Rule to find two other numbers e and d: med mod n = m mod n for all numbers of m To use RSA then, we generate two primes p and q and multiple them to get n i.e. n = pq. Since WE know the factorization, we can find e and d so that med = m mod n". Now we can lock away p, q and d and can share e and n as a public key. Someone sending us a message can encrypt the message m using the public keys e and n: S = me mod n We can use our private key d to decrypt the secret message S: Sd mod n = (me)d mod n = med mod n = m mod n (which is the original message) A quick example which should help make this a little clearer -- using small numbers. Let's say Alice has the following: n = 3127 (remember that n = pq), e = 3 and d = 2011. Bob wants to encrypt the message "50" so that Alice can decrypt it. Bob will know the public keys that Alice has shared: n = 3127 and e = 3. He would encrypt his message "50" by computing: me mod n (503 mod 3127 = 3047) He would send "3047" to Alice who can decrypt it using the private key d: Sd mod n (30472011 mod 3127 = 50) with "50" being the original data "Ah-ah" you say, a bad actor just needs to factorize the public key (n and e) to recover the underlying primes and learn the secret to also be able to do clock arithmetic cube roots. Finding two 300-digit random primes that no one else has used from their 600-digit product is beyond the conventional computing power of the planet. The security of this prime based public key algorithm (RSA) is based on this impossibility of finding prime factors using classical i.e. non quantum, computers of really big numbers.