GMP - Arithmetic without limitations

Theoretical research in cryptography can be extremely exciting but, on the other hand, a lot of effort should be devoted to correctly and securely implementing cryptosystems that help protect people's privacy. The presence of a bug in a software can be very annoying but if this software deals with crypto and security, then the consequences can be catastrophic.

For many cryptosystems based on number theoretic problems, one of the first issues that a developer faces is the size of the numbers involved in the computations. These numbers are composed of thousands of bits (or hundreds of digits) and they need to be added, multiplied, raised to some powers, etc. Performing these operations is complicated, and doing it efficiently is even more complicated. But thankfully there are tools (libraries) that come to the rescue.

In this post, I will talk about GMP, The GNU Multiple Precision Arithmetic Library. Quoting from the library's homepage, "GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating-point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on. GMP has a rich set of functions, and the functions have a regular interface." This library is written in C but also offers an interface for C++ code, and we are going to focus on this particular one. The final goal of this post will be to implement a simple but complete example of an RSA cryptosystem, from key generation to encryption and decryption of messages.
But, before moving on, a little disclaimer: implementing cryptographic solutions is not an easy task and using homemade solutions is generally considered as not a good idea because of bugs and lack of scrutiny by other members of the community. The sole goal of this post is to show some of the potential of the GMP library.

• Data type -- the basic data type that we will deal with is mpz_class. We can think of it as an arbitrary-sized integer. Some of the functions we will talk about only accepts parameters of type mpz_t, which is the corresponding C type. Luckily, we can always call the function get_mpz_t on a mpz_class object to obtain the corresponding mpz_t object;
• Generating random numbers -- first of all, we consider the problem of generating random numbers with a specific size (measured in bits). GMP offers a function called get_z_bits, that takes in input a number of bits and returns a number with that many bits. But be careful! It means that the returned number takes up to that number of bits. So calling it with argument '3' means that the returned value will be a number between 0 and 7. Instead, what we want is a number that is represented exactly by 3 bits, so 4, 5, 6, or 7. Doing that is quite straightforward: given a number of bits k, we want a random number in the range $\left[2^{k-1}, 2^k\right)$. In order to handle this exponentiation (since $k$ can be very big), we are going to use the function mpz_ui_pow_ui, that raises an unsigned int basis to an unsigned int power and writes the result to a mpz_t object. In order to draw a random number, we are going to initialize a random number generator with this code:
  gmp_randclass rng(gmp_randinit_mt).
  Note: this example uses the Mersenne Twister PRNG, which is known to be insecure for cryptographic applications. After this is done, our function for generating a random number with a specific number of bits can look like the following
  mpz_class generate_rand_exact_bits (const unsigned int size)
  {
      // 2^(size-1)
      mpz_class out;
      mpz_ui_pow_ui(out.get_mpz_t(), 2, size-1);
  
      // 2^(size)
      mpz_class bound;
      mpz_ui_pow_ui(bound.get_mpz_t(), 2, size);
  
      // random offset
      mpz_class rand = rng.get_z_range(bound-out);
  
      return (out + rand);
  }
• Generating prime numbers -- generating random numbers is nice but often not sufficient; we need to generate random-looking prime numbers. This task is obviously harder because there are more constraints that have to be satisfied. Thankfully, GMP comes to the rescue once again: we can in fact take advantage of the function mpz_probab_prime_p that takes as input a mpz_t object that represents the candidate prime and a number that specifies how many times the Miller-Rabin primality test has to be executed, and returns 0 if the candidate is not prime, 1 if it is probably prime and 2 if it is surely prime. Repeating the test 50 times gives a very high degree of confidence on the primality of the candidate, so we are going to generate a random number and test it until we find a candidate that passes all the tests. The code for a function that performs this task can be the following
  mpz_class generate_prime_exact_bits (const unsigned int size)
  {
      mpz_class candidate;
      do {
          candidate = generate_rand_exact_bits(size);
      } while (mpz_probab_prime_p(candidate.get_mpz_t(), REPEAT_MILLER_RABIN) == 0);
      return candidate;
  }
• Modular exponentiation -- the goal of this step is to take a basis $b$, an exponent $e$ and a modulus $m$ and compute $b^e \mod m$. GMP already offers a function called mpz_powm that does what we need, but we can "beautify" it a little bit by wrapping it in another function like the following:
  mpz_class mod_exp (const mpz_class base, const mpz_class exp, const mpz_class mod)
  {
      mpz_class out;
      mpz_powm (out.get_mpz_t(), base.get_mpz_t(), exp.get_mpz_t(), mod.get_mpz_t());
      return out;
  }
• Encryption and decryption -- once we have the function mod_exp for modular exponentiation, RSA encryption and decryption are trivial:
  mpz_class rsa_encrypt (const mpz_class pk, const mpz_class m, const mpz_class mod)
  {
      return mod_exp (m, pk, mod);
  }
  
  
  mpz_class rsa_decrypt (const mpz_class sk, const mpz_class c, const mpz_class mod)
  {
      return mod_exp (c, sk, mod);
  }

Now, we will put everything together and in the main function we will do the following:

