- Public-Key Encryption. - 8.2 RSA public-key encryption. - 8.3 Rabin public-key encryption. - 8.4 ElGamal public-key encryption. - 8.5 McEliece public-key encryption. - 8.6 Knapsack public-key encryption. - 8.7 Probabilistic public-key encryption. - 1.8.1), in public-key encryption sys- tems each entity A has a public key e and a corresponding private key d. - The main objective of public-key encryption is to provide privacy or confidentiality.. - Public-key encryption schemes are typically substantially slower than symmetric-key encryption algorithms such as DES. - The RSA public-key encryption scheme is presented in § 8.2. - Rabin’s public-key encryption scheme, which is provably as secure as factoring, is the topic of § 8.3. - The McEliece public-key encryption scheme, based on error-correcting codes, is examined in § 8.5. - Although known to be insecure, the Merkle-Hellman knapsack public-key encryption scheme is presented in. - 8.6 for historical reasons – it was the first concrete realization of a public-key encryption scheme. - 8.6.2) as an example of an as-yet un- broken public-key encryption scheme based on the subset sum (knapsack) problem. - public-key encryption scheme computational problem. - Since the encryption transformations are public knowledge, a passive adversary can al- ways mount a chosen-plaintext attack on a public-key encryption scheme (cf. - Some of the public-key encryption schemes described in this chapter assume that the mes- sage to be encrypted is, at most, some fixed size (bitlength). - 7.2.2(iii) and § 7.2.2(iv)) employ only single-block encryption (and not decryption) for both message encryption and decryption, they cannot be used with public-key encryption schemes.. - Adleman, is the most widely used public-key cryptosystem. - 8.1 Algorithm Key generation for RSA public-key encryption. - SUMMARY: each entity creates an RSA public key and a corresponding private key.. - A’s public key is (n, e). - 8.3 Algorithm RSA public-key encryption. - (a) Obtain A’s authentic public key (n, e).. - 8.2 RSA public-key encryption 287. - A’s public key is the pair (n e while A’s private key is d = 422191.. - 8.2 RSA public-key encryption 289 In other words, the ciphertext corresponding to the plaintext m = m 1 m 2 mod n is c = c 1 c 2 mod n. - A plaintext message m, 0 ≤ m ≤ n − 1, in the RSA public-key encryption scheme is said to be unconcealed if it encrypts to itself. - 8.2 RSA public-key encryption 291 (ii) Another restriction on the primes p and q is that the difference p − q should not be. - 8.10 Algorithm Key generation for Rabin public-key encryption. - SUMMARY: each entity creates a public key and a corresponding private key.. - A’s public key is n. - 8.11 Algorithm Rabin public-key encryption. - (a) Obtain A’s authentic public key n.. - 8.3 Rabin public-key encryption 293. - Hence, assuming that factoring n is computationally intractable, the Rabin public-key encryption scheme is provably secure against a passive adver- sary.. - (ii) While provably secure against a passive adversary, the Rabin public-key encryption scheme succumbs to a chosen-ciphertext attack (but see Note 8.14(ii. - (iii) The Rabin public-key encryption scheme is susceptible to attacks similar to those on RSA described in § 8.2.2(ii. - A’s public key is n = 91687, while A’s private key is (p = 277, q = 331).. - The ElGamal public-key encryption scheme can be viewed as Diffie-Hellman key agree- ment. - 8.17 Algorithm Key generation for ElGamal public-key encryption. - A’s public key is (p, α, α a. - 8.4 ElGamal public-key encryption 295. - 8.18 Algorithm ElGamal public-key encryption. - (a) Obtain A’s authentic public key (p, α, α a. - A’s public key is (p = 2357, α = 2, α a = 1185).. - 8.4 ElGamal public-key encryption 297. - 8.25 Algorithm Key generation for generalized ElGamal public-key encryption SUMMARY: each entity creates a public key and a corresponding private key.. - A’s public key is (α, α a. - 8.26 Algorithm Generalized ElGamal public-key encryption. - (a) Obtain A’s authentic public key (α, α a. - A’s public key is α a = (1011) (together with α = (0010) and the polynomial f (x) which defines the mul- tiplication in G, if these parameters are not common to all entities).. - The McEliece public-key encryption scheme is based on error-correcting codes. - It is also notable as being the first public-key encryption scheme to use randomization in the encryption process. - 8.29 Algorithm Key generation for McEliece public-key encryption. - A’s public key is ( G, t). - 8.5 McEliece public-key encryption 299. - 8.30 Algorithm McEliece public-key encryption. - (a) Obtain A’s authentic public key ( G, t). - Knapsack public-key encryption schemes are based on the subset sum problem, which is NP-complete (see § 2.3.3 and § 3.10). - 8.6.1) is important for historical reasons, as it was the first concrete realization of a public-key encryption scheme. - 8.36 Algorithm Key generation for basic Merkle-Hellman knapsack encryption SUMMARY: each entity creates a public key and a corresponding private key.. - A’s public key is (a 1 , a 2. - 8.6 Knapsack public-key encryption 301. - 8.37 Algorithm Basic Merkle-Hellman knapsack public-key encryption SUMMARY: B encrypts a message m for A, which A decrypts.. - (a) Obtain A’s authentic public key (a 1 , a 2. - A’s public key is the knapsack set while A’s private key is (π, M, W . - 8.6 Knapsack public-key encryption 303. - 8.41 Algorithm Key generation for Chor-Rivest public-key encryption. - A’s public key is ((c 0 , c 1. - 8.42 Algorithm Chor-Rivest public-key encryption. - (a) Obtain A’s authentic public key ((c 0 , c 1. - 8.6 Knapsack public-key encryption 305 8. - A’s public key is ((c 0 , c 1 , c 2 , c 3 , c 4 , c 5 , c 6. - (a) Obtains authentic A’s public key.. - Intuitively, a public-key encryption scheme is semantically secure if the ciphertext does not leak any partial information whatsoever about the plaintext that can be computed in expected polynomial time.. - 8.7 Probabilistic public-key encryption 307 8.48 Remark (perfect secrecy vs. - 8.49 Fact A public-key encryption scheme is semantically secure if and only if it is polynomi- ally secure.. - The Goldwasser-Micali scheme is a probabilistic public-key system which is semantically secure assuming the intractability of the quadratic residuosity problem (see § 3.4).. - A’s public key is (n, y). - 8.51 Algorithm Goldwasser-Micali probabilistic public-key encryption SUMMARY: B encrypts a message m for A, which A decrypts.. - (a) Obtain A’s authentic public key (n, y).. - 8.55 Algorithm Key generation for Blum-Goldwasser probabilistic encryption SUMMARY: each entity creates a public key and a corresponding private key.. - 8.7 Probabilistic public-key encryption 309. - 8.56 Algorithm Blum-Goldwasser probabilistic public-key encryption SUMMARY: B encrypts a message m for A, which A decrypts.. - A’s public key is n = 272953, while A’s private key is (p, q, a, b).. - 8.61 Fact If a public-key encryption scheme is non-malleable, it is also semantically secure.. - 8.62 Definition A public-key encryption scheme is said to be plaintext-aware if it is computa- tionally infeasible for an adversary to produce a valid ciphertext without knowledge of the corresponding plaintext.. - For an introduction to public-key cryptography and public-key encryption in particular, see. - A comparison of the features of public-key and symmetric-key encryption is given in § 1.8.4. - H˚astad also showed that sending three linearly related messages using the Rabin public-key encryption scheme (Algorithm 8.11) is insecure.. - The Rabin public-key encryption scheme (Algorithm 8.11) was proposed in 1979 by Ra- bin [1023]. - m(m + b) mod n, where b and n comprise the public key. - Naor and Yung [921] proposed the first concrete public-key encryption scheme that is semantically secure against indifferent chosen-ciphertext attack.. - The Merkle-Hellman knapsack scheme illustrates the limitations of using an NP-complete problem to design a secure public-key encryption scheme. - They also proposed an efficient public-key encryption scheme based on subset factorizations of the additive group Z n of integers modulo n. - Two probabilis- tic public-key encryption schemes, one whose breaking is equivalent to solving the RSA problem. - Let h = b lg lg n c , where (n, e) is entity A’s RSA public key
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt