# Implementing RSA with small integers in CUDA

I have found some researches dedicated for speeding-up RSA calculations using CUDA. But I am wondering how they do that, given that the biggest unsigned int that could be declared in CUDA is 64 bit.

Could anyone clarify this ambiguity for me?

• Crypto libraries are usually written in C, which also only has at most 64-bit native integers... how do they do it? Why not read the source of openssl or nacl to find out? – Thomas Mar 11 '16 at 4:44
• GCC does have an uint128_t/int128_t type. But nvcc which is cuda compiler has not this type. – Mohamed Esseissah Mar 11 '16 at 4:49
• 128 bits is still not enough, so this doesn't really tell you anything. – Thomas Mar 11 '16 at 5:04
• Many 10y old are familiar with algorithms to perform integer multiplication, and Euclidian division yielding remainder (and quotient), for integers with multiple decimal digits. On a computer, it is more efficient to use base $2^n$ where $n$ is just small enough that $n$-bit values can be efficiently used as operands of multiplication with exact result. In the case of something written for the CUDA compiler you consider, that might be base $2^{32}$. These multiplication and division with remainder algorithms are the hardest part of implementing a working RSA (but not a side-channel proof one). – fgrieu Mar 11 '16 at 10:20
• Of course you can just publish a paper where you simply use "Values of message between 0 and 800 which can accommodate the complete ASCII table" and "8 bit Key Values". Oh and "parallelized RSA that is making use of large prime numbers and large value of n (513581)". Beware when browsing for information on this subject, papers may not be up to scientific standards. – Maarten Bodewes Mar 11 '16 at 12:05

It is of course possible to combine multiple operations on 64 bit or 128 bit to operations modulo $N$ where $N$ is a value up to $2^{1024}$, where 1024 bits is about the absolute minimum size for an RSA key (2048 bit is now being more common, at least 3072 bits is recommended).

For example, take a look at my 32 bit JCInteger class that I created for the 16 bit Java Card platform. Processors even only handle operations on single bits and combine them into 64 or 128 bit instructions resulting in operations in your GPU.

One problem is that modular exponentiation - the most inefficient part of RSA operations - can only be parallelized to a small extend, leading to speed ups of about 2 times single core operation. This is because the multiplications required to perform the exponentiation generally require the outcome of previous multiplications.

So what you will probably see is that 1-4 GPU threads (1 probably most common) will be used to implement modular exponentiation. The rest of the speedup must come from executing a lot of RSA calculations in parallel. This would be useful for instance when a lot of server authentications are required for parallel TLS handshakes.

Parallel operation could be very efficient for creating RSA keys as well. Looking for primes is embarrassingly parallel, and creating RSA keys of 8Ki size and over takes plenty of time even on the fastest CPU's. Unfortunately that doesn't mean much in the end; generally RSA keys are long term keys so there are few use cases where the - possibly huge - speedup would be useful.

Note that I found quite a few CUDA related RSA papers that simply implement RSA for very small sizes of $N$. These should be thought of as exercises rather than real implementations of RSA. This is not always clearly mentioned in the readme files or papers.

• It's more common to try to speed up e.g. the AES encryption as that is used for encrypting the bulk of the data, not just the handshake. – Maarten Bodewes Mar 12 '16 at 0:42

You can do large integer arithmetic in CUDA using PTX assembly. Here is a 128-bit example.

A single CUDA thread itself is quite slow, so you'll need to get a bit creative and find a way to distribute the work among multiple threads if you want to get any speedup.