[PDF] This is a Chapter from the Handbook of Applied Cryptography by A

View - Download This is a Chapter from the Handbook of Applied Cryptography by A

Previous PDF

Next PDF

This is a Chapter from theHandbook of Applied Cryptography, by A. Menezes, P. van

Oorschot, and S. Vanstone, CRC Press, 1996.

For further information, seewww.cacr.math.uwaterloo.ca/hac CRC Press has granted the following specic permissions for the electronic version of this book: Permission is granted to retrieve, print and store a single copy of this chapter for personal use. This permission does not extend to binding multiple chapters of the book, photocopying or producing copies for other than personal use of the person creating the copy, or making electronic copies available for retrieval by others without prior permission in writing from CRC Press. Except where over-ridden by the specic permission above, the standard copyright notice from CRC Press applies to this electronic version: Neither this book nor any part may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, microlming, and recording, or by any information storage or retrieval system, without prior permission in writing from the publisher. The consent of CRC Press does not extend to copying for general distribution, for promotion, for creating new works, or for resale. Specic permission must be obtained in writing from CRC Press for such copying. c ?1997 by CRC Press, Inc.

Chapter8

Public-Key Encryption

Contents in Brief

8.1 Introduction:::::::::::::::::::::::::::::283

8.2 RSA public-key encryption:::::::::::::::::::::285

8.3 Rabin public-key encryption::::::::::::::::::::292

8.4 ElGamal public-key encryption:::::::::::::::::::294

8.5 McEliece public-key encryption::::::::::::::::::298

8.6 Knapsack public-key encryption::::::::::::::::::300

8.7 Probabilistic public-key encryption:::::::::::::::::306

8.8 Notes and further references::::::::::::::::::::312

8.1 Introduction

This chapter considers various techniques for public-key encryption, also referred to as asymmetric encryption. As introduced previously (x1.8.1), in public-key encryption sys- tems each entityAhas apublickeyeand a correspondingprivate keyd. In secure systems, thetaskofcomputingdgiveneiscomputationallyinfeasible. Thepublickeyde®nesanen- cryption transformationE e , while the private key de®nes the associateddecryption trans- formationD d . Any entityBwishing to send a messagemtoAobtains an authentic copy ofA'spublickeye, usestheencryptiontransformationtoobtaintheciphertextc=E e (m), and transmitsctoA. To decryptc,Aapplies the decryption transformation to obtain the original messagem=D d (c). The public key need not be kept secret, and, in fact, may be widely available ± only its authenticity is required to guarantee thatAis indeed the only party who knows the corre- spondingprivatekey. Aprimaryadvantageofsuchsystemsisthatprovidingauthenticpub- lic keys is generally easier than distributing secret keys securely, as requiredin symmetric- key systems. The main objective of public-key encryption is to provideprivacyorcon®dentiality. not providedata origin authentication(De®nition 9.76) ordata integrity(De®nition 9.75). message authentication codes and digital signatures. Public-key encryption schemes are typically substantially slower than symmetric-key encryption algorithms such as DES (x7.4). For this reason, public-key encryption is most commonly used in practice for the transport of keys subsequently used for bulk data en- cryption by symmetric algorithms and other applications including data integrity and au- thentication, and for encrypting small data items such as credit card numbers and PINs. 283

284 Ch.8 Public-Key Encryption

Public-key decryption may also provide authentication guarantees in entity authentication and authenticated key establishment protocols.

Chapter outline

tation issues are also discussed. Rabin's public-key encryption scheme, which is provably as secure as factoring, is the topic ofx8.3.x8.4 considers the ElGamal encryption scheme; related security and implementation issues are also discussed. The McEliece public-key encryptionscheme, based on error-correctingcodes, is examined inx8.5. Although known tobe insecure,theMerkle-Hellmanknapsackpublic-keyencryptionschemeis presentedin x8.6 for historical reasons ± it was the ®rst concrete realization of a public-key encryption scheme. Chor-Rivest encryption is also presented (x8.6.2) as an example of an as-yet un- broken public-key encryption scheme based on the subset sum (knapsack) problem.x8.7 introduces the notion of probabilistic public-key encryption, designed to meet especially stringent security requirements.x8.8 concludes with Chapter notes and references. The number-theoretic computational problems which form the security basis for the public-key encryption schemes discussed in this chapter are listed in Table 8.1. public-key encryption schemecomputational problem

