Cryptographic Identification Protocols and Solutions in Cryptology

Introduction to Cryptology Tutorial-12 Cryptographic Identification 22.05.2023, v39 Page : 1

Problem 12-1: Fiat Shamir Proof of Identity Protocol Set up Fiat Shamir Proof of Identity Protocol over Z33. User A has the secret key a=7. 1. User A generated 3 random numbers 22,27,32. Which one of these numbers is a unit? Use it as r for user sA first challenge and compute S. 2. How many possible units can be selected in this system setup? 3. The verifier responded with the challenge b=1. Compute user A s response t. 4. Excute the verifier computations to check the response of A. 5. If the user A used the same random number again and the verifier challenged this time with b=0. How can you attack user s A identity. Page : 2

Solution 12.1: 1. As gcd (33,22) = 11, 22 is not invertible. gcd (33,27) = 3, 27 is not invertible, gcd (33,32) = 1, 32 is invertible or it is a unit. S= r2= 322= 1 2. The number of units is: (33) = (3 x 11) =(3-1) (11-1)=20 3. and 4. See the protocol sketch in the next slide. 5. For b=0 and having the same random r the new response is t2 = r, as the first response t1 = r. Xa solving for Xafrom the above two equations yields: Xa= t1 / t2 = t1 x t2 -1 = 26 x 32 = 7. Page : 3

Solution 12.1 : Fiat-Shamir Proof-of-Identity Protocol (1986) A Zero-Knowledge proof protocol Security relies on the Factoring Problem ! Public Directory m = p1p2 = 33 p1p2 are secrets which no body should know m= 33 is RSA type modulus ya= xa2= 16 in Z33(mod m) xa= secret key of A=7 Prover A A chooses a unit r = 32 in Z33and computes Verifier ( I am user A, S ) S = r 2 = ..2 = 1 randomly choose b b = 1 or 0 b=1 S ya t1 =26 for b=1 t2 =32 for b=0 If t2= S . yab = 262= 1 X 161 16 = 16 then A is authentic (A knows xa) t = r. xab= 32 . 7b= -7=26 Prob. of a successful attack after k trials = 2-k Page : 4

Problem 12-2: Set up Omura Proof of Identity Protocol over GF(24) . User the generator polynomial P(x) = x4 + x3+ x2 + x + 1. Compute all powers of x up to 10. Select a primitive element from the following list 0010, 0011 and compute the order of the selected one. 1. 2. How many primitive elements do we have over GF(24)? 3. State three other primitive elements. 4. If the verifier selects K= 6, compute the verifier s challenge R. 5. Compute user s A response if the secret key of A is 7 6. Verify user s A response. Page : 5

Solution 12-2: P(x) = x4 + x3+ x2 + x + 1=0, x4 = x3+ x2 + x + 1. The powers of x are: x=x x2= x2 x3= x3 x4= x3+ x2 + x + 1 x5= x4+ x3 + x2 + x = x3+ x2 + x + 1 + x3 + x2 + x = 1 => ord(x)=5 x6= x, x7= x2, x8= x3, x9= x4,x10= x0=1 1. The orders of elements are the divisors of 24-1= 15, that is 1,3,5,15 Order of 0010 = x = 5 the element is not primitive. 0011 = 1+x : (1+x)3= (1+x2)(1+x) = 1 + x2+ x + x3 1 (1+x)5= (1+x)3(1+x)2= (1 + x2+ x + x3)(1+x2) = 1 + x2+ x + x3+ x2+ x4+ x3+ x5 = 1 + x2+ x3 1 thus order of (1+x) is 15 and it is primitive. 2. The number of primitive elements is (15) = (3-1)(5-1)=8 3. As (1+x) is primitive, then (1+x)iis also primitive iff gcd(15,i)=1 4. therefore (1+x)2, (1+x)4, (1+x)7 are all primitive elements. Page : 6

