Cryptography: Public Key Cryptography – Analysis

  

•In this case, we begin as before by encrypting a message, using the sender’s private key. This provides the digital signature. Next, we encrypt again, using the receiver’s public key. The final ciphertext can be decrypted only by the intended receiver, who alone has the matching private key. Thus, confidentiality is provided.

•Disadvantage

•The disadvantage of this approach is that the public-key algorithm, which is complex, must be exercised four times rather than two in each communication.

•

Applications for Public-Key Cryptosystems  

•Encryption/decryption: The sender encrypts a message with the recipient’s public key. 


•Digital signature: The sender “signs” a message with its private key. Signing is achieved by a cryptographic algorithm applied to the message or to a small block of data that is a function of the message. 


•Key exchange: Two sides cooperate to exchange a session key. Several different approaches are possible, involving the private key(s) of one or both parties. 


Requirements for Public-Key Cryptography  

1.It is computationally easy for a party B to generate a pair (public key PUb, private key PRb).

2.It is computationally easy for a sender A, knowing the public key and the message to be encrypted, M, to generate the corresponding ciphertext: 
C = E(PUb, M) 


3.It is computationally easy for the receiver B to decrypt the resulting ciphertext using the private key to recover the original message:
M = D(PRb, C) = D[PRb, E(PUb, M)] 


4.It is computationally infeasible for an adversary, knowing the public key, PUb, to determine the private key, PRb. 


5.It is computationally infeasible for an adversary, knowing the public key, PUb, and a ciphertext, C, to recover the original message, M.

We can add a sixth requirement that, although useful, is not necessary for all public-key applications:

6.
The two keys can be applied in either order:
M = D[PUb, E(PRb, M)] = D[PRb, E(PUb, M)]

Public Key Cryptography – Cryptanalysis  

•As with symmetric encryption, a public-key encryption scheme is vulnerable to a brute-force attack.

•Countermeasure? Use large keys.

•However, there is a tradeoff to be considered.

•Public-key systems depend on the use of some sort of invertible mathematical function.

–The complexity of calculating these functions may not scale linearly with the number of bits in the key but grow more rapidly than that.

•Thus, the key size must be large enough to make brute-force attack impractical but small enough for practical encryption and decryption.

•Another form of attack is to find some way to compute the private key given the public key.

•To date, it has not been mathematically proven that this form of attack is infeasible for a particular public-key algorithm.

•Thus, any given algorithm, including the widely used RSA algorithm, is suspect.

•The history of cryptanalysis shows that a problem that seems insoluble from one perspective can be found to have a solution if looked at in an entirely different way.