RSAinteger factorization problem (x3.2)

RSA problem (x3.3)

Rabininteger factorization problem (x3.2)

square roots modulo compositen(x3.5.2)

ElGamaldiscrete logarithm problem (x3.6)

Dif®e-Hellman problem (x3.7)

generalized ElGamalgeneralized discrete logarithm problem (x3.6) generalized Dif®e-Hellman problem (x3.7)

McEliecelinear code decoding problem

Merkle-Hellman knapsacksubset sum problem (x3.10)

Chor-Rivest knapsacksubset sum problem (x3.10)

Goldwasser-Micali probabilisticquadratic residuosity problem (x3.4) Blum-Goldwasser probabilisticinteger factorization problem (x3.2)

Rabin problem (x3.9.3)

Table 8.1:Public-key encryption schemes discussed in this chapter, and the related computational problems upon which their security is based.

8.1.1 Basic principles

Objectives of adversary

The primaryobjectiveof an adversarywho wishes to ªattackº a public-keyencryptionsch- emeis tosystematicallyrecoverplaintextfromciphertextintendedforsome otherentityA. If this is achieved, the encryption scheme is informally said to have beenbroken.Amore ambitiousobjective iskey recovery± to recoverA's private key. If this is achieved, the en- c ?1997 by CRC Press, Inc. Ð See accompanying notice at front of chapter. x8.2 RSA public-key encryption 285 cryptionschemeis informallysaid tohavebeencompletelybrokensince theadversarythen has the ability to decryptallciphertext sent toA.

Types of attacks

Since the encryption transformations are public knowledge, a passive adversary can al- ways mount achosen-plaintext attackon a public-key encryption scheme (cf.x1.13.1). A stronger attack is achosen-ciphertext attackwhere an adversary selects ciphertext of its choice, and then obtains by some means (from the victimA) the corresponding plaintext (cf.x1.13.1). Two kinds of these attacks are usually distinguished.

1. In anindifferentchosen-ciphertextattack, theadversaryisprovidedwithdecryptions

the (target) ciphertextcit actually wishes to decrypt.

2. Inanadaptivechosen-ciphertextattack,theadversarymayuse(orhaveaccessto)A's

textc. The adversary may request decryptionsof ciphertextwhich may be related to both the target ciphertext, and to the decryptions obtained from previous queries; a restriction is that it may not request the decryption of the targetcitself. Chosen-ciphertext attacks are of concern if the environment in which the public-key en- cryption scheme is to be used is subject to such an attack being mounted; if not, the exis- tenceof a chosen-ciphertextattackis typicallyviewedasacerti®cationalweaknessagainst a particular scheme, although apparently not directly exploitable.

Distributing public keys

The public-key encryption schemes described in this chapter assume that there is a means for the sender of a message to obtain anauthenticcopy of the intended receiver's public key. In the absence of such a means, the encryption scheme is susceptible to animperson- ationattack,asoutlinedinx1.8.2. Therearemanytechniquesinpracticebywhichauthentic public keys can be distributed, including exchanging keys over a trusted channel, using a trusted public ®le, using an on-line trusted server, and using an off-line server and certi®- cates. These and related methods are discussed inx13.4.

Message blocking

Some of the public-key encryption schemes described in this chapter assume that the mes- sage to be encrypted is, at most, some ®xed size (bitlength). Plaintext messages longer than this maximum must be brokenintoblocks, each of the appropriatesize. Speci®c tech- niques for breaking up a message into blocks are not discussed in this book. The compo- nent blocks can then be encrypted independently (cf. ECB mode inx7.2.2(i)). To provide (CBC) modemaybeused(cf.x7.2.2(ii)andExample9.84). SincetheCFBandOFBmodes both message encryption and decryption, they cannot be used with public-key encryption schemes.

8.2 RSA public-key encryption

The RSA cryptosystem, namedafter its inventorsR. Rivest, A. Shamir, and L. Adleman, is the most widely used public-keycryptosystem. It may be used to provide both secrecy and digital signatures and its security is based on the intractability of the integer factorization Handbook of Applied Cryptographyby A. Menezes, P. van Oorschot and S. Vanstone.