Omura Proof-of-Identity Protocol Public Directory Solution 12-2: Prover A Verifier = (1 +x) is a primitive element in GF( 24) P(x) = x4 + x3+ x2 + x + 1 ya= 0111= public key of A ya= Xa= (1+x)7= (1+x)5(1+x)2 = (1 + x2+ x3) (1+ x2) = 1 + x2+ x3+ x2+ x4+x5 ya= x3+ 1 +x+ x2+ x3= 1 +x+ x2 Randomly choose k=6 compute R = 6=1000 =x3 Who are you?, R= x3 R=1000= x3 6= (1+x)6= (1+x)5(1+x) = (1 + x2+ x3) (1+ x) = 1 + x2+ x3+ x + x3+x4 = 1+ x+x2+ 1 +x+ x2+ x3= x3 I am user A, RXa = x RXa= (x3)7 mod 5 = x check RXa= yak x = (1+x+x2)6 x= x (1 + x + x2)6= (1 + x + x2)4(1 + x + x2)2= (1 + x4+ x8) (1 + x2+ x4) = 1 + x4+ x8 + x2+ x6+ x10 + x4+ x8+ x12 = = 1 + x2+ x + x0 + x2 = x => User is authentic Page : 7

Schnorrs Identification/signature Scheme Problem 12-3: Set up Schnorr s Identification/signature Scheme over GF(139). User A has the secret key XA=18. 1. Compute q the order of the element =26in GF(139). Is q suitable for Schnorr s Identification/signature Scheme.? 2. Compute the public key of A: ??= ???mod? , for a random value k=15. 3. Compute ? = ??mod? 4. Compute the hash value H(M|r) for a message message M =37 by using the following hash function: = 3 ( ) mod83 H x x 5. Compute A s Schnorr signature for the message M=37. 6. Make all necessary tomputations to verify A signature. Page : 8

Schnorrs Identification/signature Scheme Open Directory (as DH public directory) GF(p), Element has order q such that q is prime which divides p-1 is the public key of A having secret key xA< q mod p = x A y A User A sings a hash value H(M|r) for a message message M: Similarity to ElGamal Signature = k 1 : mod [ ( )] Compute r p forarandomk GF q 2 ??????? ? ? ?? ????? ? = ?(?|?) 3 ComputetheSignature = ( ) mod S k x m q A verifier Prover A A signed message M is : M, (S,m) = then Aisauthentic S m A 1 2 ' mod Compute if m r | '), y p - A proves that he knows xA - A good ans strong hash function is required = ( H M r = k x m = ( ) x m k ' Notice that r A A Page : 9

Solution 12-3: 1. The possible units orders in GF(139) are the divisors of (139) = 138 => the divisors of 138 are 1, 2, 3, 6, 23, 46,69, and 138 Order of 2: 21= 2 1, 22= 4 1, 23= 8 1, 26= 64 1, 223= 97 1 , 246= 96 1, 269= 138 1, => order of 2 is 138 Order of 26=64: ord(2k)= ord(2)/gcd(k,ord(2)) Ord(64)=ord(26)= ord(2)/gcd(6,ord(2))=138/gcd(6,138)=138/6=23 = x mod A y p 2. The public key of A: = 6418 mod 139 = 34 A = k mod r p 3. For k=15; =6415mod 139=80 = 3 4. For M=37; ( || ) r ( || ) mod83 r H M M =(3780)3mod 83=74 Page : 10

Solution 12-3: 5. Prover A sings a hash value H(M|r). public directory GF(139), =26=64 YA= 34 Prover A = = ( || ) r 74 m H M = ( ) mod S k x m q =(15- 18x 74)mod 23=17 A : ( , ) S m = (17,74) Signature formessageM is Verifier 6. verify A signature. ?mod? (3780)3mod 83=74=m Step1: ? = ???? Step2:H(M|r ) = =(6417x 3474)mod 139= 80 Then, A is authentic Page : 11