Before explaining my question, please let me introduce the scenario:

  • There are 2 type of actors: 1 server and N clients
  • Each actor has a RSA 2048 bit private/public key
  • The server knows all the clients public keys
  • The clients know the public key of the server

The desired goals are the following:

  • Clients must authenticate themselves to the server
  • Integrity must be guaranteed for all exchanged messages
  • Secrecy is a plus but not mandatory

A solution that came to my mind is to share a secret between all server-client pairs and then proceed by sending the messages concatenated to the MAC

Server ---- M | MAC(M) ----> Client
Client <--- M | MAC(M) ----- Server

Then on top of this, a challenge-response protocol is used to guarantee the authenticity of the clients.

However, by searching online I was not able to find a "standard" way to generate a shared secret using RSA. I was only able to find DH or ECC protocols for this.

There is a well-defined scheme based on RSA to obtain a shared secret or the aforementioned goals?

  • 2
    $\begingroup$ Couldn't you use basic TLS ? Seems like that would satisfy your requirements. If not, what's different / missing? $\endgroup$ Sep 10, 2018 at 11:05
  • $\begingroup$ The problem is that I'm working on a embedded system. The only functions that I can use are the one provided by github.com/libtom/libtomcrypt $\endgroup$
    – barbo
    Sep 10, 2018 at 11:37
  • $\begingroup$ Is there a reason why you need to use a symmetric MAC for authenticity and not just use RSA signatures? $\endgroup$
    – mat
    Sep 10, 2018 at 13:19
  • $\begingroup$ Wait, is it possible to use RSA to guarantee integrity of the message? It seems not possible: crypto.stackexchange.com/questions/31643/… $\endgroup$
    – barbo
    Sep 10, 2018 at 14:13
  • $\begingroup$ Message integrety can't be guaranteed with RSA since anyone who knows your public key can encrypt any message for you. $\endgroup$ Sep 10, 2018 at 15:38

2 Answers 2


What you want to do is establish a shared, authenticity guaranteeing channel assuming both sides know a fixed public key (either RSA or ECDH based) of each other.

Transport Layer Security (TLS) can do that and really should be used if possible, given that it also takes care of things like state management and replay-prevention for you. If you need a list of embedded-friendly TLS libraries have a look here and also note that TLS does offer cipher suites which only perform authentication and no encryption if the cost of encryption is unbearable to you (though many implementations don't actually have them).

Alternatively if TLS is really not an option and you have the replay-protection figured out, you can also just use RSA signatures (not to be confused with the integrity guarantees provided by RSA encryption!). This can be done either by using RSA-PSS (preferred these days) or by using RSA-PKCSv15 signatures, both of which are supported by LibTomCrypt (your currently preferred library) and guarantee that the signed message actually came from the owner of the associated public / private key and was not altered and can be verified just using the public key.

But now to the question you asked (but probably didn't mean to ask):

There is a well defined scheme based on RSA to obtain a shared secret or the aforementioned goals?

The standard way to do this (and the way TLS does it) is that one side of the exchange picks a random number (e.g. 64 bytes long) and then encrypts it with the other side's public RSA key (and e.g. RSA-OAEP).

If you also want to ensure that the sender is actually who they claim to be, simply sign the resulting ciphertext and enforce signature-checking on the receiver-side.

In addition to this how can I avoid reply attacks?

If there is a a relieable clock on the devices one could e.g. send nonce+timestamp pairs and clean nonces from the cache after e.g. an hour (assuming the nonces are covered in the signed data). Alternatively one could have the recipient send a fresh nonce and the next message must use that nonce so that only one nonce needs to be stored.

That means the first approach would mean this message format:

$$\text{Timestamp}\parallel \text{SenderNonce}\parallel M\parallel \operatorname{Sign}(\text{Timestamp}\parallel \text{FreshSenderChosenNonce}\parallel M)$$

and discard nonces from memory after one hour. Or alternatively

$$\text{ReceiverNonce}\parallel \text{SenderNonce}\parallel M\parallel \operatorname{Sign}(\text{ReceiverNonce}\parallel \text{SenderNonce}\parallel M)$$

where ReceiverNonce was transmitted as the nonce to be used on the next transmission from the receiver to the sender.

  • $\begingroup$ Thank you for your very helpful reply! Unfortunately I am working on a system without stdlib or any syscall so it's very hard and time consuming porting a TLS lib. Since my project is only for a demo purpose I think that I will proceed with RSA signature since I have PSS already available. Just to be sure: every message is encrypted with the private key, so anyone can decrypt it. This doesn't guarantee secrecy but only integrity right? $\endgroup$
    – barbo
    Sep 10, 2018 at 16:49
  • $\begingroup$ @barbo actually I know at least BearSSL only needs memcpy, memmove, memcmp and strlen from the standard library and I'm somewhat confident in saying that cryptlib and mbedtls also need no dynamic memory management. And yes, signatures only guarantee integrity but not secrecy. $\endgroup$
    – SEJPM
    Sep 10, 2018 at 16:55
  • $\begingroup$ Thank you again for your reply. Last doubt: what about a protocol like this one: "M | SIGN(M)". In this way the authenticity and the integrity is guaranteed by the signature of the message $\endgroup$
    – barbo
    Sep 11, 2018 at 8:18
  • $\begingroup$ @barbo see the latested edit. $\endgroup$
    – SEJPM
    Sep 11, 2018 at 8:57
  • $\begingroup$ @barbo: You asked confirmation that "every message is encrypted with the private key" but NO, that's not at all how the answer's "RSA signature" solution works. Rather, it establishes a shared secret by DH or ECDH; then signs a value derived from that shared secret (or at least, part of it) using RSA, proving there was no MitM and that using the shared secret (or the rest of that) for integrity and/or confidentiality is OK. $\endgroup$
    – fgrieu
    Sep 11, 2018 at 9:06

It is asked (among other things)

a well defined scheme based on RSA to obtain a shared secret

The NIST has a recommendation SP 800-56B Rev. 1, titled Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization Cryptography. There's a draft Rev. 2. These propose several key agreement schemes based on RSA (not requiring DH or ECDH). The key established will be used for integrity and (optionally) confidentiality, using symmetric cryptography and some authenticated encryption.

In the situation where both parties have a public/private key pair and know the other party's public key, KAS2 or KTS-KEM-KWS with Key Confirmation are applicable. KEM is conceptually simpler, thus probably better.

Beware that

  • The security analysis assumes that RSA public/private keys used by these schemes are used exclusively for the purpose of key establishment.
  • These schemes do not provide forward secrecy (which is difficult with RSA).
  • Security is lost if the Random Number Generator used to generate the shared key is predictable.

That other answer hints at other solutions, including some that solve the above issues, make use of RSA and asymmetric keys as in the question, but additionally require DH or ECDH.


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.