Читать книгу Security Engineering - Ross Anderson - Страница 157

A public-key encryption algorithm is a special kind of block cipher in which the elf will perform the encryption corresponding to a particular key for anyone who requests it, but will do the decryption operation only for the key's owner. To continue with our analogy, the user might give a secret name to the scroll that only she and the elf know, use the elf's public one-way function to compute a hash of this secret name, publish the hash, and instruct the elf to perform the encryption operation for anybody who quotes this hash. This means that a principal, say Alice, can publish a key and if Bob wants to, he can now encrypt a message and send it to her, even if they have never met. All that is necessary is that they have access to the oracle.

The simplest variation is the trapdoor one-way permutation. This is a computation that anyone can perform, but which can be reversed only by someone who knows a trapdoor such as a secret key. This model is like the ‘one-way function’ model of a cryptographic hash function. Let us state it formally nonetheless: a public key encryption primitive consists of a function which given a random input will return two keys, (the public encryption key) and (the private decryption key) with the properties that

1 Given , it is infeasible to compute (so it's not possible to compute either);

2 There is an encryption function which, applied to a message using the encryption key , will produce a ciphertext ; and

3 There is a decryption function which, applied to a ciphertext using the decryption key , will produce the original message .

For practical purposes, we will want the oracle to be replicated at both ends of the communications channel, and this means either using tamper-resistant hardware or (more commonly) implementing its functions using mathematics rather than metal.

In most real systems, the encryption is randomised, so that every time someone uses the same public key to encrypt the same message, the answer is different; this is necessary for semantic security, so that an opponent cannot check whether a guess of the plaintext of a given ciphertext is correct. There are even more demanding models than this, for example to analyse security in the case where the opponent can get ciphertexts of their choice decrypted, with the exception of the target ciphertext. But this will do for now.