Page 1 :
CS8792, , CRYPTOGRAPHY AND NETWORK, SECURITY, UNIT 3 NOTES

Page 2 :
UNIT III PUBLIC KEY CRYPTOGRAPHY, MATHEMATICS OF ASYMMETRIC KEY CRYPTOGRAPHY: Primes – Primality Testing –, Factorization – Euler‘s totient function, Fermat‘s and Euler‘s Theorem – Chinese Remainder, Theorem – Exponentiation and logarithm – ASYMMETRIC KEY CIPHERS: RSA cryptosystem, – Key distribution – Key management – Diffie Hellman key exchange -ElGamal cryptosystem –, Elliptic curve arithmetic-Elliptic curve cryptography.

Page 3 :
TWO ASSERTION OF CRT

Page 6 :
Example, Prime Number, An integer p > 1 is a prime number if and only if its only divisors are ±1, and ±p., Fermat’s Theorem, If p is prime and a is a positive integer not divisible by p, then, ap-1 ≡ 1 (mod p)., Example:, a = 7, p = 19, 72 = 49 ≡ 11 (mod 19), 74 ≡ 121 ≡ 7 (mod 19), 78 ≡ 49 ≡11 (mod 19), 716 ≡121 ≡ 7 (mod 19), ap-1 = 718 ≡ 716 *72 ≡ 7*11≡ 1 (mod 19), If p is prime and a is a positive integer, then ap ≡ a(mod p), Euler’s Totient Function, The number of positive integers less than n and relatively prime to n. ø(1)=1, ø(p) = p - 1, suppose that we have two prime numbers p and q with p ≠ q. Then we can, show that, for n = pq,, ø(n) = ø(pq) = ø(p) * ø(q) = (p - 1) * (q - 1), Example:, ø(21) = ø(3) * ø(7) = (3 - 1) * (7 - 1) = 2 * 6 = 12, where the 12 integers are {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}., Euler’s Theorem, Euler’s theorem states that for every a and n that are relatively prime:, aø(n) ≡ 1(mod n)

Page 7 :
Example:, a = 3; n = 10; ø(10) = 4 aø(n) = 34 = 81 = 1 (mod 10) = 1 (mod n), a = 2; n = 11; ø(11) = 10 aø(n) = 210 = 1024 = 1 (mod 11) = 1 (mod n), Testing for Primality, Used to determine whether a given number is prime number or not., Miller-Rabin Algorithm, any positive odd integer n ≥3 can be expressed as, n - 1 = 2kq, with k > 0, q odd, n - 1 is an even integer. Then, divide (n - 1) by 2 until the result is an odd number q, for a total of k divisions., If n is expressed as a binary number, then the result is achieved by shifting the number to the right until the, rightmost digit is a 1, for a total of k shifts., Properties of Prime Numbers:, First Property:, If p is prime and a is a positive integer less than p, then a2 mod p = 1 if and only if either a mod p = 1 or a, mod p = -1 mod p = p - 1., By the rules of modular arithmetic (a mod p) (a mod p) = a2 mod p., Thus, if either a mod p = 1 or a mod p = -1, then a2 mod p = 1., Conversely, if a2 mod p = 1, then (a mod p)2 = 1, which is true only for, a mod p = 1 or a mod p = -1., Second Property:, Let p be a prime number greater than 2., n -1 = 2kq, with k > 0, q odd, Let a be any integer in the range 1<a<p - 1. Then one of the two following conditions is true., 1. aq is congruent to 1 modulo p. That is, aq mod p = 1, or equivalently,, aq = 1(mod p)., 2. One of the numbers aq, a2q, a4q, ....... , a2k - 1q is congruent to -1 modulo p., That is, there is some number j in the range (1≤ j≤k) such that a2j - 1q, mod p = -1 mod p = p - 1 or equivalently, a2j - 1q = -1 (mod p).

