# How do institutions like banks do RSA with big primes?

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?

-
They use computers which have no problems working with large numbers. –  mikeazo Jan 30 at 19:20
You reduce modulo n after each multiplication. You only need about 1000 squaring and 1000 multiplications (on 1000 bit numbers) when you use square-and-multiply to compute the exponentiation. So the whole thing takes about 1ms total. –  CodesInChaos Jan 30 at 20:02
As an aside, banks probably don't use numbers much larger than most organizations, or even people. They're more cautious about things like key management, but exceptionally strong crypto is widely available these days; it's more of a matter of ensuring your protocols are properly secure instead of picking a insanely high (computational) security level. –  Reid Jan 30 at 22:12
Incidentally, 10^254 is around 2^850. An 850-bit RSA key is awful. It's borderline breakable now. 1024-bit keys are considered deprecated and barely secure; 2048-bit keys are normally used nowadays. –  Matt Nordhoff Jan 31 at 4:17
@fgrieu Sounds pretty close. I get 1.5 ms (660 signs/s) on my 32-bit, four-year-old Xeon, Xen VPS with openssl speed rsa (single-threaded). (13,100 verifies/s, or... 0.076 ms.) –  Matt Nordhoff Feb 1 at 3:02

When calculating terms in the form of a ^ b mod c 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^b$ with 4096-bit keys would require more RAM than even todays biggest computers have).

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

1. If $e$ is negative return modInverse(a, m) ^ -e mod m
2. If $e = 1$ the exponentionation can be ignored and the simple modulo is calcualted.
3. $s=1$
4. While $e$ is not $0$

1. s = s * t mod m
2. e = floor(e / 2) (bitshift to the right by 1)
3. a=a * a mod m
5. a is the result.

-
You never defined $t$... –  figlesquidge May 1 at 17:11
Sorry for this, $t=a$ –  marstato May 2 at 16:13
Fair enough. However, it sounds like your algorithm will give the same output for $e=\mathtt{0b1000}$ and $e=\mathtt{0b1011}$. that is, I can't see anywhere why you use the actual values of $e$, rather than just it's bit-length –  figlesquidge May 2 at 16:15
I just transcribed the code for the method modPow of Javas BigInteger class as seen here: link –  marstato May 2 at 18:32

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.

-
do you have any sources to back up your claim that banks do this (not saying you are wrong, just that a source would add credibility). –  mikeazo Jan 31 at 13:12
1) CRT is only a factor 4 speedup. The OP has trouble understanding why modular exponentiation has anywhere near acceptable performance, a factor 4 is irrelevant in this context. 2) Larger devices will use CRT as well. It's just as nice on a large x86/AMD64 as it is on a constrained device. –  CodesInChaos Jan 31 at 13:28