TWENTY YEARS OF ATTACKS ON THE RSA CRYPTOSYSTEM

摘要: Introduction The RSA cryptosystem, invented by Ron Rivest, Adi Shamir, and Len Adleman [18], was first publicized in the August 1977 issue of Scientific American. cryptosystem is most commonly used for providing privacy ensuring authenticity digital data. These days deployed many commercial systems. It Web servers browsers to secure traffic, it ensure e-mail, remote login sessions, at heart electronic credit card payment In short, frequently applications where security data a concern. Since its initial publication, system has been analyzed vulnerability researchers. Although twenty years research have led number fascinating attacks, none them devastating. They mostly illustrate dangers improper use RSA. Indeed, securely implementing nontrivial task. Our goal survey some these attacks describe underlying mathematical tools they use. Throughout we follow standard naming conventions “Alice” “Bob” denote two generic parties wishing communicate with each other. We “Marvin” malicious attacker eavesdrop or tamper communication between Alice Bob. begin describing simplified version encryption. Let N = pq be product large primes same size (n/2 bits each). A typical n 1024 bits, i.e., 309 decimal digits. Each factors 512 bits. e, d integers satisfying ed 1 mod φ(N) (p − 1)(q 1) order multiplicative group ZN. call modulus, e encryption exponent, decryption exponent. pair 〈N, e〉 public key. As name suggests, encrypt messages. 〈N,d〉 called secret key private known only recipient encrypted enables ciphertexts. message an integer M ∈ To M, one computes C =Me . decrypt ciphertext, legitimate receiver Cd N. =Med =M N,