I am new to cryptography and am going through the book Understanding Cryptography by Paar and Pelzl.

From what I understand Symmetric key distribution systems like Kerberos do not provide PFS because an attacker will be able to decrypt every session key ever encrypted with a compromised KEK.

In the book, on page 342, they say that Asymmetric ciphers like Diffie-Hellman or RSA, when used for key distribution, will provide FPS. I understand that Diffie-Hellman will provide PFS because each session key will have nothing to do with any other session key. However I've been stumped for a few days now trying to figure out how RSA will provide PFS. Am I missing something or just misunderstanding what they wrote?

  • 12
    $\begingroup$ You can achieve forward secrecy with RSA if you generate short lived key-pairs. But most protocols that provide forward secrecy use Diffie-Hellman, probably because generating DH keys is cheap and easy compared to RSA keys. $\endgroup$ Aug 1, 2014 at 8:13

2 Answers 2


This expands CodesInChaos's comment into an answer.

Forward Secrecy (that is, maintaining confidentiality of messages enciphered before compromise of the long term key) can be achieved in a protocol using a public-key signature scheme with a long-term public key, and a public-key encryption scheme with a per-session key; but in the case of RSA signature and encryption, that's inefficient, thus unusual.

As an example: Bob has a long-term RSA key pair $(Mpub_B,Mpriv_B)$ used for signature, with $Mpub_B$ trusted by Alice (perhaps by way of some certificate). In order for Alice to send a confidential message to Bob:

  • Alice
    • draws a 256-bit random $R$
    • sends $R$ to Bob
  • Bob
    • generates a new RSA key pair $(Tpub_B,Tpriv_B)$ used for encryption,
    • RSA-signs the (hash of the) message $R\|Tpub_B$ using $Mpriv_B$ giving signature $S$
    • sends $Tpub_B\|S$ to Alice
  • Alice
    • gets $Tpub_B$ and $S$
    • verifies that $S$ is a valid signature with respect to $Mpriv_B$ for $R\|Tpub_B$, where $R$ is from the recent first step
    • generates a random symmetric session key $K$
    • RSA-enciphers $K$ using $Tpub_B$ yielding $X$
    • enciphers the plaintext message $M$ using key $K$ by a symmetric algorithm (say, AES-CTR will implicit zero IV) yielding ciphertext $C$
    • forgets $K$
    • sends $X\|C$ to Bob
  • Bob
    • gets $X$ and $C$
    • RSA-deciphers $X$ using $Tpriv_B$ yielding $K$
    • forgets $Tpriv_B$
    • deciphers ciphertext $C$ with key $K$ yielding plaintext message $M$
    • forgets $K$.

$K$ allows $M$ to be large, when RSA encryption only directly allows short messages. $R$ protects against replay of an earlier $Tpub_B$.

The scheme is inefficient because the generation of a new RSA key pair is relatively expensive (and normally rare, thus not optimized for speed). That's a good reason why (EC)DH is most used in practice.

It is possible to send several messages using the same $K$, or/and reuse $(Tpub_B,Tpriv_B)$ across multiple sessions, improving performance. But Forward Secrecy triggers only when $K$ and $Tpriv_B$ are forgotten, and $R$ is no longer accepted.

Note: the scheme provides confidentiality, but not integrity or proof of origin; that can be added.

  • 5
    $\begingroup$ You don't need a per session key. You can reuse it for other sessions as long as you discard it after a short time. For example you could use RSA keys rotated once a minute, that way the key generation cost is amortized over several connections andis no longer a limitation, even with RSA. The main downside ia that it complicates the protocol compared to per session keys. $\endgroup$ Aug 2, 2014 at 6:32
  • 7
    $\begingroup$ One may note that SSL used to support ephemeral RSA keys. It was defined as part of the "RSA_EXPORT" cipher suites, in SSL 3.0 and TLS 1.0 (support was dropped in TLS 1.1). When an RSA_EXPORT cipher suite was chosen and the server's public key length was 513 bits or more, the server had to send a ServerKeyExchange message with a RSA key pair in it. I am not sure many SSL implementations supported it, though. $\endgroup$ Aug 3, 2014 at 16:31

You're missing that key generation would occur inside the box (if there was one for RSA key agreement), like for $k_{pr,A}$ and $k_{pub,A}$ on page 343, rather than outside the box, as happened for $k_{pub,CA}$ on page 347.

  • 10
    $\begingroup$ This is a bit cryptic for those without access to the book. $\endgroup$
    – otus
    Aug 1, 2014 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.