0
$\begingroup$

I am attempting to get a hardware implementation of RSA working but I am having trouble with encryption and decryption. First, I ran these commands to generate the keys:

openssl genrsa -out private-key.pem 2048

openssl rsa -in private-key.pem -pubout -out pubkey-key.pem

I then ran some of my own programs to generate the input files from these for my hardware implementation, specifically files containing the public modulus, public exponent, private modulus (= public modulus) and private exponent. The way I am doing the encrypt and decrypt is breaking the message, exponent and modulus into 32 bit chunks and applying (a ** b) mod n to each chunk. The problem I am having is that when I let's say input the first message chunk, exponent chunk, and modulus chunk into an online calculator (https://www.boxentriq.com/code-breaking/modular-exponentiation), I get an answer and that matches what my hardware calculates, however, when that answer is used as the message for the decyrpting, the online calculator and my hardware both get the same answer, however, that is not the original message. Any idea what I am doing wrong?

$\endgroup$
1
  • 2
    $\begingroup$ "The way I am doing the encrypt and decrypt is breaking the message, exponent and modulus into 32 bit chunks..." - I hope that you're doing that only for testing purposes, and that you'll do something secure (e.g. do OAEP padding) on the real system... $\endgroup$
    – poncho
    Dec 6, 2023 at 15:21

2 Answers 2

3
$\begingroup$

The question says:

The way I am doing the encrypt and decrypt is breaking the message, exponent and modulus into 32 bit chunks and applying $(a^b)\bmod n$ to each chunk.

This fails because when we break $n$ and $d$ into 32-bit chunks

  • The chunks no longer have the desired mathematical property that $e\,d\equiv1\pmod{\lambda(n)}$ where $\lambda$ is the Carmichael function.
  • Beside, the 32-bit chunks of the modulus $n$ often are less than the message chunk, and (textbook) RSA decryption always has a result less than $n$, which thus can't be the original message chunk.

Anyway, RSA is only safe for large modulus. 32-bit (including multiple 32-bit chunks) is broken in milliseconds. 512-bit is easily broken. 2048-bit (without truncation in chunks) is the modern baseline.

Further, RSA encryption requires random padding (e.g. RSAES-OAEP) or hybrid encryption (e.g. with RSA-KEM for the RSA part) in order to be secure.


The correct way to implement RSA modular exponentiation in hardware and have it run fast is to implement multiple-precision arithmetic. An old but still good reference is chapter 14 in the Handbook of Applied Cryptography. See also Modern Computer Arithmetic.

If the primary goal is to get the thing running at all and performance is secondary, the easiest may be bit-by-bit scanning of multiplicand with progressive modular reduction. Basically

  • One block computes for 2048-bit operands $u+v$, then $(u+v)-n$, and selects the second if non-negative, or the first otherwise. That's $u+v\bmod n$.
  • 4096 iterations of that allow computing $x\,y\bmod n$ (by the double and add multiplication method).
  • 4096 iterations of the above let one compute $x^d\bmod n$ (by a square and multiply modular exponentiation method).

This is hugely suboptimal, and could be vulnerable to side-channel attack. But at least it is feasible with modest math and FPGA skills.

$\endgroup$
3
  • 1
    $\begingroup$ I didn't even see the part that he split the modulus into 32 bit chunks (!). Doing something as silly as that never occurred to me... $\endgroup$
    – poncho
    Dec 6, 2023 at 16:33
  • 1
    $\begingroup$ @poncho: at least the OP realized something is wrong in their result and took action. Compared to the bulk of crypto-themed "papers" written by students, that may be above average. $\endgroup$
    – fgrieu
    Dec 6, 2023 at 17:10
  • 1
    $\begingroup$ This is true - everyone makes mistakes - what is important is that you are on a look out for such mistakes (and correct them when you find them) $\endgroup$
    – poncho
    Dec 6, 2023 at 18:25
1
$\begingroup$

Any idea what I am doing wrong?

My initial inclination is that you might be interpreting the pem files incorrectly, that is:

  • Perhaps the value of the modulus is not what OpenSSL meant

  • Perhaps the encryption or decryption exponent you are using is incorrect; it should have $e \cdot d \equiv 1 \pmod{(p-1)(q-1)}$

If either is the case, you would have precisely the symptoms you are showing...

$\endgroup$
3
  • $\begingroup$ Is there any guideline on how to determine d and e (and the modulus) from the pem files? I did not write the C++ code that is parsing the pem files to get these values, so I have no idea where the problem might be. $\endgroup$ Dec 6, 2023 at 15:45
  • $\begingroup$ You can use e.g. openssl to dump the contents of the key in a human-readable way, to check whether your parser produces the correct values. Cf openssl rsa -in path/to/private/key -noout -text $\endgroup$
    – Morrolan
    Dec 6, 2023 at 16:10
  • $\begingroup$ So I did that and for example the first modulus line is: 00:f7:b3:3b:c7:64:72:4a:9d:e5:5b:a7:f5:3c:9f: So from that I got the first 32 bit modulus applied to my 32 bit message is: f7b33bc7h (which is the same as the first 32 bit public modulus() and for the exponent the line is: 32:44:99:79:19:95:68:37:2a:f8:b2:d9:3d:f8:66: so my first 32 bit exponent is 32449979h. These should be the only values I need to feed to the hardware, so I don't know where the imisnterpretation is. $\endgroup$ Dec 6, 2023 at 16:47

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.