HesapHanem

CRT Decryption Speedup Calculator

Enter the CRT parameters p, q, dp, dq and the ciphertext to recover the message.

How it is calculated

Given the primes p and q, the reduced exponents dp = d mod (p−1) and dq = d mod (q−1), and a ciphertext c, the tool computes m_p = c^dp mod p and m_q = c^dq mod q by square-and-multiply. It finds qinv = q⁻¹ mod p with the extended Euclidean algorithm, forms h = qinv × (m_p − m_q) mod p and recombines m = m_q + h × q (Garner's formula).

It returns no result unless all five inputs are whole numbers, p and q are above 1, dp, dq and c are not negative, and q is invertible modulo p (so p = q fails). Every input must stay within 253, and p × q must fit a 64-bit integer (below about 9.2 × 1018), so the exact message can be shown. Primality of p and q and consistency of dp and dq are not checked. The ≈4× line is a fixed label, not a measurement.

Worked example

Textbook key: p = 61, q = 53 (n = 3233, d = 2753), so dp = 2753 mod 60 = 53 and dq = 2753 mod 52 = 49. Take c = 2790. Then m_p = 279053 mod 61 = 4 and m_q = 279049 mod 53 = 12. The inverse of 53 mod 61 is qinv = 38. h = 38 × (4 − 12) mod 61 = 1. Message: m = 12 + 1 × 53 = 65. Encrypting 65 with e = 17 gives back 2790, so the round trip checks out.

Try this example →

Common mistakes

  • Entering the full private exponent d in the dp or dq field. Use the reduced values d mod (p−1) and d mod (q−1); with an inconsistent exponent the tool still returns a number, but it is not the plaintext.
  • Swapping p and q while keeping dp and dq in the old order. Each exponent must go with its own prime, otherwise m is wrong.
  • Using a composite number for p or q. Primality is not checked and the tool still answers: p = 65 with q = 53 gives a confident 3,245, which is not a valid decryption.
  • Entering a ciphertext larger than n = p × q. The answer is for c mod n, not for the number you typed, and it is always below p × q.
  • Pasting real 2048-bit key values. Inputs beyond 253 (or a p × q beyond 64 bits) show no result, so the tool is for learning with small keys, not for decrypting real traffic.

About this calculator

RSA decryption normally computes m = c^d mod n directly, an expensive modular exponentiation with d often 2048 bits long. The Chinese Remainder Theorem (CRT) optimization splits this into two smaller exponentiations modulo the prime factors p and q instead: m_p = c^dp mod p and m_q = c^dq mod q, using the reduced exponents dp = d mod (p−1) and dq = d mod (q−1).

Because p and q are each roughly half the bit-length of n, these two exponentiations are individually much cheaper, and recombining m_p and m_q with Garner's formula restores the full plaintext m. The net effect is close to a 4× speedup over plain modular exponentiation — this is why CRT-based decryption is the default implementation choice in TLS stacks and crypto libraries like OpenSSL, and why RSA private keys are usually stored with p, q, dp, dq and qInv rather than just d.

Was this helpful?

You can pick up to 3 reactions.

Comments (1)

  • Editorial team

    The 4x speedup is a fixed label, not a timing. The idea behind it: two modular exponentiations with half-size numbers cost roughly one eighth each, so about a quarter of one full-size exponentiation. The tool only handles small textbook keys, with p × q below about 9.2 × 10¹⁸. What key sizes would you like to try?

Popular calculators

Loan Calculator

Monthly payment, total interest and full amortization schedule.

Percentage Calculator

Percent change, percent of, and ratio calculations.

Discount Calculator

Calculate final price, savings, and discount amount.

BMI Calculator

Body mass index from height and weight (metric or imperial).

Age Calculator

Compute your exact age in years, months and days from a birth date.

Compound Interest Calculator

Calculate the final amount and interest earned with compounding.

All Calculators