Page 8 :
3.5 DISCRETE LOGARITHMS

Page 10 :
3.6 ASYMMETRIC KEY CIPHERS:, RSA cryptosystem, The best known and widely regarded as most practical public-key scheme was proposed by, Rivest, Shamir & Adleman in 1977:, It is a public-key scheme which may be used for encrypting messages, exchanging keys, and, creating digital signatures, RSA is a public key encryption algorithm based on exponentiation using modular arithmetic, to use the scheme, first generate keys:, Key-Generation by each user consists of:,  selecting two large primes at random (~100 digit), p, q,  calculating the system modulus R=p.q p, q primes,  selecting at random the encryption key e,,  e < R, gcd(e, F(R)) = 1,  solving the congruence to find the decryption key d,,  e.d [[equivalence]] 1 mod [[phi]](R) 0 <= d <= R,  publishing the public encryption key: K1={e,R},  securing the private decryption key: K2={d,p,q}, Encryption of a message M to obtain ciphertext C is:, C = Me mod R 0 <= d <= R, Decryption of a ciphertext C to recover the message M is:, M = Cd = Me.d = M1+n.[[phi]](R) = M mod R, The RSA Algorithm, Key Generation, Select p, q, Calculate n = p * q, Calcuate f(n) = (p - 1)(q - 1), Select integer e, Calculate d, Public key, Private key, Encryption, Plaintext:, Ciphertext:, , p and q both prime, p ≠ q, , gcd (ø(n), e) = 1; 1<e<ø(n), d ≡e-1 (mod ø(n)), PU = {e, n}, PR = {d, n}, , M<n, C =Me mod n

Page 11 :
Decryption, Ciphertext:, Plaintext:, Example:, P=17 q=11, , C, M =Cd mod n, , e=7, , M=88, , 1. Select two prime numbers, p = 17 and q = 11., 2. Calculate n = pq = 17 * 11 = 187., 3. Calculate ø(n) = (p - 1)(q - 1) = 16 * 10 = 160., 4. Select e such that e is relatively prime to ø(n) = 160 and less than ø(n); we choose e = 7., 5. Determine d such that de ≡ 1 (mod 160) and d <160. The correct value is, d = 23, because 23 * 7 = 161 = (1 * 160) + 1; d can be calculated using the, extended Euclid’s algorithm., The resulting keys are public key PU={7,187} and private key PR={23,187}., Plaintext input of M = 88., For encryption,, calculate C = 887 mod 187., 887 mod 187 = [(884 mod 187) * (882 mod 187) * (881 mod 187)] mod 187, 881 mod 187 = 88, 882 mod 187 = 7744 mod 187 = 77, 884 mod 187 = 59,969,536 mod 187 = 132, 887 mod 187 = (88 * 77 * 132) mod 187 = 894,432 mod 187 = 11, For decryption,, calculate M = 1123 mod 187, 1123 mod 187 = [(111 mod 187) * (112 mod 187) * (114 mod 187) *, (118 mod 187) * (118 mod 187)] mod 187, 111 mod 187 = 11, 112 mod 187 = 121, 114 mod 187 = 14,641 mod 187 = 55, 118 mod 187 = 214,358,881 mod 187 = 33, 1123 mod 187=(11* 121 * 55 * 33 * 33) mod 187 =79,720,245 mod 187= 88, The Security of RSA, Brute force: This involves trying all possible private keys., Mathematical attacks: There are several approaches, all equivalent in effort to factoring the product of, two primes., Timing attacks: These depend on the running time of the decryption algorithm., Hardware fault-based attack: This involves inducing hardware faults in the processor that is generating, digital signatures., Chosen ciphertext attacks: This type of attack exploits properties of the RSA algorithm., Solve:, a. p = 3; q = 11, e = 7; M = 5, b. p = 5; q = 11, e = 3; M = 9, c. p = 7; q = 11, e = 17; M = 8

