How do institutions like banks do RSA with big primes?

Question

When encrypting with RSA it is often infeasible to decrypt by just doing c^d mod n, because for example when using the primes $(p,q)=(12553,1233)$, which are small primes compared to those in used by banks, one would often choose the Fermat number $65537$ as public exponent $e$, then the private exponent $d$ is $4267793$, which is a huge number when used as an exponent. How do banks etc. decrypt their data when they choose primes for $p$ and $q$ which are 100s of digits?

Answer 1

First of all to encrypt/decrypt data such institutions as banks use some block or stream ciphers for instance AES (Advanced Encryption Standard), which are very fast compared to RSA algorithm, hundreds times faster to process same amount of data. But block and stream ciphers use symmetric key (which is usually 128-256 bits random number, much smaller than RSA keys), it means that both parties A and B who exchange data encrypted with ciphers need to have same symmteric key and for that they need to share securely this key.

To exchange a symmetric key an asymmetric encryption is used. RSA is an example of an asymmetric encryption system. Most asymmetric encryption systems are much slower than symmetric ciphers, mostly due to usage of big numbers (as you mentioned) in computation.

So to exchange a shared symmetric key, used to encrypt large amount of data, we encrypt this key using RSA public key of recipient. Because only small key (e.g. 256 bits long) is encrypted using RSA, quite small amount of time (e.g. 0.5-1 second) is used for that. After that large symmetrically encrypted data and small asymmetrically (using RSA) encrypted key are send to recipient. On the recipient side the opposite is done - first the symmetric key is decrypted using RSA private key and second large data is decrypted using symmetric key with block or stream cipher like AES.

Also usually some integrity check is done, e.g. by using MAC (Message Authentication Code) - MAC is computed on sender side and checked on recipient side. Or instead of MAC a digital signature (using e.g. DSA, Digital Signature Algorithm) is create on sender's side using sender's private key and verified on recipient's side using sender's public key. MAC is an integrity check value created using symmetric algorithms (e.g. AES, 3DES), while digital signature is created using asymmetric algorithms (e.g. RSA or DSA).

To answer your question about large numbers - in order to compute those large exponents by some large modulus arbitrary length big numbers simulation is done with numbers having thousands of bits, i.e. around one thousand decimal digits. I'll give an example of how exponentiation can be computed in a quite fast way instead of straightforward multiplication (which can take forever). All the multiplications, additions, subtractions and divisions are simulated as a huge numbers arithmetic in the memory using algorithms similar to those that we studied at school to e.g. multiply or divide long numbers on paper. To do a fast exponentiation a technique called Exponentiation by Squaring is used. We will compute value of C = M^E (mod N). This algorithm is proportional to the number of bits in exponent E, i.e. does several big number operations (approximately two multiplies and two divisions) per each bit in number E, so if E is from 1024 to 2048 bits (these lengths are usual for RSA) then algo makes around 1024 to 2048 blocks of 2 to 4 arithmetic operations on big numbers. There are two main versions of that algorithm exist, one is iterating through bits of exponent left to right (MSB-first (Most Significant Bit first) order), another one is iterating right to left (LSB-first (Least Significant Bit first) order) (cited from here):

// LSB Binary Exponentiation Algorithm (scans exponent's E bits right to left)
// Input: Exponent: E of k bits, message M              
// Output: Ciphertext: C = M^E (mod N)                  
C =1 ; S = M;                                           
// Scan E's bits from LSB to MSB (right to left).       
for i := 0 to k-1
  begin                                                 
    // Multiply by degree of M.                         
    if (E_i = 1) C = C * S (mod N);                     
    // Square degree of M.                              
    S = S * S (mod N);                                  
  end;                                                  


// MSB Binary Exponentiation Algorithm (scans exponent's E bits left to right)
// Input: Exponent: E of k bits, message M              
// Output: Ciphertext: C = M^E (mod N)                  
C = 1;                                                  
// Scan E's bits from MSB to LSB (left to right).       
for i := k-1 downto 0 do                          
  begin                                                 
    // Square result.                                   
    C = C * C (mod N);                                  
    // Multiply by M if E's bit is set.                 
    if (E_i = 1) C = C * M (mod N);                     
  end;                                                  

Answer 2

The standard algorithm used for RSA encryption and decryption is exponentiation by squaring.

The basic idea is to write the exponent out in binary. For example, for $d = 4267793$, $$\begin{aligned} 4267793 &= 10000010001111100010001_2 \\ &= 2^{22} + 2^{16} + 2^{12} + 2^{11} + 2^{10} + 2^9 + 2^8 + 2^4 + 2^0.\end{aligned}$$

