# Proof of concept for RSA malleability

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):
out = (~ (b1[0] & b2[0]) & 0xff) # simple '~' is not enough
outByte = out.to_bytes(1, 'big', signed=False)
fb.write(outByte)


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".

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$$.
• 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? – hbogert Nov 24 '18 at 20:10