Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
5  
They use computers which have no problems working with large numbers. –  mikeazo Jan 30 at 19:20
7  
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
4  
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
1  
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
1  
@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
show 6 more comments

2 Answers 2

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
2  
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
6  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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