CT-RSA 2010: Topics in Cryptology - CT-RSA 2010 pp 26-40

# Efficient CRT-RSA Decryption for Small Encryption Exponents

• Subhamoy Maitra
• Santanu Sarkar
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 5985)

## Abstract

Consider CRT-RSA with the parameters p, q, e, d p , d q , where p, q are secret primes, e is the public encryption exponent and d p , d q are the private decryption exponents. We present an efficient method to select CRT-RSA parameters in such a manner so that the decryption becomes faster for small encryption exponents. This is the most frequently used situation for application of RSA in commercial domain. Our idea is to choose e and the factors (with low Hamming weight) of d p , d q first and then applying the extended Euclidean algorithm, we obtain p, q of same bit size. For small e, we get an asymptotic reduction of the order of $${{1}\over{3}}$$ in the decryption time compared to standard CRT-RSA parameters for large N = pq. In case of practical parameters, with 1024 bits N and e = 216 + 1, we achieve a reduction of more than 27%. Extensive security analysis is presented for our selected parameters and benchmark examples are also provided.

### Keywords

RSA CRT-RSA Key Generation Efficient Decryption Primes Exponents

## Preview

### References

1. 1.
Bleichenbacher, D., May, A.: New Attacks on RSA with Small Secret CRT-Exponents. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 1–13. Springer, Heidelberg (2006)
2. 2.
Blömer, J., May, A.: New Partial Key Exposure Attacks on RSA. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 27–43. Springer, Heidelberg (2003)Google Scholar
3. 3.
Boneh, D.: Twenty Years of Attacks on the RSA Cryptosystem. Notices of the AMS 46(2), 203–213 (1999)
4. 4.
Boneh, D., Durfee, G.: Cryptanalysis of RSA with Private Key d Less Than N 0.292. IEEE Transactions on Information Theory 46(4), 1339–1349 (2000)
5. 5.
Boneh, D., Shacham, H.: Fast variants of RSA. CryptoBytes 5(1), 1–9 (2002)Google Scholar
6. 6.
Coppersmith, D.: Small Solutions to Polynomial Equations and Low Exponent Vulnerabilities. Journal of Cryptology 10(4), 223–260 (1997)
7. 7.
Durfee, G., Nguyen, P.: Cryptanalysis of the RSA schemes with short secret exponents from Asiacrypt 1999. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 14–29. Springer, Heidelberg (2000)
8. 8.
Ernst, M., Jochemsz, E., May, A., de Weger, B.: Partial Key Exposure Attacks on RSA up to Full Size Exponents. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 371–386. Springer, Heidelberg (2005)Google Scholar
9. 9.
Galbraith, S., Heneghan, C., McKee, J.: Tunable Balancing RSA. In: Boyd, C., González Nieto, J.M. (eds.) ACISP 2005. LNCS, vol. 3574, pp. 280–292. Springer, Heidelberg (2005)Google Scholar
10. 10.
Galbraith, S., Heneghan, C., McKee, J.: Tunable Balancing RSA, http://www.isg.rhul.ac.uk/~sdg/full-tunable-rsa.pdf
11. 11.
Jochemsz, E., May, A.: A Polynomial Time Attack on RSA with Private CRT-Exponents Smaller Than N 0.073. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 395–411. Springer, Heidelberg (2007)
12. 12.
Lenstra, A.: Generating RSA moduli with a predetermined portion. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 1–10. Springer, Heidelberg (1998)
13. 13.
Lenstra, A.K., Lenstra Jr., H.W.: The Development of the Number Field Sieve. Springer, Heidelberg (1993)
14. 14.
May, A.: Cryptanalysis of unbalanced RSA with small CRT-exponent. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 242–256. Springer, Heidelberg (2002)
15. 15.
Menezes, A., Van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1997)
16. 16.
Quisquater, J.-J., Couvreur, C.: Fast decipherment algorithm for RSA public-key cryptosystem. Electronic Letters 18, 905–907 (1982)
17. 17.
Rivest, R.L., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of ACM 21(2), 158–164 (1978)
18. 18.
Stinson, D.R.: Some baby-step-giant-step algorithms for the low Hamming weight discrete logarithm problem. Math. Comp. 71(237), 379–391 (2001)
19. 19.
Stinson, D.R.: Cryptography - Theory and Practice, 2nd edn. Chapman & Hall/CRC, Boca Raton (2002)Google Scholar
20. 20.
Sun, H.M., Yang, C.T.: RSA with Balanced Short Exponents and Its Application to Entity Authentication. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 199–215. Springer, Heidelberg (2005)Google Scholar
21. 21.
Sun, H.-M., Wu, M.-E.: Design of Rebalanced RSA-CRT for Fast Encryption. In: Proceedings of Information Security Conference, pp. 16–27 (2005), http://eprint.iacr.org/2005/053
22. 22.
Sun, H.-M., Hinek, M.J., Wu, M.-E.: On the Design of Rebalanced RSA-CRT, http://www.cacr.math.uwaterloo.ca/techreports/2005/cacr2005-35.pdf
23. 23.
Verheul, E., van Tilborg, H.: Cryptanalysis of less short RSA secret exponents. Applicable Algebra in Engineering, Communication and Computing 18, 425–435 (1997)
24. 24.
de Weger, B.: Cryptanalysis of RSA with small prime difference. Applicable Algebra in Engineering, Communication and Computing 13, 17–28 (2002)
25. 25.
Wiener, M.: Cryptanalysis of Short RSA Secret Exponents. IEEE Transactions on Information Theory 36(3), 553–558 (1990)
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8565849661827087, "perplexity": 20008.865102271804}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2018-05/segments/1516084887224.19/warc/CC-MAIN-20180118091548-20180118111548-00654.warc.gz"}