286 Ch.8 Public-Key Encryption

problem (x3.2). This section describes the RSA encryption scheme, its security, and some implementation issues; the RSA signature scheme is covered inx11.3.1.

8.2.1 Description

8.1 AlgorithmKey generation for RSA public-key encryption

SUMMARY: each entity creates an RSA public key and a corresponding private key.

Each entityAshould do the following:

1. Generatetwolargerandom(anddistinct)primespandq, eachroughlythesame size.

2. Computen=pqand=(p-1)(q-1).(SeeNote8.5.)

3. Select a random integere,1

4. Use the extended Euclidean algorithm (Algorithm 2.107) to compute the unique in-

tegerd,15.A's public key is(n;e);A's private key isd.

8.2 De®nitionTheintegerseanddinRSA keygenerationare calledtheencryptionexponent

and thedecryption exponent, respectively, whilenis called themodulus.

8.3 AlgorithmRSA public-key encryption

SUMMARY:Bencrypts a messagemforA,whichAdecrypts.

1.Encryption.Bshould do the following:

(a) ObtainA's authentic public key(n;e). (b) Represent the message as an integermin the interval[0;n-1]. (c) Computec=m e modn(e.g., using Algorithm 2.143). (d) Send the ciphertextctoA.

2.Decryption.To recover plaintextmfromc,Ashould do the following:

(a) Use the private keydto recoverm=c d modn. Proof that decryption works.Sinceed1(mod), there exists an integerksuch that ed=1+k.Now,ifgcd(m;p)=1then by Fermat's theorem (Fact 2.127), m p-1

1(modp):

Raising bothsidesofthiscongruenceto thepowerk(q-1)andthenmultiplyingbothsides bymyields m

1+k(p-1)(q-1)

m(modp): Ontheotherhand,ifgcd(m;p)=p, thenthislast congruenceisagainvalidsinceeachside is congruent to0modulop. Hence, in all cases m ed m(modp):

By the same argument,

m ed m(modq): Finally, sincepandqare distinct primes, it follows that m ed m(modn); c ?1997 by CRC Press, Inc. Ð See accompanying notice at front of chapter. x8.2 RSA public-key encryption 287 and, hence, c d (m e d m(modn):

8.4 Example(RSA encryption with arti®cially small parameters)

Key generation. EntityAchooses the primesp= 2357,q= 2551, and computesn= pq= 6012707and=(p-1)(q-1) = 6007800.Achoosese= 3674911and, using the extended Euclidean algorithm, ®ndsd= 422191such thated1(mod).A's public key is the pair(n= 6012707;e= 3674911), whileA's private key isd= 422191. Encryption. To encrypt a messagem= 5234673,Buses an algorithm for modular expo- nentiation (e.g., Algorithm 2.143) to compute c=m e modn= 5234673

3674911

mod 6012707 = 3650502; and sends this toA.

Decryption. To decryptc,Acomputes

c d modn= 3650502

422191

mod 6012707 = 5234673:

8.5 Note(universal exponent) The number=lcm(p-1;q-1), sometimes called theuni-

versal exponentofn, may be used instead of=(p-1)(q-1)in RSA key generation (Algorithm 8.1). Observe thatis a proper divisor of.Usingcan result in a smaller decryption exponentd, which may result in faster decryption (cf. Note 8.9). However, ifp andqarechosenatrandom,thengcd(p-1;q-1)isexpectedtobesmall, andconsequently andwill be roughly of the same size.

8.2.2 Security of RSA

ThissubsectiondiscussesvarioussecurityissuesrelatedtoRSAencryption. Variousattacks which have been studied in the literature are presented, as well as appropriate measures to counteract these threats. (i) Relation to factoring ing ciphertextc, given the public information(n;e)of the intended receiverA.Thisis called theRSA problem(RSAP), which was introduced inx3.3. There is no ef®cient algo- rithm known for this problem. One possible approach which an adversary could employ to solving the RSA problem is to ®rst factorn, and then computeanddjust asAdid in Algorithm 8.1. Oncedis obtained, the adversary can decrypt any ciphertext intended forA. On the other hand, if an adversary could somehow computed, then it could subse- quently factornef®ciently as follows. First note that sinceed1(mod),thereisan integerksuch thated-1=k. Hence, by Fact 2.126(i),a ed-1

1(modn)for all

a2Z n .Leted-1=2 s t,wheretis an odd integer. Then it can be shown that there exists ani2[1;s]such thata 2 i-1 t

6 1(modn)anda

2 i t

1(modn)for at least half

of alla2Z n ;ifaandiare such integers thengcd(a 2 i-1 t -1;n)is a non-trivial factor ofn. Thus the adversary simply needs to repeatedly select randoma2Z n and check if ani2[1;s]satisfying the above property exists; the expected number of trials before a non-trivial factor ofnis obtained is2. This discussion establishes the following.

8.6 FactTheproblemofcomputingtheRSAdecryptionexponentdfromthepublickey(n;e),

and the problem of factoringn, are computationally equivalent. Handbook of Applied Cryptographyby A. Menezes, P. van Oorschot and S. Vanstone.

288 Ch.8 Public-Key Encryption

When generating RSA keys, it is imperative that the primespandqbe selected in such a way that factoringn=pqis computationally infeasible; see Note 8.8 for more details. (ii) Small encryption exponente In order to improve the ef®ciency of encryption, it is desirable to select a small encryption exponente(see Note 8.9)such ase=3. A groupof entities may all have the same encryp- tion exponente, however, each entity in the group must have its own distinct modulus (cf. x8.2.2(vi)). If an entityAwishes to send the same messagemto three entities whose pub- lic moduli aren 1 ,n 2 ,n 3 , and whose encryption exponents aree=3,thenAwould send c i =m 3 modn i ,fori=1;2;3. Since these moduli are most likely pairwise relatively prime, an eavesdropper observingc 1 ,c 2 ,c 3 can use Gauss's algorithm (Algorithm 2.121) to ®nd a solutionx,0xSincem 3 However,ifgcd(p-

1;q-1)is small, as is typically the case, and ifdhas up to approximately one-quarter as

