Elgamal_digital_signature_scheme.pptx

Elgamal Digital Signature Scheme.
The ElGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms.

1. Elgamal digital signature scheme Under Supervision of: Prof. Dr. Hesham El Zouka   Student Name : Karim Mohamed Monir Abdelfattah Hassan Abouelmakarem Registration No. : 20135001

2. Number Theory Recap Primitive root: A number is said to be a primitive root modulo n if every number coprime to n is congruent to a power of modulo n.  A number ‘ ’ is said to be a primitive root of prime number ‘p’, if : 1 mod p, 2 mod p, 3 mod p, ……...., p-1 mod p, are distinct (Normally distributed) (Not repeated).  

3. Number Theory Recap Primitive root: Example: Is 2 a primitive root of prime number 5? Solution: All the positive numbers less than 5 are normally distributed, distinct, not repeated , t hen 2 is a primitive root of 5 2 1 mod 5 2 mod 5 2   2 2 mod 5 4 mod 5 4   2 3 mod 5 8 mod 5 3   2 4 mod 5 16 mod 5 1  

4. Number Theory Recap Extended Euclidean Algorithm To find X -1 mod p (The multiplicative inverse) X and p must be relatively prime to each other [GCD(X, p) = 1], otherwise, there will be no multiplicative inverse. This means finding the number that if it was multiplied by X then divided by p, the remainder would be equal to 1 For example : 16 -1 mod 89 This means we need to find : 16*X mod 89 = 1

5. Number Theory Recap 89 89 [(16*5=80) then (89-80=9)]  16 1  [(1*5=5) then (89-5=84)] [(9*1=9) then (16-9=7)]  9 84 [(84*1=84) then (1-84=-83)] [(7*1=7) then (9-7=2)]  7 -83 [(-83*1=-83), (84-(-83)=167)] [(2*3=6) then (7-6=1)]  2 167 [(167*3=501), (-83-501=-584)] (We reached 1) 1 -584 Multiplicative inverse When the result multiplicative inverse is negative, we add P (in this case 89) until we reach the positive value  39

6. Number Theory Recap Second method: 89 - 16 (X) = ? 89 – 16 (5) = 9 ------  (1) The number X to be multiplied by 16 and would give the closest result less than 89 Then we extend the regular way: 16 – 9 (1) = 7 -------  (2) 9 – 7(1) = 2 -------  (3) 7 – 2(3) = 1 -------  (4) We reached a result of 1, so we substitute reversely as follows: from equation (3), equation (4) will be: 7 – (9-7) (3) = 1 9 (-3) + 7 (4) = 1 ----  (5)

7. Number Theory Recap From equation (2), equation (5) will be: 9 (-3) + (16-9)(4) = 1 16 (4) + 9 (-7) = 1 -----  (6) From equation (1), Equation (6) will be: 16 (4) + [89-16(5)] (-7) = 1 89 (-7) + 16 (35) + 16 (4) = 1 89 (-7) + 16 (39) = 1 --------  (7) From the final form of equation (7), hence, the multiplicative inverse for 16 is 39. So, our original equation will be: 16 -1 mod 89 39 mod 89 Remember, if the inverse is negative we add p to it until we get the true positive value.

8. Number Theory Recap Third method: When we reach to the remainder equaling 0, then the multiplicative inverse is T 2

9. Digital Signature A digital signature is a mathematical technique used to validate the authenticity and integrity of a message, software, or digital document. Digital signatures can provide evidence of origin, identity and status of electronic documents, transactions or digital messages. Signers can also use them to acknowledge informed consent. Digital signature is commonly used for software distribution, financial transactions and other cases where it is important to detect forgery and tampering.

10. Digital Signature Importance Authentication : When the verifier validates the digital signature using public key of a sender, he is assured that signature has been created only by sender who possess the corresponding secret private key and no one else. Data Integrity : In case an attacker has access to the data and modifies it, the digital signature verification at receiver end fails. The hash of modified data and the output provided by the verification algorithm will not match. Hence, receiver can safely deny the message assuming that data integrity has been breached. Non-repudiation : Since it is assumed that only the signer has the knowledge of the signature key, he can only create unique signature on a given data. Thus the receiver can present data and the digital signature to a third party as evidence if any dispute arises in the future.

11. How Does it work?

12. Elgamal Digital Signature Scheme The ElGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms. It was described by Taher ElGamal in 1984. The ElGamal signature algorithm is rarely used in practice. A variant developed at NSA and known as the Digital Signature Algorithm is much more widely used. The ElGamal signature scheme must not be confused with ElGamal encryption which was also invented by Taher ElGamal .

13. Elgamal Digital Signature Scheme How does it work? Main system parameters: Let H be a collision-resistant hash function. [ A hash function H is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b where a ≠ b but H(a) = H(b).] Let p be a large prime such that computing discrete logarithms modulo p is difficult. Let be a randomly chosen number that satisfies the following conditions: 1) is a primitive root of p. 2) is < p.  

14. Elgamal Digital Signature Scheme How does it work? Now, after the determination of the system parameters, the three main steps:- 1- Generation of keys (the same as Elgamal encryption). 2- Signature Generation. 3- Verification.

15. Elgamal Digital Signature Scheme 1- Generation of keys:- We already have p and So, Generate a random integer X A such that, 1 < X A < p-1 Compute Y A = XA mod p The sender’s private key is X A The sender’s public key is (P, , Y A ) m is the message digest such that, m=H(M)  

16. Elgamal Digital Signature Scheme 2- Generation of signature:- Generating a random integer K such that, 1 K p-1 && GCD(K, p-1) = 1 meaning K is relatively prime to p-1 b) Compute the first component of the signature: S 1 = K mod p c) Compute the second component of the signature: S 2 = K -1 (m-X A S 1 ) mod (p-1)  If any of S 1 or S 2 equals 0, we start over choosing another K.  The signature consists of the pair (S 1 , S 2 )  

17. Elgamal Digital Signature Scheme 3- Verification of the signature (Receiver’s side) :- Compute V1 such that: V 1 = mod p b) Compute V2 such that: V 2 = (Y A ) S1 (S 1 ) S2 mod p  If V 1 = V 2 then the signature is valid.  

18. Elgamal Digital Signature Scheme Public key (P, , Y A ) Private key (X A ) M essage digest m = H(M) Signature (S 1 , S 2 )  

19. Elgamal Digital Signature Scheme Example: P=19, = 10, X A = 16, m = 14, K = 5 Solution:  Key generation Calculate YA: Y A = XA mod p Y A = 10 16 mod 19 = 4 Public key (19, 10, 4) Private key (16)  

20. Elgamal Digital Signature Scheme Solution: P=19, = 10, X A = 16, m = 14, K = 5, Y A = 4  Signature generation 2) Calculate S 1 : S 1 = mod p S 1 = 10 5 mod 19 = 3 3) Calculate S 2 : S 2 = K -1 (m - X A .S 1 ) mod (p-1) S 2 = 11 (14 – 16*3) mod 18 = 4  The signature is (3, 4)  

21. Elgamal Digital Signature Scheme Solution: P=19, = 10, X A = 16, m = 14, K = 5, Y A = 4, S 1 = 3, S 2 = 4  Signature Verification 4) Calculate V 1 : V 1 = mod p V 1 = 10 14 mod 19 = 16 5) Calculate V 2 : V 2 = (YA) S1 *(S 1 ) S2 mod p V 2 = (4) 3 * (3) 4 mod 19 = 16  V 1 = V 2 , hence, it’s a valid signature.