Now, given some RSA ciphertext $c$, we can express the decryption operation $m = c^d$ as $$\begin{aligned} c^{4267793} &= c^{2^{22} + 2^{16} + 2^{12} + 2^{11} + 2^{10} + 2^9 + 2^8 + 2^4 + 2^0} \\ &= c^{2^{22}} c^{2^{16}} c^{2^{12}} c^{2^{11}} c^{2^{10}} c^{2^9} c^{2^8} c^{2^4} c^{2^0}.\end{aligned}$$

(Here, all the multiplications and powers are taken modulo $n$, of course, but I'm not bothering to write that out explicitly.) Thus, we just need to compute all those powers of $c$ (modulo $n$) and multiply them together (again modulo $n$, of course).

How do we do that? Well, $c^{2^0} = c^1 = c$, of course, and $c^{2^1} = c^2 = c^1 \cdot c^1$. Going further, we have $c^{2^2} = c^4 = c^2 \cdot c^2$, and $c^{2^3} = c^8 = c^4 \cdot c^4$, and so on. In fact, we have the following general formula: $$c^{2^{k+1}} = c^{2^k} \cdot c^{2^k}.$$

Thus, we can start with $c^{2^0} = c$ and repeatedly square it (modulo $n$) to obtain $c^{2^k}$ for any $k$.

To compute $c^d = c^{4267793}$, we need to do this (at least) 22 times, to obtain all the powers up to $c^{2^{22}}$, and then multiply together those $c^{2^k}$ for which the $k$-th bit of $d = 4267793$ is $1$. Thus, in total, we need to do up to $2 \cdot 22 = 44$ modular multiplications (actually fewer; but see below), much fewer than the $4267793$ multiplications we'd need for naïve exponentiation.

There are various optimizations that can reduce the number of multiplications needed even further; see e.g. the linked Wikipedia article for details.

---

Ps. One potential security issue with this method is that the number of multiplications needed depends on the private exponent $d$. Under some circumstances, this could leak information about the private exponent to the attacker, if they can monitor the time needed for decryption (or signing). In fact, in some scenarios, the attacker might even be able to monitor the power consumption of the device doing the decryption, which can potentially leak even more information about which specific bits of $d$ are set.

To avoid such side channel attacks, we can modify the algorithm to always perform the same number of multiplications regardless of $d$. One such variant is Montgomery's ladder method, which always does two multiplications (one of which is a squaring) for each bit of $d$.

Answer 3

When calculating terms in the form of $a^e\bmod m$ most libraries for arbitrary sized integer calculations (e.g. Java's BigInteger) use a special algorithm instead of first doing the exponentiation and then doing the modulo (since storing the result of $a^e$ with 4096-bit keys would require more RAM than even todays biggest computers have).

So this is how Java does it when $a^e\bmod m$ is to be calculated (Pesudo-code):

1. If $e$ is negative, then return $(a^{-1}\bmod m)^{-e}\bmod m\;$, where $a^{-1}\bmod m$ is computed using Euclid's algorithm.
2. If $e = 1$ the exponentiation can be ignored and the simple modulo $a^\bmod m$ is calculated.
3. $s=1$
4. While $e\ne0$
   1. if $e$ is odd, then let $s=s\cdot t\bmod m$
   2. $e=\lfloor e/2\rfloor\;$ (bitshift to the right by 1)
   3. $a = a\cdot a \bmod m$
5. $s$ is the result.

Answer 4

A lot of them (or their HSM) rely on the Chinese Remainder Theorem to speed up computation for decryption and signing.

To quote Wikipedia:

The following values are precomputed and stored as part of the private key:

• p and q: the primes from the key generation,

• $d_P = d\text{ (mod }p - 1\text{)}$,

• $d_Q = d\text{ (mod }q - 1\text{)}$ and

• $q_\text{inv} = q^{-1}\text{ (mod }p\text{)}$.

These values allow the recipient to compute the exponentiation m = cd (mod pq) more efficiently as follows:

• $m_1 = c^{d_P}\text{ (mod }p\text{)}$

• $m_2 = c^{d_Q}\text{ (mod }q\text{)}$

• $h = q_\text{inv}(m_1 - m_2)\text{ (mod }p\text{)}$

(if $m_1 < m_2$ then some libraries compute $h$ as $q_\text{inv}(m_1 + > p - m_2)\text{ (mod }p\text{)}$)

• $m = m_2 + hq$,

This is more efficient than computing $m ≡ c^d \text{ (mod > }pq\text{)}$ even though two modular exponentiations have to be computed. The reason is that these two modular exponentiations both use a smaller exponent and a smaller modulus.

This is typically the kind of things you may find implemented in smart cards or in constrained devices.