In some contexts (like Internet of Things, QR codes, NFC…) we sometimes need to store data in a very small footprint while still requiring a maximum level of digital security.

Several schemes exists, but we found one combination particularly appealing.

Usually, digital signatures add a minimum overhead of up to 512 bits to the size of the payload (if using Elliptic Curves) or up to 2048 bits (if using RSA).

But there are ways to reduce the overhead caused by the security by using variant modes of RSA providing “signature with message recovery”, like the EMV format used in hundred of millions of credit cards (see here for a related cryptanalysis).

The smart idea is that you can store a part of the data that you want to secure INSIDE the signature itself, and recover it at the same time as you verify that the signature is untampered.

The most efficient of such methods we found is called OPSSR for Optimal Padding for Signature Scheme with message Recovery. The paper explaining the method in details can be found here.

In a very summarized way, the idea is to append a small hash of the data at the end of the payload, encrypt a block of the size of the RSA signature, then sign it with RSA.

For example, if we want a 64-bit level of security (which would require about $$2^{64}$$ attacks to break), with a 2048-bit RSA key, we would follow the signature process described below :

OPSSR Signature

The reverse (signature verification) process being quite natural :

OPSSR Verification

One issue is that the OPSSR paper doesn’t specify a 2048-bit block encryption scheme.

Luckily, there is a scheme called CMC described in details in the research paper here.

In a very summarized way, the idea is to implement two (forward and backward) passes of AES-CBC with a few tweaks in between, as described here :

CMC Mode Encryption

The reverse process being quite natural :

CMC Mode Decryption

In the end, for the calculation cost of just two hashes, two AES-CBC and one RSA, we have a digital signature/verification scheme which has a very minimal footprint overhead !