Page 12 :
d. p = 11; q = 13, e = 11; M = 7, , 3.7 KEY MANAGEMET AND KEY DISTRIBUTION, For symmetric encryption to work, the two parties to an exchange must share the same key, and that key, must be protected from access by others. For symmetric encryption to work, the two parties to an exchange, must share the same key, and that key must be protected from access by others., For two parties A and B, key distribution can be achieved in a number of ways, as follows:, 1. A can select a key and physically deliver it to B., 2. A third party can select the key and physically deliver it to A and B., 3. If A and B have previously and recently used a key, one party can transmit the new key to the other,, encrypted using the old key., 4. If A and B each has an encrypted connection to a third party C, C can deliver a key on the encrypted, links to A and B., A Key Distribution Scenario, User A wishes to establish a logical connection with B and requires a one-time session key to protect the, data transmitted over the connection. A has a master key, Ka, known only to itself and the KDC; similarly,, B shares the, master key Kb with the KDC. The following steps occur., 1. A issues a request to the KDC for a session key to protect a logical connection to B. The message includes, the identity of A and B and a unique identifier, N1, for this transaction, which we refer to as a nonce. The, nonce may be a timestamp, a counter, or a random number; the minimum requirement is that it differs with, each request. Also, to prevent masquerade, it should be difficult for an opponent to guess the nonce. Thus,, a random number is a good choice for a nonce., 2. The KDC responds with a message encrypted using Ka. Thus, A is the only one who can successfully, read the message, and A knows that it originated at the KDC. The message includes two items intended for, A:, • The one-time session key, Ks, to be used for the session, • The original request message, including the nonce, to enable A to match, this response with the appropriate request Thus, A can verify that its original request was not altered before, reception by the KDC and, because of the nonce, that this is not a replay of some previous request., In addition, the message includes two items intended for B:, • The one-time session key, Ks, to be used for the session, • An identifier of A (e.g., its network address), IDA, These last two items are encrypted with Kb (the master key that the KDC, shares with B). They are to be sent to B to establish the connection and prove A’s identity.

Page 13 :
3. A stores the session key for use in the upcoming session and forwards to B the information that originated, at the KDC for B, namely,, E(Kb,[Ks || IDA])., Because this information is encrypted with Kb, it is protected from eavesdropping. B now knows the session, key (Ks), knows that the other party is A (from IDA), and knows that the information originated at the KDC, (because it is encrypted using Kb)., 4. Using the newly minted session key for encryption, B sends a nonce, N2, to A., 5. Also, using Ks, A responds with f(N2), where f is a function that performs, some transformation on N2, Hierarchical Key Control, It is not necessary to limit the key distribution function to a single KDC., A hierarchical scheme minimizes the effort involved in master key distribution, because most master keys, are those shared by a local KDC with its local entities., Session Key Lifetime, The more frequently session keys are exchanged, the more secure they are, because the opponent has less, ciphertext to work with for any given session key. On the other hand, the distribution of session keys delays, the start of any exchange and places a burden on network capacity. A security manager must try to balance, these competing considerations in determining the lifetime of a particular session key.

