Public Key Cryptanalysis
A public-key encryption scheme has six parts.
- Plaintext: This is the readable message or data that is fed into the algorithm as input.
- Encryption algorithm: The encryption algorithm performs various transformations on the plaintext.
- Public and private keys: This is a pair of keys that have been selected so that if one is used for encryption, the other is used for decryption.
- Ciphertext: This is the scrambled message produced as output. It depends on the plaintext and the key.
- Decryption algorithm: This algorithm accepts the ciphertext and the matching key and produces the original plaintext.
Brute force attack: Public Key Cryptanalysis
- This attack includes trying all the alternate keys until the correct key is found.
- The countermeasure to this uses large keys.
- However, public-key systems depend on the use of some sort of invertible mathematical function which is really time-consuming and increases overhead.
- Thus, there is a tradeoff. The key size must be large enough to make brute-force attack impractical but small enough for practical encryption and decryption.
- Secure keys are long enough to make encryption-decryption really slow.
- Hence, public-key encryption currently confined to key management and signature applications
Computation of private key from public key
- In this attack, some characteristics of an algorithm exploited to calculate the private key from the public key.
- This attack needs many known or chosen plaintext-ciphertext pairs.
- To date, it has not been mathematically proven that this form of attack is infeasible for a particular algorithm. Thus any given algorithm is suspect.
Probable message attack: Public Key Cryptanalysis
- In this attack, the opponent has some idea about the plaintext and he uses this information to find the private key.
- Suppose that a message consists only a 56-bit DES key.
- An adversary could encrypt all possible 56-bit DES keys using the public key and could discover the encrypted key by matching the transmitted ciphertext.
- Thus, no matter how large the key size of the public-key scheme, the attack reduced to a brute-force attack on a 56-bit key.
- This attack can prevent by appending some random bits to such simple messages.