6
$\begingroup$

We have data types like int and long etc. which can store just a few bytes of integers. But when we are implementing cryptographic algorithms like RSA or Elliptic Curves, we know that the key values are usually 1024 bits long.

How is this implemented in C and C++?

I had gone through /crypto/rsa.c in the Linux kernel which stored these values in some sort of data type called MPI which was included by a module named <linux/mpi.h>. It would be nice if someone could explain what this MPI thing was.

$\endgroup$
1
11
$\begingroup$

MPI stands for Multiple Precision Integer. Multiple precision arithmetic is what you need when you work with integer types that go beyond the machine width $w$.

The basic idea is simple, you represent a large integer with multiple fixed-width words where the i-th word is the i-th "digit" in base B where $B = 2^w$. For example, most current machines are 64-bit so the width $w$ is 64, so with a single word you can represent unsigned integers up $2^{64}-1$. To represent integers larger than $2^{64}-1$, say a 1024-bit integer as in your RSA example, you use $\lceil{1024 / 64}\rceil = 16$ words $a_0, a_1, a_2, \ldots, a_{15}$. Then your integer $x$ of choice is encoded as $$ x = a_0 + 2^{64} a_1 + 2^{2*64} a_2 + \ldots + 2^{15*64} a_{15}. $$ Note that this is essentially a $1024$-bit representation, the only difference is that the bits are grouped into blocks of size 64.

Operations like additions, multiplication etcetera are implemented by building on machine addition, multiplication and so on, but of course additional work is needed to take care of carries and the like. I am not sure what the Linux kernel is using, but in the GNU/Linux world a widely used multiple precision arithmetic library is the GMP.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.