class: big, middle # ECE 7420 / ENGI 9823: Security .title[ .lecture[Lecture 16:] .title[Public-key cryptography] ] --- # Recall -- ### Classical cryptography -- ### One-time pad -- ### Block ciphers -- ### Cipher modes and MACs --- # Symmetric-key cryptography ### Can demonstrate semantic security for: -- * One-time pad -- (perfectly secure **iff** -- key symbols unpredictable) -- * Block ciphers (with appropriate modes) -- * Stream ciphers (inspired by one-time pad) -- ### but... -- how to share the key? -- * _key exchange problem_ meant crypto only really for global orgs ??? Up until the 1970s, in order to really make use of cryptography, you needed to have a mechanism to reliably and confidentially distribute keying material to all of the places it might be used. This kept the tool of full-strength cryptography out of the hands of all but large and powerful organizations with global networks, i.e., governments and some multi-national corporations. And, of course, multinationals don't have diplomatic pouches! --- # Diffie and Hellman&ast; .footnote[ &ast; Diffie and Hellman, "New directions in cryptography", _IEEE Transactions on Information Theory_ 22(6), 1976. DOI: <a href="https://doi.org/10.1109/TIT.1976.1055638">10.1109/TIT.1976.1055638</a> ] -- #### How to solve key exchange problem? ??? Solving this problem could make cryptography much more useful, both for "ordinary" people and for traditional users of cryptography who wouldn't have to expend so much effort or limit its use quite so much. -- #### Focused on _discrete logarithm_ problem: $$ \begin{align} Y &= \alpha^X & \pmod q \\\\ X &= \log\_\alpha Y & \pmod q \end{align} $$ -- "Normal" logarithms are easy... _discrete_ log$\pmod q$ tougher! -- Example of mathematical [one-way function](https://link.springer.com/referenceworkentry/10.1007%2F978-1-4419-5906-5_467) ??? A [one-way function](https://link.springer.com/referenceworkentry/10.1007%2F978-1-4419-5906-5_467) is one that is relatively easy to compute in one direction (in this case, raising a value to an exponent in a finite field) and extraordinarily difficult to compute in the other direction (in this case, finding the logarithm of $\alpha^X$). How can we use these kinds of one-way functions for cryptographic ends? --- # Diffie-Hellman operations ??? Diffie and Hellman proposed a cryptographic scheme in which two subjects — conventionally referred to as **Alice** and **Bob** — would exchange messages **in the clear**, i.e., assuming that **an eavesdropper can overhear them**. -- 1. Raise $\alpha$ to random numbers $X\_A$, $X\_B \pmod q$: $$ \begin{align} Y\_A &= \alpha^{X\_A} \pmod{q} \\\\ Y\_B &= \alpha^{X\_B} \pmod{q} \end{align} $$ -- 2. Raise results to $X\_A$, $X\_B \pmod q$: $$ {Y\_A}^{X\_B} \mod q = \left( \alpha^{X\_A} \textrm{ mod }{q} \right)^{X\_B} \mod{q} = \alpha^{X\_A X\_B} \mod q $$ -- $$ {Y\_B}^{X\_A} \mod q = \left( \alpha^{X\_B} \textrm{ mod }{q} \right)^{X\_A} \mod{q} = \alpha^{X\_A X\_B} \mod q $$ --- # Diffie-Hellman key exchange $$ {Y\_A}^{X\_B} \mod q = \alpha^{X\_A X\_B} \mod q $$ $$ {Y\_B}^{X\_A} \mod q = \alpha^{X\_A X\_B} \mod q $$ -- #### So what? -- * What if $\alpha^{X\_A X\_B} \mod q$ were called... -- $K\_{AB}$? -- * Exchange of $\alpha^{X\_A}$ and $\alpha^{X\_B}$ **in the clear** establishes a key -- * As long as the discrete log problem is "hard", the established key can be used for symmetric-key cryptography ??? In the brave new world of quantum computers, an algorithm called **Shor's algorithm** can be used to efficiently compute discrete logarithms. So, straightforward Diffie-Hellman key exchange as originally proposed won't work forever — we need another hard mathematical problem. However, there are lots of **one-way functions** out there, some of which are more amenable than others to an environment where the adversary possesses quantum computers. Whether or not we use discrete log as our one-way function, the _idea_ of Diffie-Hellman key exchange is still useful. That's why it turns up all over the place, e.g., ECDH in a TLS cipher suite. -- (with **one** caveat) --- # Significance ### Created a new era of _public-key cryptography_ ??? This is an example of a funny thing that often happens: pure mathematicians play around with number theory and find a result that is elegant, pure and also completely useless in practical terms. That result then sits on the shelf for years and years until someone discovers a way to **apply that result** to a new problem that had nothing to do with the original mathematicians' objectives (which was do discover something elegant). This kind of progression (pure research leads to applied research which leads to practical products) happens all the time, leading to **discoveries you would never have throught to look for**, and it **doesn't work** if you only look for things you can already think of. That's why the "little R, big D" style of R&D doesn't offer much of a future by itself. -- * well, at least as far we anyone knew at the time&ast; .footnote[ &ast; P. Wayner, ["British Document Outlines Early Encryption Discovery"]( https://archive.nytimes.com/www.nytimes.com/library/cyber/week/122497encrypt.html), _The New York Times_, 24 Dec 1997. ] ??? Diffie and Hellman were, unbeknownst by them, beaten to the punch by six years by cryptographers working for the UK government. [C.E.S.G. Report No. 3006](https://web.archive.org/web/20170216051636/https://www.gchq.gov.uk/sites/default/files/document_files/CESG_Research_Report_No_3006_0.pdf) was declassified by GCHQ in 1997, but annoyingly, the report doesn't include any declassification markings: it still looks like a classified document! So, depending on where you work, don't print this out and leave it lying around. 🙂 -- * a.k.a., _asymmetric-key cryptography_ -- * first possiblity of cryptography for everyone --- # Diffie-Hellman today -- <img src="tls-ecdhe-hello.png" width="500" align="right"/> ### Foundation of TLS -- * Used to establish symmetric keys between parties ??? Demo: <img src="tls-hello.png" width="800"/> -- * Inspiration for later ECDHE (will discuss in a few slides) -- ## More TLS later... ??? We'll talk more about TLS and its importance when we get to the **network security** portion of the course next week. --- # RSA cryptosystem .footnote[ Rivest, Shamir, Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", _Communications of the ACM_. 21 (2): 120–126, 1978. DOI: [10.1145/359340.359342](https://doi.org/10.1145%2F359340.359342). ] ??? Although Diffie-Hellman came first, the most famous public-key cryptographic algorithm is RSA. Unlike Diffie-Hellman key agreement, which just lays the groundwork for subsequent use of a symmetric-key cipher, RSA really is an encryption algorithm all by itself. -- 1. Choose large primes $p$ and $q$, compute $n = p \cdot q$ -- 2. Choose $b$, compute $a$ from $a \cdot b \mod \phi(n) = 1$ * $\phi(n) = (p-1)(q-1)$ is the _Euler totient function_ -- * $b$ should be co-prime with $\phi(n)$; compute $a$ using _extended Euclidean algorithm_ -- 3. _Public key_ $K\_P = \\{b, n\\}$, _secret key_ $K\_S = \\{a, p, q\\}$ --- # RSA encryption/decryption -- ### Given large (e.g., 2048b) plaintext $P$: $$ C = P^b \mod n $$ -- $$ \begin{align} P &= C^a \pmod n \\\\ &= \left( P^b \right)^a \pmod n \\\\ &= P^{a \cdot b} \pmod n \\\\ &= P^{k \cdot \phi(n) + 1} \pmod n \\\\ &= P \pmod n \textrm{ if } b \textrm{ co-prime to } n \end{align} $$ ??? This is an example of a **trap-door function**, which adds an additional layer on top of a one-way function. Like a one-way function, a **trap-door** function should be easy to compute in one direction and hard in the other. What's new here is that some **secret knowledge** (in this case, the value $a$) can make even the hard direction easy. Whoever possesses the **private key** can encrypt or decrypt, whereas you can only encrypt without it. --- # Significance of RSA encryption ### Uses _asymmetric key pair_ -- * Can encrypt using public key -- * Decryption requires knowledge of private/secret key -- ### Much slower than symmetric-key encryption! -- * Can be used to encrypt a symmetric key for bulk crypto --- # Security of RSA -- Given $b$, $n$ and $C = P^b \mod n$, find $P$ -- #### Difficult to invert exponentiation ??? #### Difficult to invert exponentiation We already know that the discrete log problem is hard: we can't just find the logarithm of $P^b \mod n$. If you find a way to do that easily, you will break both Diffie-Hellman key exchange _and_ RSA encryption. And become very famous... or very rich! -- * Easy if we know $a$ (remember: $a \cdot b \mod \phi(n) = 1$) -- * Easy if we know $p$ or $q$ (which we can use to find $a$) ??? Finding a multiplicative inverse in real numbers is easy: if $ab=1$, $a=\frac{1}{b}$. However, in a finite, field, finding the inverse of $ab \mod n$ is not so easy! In fact, it's another known "hard problem" in mathematics and computing. -- #### Difficult to factor $n$ ??? #### Difficult to factor $n$ If we could factor $n$ into $p$ and $q$, we could find $a$ in the same way that the private key owner did when they generated it. However, factoring large almost-prime numbers is another known hard problem. Well, at least with conventional computers... -- * ... at least until [quantum computing](https://en.wikipedia.org/wiki/Shor%27s_algorithm) becomes "real"! ??? This is one instance in which some of the hype around quantum computing is justified. If people ever manage to build a quantum computer large enough and powerful enough, [Shor's algorithm](https://en.wikipedia.org/wiki/Shor%27s_algorithm) provides a method of factoring large integers in [bounded-error quantum polynomial time (BQP)](https://en.wikipedia.org/wiki/BQP). So, will that "break all cryptography"? **No! We are already preparing for a quantum world with** [quantum-resistant algorithms](https://en.wikipedia.org/wiki/Post-quantum_cryptography): * [algorithm standardization](https://csrc.nist.gov/projects/post-quantum-cryptography) * [practical experimentation](https://en.wikipedia.org/wiki/CECPQ2) --- # RSA factoring .floatright[ | Bits | Factored | |------|----------| | 330 | 1991 | | 426 | 1994 | | 512 | 1999 | | 640 | 2005 | | 768 | 2009 | | 795 | 2019 | | 829 | 2020 | ] ### RSA Factoring Challenge * Historic contest funded by RSA Security, Inc. -- * Now defunct, people still attacking challenges -- ### Current recommendations * 2048b RSA keys until... 2030? -- * Beyond that... not RSA-2048! ??? Once we get beyond 2048b RSA keys, we're not going to keep using larger and larger RSA moduli. As these numbers get bigger and bigger, it becomes more and more expensive to perform even legitimate RSA operations. Instead, the world is already moving away from RSA and towards... --- # Elliptic-curve cryptography <img src="https://cdn.arstechnica.net/wp-content/uploads/2013/10/elliptic-curve-crypt-image00.png" align="right" width="300"/> * Curve over finite field that satisfies: $$ y^2 = x^3 + ax + b $$ ??? Again, this is all in a **finite field**, not general (real) numbers. Here, we can replace the standard discrete log problem with the **elliptic curve discrete log problem** and re-constitute the same sorts of public-key cryptographic algorithm that we've built with the regular discrete log. -- * Relies on _point addition_ (and many additions makes for multiplication) -- * Can represent keys with _hundreds_ of bits instead of _thousands_ ??? One major advantage of ECC is that we can use smaller keys (hundreds of bits providing equivalent security to thousands of bits for RSA) and do less computational work. -- * ECDH, ECES, ECDSA... ??? Using elliptic curves, we can do key negotation (Elliptic Curve Diffie-Hellman), encryption (Elliptic Curve Encryption Standard) and other things (e.g., the Elliptic Curve Digital Signature Algorithm). --- # How about the reverse? ??? If we have public-key cryptographic algorithms that are easy in one direction and hard in the other direction, could we reverse them so that the opposite is true? -- ### We know that: * $c = E\_P(p)$ requires knowledge of a public key * $p = D\_S(c)$ requires knowledge of a private key -- ### What about: * $s = D\_S(m), m$? ??? Yes! We can apply the "decryption" operation (using the private key) in order to produce a message. -- * **Anyone** can check that $m = E\_P(s)$! ??? If we do this, the message will be such that anyone can check it using the public key. If it checks out, this must mean that **the private key was used to generate the message**. This is a bit like a Message Authentication Code, but now we don't need to have access to a secret key in order to verify the message, **only to create it**! --- # Digital signatures ??? When we use public-key cryptography to produce such a verification token, we call it a **digital signature**. -- * Like encrypting large plaintexts, too slow to be practical -- * Instead, "decrypt" a _cryptographic hash_ of a message ??? We never digitally sign a message directly. Instead, we compute the hash of a message (which computes a fixed-length value from an arbitrary-length message), then produce a digital signature of that hash value. Now we can understand all of the elements of a _TLS Cipher Suite_, e.g.: <img src="tls-ecdhe-hello.png" width="500"/> * ECDHE (Elliptic Curve Diffie-Hellman Exchange) for key negotation * RSA for digital signature of server information * AES-128 in GCM (Galois Counter Mode) for encryption * SHA-256 for message hashing -- #### Used for: <img src="signature.png" align="right" width="450"/> * Signing documents (a bit) <img src="https://freesvg.org/img/Richard_M_Nixon_Signature.png" align="right" width="300" height="100" style="object-fit: cover"/> -- * Signing server certificates (later) -- * Signing code (next time) --- # Summary ### Diffie-Hellman ### RSA ### Elliptic curves ### Digital signatures --- class: big, middle The End.