I'm trying to see how easy RSA malleability is.

I generate 2 ciphertexts with a public key:

cat file1 |  openssl rsautl -raw -encrypt -pubin -inkey public.pem >messageA.encrypted
cat file2 |  openssl rsautl -raw -encrypt -pubin -inkey public.pem >messageB.encrypted

Where file1 and file2 are filled with '1's and '2's resp. I assume -raw means no padding schemes. The files are 256 bytes and the keypair is a plain openssl generated RSA keypair of 2048 bits.

Then I read the files per byte and NAND them with a python script:

with open("messageA.encrypted", "rb") as f1, open("messageB.encrypted", 'rb') as f2, open("messageC.encrypted", "wb") as fb:
for i in range(256):
    b1 = f1.read(1)
    b2 = f2.read(1)
    out = (~ (b1[0] & b2[0]) & 0xff) # simple '~' is not enough
    outByte = out.to_bytes(1, 'big', signed=False)

Afterwards I try to decrypt the file, however it fails as follows:

openssl rsautl -raw -decrypt -in messageC.encrypted -inkey private.pem 
RSA operation error
139710772687296:error:04065084:rsa routines:rsa_ossl_private_decrypt:data too large for modulus:../crypto/rsa/rsa_ossl.c:411:

where file "messageC.encrypted" has a size of 256 bytes

Am I wrong to have expected the above to at least to not fail during decryption?

/update, I would have expected the 'O' (capital 'oh') to be in the decrypted "messageC.encrypted".


1 Answer 1


NAND is not the appropriate combiner for RSA malleability , and can causes the issue observed by making what's produced larger than the public modulus $N$.

RSA malleability applies to textbook RSA, where encryption goes $$x\to \text{Enc}_{(N,e)}(x)=x^e\bmod N$$ and malleability is the property $$\text{Enc}_{(N,e)}(x_1\cdot x_2\bmod N)=\text{Enc}_{(N,e)}(x_1)\cdot\text{Enc}_{(N,e)}(x_2)\bmod N$$ where $\cdot$ stands for integer multiplication (just nothing to do with NAND).

Verifying this with plaintext consisting of files with bytes containing 1 and 2 requires extracting $N$ from the public key, and large-integer arithmetic modulo $N$.

  • $\begingroup$ hmm I should have looked better at the formulas, of course it fails! However, the 'dot' between $x_1 \cdot x_2$ can still be a nand right? Or did I completely misunderstood that part as well? $\endgroup$
    – hbogert
    Nov 24, 2018 at 20:10
  • 1
    $\begingroup$ @hbogert no multiplication. $\endgroup$
    – kelalaka
    Nov 24, 2018 at 21:02
  • 2
    $\begingroup$ @hbogert No, it is multiplication. You can do it with the C library of openssl, not the command line tool. And then it becomes more of a programming question. It's easier in Python, which has built-in bignums. $\endgroup$ Nov 24, 2018 at 23:34

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.