1. generate two numbers rsa_p and rsa_q which are prime and composed of an arbitrary (here 2048) number of bits;
2. multiply together rsa_p and rsa_q to obtain the modulus rsa_mod;
3. calculate the Euler's totient function of the modulus by multiplying (rsa_p  -1) and (rsa_q - 1);
4. choose a public exponent rsa_pk: here we are going to use 65537;
5. compute the secret exponent rsa_sk by calculating the multiplicative inverse of rsa_pk modulo rsa_totient. For this task, we can use the function mpz_invert offered by GMP;
6. generate a random 32-bits message;
7. encrypt it and decrypt it to show that the message is recovered correctly

The full code is available here. Assuming that it is saved in a file called main.cpp, it can be compiled with the following command:
g++ -Wall -o main main.cpp -lgmp -lgmpxx

Finally, here is a possible output of the program:

p: 23792449500522212951496314702038682121347194317959904876008718825662914075875899470581320800653437713536069408253411676817620646430212407540403369694134781759107125478056393908946127803961090931948553568336876469309822272887045095561051090700123699901361196085633529272849875353866567000752182158071024473204684307004694765510326847369963753315267894351158697231078788807690227802109570252088084877486698404206015111529669790467025281249212356222609928349702116676081721161733842190421613247070310376995600752548098115546539048072846637620536666595226297844398938704443953343779702008604938853732596401295126782941987

q: 29112805945439121371217246384724375309040486330485414315973357532238818896560861590487525988011993439077520550311524035984480970497774071062272700839286098068182559422588276697743896386738257138746524032717815962171954684796109782069096410172414189261142167684350607916360394902788649692558546060677368837462937413290555419196322614840219369972120722061013641236619226520826654042088554099043918184746705620357166310881550460726728460067235575345180739677700783783242815237362918214982959525838694224404066952951953880663045068810920848575666730532567285210572753317549500155052830379131918899635413209365556429526661

Modulus: 692664965275363134868164310308043386530889977137116066460956916982191344093600913377382983586757778122293014614580541617686926517513948142377215870615527742653194700493457784251321237254925462486660424748287684799960005285232140262663908204076330275297015032277805385557802277182249107190208144962072627103333702166712562912412455374055377823609059561406201023023953754548932692770545184532804691011451566435370564027281954154745605054059335653411252856827668944053539165109486066934327992280592181117681540307774187890207024741310917968286855939570200842820225004987124097822236170460663883584621535528990367892742357001025439624939219952367312627679661863266398010079250545044069312072321631423895274591504669908947731669841676290437961150479342566664751624244101084250756141019398564481030304316812644414619975245318775213481846709606949913834082310037698177108248900032520946078124914227912956069612730720184002438971635446900598624230868985779777067182408067527262398836477646176180149265564531633256045959807480886640631812690951578507074608608075924577570127277599939833799849839997452314926854023853061044555560190656563707831534988797823714162801693363417381512465247240619960211197273430707134124687895683306648515432815407

Totient: 692664965275363134868164310308043386530889977137116066460956916982191344093600913377382983586757778122293014614580541617686926517513948142377215870615527742653194700493457784251321237254925462486660424748287684799960005285232140262663908204076330275297015032277805385557802277182249107190208144962072627103333702166712562912412455374055377823609059561406201023023953754548932692770545184532804691011451566435370564027281954154745605054059335653411252856827668944053539165109486066934327992280592181117681540307774187890207024741310917968286855939570200842820225004987124097822236170460663883584621535528990367892742304095769993663604897238806225864622231475585749564760058562967711410339349194662834205744716004477795118079883111354725159048862414580186148948173567663370928851334497919810423614292621945066549280167717720521050364932649266758956452162536825639219086396668750961940935703957656300852919419991965254045660967825180303374046162336317566884059120678910850226498009948160851632383720333508904913956745247482616068631268540358255880854866759476646002336609572536933340525303598355554521449451080152039954160522951063655835325404680939946676605489966289587929410275548597966757698440898319397266934527673695987832220346760

Message: 2699077189

Ciphertext: 681377152725050864187889498396285584066530595533108416812276566730393956984527765118715661493472361295191987186484833223806930407591255557303290975217436524165953995313143542640632193731686512007342253568013661854913604989704338096439627987512846172004801196181232822308088685943243400345975426883909096147339045273787325984512823244957423398055174828695879849942493712502158108081782163024167101957978799078692054106581518638832961868215165854308314877242675212188837955873975174727647247990393606326403876490500815929414980002030276198625866328310973421532151059071628038306926281825502507926893439321472535762059281448571817796845306517579637703981694846774635322811199431875663174162751403156127612351378340405058549628085390124779083962094777489309709766752481986327599769351343828713992159924065615106068412838813886565270542810886921193120790895042994364186375596015716254331672407180666306582326345460867181975252903332881845979999145141098787286539117576791635044116865176716309063466576180971588107298159543491564320012605624880056428982408094160945322909734375254637560779872935691072801422766106105016077161030768880774211449289008906840655161792691129673110760644874000744631018536155622276779954270891913007605935768473

Decrypted: 2699077189