CODEWITHSUNDEEP
crsabignum
wolfgunner
wolfgunner

Reputation: 27

How to manipulate big integers for the RSA algorithm in C?

I want to implement the RSA cryptosystem in C. Right now I can encrypt values that fit in one byte (which I know is way too small for any security), but when I increase the size of the primes p and q (and thus of the modulus n = pq), and the size of the encrypted values, it doesn't work.

I believe I know the reasons why my code fails:

  1. the value to be encrypted must be less than the n value (which is not always the case), and
  2. the value of n = pq that I calculate is incorrect, because the real value can't be stored in the variable type that I'm using, and overflows instead.

My question is, how can I use big numbers (pack into 256 bytes, 512 bytes, etc.) and manipulate them in C? Must I use libraries (e.g. GMP)?

Upvotes: 2

Views: 1891

Answers (1)

Ilmari Karonen
Ilmari Karonen

Reputation: 50328

The C language has no native support for arbitrary-precision integer ("bignum") arithmetic, so you will either have to use a library that provides it (I've heard that GMP is a popular choice) or write your own code to handle it.

If you choose the do-it-yourself path, I would recommend representing your numbers as arrays of some reasonably large native unsigned integer type (e.g. uint32_t or uint64_t), with each array element representing a digit in base 2k, where k is the number of bits in the underlying native integers.

For RSA, you don't need to worry about representing negative values, since all the math is done with numbers ranging from 0 up to the RSA modulus n. If you want, you can also take advantage of the upper limit n to fix the number of base 2k digits used for all the values in a particular RSA instance, so that you don't have to explicitly store it alongside each digit array.

Ps. Note that "textbook RSA" is not a secure encryption scheme by itself. To make it semantically secure, you need to also include a suitable randomized padding scheme such as OAEP. Also, padded or not, normal RSA can only encrypt messages shorter than the modulus, minus the length taken up by padding, if any. To encrypt longer messages, the standard solution is to use hybrid encryption, where you first encrypt the message using a symmetric encryption scheme (I would recommend AES-SIV) with a random key, and then encrypt the key with RSA.

Upvotes: 4

Related Questions