Page 14 :
For connection-oriented protocols, one obvious choice is to use the same session key for the length of time, that the connection is open, using a new session key for each new session. If a logical connection has a very, long lifetime, then it would be prudent to change the session key periodically, perhaps every time the PDU, (protocol data unit) sequence number cycles., For a connectionless protocol, such as a transaction-oriented protocol, there, is no explicit connection initiation or termination. Thus, it is not obvious how often one needs to change, the session key. The most secure approach is to use a new session key for each exchange. However, this, negates one of the principal benefits of connectionless protocols, which is minimum overhead and delay, for each transaction. A better strategy is to use a given session key for a certain fixed period only or for a, certain number of transactions., Decentralized Key Control, The use of a key distribution center imposes the requirement that the KDC be trusted and be protected from, subversion. This requirement can be avoided if key distribution is fully decentralized., A decentralized approach requires that each end system be able to communicate in a secure manner with, all potential partner end systems for purposes of session key distribution. Thus, there may need to be as, many as [n(n - 1)]/2 master keys for a configuration with n end systems., , A session key may be established with the following sequence of steps, 1. A issues a request to B for a session key and includes a nonce, N1., 2. B responds with a message that is encrypted using the shared master key. The response includes the, session key selected by B, an identifier of B, the value f(N1), and another nonce, N2., 3. Using the new session key, A returns f(N 2) to B., Symmetric Key Distribution using Asymmetric Encryption, Simple Secret Key Distribution, 1. A generates a public/private key pair {PUa, PRa} and transmits a message to B consisting of PUa and an, identifier of A, IDA., 2. B generates a secret key, Ks, and transmits it to A, which is encrypted with A’s public key., 3. A computes D(PRa, E(PUa, Ks)) to recover the secret key. Because only A, can decrypt the message, only A and B will know the identity of Ks., 4. A discards PUa and PRa and B discards PUa.

Page 15 :
Public-Key Distribution of Secret Keys, , 1. A uses B’s public key to encrypt a message to B containing an identifier of A(IDA) and a nonce (N1),, which is used to identify this transaction uniquely., 2. B sends a message to A encrypted with PUa and containing A’s nonce (N1) as well as a new nonce, generated by B (N2). Because only B could have decrypted message (1), the presence of N1 in message (2), assures A that the correspondent is B., 3. A returns N2, encrypted using B’s public key, to assure B that its correspondent is A., 4. A selects a secret key Ks and sends M = E(PUb, E(PRa, Ks)) to B. Encryption of this message with B’s, public key ensures that only B can read it; encryption with A’s private key ensures that only A could have, sent it., 5. B computes D(PUa, D(PRb, M)) to recover the secret key., Distribution of Public Keys, • Public announcement, • Publicly available directory, • Public-key authority, • Public-key certificates

Page 16 :
Public Announcement of Public Keys, , Publicly Available Directory, 1. The authority maintains a directory with a {name, public key} entry for each participant., 2. Each participant registers a public key with the directory authority., Registration would have to be in person or by some form of secure authenticated communication., 3. A participant may replace the existing key with a new one at any time, either because of the desire to, replace a public key that has already been used for a large amount of data, or because the corresponding, private key has been compromised in some way., 4. Participants could also access the directory electronically. For this purpose, secure, authenticated, communication from the authority to the participant is mandatory., Public-Key Authority, 1. A sends a timestamped message to the public-key authority containing a, Request for the current public key of B., 2. The authority responds with a message that is encrypted using the authority’s private key, PR auth. Thus,, A is able to decrypt the message using the authority’s public key. Therefore, A is assured that the message, originated with the authority. The message includes the following:, • B’s public key, PUb, which A can use to encrypt messages destined for B, • The original request used to enable A to match this response with the corresponding earlier request and to, verify that the original request was not, altered before reception by the authority, • The original timestamp given so A can determine that this is not an old, message from the authority containing a key other than B’s current public key.

Page 17 :
3. A stores B’s public key and also uses it to encrypt a message to B containing an identifier of A (IDA) and, a nonce (N1), which is used to identify this transaction uniquely., 4, 5. B retrieves A’s public key from the authority in the same manner as A, Retrieved B’s public key., At this point, public keys have been securely delivered to A and B, and they, may begin their protected exchange. However, two additional steps are desirable:, 6. B sends a message to A encrypted with PUa and containing A’s nonce (N1) as well as a new nonce, generated by B (N2). Because only B could have decrypted message (3), the presence of N1 in message (6), assures A that the correspondent is B., 7. A returns N2, which is encrypted using B’s public key, to assure B that its, Correspondent is A., , Public-Key Certificates, 1. Any participant can read a certificate to determine the name and public key of the certificate’s owner., 2. Any participant can verify that the certificate originated from the certificate authority and is not, counterfeit., 3. Only the certificate authority can create and update certificates., 4. Any participant can verify the currency of the certificate.

