Key encapsulation mechanism

{{Short description|Public-key cryptosystem}} {{distinguish|Key wrap}} right|thumb|alt=Flow diagram of a key encapsulation mechanism, relating the inputs and outputs of the Gen, Encap, and Decap algorithms of a KEM|A key encapsulation mechanism, to confidentially transport a ''random secret key'' <math>k</math> from a sender to a receiver, consists of three algorithms: Gen, Encap, and Decap. Circles shaded blue—the receiver's public key <math>pk</math> and the encapsulation <math>c</math>—can be safely revealed to an adversary, while boxes shaded red—the receiver's private key <math>sk</math> and the encapsulated secret key <math>k</math>—must be kept secret. The secret key <math>k</math> is chosen at random inside the logic of Encap, and the sender has no control over it.

In cryptography, a '''key encapsulation mechanism''' ('''KEM''') is a public-key cryptosystem that allows a sender to generate a short secret key and transmit it to a receiver confidentially, in spite of eavesdropping and intercepting adversaries.<ref name="galbraith2012mathpkcbook-kemdem">{{cite book |author-last=Galbraith |author-first=Steven |title=Mathematics of Public-Key Cryptography |date=2012 |section=§23.1.1: The KEM/DEM paradigm |pages=471–478 |publisher=Cambridge University Press |isbn=978-1-107-01392-6 }}</ref><ref name="shoup2000hashhedgecca">{{cite conference |author-last=Shoup |author-first=Victor |author-link=Victor Shoup |title=Using Hash Functions as a Hedge against Chosen Ciphertext Attack |editor-last=Preneel |editor-first=Bart |editor-link=Bart Preneel |date=May 2000 |conference=Advances in Cryptology – EUROCRYPT 2000 |conference-url=https://link.springer.com/book/10.1007/3-540-45539-6 |volume=1807 |series=Lecture Notes in Computer Science |publisher=Springer |location=Bruges, Belgium |isbn=978-3-540-67517-4 |pages=275–288 |doi=10.1007/3-540-45539-6_19 |doi-access=free |url=https://link.springer.com/chapter/10.1007/3-540-45539-6_19 }}</ref><ref name="cramer-shoup2003pkecca">{{cite journal |author-last1=Cramer |author-first1=Ronald |author-link1=Ronald Cramer |author-last2=Shoup |author-first2=Victor |author-link2=Victor Shoup |title=Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack |journal=SIAM Journal on Computing |volume=33 |issue=1 |pages=167–226 |year=2003 |publisher=Society for Industrial and Applied Mathematics |doi=10.1137/S0097539702403773 |url=https://epubs.siam.org/doi/10.1137/S0097539702403773 |url-access=subscription }}</ref> Modern standards for public-key encryption of arbitrary messages are usually based on KEMs.<ref name="fips203">{{citation |title=FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard |publisher=NIST |date=2024-08-13 |url=https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.pdf |doi=10.6028/NIST.FIPS.203 |doi-access=free }}</ref>{{Ref RFC|9180}}

A KEM allows a sender who knows a public key to simultaneously generate a short random secret key and an '''encapsulation''' or '''ciphertext''' of the secret key by the KEM's '''encapsulation algorithm'''. The receiver who knows the private key corresponding to the public key can recover the same random secret key from the encapsulation by the KEM's '''decapsulation algorithm'''.<ref name="galbraith2012mathpkcbook-kemdem"/><ref name="shoup2000hashhedgecca"/><ref name="cramer-shoup2003pkecca"/>

The security goal of a KEM is to prevent anyone who ''does not'' know the private key from recovering any information about the encapsulated secret keys, even after eavesdropping or submitting other encapsulations to the receiver to study how the receiver reacts.<ref name="galbraith2012mathpkcbook-kemdem"/><ref name="shoup2000hashhedgecca"/><ref name="cramer-shoup2003pkecca"/>

==Difference from public-key encryption==

left|thumb|alt=Flow diagram of a public-ken encryption scheme, relating the inputs and outputs of its Gen, Encrypt, and Decrypt algorithms|A public-key encryption scheme, to confidentially transport an ''arbitrary message'' <math>m</math> from a sender to a receiver. The message <math>m</math> is chosen by the sender. The difference between a public-key encryption scheme and a KEM is that a public-key encryption scheme allows a sender to choose an arbitrary message from some space of possible messages, while a KEM chooses a short secret key at random for the sender.<ref name="galbraith2012mathpkcbook-kemdem"/><ref name="shoup2000hashhedgecca"/><ref name="cramer-shoup2003pkecca"/>

The sender may take the random secret key produced by a KEM and use it as a symmetric key for an authenticated cipher whose ciphertext is sent alongside the encapsulation to the receiver. This serves to compose a public-key encryption scheme out of a KEM and a symmetric-key authenticated cipher in a hybrid cryptosystem.<ref name="galbraith2012mathpkcbook-kemdem"/><ref name="shoup2000hashhedgecca"/><ref name="cramer-shoup2003pkecca"/>{{Ref RFC|9180}}

Most public-key encryption schemes such as RSAES-PKCS1-v1_5, RSAES-OAEP, and Elgamal encryption are limited to small messages{{Ref RFC|8017}}<ref name="menezes-vanoorschoot-vanstone1996hac">{{cite book |author-last1=Menezes |author-first1=Alfred J. |author-link1=Alfred Menezes |author-last2=van Oorschot |author-first2=Paul C. |author-link2=Paul van Oorschot |author-last3=Vanstone |author-first3=Scott A. |author-link3=Scott Vanstone |title=Handbook of Applied Cryptography |publisher=CRC Press |date=October 1996 |isbn=0-8493-8523-7 |url=https://cacr.uwaterloo.ca/hac/ |chapter=8. Public-Key Encryption |chapter-url=https://cacr.uwaterloo.ca/hac/about/chap8.pdf#page=2 |pages=283–319 }}</ref> and are almost always used to encrypt a short random secret key in a hybrid cryptosystem anyway.<ref name="ferguson-kohno-schneier2010cryptoengineering">{{cite book |author-last1=Ferguson |author-first1=Niels |author-link1=Niels Ferguson |author-last2=Kohno |author-first2=Tadayoshi |author-link2=Tadayoshi Kohno |author-last3=Schneier |author-first3=Bruce |author-link3=Bruce Schneier |title=Cryptography Engineering |year=2010 |publisher=Wiley |isbn=978-0-470-47424-2 |chapter=12. RSA |pages=195–211 }}</ref>{{Ref RFC|4880}}{{Ref RFC|9180}} And although a public-key encryption scheme can conversely be converted to a KEM by choosing a random secret key and encrypting it as a message, it is easier to design and analyze a secure KEM than to design a secure public-key encryption scheme as a basis. So most modern public-key encryption schemes are based on KEMs rather than the other way around.<ref name="nist-pqc-faqs">{{cite web |title=Post-Quantum Cryptography: FAQs |publisher=NIST |date=2024-07-19 |url=https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/faqs |access-date=2024-07-20 |archive-date=2024-06-26 |archive-url=https://web.archive.org/web/20240626090150/https://csrc.nist.gov/Projects/post-quantum-cryptography/faqs }}</ref><ref name="rfc9180"/>

==Definition==

===Syntax===

A KEM consists of three algorithms:<ref name="galbraith2012mathpkcbook-kemdem"/><ref name="shoup2000hashhedgecca"/><ref name="cramer-shoup2003pkecca"/><ref name="dent2002designerkem">{{citation |author-last=Dent |author-first=Alexander W. |title=A Designer's Guide to KEMs |year=2002 |issue=2002/174 |series=Cryptology ePrint Archive |publisher=IACR |url=https://eprint.iacr.org/2002/174 }}</ref><ref name="hofheinz-hövelmanns-kiltz2017modularfo">{{cite conference |author-last1=Hofheinz |author-first1=Dennis |author-last2=Hövelmanns |author-first2=Kathrin |author-last3=Kiltz |author-first3=Eike |title=A Modular Analysis of the Fujisaki-Okamoto Transformation |editor-last1=Kalai |editor-first1=Yael |editor-last2=Reyzin |editor-first2=Leonid |date=November 2017 |conference=Theory of Cryptography – TCC 2017 |conference-url=https://link.springer.com/book/10.1007/978-3-319-70500-2 |volume=10677 |series=Lecture Notes in Computer Science |publisher=Springer |location=Baltimore, MD, United States |isbn=978-3-319-70499-9 |pages=341–371 |doi=10.1007/978-3-319-70500-2_12 |doi-access=free |url=https://link.springer.com/chapter/10.1007/978-3-319-70500-2_12 }}</ref>

# '''Key generation''', <math>(\mathit{pk}, \mathit{sk}) := \operatorname{Gen}()</math>, takes no inputs and returns a pair of a public key <math>\mathit{pk}</math> and a private key <math>\mathit{sk}</math>. # '''Encapsulation''', <math>(k, c) := \operatorname{Encap}(\mathit{pk})</math>, takes a public key <math>\mathit{pk}</math>, randomly chooses a secret key <math>k</math>, and returns <math>k</math> along with its encapsulation <math>c</math>. # '''Decapsulation''', <math>k' := \operatorname{Decap}(\mathit{sk}, c')</math>, takes a private key <math>\mathit{sk}</math> and an encapsulation <math>c'</math>, and either returns an encapsulated secret key <math>k'</math> or fails, sometimes denoted by returning <math>\bot</math> (called "bottom").

In the asymptotic setting of theoretical cryptography, the algorithms are all probabilistic polynomial-time in a security parameter <math>\lambda</math>, and the length of the secret key <math>k</math> is a function of the security parameter <math>\lambda</math>.<ref name="galbraith2012mathpkcbook-kemdem"/><ref name="shoup2000hashhedgecca"/>

In practical cryptography, the secret key <math>k</math> is usually of a fixed length for each algorithm. For example, ML-KEM always uses 256-bit secret keys,<ref name="fips203"/>{{Rp|§ 3.3, p. 16}} while the algorithms in {{IETF RFC|9180}} vary between 256-, 384-, and 512-bit secret keys;<ref name="rfc9180"/>{{Rp|§ 7.1}} secret keys of arbitrary length can be derived from <math>k</math> by a key derivation function.<ref name="NIST.SP.800-227">{{citation |author1-last=Alagic |author1-first=Gorjan |author2-last=Barker |author2-first=Elaine |author3-last=Chen |author3-first=Lily |author4-last=Dustin |author4-first=Moody |author5-last=Robinson |author5-first=Angela |author6-last=Silberg |author6-first=Hamilton |author7-last=Waller |author7-first=Noah |title=SP 800-227 ipd: Recommendations for Key-Encapsulation Mechanisms |version=Initial public draft |publisher=NIST |date=January 2025 |url=https://csrc.nist.gov/pubs/sp/800/227/ipd |doi=10.6028/NIST.SP.800-227.ipd |doi-access=free }}</ref>{{Rp|§ 5.3}}<ref name="rfc9180"/>

====Explicit ''vs.'' implicit rejection====

Decapsulation can fail because its input <math>c'</math> is not an encapsulation <math>c</math> returned by Encap, but has been tampered with or maliciously crafted. KEMs which report failure by a distinguished symbol <math>\bot</math> (implemented in practice by returning an error code or raising an exception) are said to use '''explicit rejection'''. A KEM may instead return a random secret key in this event, or a secret key derived pseudorandomly from <math>c'</math> under the key <math>sk</math>; this is called '''implicit rejection'''.<ref name="Persichetti2012thesis">{{cite thesis |last=Persichetti |first=Edoardo |title=Improving the Efficiency of Code-Based Cryptography |date=November 2012 |degree=PhD |publisher=University of Auckland |department=Department of Mathematics |url=https://hdl.handle.net/2292/19803 }}</ref>{{Rp|§ 5.3, pp. 76–78}}<ref name="hofheinz-hövelmanns-kiltz2017modularfo"/>

===Correctness===

A KEM is '''correct''' if, for any key pair <math>(\mathit{pk}, \mathit{sk})</math> generated by <math>\operatorname{Gen}</math>, decapsulating an encapsulation <math>c</math> returned by <math>(k, c) := \operatorname{Encap}(\mathit{pk})</math> with high probability yields the same key <math>k</math>, that is, <math>\operatorname{Decap}(\mathit{sk}, c) = k</math>.<ref name="shoup2000hashhedgecca"/><ref name="cramer-shoup2003pkecca"/><ref name="dent2002designerkem"/><ref name="hofheinz-hövelmanns-kiltz2017modularfo"/>

===Security: IND-CCA===

'''Security''' of a KEM is quantified by its indistinguishability against adaptive chosen-ciphertext attack, IND-CCA, which is loosely how much better an adversary can do than a coin toss to tell whether, given a random key and an encapsulation, the key is encapsulated by that encapsulation or is an independent random key.<ref name="shoup2000hashhedgecca"/><ref name="cramer-shoup2003pkecca"/><ref name="dent2002designerkem"/><ref name="hofheinz-hövelmanns-kiltz2017modularfo"/><ref name="galbraith2012mathpkcbook-kemdem"/>

Specifically, in the IND-CCA game:

# The key generation algorithm is run to generate <math>(\mathit{pk}, \mathit{sk}) := \operatorname{Gen}()</math>. # <math>\mathit{pk}</math> is revealed to the adversary. # The adversary can query <math>\operatorname{Decap}(\mathit{sk}, c')</math> for arbitrary encapsulations <math>c'</math> of the adversary's choice. # The encapsulation algorithm is run to randomly generate a secret key and encapsulation <math>(k_0, c) := \operatorname{Encap}(\mathit{pk})</math>, and another secret key <math>k_1</math> is generated independently at random. # A fair coin is tossed, giving an outcome <math>b \in \{0,1\}</math>. # The pair <math>(k_b, c)</math> is revealed to the adversary. # The adversary can again query <math>\operatorname{Decap}(\mathit{sk}, c')</math> for arbitrary encapsulations <math>c'</math> of the adversary's choice, ''except'' for <math>c</math>. # The adversary returns a guess <math>b' \in \{0,1\}</math>, and wins the game if <math>b = b'</math>.

The '''IND-CCA advantage''' of the adversary is <math>\left|\Pr[b' = b] - 1/2\right|</math>, that is, the probability beyond a fair coin toss at correctly distinguishing an encapsulated key from an independently randomly chosen key.

==Applications==

===Public-key encryption===

A key encapsulation mechanism can be used together with an authenticated symmetric cipher to construct a public-key encryption scheme for arbitrary messages. The security requirement for the symmetric cipher, called a '''data encapsulation mechanism''' or '''DEM''', is indistinguishability against chosen-ciphertext attack for a ''single'' message encrypted by the sender.<ref name="shoup2001isoproposal"/><ref name="dent2002designerkem"/>{{Ref RFC|9690}}

Given a secure KEM with algorithms Gen/Encap/Decap, and a secure DEM <math>E_k(m)</math>, the following hybrid public-key encryption scheme is also secure against adaptive chosen-ciphertext attack in the public-key setting:<ref name="galbraith2012mathpkcbook-kemdem"/><ref name="shoup2000hashhedgecca"/>{{Rp|§ 7.2, Theorem 7.3}}<ref name="NIST.SP.800-227"/>{{Rp|§ 6.2.1}}

* Key generation: Same as the KEM. * To encrypt a message <math>m</math> for a public key <math>\mathit{pk}</math>: *# Let <math>(k, c) := \operatorname{Encap}(\mathit{pk})</math>. *# Let <math>\sigma := E_k(m)</math>. *# Send <math>(c, \sigma)</math> as the ciphertext. * To decrypt a ciphertext <math>(c', \sigma')</math> with private key <math>\mathit{sk}</math>: *# Let <math>k' := \operatorname{Decap}(\mathit{sk}, c')</math>, or fail if it fails. *# Return the message <math>E_{k'}^{-1}(\sigma')</math>, or fail if it fails.

Note that—as with any public-key encryption on its own—this does not authenticate the sender: anyone with the public key can send a message to a recipient with the private key. Other cryptography, such as digital signatures, must be used in a protocol for a sender to prove its identity to the receiver.<ref name="an2001pkae">{{citation |author-last=An |author-first=Jee Hea |title=Authenticated Encryption in the Public-Key Setting: Security Notions and Analyses |year=2001 |series=Cryptology ePrint Archive |issue=2001/079 |publisher=IACR |url=https://eprint.iacr.org/2001/079 }}</ref>

The use of an ''authenticated'' symmetric cipher is nevertheless required in this ''anonymous'' public-key encryption scheme to meet IND-CCA security. If an ''unauthenticated'' cipher were used, secure only against chosen-plaintext attack (IND-CPA), an adversary could selectively modify a message through its ciphertext in transit, which not only fails IND-CCA on a technicality<ref name="BDPR1998pkesecrelations">{{cite conference |author-last1=Bellare |author-first1=Mihir |author-link1=Mihir Bellare |author-last2=Desai |author-first2=Anand |author-last3=Pointcheval |author-first3=David |author-link3=David Pointcheval |author-last4=Rogaway |author-first4=Phillip |author-link4=Phillip Rogaway |title=Relations among notions of security for public-key encryption schemes |editor-last=Krawczyk |editor-first=Hugo |editor-link=Hugo Krawczyk |book-title=18th Annual International Cryptology Conference, Santa Barbara, California, USA, August 23–27, 1998, Proceedings |conference=Advances in Cryptology—CRYPTO '98 |conference-url=https://link.springer.com/book/10.1007/BFb0055715 |date=1998 |series=Lecture Notes in Computer Science |volume=1462 |issn=0302-9743 |publisher=Springer |isbn=978-3-540-64892-5 |pages=26–45 |url=https://link.springer.com/chapter/10.1007/BFb0055718 |doi=10.1007/BFb0055718 |doi-access=free }}</ref> but also can compromise confidentiality in practice as in EFAIL.<ref name="2018EFAIL">{{cite conference |author-last1=Poddebniak |author-first1=Damian |author-last2=Dresen |author-first2=Christian |author-last3=Müller |author-first3=Jens |author-last4=Ising |author-first4=Fabian |author-last5=Schinzel |author-first5=Sebastian |author-last6=Friedberger |author-first6=Simon |author-last7=Somorovsky |author-first7=Juraj |author-last8=Schwenk |author-first8=Jörg |title=Efail: Breaking S/MIME and OpenPGP Email Encryption using Exfiltration Channels |book-title=27th USENIX Security Symposium (USENIX Security 18) |date=August 2018 |isbn=978-1-939133-04-5 |pages=549–566 |url=https://www.usenix.org/conference/usenixsecurity18/presentation/poddebniak |publisher=USENIX Association }}</ref>

===Key agreement protocols===

A KEM can also be used in an authenticated key agreement protocol such as TLS with forward secrecy for an online session, by having the client and server generate KEM key pairs and exchange signed encapsulations using those key pairs, which they then erase at the end of the session.<ref name="NIST.SP.800-227"/>

===Combining KEMs===

Different KEMs rely on different mathematical problems for their security. For example, the security of Rabin-KEM relies on the difficulty of integer factorization,<ref name="dent2002designerkem"/> which has been studied for centuries, but is known to be vulnerable to quantum computers capable of running Shor's algorithm. In contrast, the security of ML-KEM relies on the difficulty of learning with errors,<ref name="fips203"/> which has only been studied for decades, but is not known to be vulnerable even to an adversary with a Shor-capable quantum computer.

A '''KEM combiner''' is a scheme for combining two KEMs, KEM1 and KEM2 with respective encapsulation algorithms KEM1.Encap and KEM2.Encap and so on, into a combined KEM which is secure if ''either'' KEM1 ''or'' KEM2 is secure.<ref name="Giacon-Hauer-Poettering2018kemcombiners">{{cite conference |author-last1=Giacon |author-first1=Federico |author-last2=Heuer |author-first2=Felix |author-last3=Poettering |author-first3=Bertram |title=KEM Combiners |editor-last1=Abdalla |editor-first1=Michel |editor-last2=Dahab |editor-first2=Ricardo |book-title=21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil, March 25–29, 2018, Proceedings, Part I |conference=Public-Key Cryptography – PKC 2018 |conference-url=https://link.springer.com/book/10.1007/978-3-319-76578-5 |series=Lecture Notes in Computer Science |volume=10769 |publisher=Springer |isbn=978-3-319-76578-5 |pages=190–218 |url=https://link.springer.com/chapter/10.1007/978-3-319-76578-5_7 |doi=10.1007/978-3-319-76578-5_7 |doi-access=free }}</ref>

A KEM that combines a quantum-vulnerable KEM such as DH-KEM using X25519 with a post-quantum KEM such as ML-KEM is sometimes called a '''hybrid''',<ref name="10.1007_978-3-030-25510-7">{{cite conference |author-last1=Bindel |author-first1=Nina |author-last2=Brendel |author-first2=Jacqueline |author-last3=Fischlin |author-first3=Marc |author-last4=Goncalves |author-first4=Brian |author-last5=Stebila |author-first5=Douglas |title=Hybrid Key Encapsulation Mechanisms and Authenticated Key Exchange |editor-last1=Ding |editor-first1=Jintai |editor-last2=Steinwaldt |editor-first2=Rainer |book-title=10th International Conference, PQCrypto 2019, Chongqing, China, May 8–10, 2019 Revised Selected Papers |conference=Post-Quantum Cryptography |conference-url=https://link.springer.com/book/10.1007/978-3-030-25510-7 |series=Lecture Notes in Computer Science |volume=11505 |publisher=Springer |isbn=978-3-030-25510-7 |doi=10.1007/978-3-030-25510-7 |url=https://link.springer.com/chapter/10.1007/978-3-030-25510-7_12 |url-access=subscription }}</ref><ref name="nist-pqc-faqs"/><ref name="ETSI_TS_103_744 V1.1.1">{{citation |author=ETSI Technical Committee Cyber Security (CYBER) |title=Quantum-safe Hybrid Key Exchanges |publisher=ETSI |series=Technical Standards |number=ETSI TS 103 744 V1.1.1 |date=December 2020 |url=https://www.etsi.org/deliver/etsi_ts/103700_103799/103744/01.01.01_60/ts_103744v010101p.pdf }}</ref> not to be confused with a hybrid cryptosystem which combines public-key cryptography with symmetric-key cryptography.

==Examples and motivation==

===RSA===

Traditional RSA encryption, with <math>t</math>-bit moduli and exponent <math>e</math>, is defined as follows:<ref name="aumasson2018seriouscrypto">{{cite book |author-last=Aumasson |author-first=Jean-Philippe |title=Serious Cryptography: A Practical Introduction to Modern Encryption |year=2018 |publisher=No Starch Press |isbn=978-1-59327-826-7 |chapter=10. RSA |pages=181–199 }}</ref><ref name="stinson2006cryptotheorypracticebook">{{cite book |author-last=Stinson |author-first=Douglas R. |author-link=Doug Stinson |title=Cryptography Theory and Practice |edition=3rd |year=2006 |publisher=Chapman & Hall/CRC |isbn=978-1-58488-508-5 |chapter=5. The RSA Cryptosystem and Factoring Integers |pages=161–232 }}</ref><ref name="rsa1978method">{{cite journal |author-last1=Rivest |author-first1=R.L. |author-link1=Ron Rivest |author-last2=Shamir |author-first2=A. |author-link2=Adi Shamir |author-last3=Adleman |author-first3=L. |author-link3=Leonard Adleman |title=A method for obtaining digital signatures and public-key cryptosystems |journal=Communications of the ACM |volume=21 |issue=2 |date=1978-02-01 |publisher=ACM |pages=120–126 |doi=10.1145/359340.359342 |doi-access=free |url=https://people.csail.mit.edu/rivest/Rsapaper.pdf }}</ref>

* '''Key generation''', <math>(\mathit{pk}, \mathit{sk}) := \operatorname{Gen}()</math>: # Generate a <math>t</math>-bit semiprime <math>n</math> with <math>2^{t - 1} < n < 2^t</math> at random satisfying <math>\gcd(e, \lambda(n)) = 1</math>, where <math>\lambda(n)</math> is the Carmichael function. # Compute <math>d := e^{-1} \bmod \lambda(n)</math>. # Return <math>\mathit{pk} := n</math> as the public key and <math>\mathit{sk} := (n, d)</math> as the private key. (Many variations on key generation algorithms and private key formats are available.<ref name="svenda2016mkq">{{cite conference |author-last1=Švenda |author-first1=Petr |author-last2=Nemec |author-first2=Matúš |author-last3=Sekan |author-first3=Peter |author-last4=Kvašňovský |author-first4=Rudolf |author-last5=Formánek |author-first5=David |author-last6=Komárek |author-first6=David |author-last7=Matyáš |author-first7=Vashek |title=The Million-Key Question—Investigating the Origins of RSA Public Keys |conference=25th USENIX Security Symposium |date=August 2016 |publisher=USENIX Association |location=Austin, TX, United States |isbn=978-1-931971-32-4 |pages=893–910 |url=https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/svenda }}</ref>) * '''Encryption''' of <math>(t - 1)</math>-bit message <math>m</math> to public key <math>\mathit{pk} = n</math>, giving <math>c := \operatorname{Encrypt}(\mathit{pk}, m)</math>: # Encode the bit string <math>m</math> as an integer <math>r</math> with <math>0 \leq r < n</math>. # Return <math>c := r^e \bmod n</math>. * '''Decryption''' of ciphertext <math>c'</math> with private key <math>\mathit{sk} = (n, d)</math>, giving <math>m' := \operatorname{Decrypt}(\mathit{sk}, c')</math>: # Compute <math>r' := (c')^d \bmod n</math>. # Decode the integer <math>r'</math> as a bit string <math>m'</math>.

This naive approach is totally insecure. For example, since it is nonrandomized, it cannot be secure against even known-plaintext attack—an adversary can tell whether the sender is sending the message <code>ATTACK AT DAWN</code> versus the message <code>ATTACK AT DUSK</code> simply by encrypting those messages and comparing the ciphertext.

Even if <math>m</math> is always a random secret key, such as a 256-bit AES key, when <math>e</math> is chosen to optimize efficiency as <math>e = 3</math>, the message <math>m</math> can be computed from the ciphertext <math>c</math> simply by taking real number cube roots, and there are many other attacks against plain RSA.<ref name="aumasson2018seriouscrypto"/><ref name="stinson2006cryptotheorypracticebook"/> Various randomized padding schemes have been devised in attempts—sometimes failed, like RSAES-PKCS1-v1_5<ref name="aumasson2018seriouscrypto"/><ref name="bleichenbacher1998pkcs1cca">{{cite conference |author-last=Bleichenbacher |author-first=Daniel |author-link=Daniel Bleichenbacher |title=Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 |editor-last=Krawczyk |editor-first=Hugo |editor-link=Hugo Krawczyk |conference=Advances in Cryptology – CRYPTO '98 |date=August 1998 |conference-url=https://link.springer.com/book/10.1007/BFb0055715 |volume=1462 |series=Lecture Notes in Computer Science |publisher=Springer |location=Santa Barbara, CA, United States |isbn=978-3-540-64892-5 |pages=1–12 |doi=10.1007/BFb0055716 |doi-access=free |url=https://link.springer.com/chapter/10.1007/BFb0055716 }}</ref><ref name="coron-joye-naccache-paillier2000newpkcs1attacks">{{cite conference |author-last1=Coron |author-first1=Jean-Sébastien |author-last2=Joye |author-first2=Marc |author-last3=Naccache |author-first3=David |author-link3=David Naccache |author-last4=Paillier |author-first4=Pascal |title=New Attacks on PKCS#1 v1.5 Encryption |editor-last=Preneel |editor-first=Bart |editor-link=Bart Preneel |conference=Advances in Cryptology – EUROCRYPT 2000 |date=May 2000 |conference-url=https://link.springer.com/book/10.1007/3-540-45539-6 |volume=1807 |series=Lecture Notes in Computer Science |publisher=Springer |location=Bruges, Belgium |isbn=978-3-540-67517-4 |pages=369–381 |doi=10.1007/3-540-45539-6_25 |doi-access=free |url=https://link.springer.com/chapter/10.1007/3-540-45539-6_25 }}</ref>—to make it secure for arbitrary short messages <math>m</math>.<ref name="aumasson2018seriouscrypto"/><ref name="stinson2006cryptotheorypracticebook"/>

Since the message <math>m</math> is almost always a short secret key for a symmetric-key authenticated cipher used to encrypt an arbitrary bit string message, a simpler approach called '''RSA-KEM''' is to choose an element of <math>\mathbb Z/n\mathbb Z</math> at random and use that to ''derive'' a secret key using a key derivation function <math>H</math>, roughly as follows:<ref name="shoup2001isoproposal">{{citation |author-last=Shoup |author-first=Victor |author-link=Victor Shoup |title=A Proposal for an ISO Standard for Public Key Encryption (version 2.1) |year=2001 |issue=2001/112 |series=Cryptology ePrint Archive |publisher=IACR |url=https://eprint.iacr.org/2001/112 }}</ref><ref name="ferguson-kohno-schneier2010cryptoengineering"/>{{Ref RFC|9690}}

* '''Key generation''': As above. * '''Encapsulation''' for a public key <math>\mathit{pk} = n</math>, giving <math>(k, c) := \operatorname{Encap}(\mathit{pk})</math>: # Choose an integer <math>r</math> with <math>0 \leq r < n</math> uniformly at random. # Return <math>k := H(r)</math> and <math>c := r^e \bmod n</math> as its encapsulation. * '''Decapsulation''' of <math>c'</math> with private key <math>\mathit{sk} = (n, d)</math>, giving <math>k' := \operatorname{Decap}(\mathit{sk}, c')</math>: # Compute <math>r' := (c')^d \bmod n</math>. # Return <math>k' := H(r')</math>.

This approach is simpler to implement, and provides a tighter reduction to the RSA problem, than padding schemes like RSAES-OAEP.<ref name="shoup2001isoproposal"/>

===Elgamal===

Traditional Elgamal encryption is defined over a multiplicative subgroup of the finite field <math>\mathbb Z/p\mathbb Z</math> with generator <math>g</math> of order <math>q</math> as follows:<ref name="galbraith2012mathpkcbook-elgamal">{{cite book |author-last=Galbraith |author-first=Steven |title=Mathematics of Public-Key Cryptography |date=2012 |section=§20.3: Textbook Elgamal encryption |pages=471–478 |publisher=Cambridge University Press |isbn=978-1-107-01392-6 }}</ref><ref name="elgamal1985pke">{{cite conference |author-last=Elgamal |author-first=Taher |author-link=Taher Elgamal |title=A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms |editor-last1=Blakley |editor-first1=George Robert |editor-link=George Blakley |editor-last2=Chaum |editor-first2=David |editor-link2=David Chaum |conference=Advances in Cryptology – CRYPTO 1984 |date=August 1984 |conference-url=https://link.springer.com/book/10.1007/3-540-39568-7 |volume=196 |series=Lecture Notes in Computer Science |publisher=Springer |location=Santa Barbara, CA, United States |isbn=978-3-540-15658-1 |pages=10–18 |doi=10.1007/3-540-39568-7_2 |doi-access=free |url=https://link.springer.com/chapter/10.1007/3-540-39568-7_2 }}</ref>

* '''Key generation''', <math>(pk, sk) := \operatorname{Gen}()</math>: # Choose <math>x \in \mathbb Z/q\mathbb Z</math> uniformly at random. # Compute <math>y := g^x \bmod p</math>. # Return <math>\mathit{sk} := x</math> as the private key and <math>\mathit{pk} := y</math> as the public key. * '''Encryption''' of a message <math>m \in \mathbb Z/p\mathbb Z</math> to public key <math>\mathit{pk} = y</math>, giving <math>c := \operatorname{Encrypt}(\mathit{pk}, m)</math>: # Choose <math>r \in \mathbb Z/q\mathbb Z</math> uniformly at random. # Compute: <math display="block">\begin{align} t &:= y^r \bmod p \\ c_1 &:= g^r \bmod p \\ c_2 &:= (t \cdot m) \bmod p\end{align}</math> # Return the ciphertext <math>c := (c_1, c_2)</math>. * '''Decryption''' of a ciphertext <math>c' = (c'_1, c'_2)</math> for a private key <math>\mathit{sk} = x</math>, giving <math>m' := \operatorname{Decrypt}(\mathit{sk}, c')</math>: # Fail and return <math>\bot</math> if <math>(c'_1)^{(p - 1)/q} \not\equiv 1 \pmod p</math> or if <math>(c'_2)^{(p - 1)/q} \not\equiv 1 \pmod p</math>, i.e., if <math>c'_1</math> or <math>c'_2</math> is not in the subgroup generated by <math>g</math>. # Compute <math>t' := (c'_1)^x \bmod p</math>. # Return <math>m' := t^{-1} c'_2 \bmod p</math>.

This meets the syntax of a public-key encryption scheme, restricted to messages in the space <math>\mathbb Z/p\mathbb Z</math> (which limits it to message of a few hundred bytes for typical values of <math>p</math>). By validating ciphertexts in decryption, it avoids leaking bits of the private key <math>x</math> through maliciously chosen ciphertexts outside the group generated by <math>g</math>.

However, this fails to achieve indistinguishability against chosen-ciphertext attack. For example, an adversary having a ciphertext <math>c = (c_1, c_2)</math> for an unknown message <math>m</math> can trivially decrypt it by querying the decryption oracle for the distinct ciphertext <math>c' := (c_1, c_2 g)</math>, yielding the related plaintext <math>m' := m g \bmod p</math>, from which <math>m</math> can be recovered by <math>m = m' g^{-1} \bmod p</math>.<ref name="galbraith2012mathpkcbook-elgamal"/>

Traditional Elgamal encryption can be adapted to the elliptic-curve setting, but it requires some way to reversibly encode messages as points on the curve, which is less trivial than encoding messages as integers mod <math>p</math>.<ref name="koblitz1987ecc">{{cite journal |author-last=Koblitz |author-first=Neal |author-link=Neal Koblitz |title=Elliptic Curve Cryptosystems |journal=Mathematics of Computation |volume=48 |issue=177 |date=January 1987 |pages=203–209 |publisher=American Mathematical Society |doi=10.1090/S0025-5718-1987-0866109-5 |doi-access=free |url=https://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866109-5/S0025-5718-1987-0866109-5.pdf }}</ref>

Since the message <math>m</math> is almost always a short secret key for a symmetric-key authenticated cipher used to encrypt an arbitrary bit string message, a simpler approach—called '''Elgamal-KEM''' or '''DH-KEM'''—is to ''derive'' the secret key from <math>t</math> and dispense with <math>m</math> and <math>c_2</math> altogether, as a KEM, using a key derivation function <math>H</math>:<ref name="galbraith2012mathpkcbook-kemdem"/>{{Ref RFC|9180}}

* '''Key generation''': As above. * '''Encapsulation''' for a public key <math>\mathit{pk} = y</math>, giving <math>(k, c) := \operatorname{Encap}(\mathit{pk})</math>: # Choose <math>r \in \mathbb Z/q\mathbb Z</math> uniformly at random. # Compute <math>t := y^r \bmod p</math>. # Return <math>k := H(t)</math> and <math>c := g^r \bmod p</math> as its encapsulation. * '''Decapsulation''' of <math>c'</math> with private key <math>\mathit{sk} = x</math>, giving <math>k' := \operatorname{Decap}(\mathit{sk}, c')</math>: # Fail and return <math>\bot</math> if <math>(c')^{(p - 1)/q} \not\equiv 1 \pmod p</math>, i.e., if <math>c'</math> is not in the subgroup generated by <math>g</math>. # Compute <math>t' := (c')^x \bmod p</math>. # Return <math>k' := H(t')</math>.

When combined with an authenticated cipher to encrypt arbitrary bit string messages, the combination is essentially the Integrated Encryption Scheme. Since this KEM only requires a one-way key derivation function to hash random elements of the group it is defined over, <math>\mathbb Z/p\mathbb Z</math> in this case, and not a reversible encoding of messages, it is easy to extend to more compact and efficient elliptic curve groups for the same security, as in the ECIES, Elliptic Curve Integrated Encryption Scheme, or {{IETF RFC|9180}} DHKEM(...) instances.

== References == {{reflist}}

{{DEFAULTSORT:Key encapsulation}} Category:Public-key encryption schemes Category:Key management