many bits as the modulusn, then there is an ef®cient algorithm (referenced on page 313) for computingdfrom the public information(n;e). This algorithm cannot be extended to the case wheredis approximately the same size asn. Hence, to avoid this attack, the de- cryption exponentdshould be roughly the same size asn. (v) Multiplicative properties Letm 1 andm 2 be two plaintext messages, and letc 1 andc 2 be their respective RSA en- cryptions. Observe that (m 1 m 2 e m e1 m e 2 c 1 c 2 (modn): 1 In this case, one would selectd®rst and then computeein Algorithm 8.1, rather than vice-versa. c?1997 by CRC Press, Inc. Ð See accompanying notice at front of chapter. x8.2 RSA public-key encryption 289 In other words, the ciphertext corresponding to the plaintextm=m 1 m 2 modnisc= c 1 c 2 modn; this is sometimes referred to as thehomomorphic propertyof RSA. This ob- servation leads to the followingadaptive chosen-ciphertext attackon RSA encryption. e mod nintended forA. Suppose also thatAwill decrypt arbitrary ciphertext for the adversary, other thancitself. The adversary can concealcby selecting a random integerx2Z n and computingc=cx e modn. Upon presentation ofc,Awill compute for the adversary m=(c) d modn.Since m(c) d c d (x e d mx(modn); the adversary can then computem= mx -1 modn. somestructuralconstraintsonplaintextmessages. Ifaciphertextcisdecryptedtoamessagequotesdbs_dbs27.pdfusesText_33

[PDF] decors chretiens de sainte sophie

[PDF] basilique sainte-sophie vikidia

[PDF] frise chronologique de sainte sophie

[PDF] chapelle du palais d'aix

[PDF] fonction dune basilique

[PDF] plan de la basilique sainte sophie

[PDF] sainte sophie plan

[PDF] conseiller d'animation sportive salaire

[PDF] fiches ressources eps lycée professionnel

[PDF] conseiller technique sportif salaire

[PDF] programme eps lycée professionnel 2016

[PDF] conseiller d'animation sportive fiche métier

[PDF] conseiller technique sportif fiche métier

[PDF] programme eps lycée 2010

[PDF] cqp aquagym