Page 18 :
For participant A, the authority provides a certificate of the form, CA = E(PRauth, [T || IDA || PUa]), where PRauth is the private key used by the authority and T is a timestamp., D(PUauth, CA) = D(PUauth, E(PRauth, [T || IDA ||PUa])) = (T || IDA ||PUa), , 3.8 DIFFIE HELLMAN KEY EXCHANGE, The purpose of the algorithm is to enable two users to securely exchange a key that can then be, used for subsequent encryption of messages.The algorithm itself is limited to the exchange of, secret values., The Diffie-Hellman algorithm depends for its effectiveness on the difficulty of computing discrete, logarithms.

Page 19 :
Diffie Hellman key exchange as follows:, There are publicly known numbers: a prime number „q‟ and an integer α that is, primitive root of q., suppose users A and B wish to exchange a key. User A selects a random integer XA, < q and computes, YA = α XA mod q. Similarly, user B independently selects a random, integer XB < q and computes YB = α XB mod q. Each side keeps the X value private, and, makes the Y value available publicly to the other side. User A computes the key as, K = (YB)XA mod q and, User B computes the key as, K = (YA)XB mod q, These two calculations produce identical results., K = (YB)XA mod q, = (α XB mod q)XA mod q, = (α XB)XA mod q, = (α XA)XB mod q, = (α XA mod q)XB mod q, = (YA)XB mod q

Page 20 :
The result is that two sides have exchanged a secret key., The security of the algorithm lies in the fact that, while it is relatively easy to, calculate Exponentials, modulo a prime, it is very difficult to calculate discrete logarithms. For large primes,, the latter task is considered infeasible., Diffie-Hellman Key Exchange, Global Public Elements, q, α, , prime number, α<q, and α is a primitive root of q, , User A Key Generation, Select private XA, Calculate public YA, , XA < q, YA = αXA mod q, , User B Key Generation, Select private XB, Calculate public YB, , XB < q, YB = αXB mod q, , Calculation of Secret Key by User A, K = (YB )XA mod q, Calculation of Secret Key by User B, K = (YA)XB mod q, Example:, Key exchange is based on the use of the prime number, q = 353 and a primitive root of 353, in this case α = 3. A and B select private keys, XA = 97 and XB = 233, respectively., A computes YA = 397 mod 353 = 40., B computes YB = 3233 mod 353 = 248., After they exchange public keys, each can compute the common secret key:, A computes K = (YB)X mod 353 = 24897 mod 353 = 160., B computes K = (YA)X mod 353 = 40233 mod 353 = 160., A, , B, , Key Exchange Protocols

Page 21 :
Man-in-the-Middle Attack, Suppose Alice and Bob wish to exchange keys, and Darth is the adversary. The attack proceeds as, follows., 1. Darth prepares for the attack by generating two random private keys XD1, and XD2 and then computing the corresponding public keys YD1 and YD2., 2. Alice transmits YA to Bob., 3. Darth intercepts YA and transmits YD1 to Bob. Darth also calculates, K2 = (YA)XD2 mod q., 4. Bob receives YD1 and calculates K1 = (YD1)XB mod q., 5. Bob transmits YB to Alice., 6. Darth intercepts YB and transmits YD2 to Alice. Darth calculates, K1 = (YB)XD1 mod q., 7. Alice receives YD2 and calculates K2 = (YD2)XA mod q.

Page 22 :
Bob and Darth share secret key K1 and Alice and Darth share secret key K 2. All future communication, between Bob and Alice is compromised in the following way., 1. Alice sends an encrypted message M: E(K2, M)., 2. Darth intercepts the encrypted message and decrypts it to recover M., 3. Darth sends Bob E(K1, M) or E(K1, M′), where M′ is any message. In the, first case, Darth simply wants to eavesdrop on the communication without, altering it. In the second case, Darth wants to modify the message going to Bob.

