•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:
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)]
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.
