Loading...
Please wait, while we are loading the content...
Similar Documents
Thirty Years of Attacks on the RSA Cryptosystem
| Content Provider | Semantic Scholar |
|---|---|
| Author | Wang, Jingjing |
| Copyright Year | 2011 |
| Abstract | The RSA cryptosystem invented by Rivest, Shamir and Adleman in 1977 is today’s most important public-key cryptosystem. Its wide application has drawn much attention to its security. Let us begin by describing a simplified version of RSA encryption. The RSA modulus is the product of two large primes of the same size, usually denoted by N = pq where p, q are the two primes. The encryption exponent e, and the decryption exponent d are two integers satisfying ed = 1 mod φ(N) where φ(N) = (p − 1)(q − 1). A message M is encrypted by C = M mod N where the pair e,N is called the public key. To decrypt the ciphertext C, the legitimate receiver who owns d, called the private key or the secret key, computes M = C mod N . It is clear that the security of RSA cryptosystem relies on the difficulty of inverting the RSA encryption function on the average, i.e. extracting eth roots in the ring ZN . Subsequently, the first attack on RSA is to factor the modulus N . Given the factorization of N , an attacker can easily construct φ(N), from which the decryption exponent d = e−1 mod φ(N) can be found. Currently, the running time of the fastest method to factor an n-bit integer in general is exp((c+ (1))n log n) for some c < 2. While this general method of factoring large integers is far from posing a threat to the security of RSA, it is still unclear whether the difficulty of inverting the RSA encryption function is equivalent to that of factoring large integers. Indeed, researchers have long been exploring ways of recovering d or M without directly factoring N . This survey on RSA attacks is intended to cover those ways. The article is organized as follows. Section 2, Section 3 and Section 4 deals with the attacks enabled by the weak private exponent, the weak public exponent, the partial key exposure and the implementation details of RSA respectively. Section 5 concludes the article. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://cryptjwang.files.wordpress.com/2012/05/rsa_attacks.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