Page 23 :
3.9 The Elgamal Cryptosystem, The variant of the Diffie-Hellman key distribution scheme, allowing secure exchange, of, Messages published in 1985 by ElGamal in T. ElGamal, "A Public Key Cryptosystem, and a Signature Scheme Based on Discrete Logarithms",, Like Diffie-Hellman its security depends on the difficulty of factoring logarithms, Key Generation,  select a large prime p (~200 digit), and,  [[alpha]] a primitive element mod p,  A has a secret number xA,  B has a secret number xB,  A and B compute yA and yB respectively, which are then made public, yA = [[alpha]]xA mod p, yB = [[alpha]]xB mod p, to encrypt a message M into ciphertext C,,  selects a random number k, 0 <= k <= p-1,  computes the message key K, K = yB, k mod p,  computes the ciphertext pair: C = {c1,c2}, C1 = [[alpha]]k mod p C2 = K.M mod p, to decrypt the message,  extracts the message key K, K = C1, xB mod p = [[alpha]]k.xB mod p,  extracts M by solving for M in the following equation:, C2 = K.M mod p, Algorithm, Global Public Elements, q, α, , prime number, α<q, and α is a primitive root of q, , Key Generation by Alice, Select private XA, , XA < q - 1

Page 24 :
Calculate YA, Public key, Private key, , YA = αXA mod q, {q, a, YA}, XA, , Encryption by Bob with Alice’s Public Key, Plaintext:, M<q, Select random integer k, k<q, Calculate K, K = (YA)k mod q, Calculate C1, C1 = αk mod q, Calculate C2, C2 = KM mod q, Ciphertext:, (C1, C2), Decryption by Alice with Alice’s Private Key, Ciphertext:, (C1, C2), Calculate K, K = (C1)XA mod q, Plaintext:, M = (C2K-1) mod q, 1. Bob generates a random integer k., 2. Bob generates a one-time key K using Alice’s public-key components, YA, q, and k., 3. Bob encrypts k using the public-key component a, yielding C1. C1, provides sufficient information for Alice to recover K., 4. Bob encrypts the plaintext message M using K., 5. Alice recovers K from C1 using her private key., -1, 6. Alice uses K to recover the plaintext message from C2., Thus, K functions as a one-time key, used to encrypt and decrypt the message., Example:, let us start with the prime field GF(19); that is, q = 19., It has primitive roots {2, 3, 10, 13, 14, 15}. choose α = 10., 1. Alice chooses XA = 5., 2. Then YA = αXA mod q = α5 mod 19 = 3., 3. Alice’s private key is 5 and Alice’s public key is {q, a, YA} = {19, 10, 3}., Suppose Bob wants to send the message with the value M = 17. Then,, 1. Bob chooses k = 6., k, 6, 2. Then K = (YA) mod q = 3 mod 19 = 729 mod 19 = 7., k, 6, 3. C1 = α mod q = α mod 19 = 11, C2 = KM mod q = 7 * 17 mod 19 = 119 mod 19 = 5, 4. Bob sends the ciphertext (11, 5)., For decryption:, 1. Alice calculates K = (C1)XA mod q = 115 mod 19 = 161051 mod 19 = 7., 2. Then K-1 in GF(19) is 7-1 mod 19 = 11., 3. Finally, M = (C2K-1) mod q = 5 * 11 mod 19 = 55 mod 19 = 17.

