Feb. 16, 2011, 2:50 p.m.

posted by superj

## Public-Key CryptographyPublic-key cryptography emerged in the mid-1970s with the work published by Whitfield Diffie and Martin Hellman.
The premise behind public-key cryptography is that it should be computationally infeasible to obtain the private key by simply knowing the public key. Toward achieving this premise, modern public-key cryptography derives from sophisticated mathematical foundations based on the one-way functions existing in the abstractions of number theory. A one-way function is an invertible function that is easy to compute but computationally difficult to invert. A one-way trapdoor function is a one-way function that can be easily inverted only if one knows a secret piece of information, known as the trapdoor. Encryption is the easy one-way trapdoor function; its inverse, decryption, is the difficult direction. Only with knowledge of the trapdoor—the private key—is decryption as easy as encryption. Two of these currently known one-way functions, factoring large numbers and computing discrete logarithms, form the basis of modern public-key cryptography. Factoring large numbers is a one-way trapdoor function, whereas computing discrete logarithms is a one-way function with no trapdoors. ## 1 Algorithms and TechniquesThis section examines the most common cryptographic algorithms that are based on the use of a public- and private-key pair. ## 1.1 RSAThe most famous of the well-known trapdoor one-way functions is based on the ease of multiplying two large prime numbers; the reverse process, factoring a very large number, is far more complex. This consideration is at the basis of Rivest-Shamir-Adleman (RSA), certainly the most widely used public-key encryption algorithm. ## Basic RSA ConceptsA prime number, by definition, is an integer that has no positive divisors other than 1 and itself. A nonprime integer is called composite. Two integers a 1 and b 2 are said to be relatively prime if their greatest common divisor GCD(a, b) is 1. The number of elements in the set
where Z is the set of all integers, is often denoted by f(b). The function f is called the Euler phi-function. Every integer b 2 can be factored as a product of powers of primes in a unique way. For example, 60 = 2 ## How the RSA Algorithm WorksIn simple terms, the RSA algorithm centers on three integer numbers: the public exponent, e; the private exponent, d; and the modulus, n. The modulus is obtained as the product of two distinct, randomly picked, very large primes, p and q. A well-known result from number theory implies that f(n) = (p - 1)(q - 1). The two numbers e and d are characterized by the fact that they are greater than 1 and smaller than f(n). In addition, e must be relatively prime with f(n), and it must also be de = 1 (mod f(n)), which means that d and e are the multiplicative inverse of the other modulo f(n). The pair (e, n) is the RSA public key, whereas the pair (d, n) is the RSA private key. A block of plaintext P whose numerical equivalent is less than the modulus is converted into a ciphertext block by the formula P To better understand how RSA works, let us consider an example involving small numbers. We randomly pick two prime numbers, p = 7 and q = 11. This implies that n = pxq = 77 and f(n) = (p - 1)(q - 1) = 60. A valid choice for the public exponent is e = 13. By solving the equation 13d = 1 (mod 60), we get d = 37. Therefore, the RSA public key in this case is the pair (13, 77), and the corresponding RSA private key is the pair (37, 77). Let us now consider the plaintext message P = 9. By encrypting it with the RSA public key, we obtain the ciphertext message C = 9 To encrypt or decrypt a message, the RSA algorithm uniquely represents a block of data in either a plaintext or ciphertext form as a very large number, which is then raised to a large power. Note here that the length of the block is appropriately sized so that the number representing the block is less than the modulus. Computing such exponentiations would be very time consuming were it not for an eloquent property that the operation of exponentiation in modular arithmetic exhibits. This property is known as the modular exponentiation by the repeated squaring method. Note that the one-way trapdoor function discussed in this section requires deciding on whether a randomly picked very large integer is prime. Primality testing, however, is a much easier task than factorization. Several methods have been devised to determine the primality of an odd number p, the most trivial of which is to run through the odd numbers starting with 3 and determine whether any of such numbers divides p. The process should terminate when the square root of p, , is reached, because if p is not a prime, the smallest of its nontrivial factors must be less than or equal to . Owing to the time complexity that it requires, in practice this procedure is stopped much earlier before reaching and is used as a first step in a series of more complicated, but faster, primality test methods. ## Security ConsiderationsBreaking the RSA algorithm is conjectured to be equivalent to factoring the product of two large prime numbers. The reason is that one has to extract the modulus n from the public-key value and proceed to factor it as the product of the two primes p and q. Knowing p and q, it would be easy to compute f(n) = (p - 1)(q - 1), and the private key (d, n) could then be obtained by solving the equation de = 1 (mod f(n)) for the unknown d. With the complexity of the fastest known factoring algorithm being in the order of |n|, where |n| is the total number of the binary bits in the modulus n, this roughly means that, for example, every additional 10 bits make the modulus ten times more difficult to factor. Given the state of factoring numbers, it is believed that keys with 2,048 bits are secure into the future. The fastest known factoring algorithm to date is the number field sieve. ## 1.2 Diffie-HellmanThe Diffie-Hellman (DH) key-agreement algorithm is an elegant procedure for use by two entities establishing a secret cryptographic key over a public network without the risk of exposing or physically exchanging it. Indeed, DH presents a critical solution to the secret-key distribution problem. The security of the algorithm relates to the one-way function found in the discrete logarithm problem. ## Basic DH ConceptsLet q be a prime number. An integer a is called a primitive root, or base generator of q, if the numbers a (mod q), a ## How the DH Algorithm WorksThe mathematics encompassed in the DH key-agreement algorithm is fairly simple. Let q and a be as explained previously. These two numbers are publicly available. Suppose that Alice and Bob want to agree on a secret key. Alice generates as her private key a secret random number x Similarly, Bob generates as his private key a secret random number x The secret key for Alice and Bob is Alice can obtain this key by getting y Bob computes the same secret key in a similar way. One problem in the algorithm that we have just described consists of finding a primitive root a of a given prime number q. The definition of primitive root does not help from a computational point of view, because it requires computing q – 1 powers in the worst case for every attempt to find a primitive root. However, a known algebraic theorem proves that an integer a is a primitive root of 9 if a ## Security ConsiderationsWith the algorithm described, Alice and Bob do not have to physically exchange keys over unsecure networks, because they can compute the same secret key independently of each other. An attacker would have to compute K In order for Bob and Alice to be able to compute the same secret key independently of each other, they have to know each other's public keys. A general security problem that arises at this point is how to ascertain that the public key of an entity belongs to that entity. The DH algorithm does not offer a direct solution to this problem. However, we will see how to solve this problem in Section 10.3.4 on page 372. ## 1.3 Elliptic CurveRecently, elliptic curves over finite fields have been proposed as another source of one-way trapdoor functions for use with existing public-key cryptographic systems. ## Basic Elliptic-Curve ConceptsAn elliptic curve in the plane x, y is the union of the singleton {} with the set of the points (x, y) of the plane satisfying an equation of the form
where a, b, c, d, and e are real numbers, and x and y take on values in the real numbers. The element is called point at infinity. For our purpose, it is sufficient to consider equations of the form
Figure shows the elliptic curve with equation y ## 16. An Elliptic CurveA form of addition can be defined over the set of points of an elliptic curve by imposing that if any three points on an elliptic curve lie on a straight line, their sum is . The operation of addition for an elliptic curve, indicated with the symbol +, is constructed on the following rules. The point at infinity, , is the additive identity. This means that = –, and for any point P on the elliptic curve, P + = + P = P. A vertical line meets the elliptic curve at two points with the same coordinates, say P _{1}= (x, y) and P_{2}= (x, -y). The vertical line also meets the curve at its infinity point, . This implies that P_{1}+ P_{2}+ = , and P_{1}= -P_{2}. Therefore, the negative of a point is a point with the same x coordinate but negative y coordinate. This construction is illustrated in Figure.##### 17. The Addition Operation on an Elliptic CurveIf Q and R are two points with different x coordinates, draw a straight line between them and find the third point of intersection P _{1}. It is easily seen that P_{1}exists and is unique, unless the line is tangent to the curve at either Q or R, in which case we take P_{1}= Q or P_{1}= R, respectively. Because P_{1}, Q, and R lie on the same straight line, it must be Q + R + P_{1}= , which implies Q + R = –P_{1}. This construction is illustrated in Figure.To double a point Q, draw the tangent line in Q and find the other point of intersection S. Then Q + Q = 2Q = –S. This construction is illustrated in Figure.
Figure shows how to perform the addition operation on the elliptic curve y It is well defined. Given any two points P and Q on an elliptic curve, their sum P + Q is still a point on the same elliptic curve. It is associative. Given any three points P, Q, and R on an elliptic curve, (P + Q) + R = P + (Q + R). It is commutative. Given any two points P and Q on an elliptic curve, P + Q = Q + P. It possesses a unity element. Rule 1 establishes that the unity element for the operation of addtion is the point at infinity, . Every point on the elliptic curve has an inverse. Given any point P on an elliptic curve, rules 1 and 2 show how to construct its inverse, –P.
These properties can be summarized by saying that the set of the points of an elliptic curve, coupled with the operation of addition that we have just defined, is an abelian group. Multiplication of a point P on an elliptic curve by a positive integer k is defined as the sum of k copies of P. Thus 2P = P + P, 3P = P + P + P, and so on. An elliptic curve can be defined on a finite field as well. Let p > 3 be a prime number. The elliptic curve y Note that the equation of an elliptic curve over the finite field Z Given an integer k < p and the equation Q = kP, where P and Q are two points on an elliptic curve E over the finite field Z ## The Elliptic-Curve AlgorithmOne straightforward application of the one-way function to DH is for two entities Alice and Bob to publicly agree on a point P on an elliptic curve E over a finite field Z To generate the key, the initiating entity, Alice, picks a random large integer a < n, computes aP over E, and sends it to the entity Bob. The integer a is Alice's private key, whereas the point aP is her public key. Bob performs a similar computation with a random large number b and sends entity Alice the result of bP. The integer b is Bob's private key, whereas the point bP is his public key. Both entities then compute the secret key K = abP, which is still a point over E. ## Security ConsiderationsGiven an elliptic curve E on a finite field Z ## 2 Public-Key Security AttributesThis section examines the security implications of using public-key cryptography. Generally speaking, the strength of each algorithm is directly related to the type of the one-way function being used and the length of the cryptographic keys. Inverting the one-way functions we have discussed, namely, factoring a very large number and computing the discrete logarithm, is known to be practically infeasible within the computing means and the theoretic knowledge available today. ## 2.1 ConfidentialityThe premise of the privacy service here is achieved by encrypting data, using the recipient's public key, and the fact that decryption can be done only by using the recipient's private key. For example, if Alice needs to send a confidential message to Bob, she can encrypt it with Bob's public key, knowing that only Bob will be able to decrypt the ciphertext with his private key (see Figure). ## 18. Public-Key ScenarioThus, only the recipient with knowledge of the private key is able to decrypt the enciphered data. It is worth noting that a privacy service strongly depends on the assurance that a public key is valid and legitimately belongs to the recipient. One confidentiality problem that needs to be addressed by public-key encryption is the fact that in some cases, the plaintext corresponding to a given ciphertext can be easily understood. As an example, we consider the scenario in which Alice is a stock client and Bob a stockbroker, as shown in Figure. ## 19. Scenario Requiring Message RandomizationTypically, Alice's messages are all likely to be of the type "Buy" or "Sell." Knowing this, an attacker could build a table mapping ciphertexts to plaintexts. This would break the confidentiality of the transmission. Even worse, the attacker could impersonate Alice and replace the ciphertext corresponding to "Buy" with the ciphertext corresponding to "Sell" and vice versa (see Figure). ## 20. Message RandomizationThis problem can be solved by randomizing the message. Before encrypting the plaintext message "Buy" or "Sell," the message-randomizing algorithm on Alice's side inserts a meaningless sequence of bits, which is randomly generated. As the ciphertext depends on the entire plaintext message, the ciphertexts produced by Alice are no longer recognizable. In addition, message randomization reduces the risks of message-prediction-and-replay-attacks (see footnote 6 on page 150). ## 2.2 Data Integrity, Data-Origin Authentication, and NonrepudiationAs we said in Section 10.3.2.1 on page 367, privacy is provided by encrypting data, using a publicly available key, typically the recipient's public key. However, an eavesdropper may intercept the data, substitute new data, and encrypt it using the same public key. Simply applying a public-key algorithm to achieve privacy does not guarantee data integrity; nor does it guarantee data-origin authentication. In practice, digital signatures are the preferred method of achieving data integrity and data-origin authenticity. Another service that is inherently offered through digital signatures is nonrepudiation. ## 3 Digital SignaturesThe use of public-key cryptography combined with one-way hash functions enables the digital signing of documents. This process inherently enables data integrity and data-origin authentication and has the potential to withstand repudiation. In fact, using the private key of a public- and private-key pair to encrypt a data stream automatically binds the subject—a person or an entity—with the encrypted data. The cost of encrypting an entire document in order to simply establish this binding can be prohibitive. Fortunately, digital signing of a document is a computationally affordable alternative, as it does not require encrypting the entire document. If confidentiality is a requirement, the message originator, Alice, encrypts the message only once, with the public key of the receiver, Bob, thereby guaranteeing confidentiality, because the ciphertext can be decrypted only with the Bob's private key. However, data integrity, data-origin authentication, and nonrepudiation are not guaranteed, because anybody could have used Bob's public key to encrypt a different message, pretending that it was sent by Alice. To resolve this ambiguity, Alice attaches a digital signature to the encrypted message. The digital signature is obtained by applying a mathematical function to the plaintext message. This mathematical function depends on Alice's private key. An eavesdropper who attempted to replace the transmitted data with new data could still encrypt the new data with Bob's public key but would not be able to use Alice's private key to generate Alice's digital signature. Once he receives the encrypted message and the digital signature, Bob decrypts the ciphertext with his own private key. Finally, he uses Alice's public key to verify Alice's digital signature. If the digital signature verifies, Bob knows that the original message has been sent by Alice and has not been compromised during transmission. Because Alice's private key has been used to compute the digital signature, this entire process guarantees data integrity, data-origin authentication, and nonrepudiation (see Figure). ## 21. Digital-Signature ScenarioWith the fundamental premise that the private key remains in the confines of its owner, verifying a digital signature using the associated public key certainly leaves no possibility for the originator to deny involvement. Denial, however, can always take place on the basis that a private key has been compromised. A strong nonrepudiation service never exposes the private keys it manages, even to the owner. Tamper-proof hardware modules for private keys become necessary for a legally binding nonrepudiation service. If a confidentiality service is not needed, Alice can transmit the signed document to Bob in its cleartext form. The signature is provided to Bob for data-integrity verification, data-origin authentication, and nonrepudiation purposes. The most well-known digital signature algorithms are RSA and Digital Signature Algorithm (DSA). These algorithms are discussed in the next two subsections. ## 3.1 RSA SignatureThe RSA digital-signature algorithm proceeds along two main steps, as shown in Figure. Using one of the common hashing algorithms, such as MD5 or SHA-1, a document is first digested into a much smaller representation: its hash value. The hash value of the document, rather than the entire document itself, is then encrypted with the private key of the originator.
## 22. The Process of Computing a Message's RSA Digital SignatureIf confidentiality is needed, the document itself must be encrypted, as explained in Section 10.3.2.2 on page 369. ## 3.2 DSA SignatureOther types of digital signatures rely on algorithms designed solely for signing but not encrypting. In other words, the digital signature is still obtained by encrypting the hash value of a document with the originator's private key, but the public and private key pair here can be used only for digital signing, not for encrypting arbitrary-size messages. An example of this class of algorithms is the standard DSA, which computes a signature over an arbitrary-size input, using SHA-1 as a message digest, five public parameters, and a private key. DSA signatures have better performance characteristics than RSA does. ## 4 Digital CertificatesAs we mention in Section 10.3.5 on page 375, authenticating the identity of a sending entity and protecting data to allow only authenticated and authorized receivers to view that data is an extremely important security requirement, especially for the exchange of security-sensitive data or when the nature of the transaction requires data-origin authentication and nonrepudiation. Encrypting a message with the receiver's public key guarantees confidentiality, whereas digitally signing a message by encrypting its hash value with the originator's public key guarantees data-origin authentication and nonrepudiation. These scenarios are very attractive, but for them to work, it is necessary to have a means to bind a public- and private-key pair to its owner. To understand why, let us consider the following scenario. Alice wants to send Bob a confidential message in a secure manner over a public network. To do so, she needs to encrypt the message with Bob's public key. For sure, only Bob will be able to read the message once it is transmitted, because the message's ciphertext can be decrypted only with Bob's private key. However, how can Alice be sure that Bob is really Bob? Owning a public- and private-key pair does not give any assurance about the real identity of a person. Similarly, Bob may receive a signed message from Alice, and he can verify the digital signature's authenticity by decrypting it with Alice's public key, but how can he be sure that the entity that signed the message declaring to be Alice is really Alice? A solution to this problem is to use digital certificates, which can be used to exchange public keys and to verify an entity's identity. An entity's digital certificate is a binary file that contains the entity's public key and Distinguished Name (DN), which uniquely identifies that entity, along with other pieces of information, such as the start and expiration dates of the certificate and the certificate's serial number (see Figure). ## 23. Information Contained in a Digital CertificateThe international standard for public-key certificates is called X.509 (see Appendix B on page 553). This standard has evolved over time, and the latest version is V3. The most significant enhancement in X.509 V3 is the ability to add other, arbitrary data in addition to the basic name, address, and organization identity fields of the DN. This is useful when constructing certificates for specific purposes. For example, a certificate could include a bank account number or credit card information. Digital certificates are released by trusted third-party registry organizations called Certificate Authorities. These CAs are public organizations that are trusted by both the sender and the receiver participating in a secure communication. An entity, Alice, can receive her own certificate by generating a public- and private-key pair and by transmitting the public key along with a certificate request and proof of ownership of the public key to a CA. For serious applications, Alice can obtain a certificate only by applying in person and showing evidence of her identity. If Alice's request for a certificate is accepted, the CA wraps Alice's public key in a certificate and signs it with its own private key. Alice can now convey her public key information to other entities by transmitting her certificate. A receiving entity, Bob, can verify the certificate's authenticity by verifying the CA's digital signature. This can be done without even contacting the CA, because CAs' public keys are available in all the most common client and server applications, such as Web browsers, Web servers, and other programs that require security. If the signature is verified, Bob is assured that the certificate really belongs to Alice. From this moment on, when he receives a message digitally signed by Alice, he knows that it is really Alice who signed it and transmitted it—data-origin authentication—and Alice will not be able to deny that the message originated from her—nonrepudiation. Similarly, by accessing Bob's certificate from a CA and by encrypting a message with Bob's public key, Alice is assured that only Bob, and no other person, will be able to decrypt the message—confidentiality. As Figure shows, certificates contain start and end dates. The validity of a certificate should not be too long, to minimize the risks associating with having inadvertently exposed the associated private key and to make sure that the current key strength still makes it computationally infeasible to compute the private key from the public key. If the private key associated with the public key in a certificate gets inadvertently exposed, a certificate's owner should make an immediate request for suspending the certificate's validity. In this case, the CA will add an entry for that certificate in its certificate revocation list. A CRL also enumerates those certificates that have been revoked because their owners failed to comply with specific requirements. A CRL should always include data explaining why a certificate was suspended or revoked. In the scenario that we have described in this section, there is only one CA that the sender and the receiver participating in a secure communication use to verify each other's public key's authenticity. In real-life situations, there are chains of CAs, whereby each successive CA verifies and vouches for the public key of the next identity in the chain. In this case, a public-key certificate embodies a chain of trust. Consider the situation shown in Figure. ## 24. Certificate HierarchyA system has received a request containing a chain of certificates, each of which is signed by the next higher CA in the chain. The system has also a collection of root certificates from trusted CAs. The system can then match the top of the chain in the request with one of these root certificates, say, Ham's. If the chain of signatures is intact, the receiver can infer that Nimrod is trustworthy and has inherited the trustworthiness from Ham. Note that one of the implications of a certificate chain is that the certificate at the top of the chain is self-signed. ## 5 Key DistributionIn public-key cryptography, an entity's private key never has to be exposed, whereas the corresponding public key is made publicly available. This makes it possible to obtain confidentiality, nonrepudiation, data-origin authentication, and data integrity without having to distribute the secret key. The main problem of public-key cryptography is that it is computationally expensive. Conversely, secret-key cryptography, described in Section 10.2 on page 346, offers better performance and scales well for Kerberos and distributed computing environment (DCE) security, even though its limitation lies in the fact that it becomes necessary to share the secret key across unsecure networks. Combining public-key and secret-key cryptography yields the performance advantages of secret-key cryptography and the security enhancements of public-key cryptography, as shown in Figure. One algorithm that combines public-key and secret-key cryptography is DH (see Section 10.3.1.2 on page 362), which allows two parties to independently compute the same secret key. To do this, each entity uses its own private key and the other entity's public key. With Diffie-Helmann, the shared secret key is mathematically computed by the two parties, and there is no need to physically exchange it over the network. ## 25. Combining Public-Key and Secret-Key CryptographyAnother way to use public-key cryptography for secure secret-key establishment over a public network is, essentially, to consider the secret key as the data that needs to be distributed with a privacy requirement. Thus, the secret key is encrypted using the public key of the target entity. The receiving entity uses its private key to decrypt the enciphered secret key and hence has established a common secret key with the sending entity. This is, for example, the approach used by the SSL and TLS protocols (see Section 13.1 on page 449). Other protocols that combine secret- and public-key cryptography are IPSec and S/MIME (see Section 12.2 on page 439). Note that authenticating the identity of the sending entity is a strong security requirement. A breach in such a key-establishment mechanism risks exposing the entire cryptographic channel that follows key establishment. |

- Comment