Page 25 :
If a message must be broken up into blocks and sent as a sequence of encrypted blocks, a unique value of, k should be used for each block. If k is used for more than one block, knowledge of one block M1 of the, message enables the user to compute other blocks as follows., Let, C1,1 = αk mod q; C2,1 = KM1 mod q, C1,2 = αk mod q; C2,2 = KM2 mod q, Then,, C2,1/C2,2 = (KM1 mod q / KM2 mod q) = (M1 mod q / M2 mod q ), If M1 is known, then M2 is easily computed as, M2 = (C2,1)-1 C2,2 M1 mod q, , 3.10 Elliptic Curve Cryptography (ECC), The principal attraction of ECC, compared to RSA, is that it appears to offer, equal security for a far smaller key size, thereby reducing processing overhead., Abelian Group:, an abelian group G, sometimes denoted by {G, • }, is a set of elements with a binary operation, denoted by, • , that associates to each ordered pair (a, b) of elements in G an element (a • b) in G, (A1) Closure: If a and b belong to G, then a • b is also in G., (A2) Associative: a • (b • c) = (a • b) • c for all a, b, c in G., (A3) Identity element: There is an element e in G such that a • e = e • a = a, for all a in G., (A4) Inverse element: For each a in G there is an element a′ in G such that, a • a′ = a′ • a = e., (A5) Commutative: a•b = b•a for all a, b in G., , Elliptic Curves over Real Numbers, Elliptic curves are not ellipses. They are so named because they are described by cubic equations, similar, to those used for calculating the circumference of an ellipse. In general, cubic equations for elliptic curves, take the following form, known as a Weierstrass equation:, y2 + axy + by = x3 + cx2 + dx + e, where a, b, c, d, e are real numbers and x and y take on values in the real numbers., y2 = x3 + ax + b, Such equations are said to be cubic, or of degree 3, because the highest exponent they contain is a 3. Also, included in the definition of an elliptic curve is a single element denoted O and called the point at infinity, or the zero point, y = √x3+ax+b, , 1. O serves as the additive identity. Thus O = -O; for any point P on the elliptic curve, P + O = P. In what, follows, we assume P ≠ O and Q ≠ O., 2. The negative of a point P is the point with the same x coordinate but the negative of the y coordinate;, that is, if P = (x, y), then -P = (x, -y)., Note that these two points can be joined by a vertical line., Note that P + (-P) = P - P = O., 3. To add two points P and Q with different x coordinates, draw a straight line between them and find the, third point of intersection R. It is easily seen that there is a unique point R that is the point of intersection

Page 26 :
(unless the line is tangent to the curve at either P or Q, in which case we take R = P or R = Q, respectively)., To form a group structure, we need to define addition on these three points: P + Q = -R. That is, we define, P + Q to be the mirror image (with respect to the x axis) of the third point of intersection., 4. The geometric interpretation of the preceding item also applies to two points, P and -P, with the same x, coordinate. The points are joined by a vertical line, which can be viewed as also intersecting the curve at, the infinity point. We therefore have P + (-P) = O, which is consistent with item (2)., 5. To double a point Q, draw the tangent line and find the other point of intersection S. Then Q + Q = 2Q =, -S., , Algebraic Description of Addition, P = (xP, yP) and Q = (xQ, yQ), that are not negatives of each other, the slope of the line l that joins them is Δ, = (yQ - yP)/(xQ - xP). There is exactly one other point where l intersects the elliptic curve, and that is the, negative of the sum of P and Q., After some algebraic manipulation, we can express the sum R = P + Q as, xR = Δ2 - xP - xQ, yR = -yP + Δ(xP - xR), P + P = 2P = R. When yP ≠ 0

Page 27 :
ECC Diffie-Hellman Key Exchange, Global Public Elements, Eq(a, b), G, , elliptic curve with parameters a, b, and q, where q is a prime or an integer, of the form 2m, point on elliptic curve whose order is large, value n, , User A Key Generation, Select private nA, Calculate public PA, , nA < n, PA = nA * G, , User B Key Generation, Select private nB, Calculate public PB, , nB < n, PB = nB * G, , Calculation of Secret Key by User A, K = nA * PB, Calculation of Secret Key by User B, K = nB * PA