With conference keying, we have \(t\) participants, and each of them generate a secret value (\(r_i\)), and then transmit a public value generated from this (\(Z_i\)). Each of the participants then uses these values, and their secret value, and will generate the same secret key (\(K_i\)). In the following we will use the Burmester-Desmedt method [1], and have five participants, and with varying sizes of a shared prime number (\(p\)), and for a common generator (\(g\)) [ECC Conference Key (Burmester-Desmedt method)].
Conference Keying (Burmester-Desmedt method) |
Theory
In the Burmester-Desmedt conference keying method, we have \(t\) users and then need to generate a common key (\(K\)). First, everyone agrees on a prime number (\(p\)) and a generator (\(g\)). Next, for each participant \(i\), each user generates a random number (\(r_i\)), and then compute a public value:
\(z_i=g^{r_i} \pmod p\)
Each user then shares this value with the rest of the participants. Each participant then computes:
\(X_i = {(z_{i+1} / z_{i-1})}^{r_i} \pmod p \)
This is equivalent to:
\(X_i=g^{r_{i+1} r_i - r_i r_{i-1}} \)
Finally each participant will compute the same key as:
\( K_i = {(z_{i-1})}^{t r_i} \cdot {X_i}^{t-1} \cdot {X_{i+1}}^{t-2} ... X_{i+(t-2)}^1 \pmod p \)
In the end the key should be:
\(K = g^{r_0 r_1 + r_1 r_2 + ... r_{t-1} r_0} \)
Coding
The coding is here:
import random import sys from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes p=997 g=3 t=5 primebits=64 msg="hello" if (len(sys.argv)>1): primebits=int(sys.argv[1]) if primebits>512: primebits=512 p = getPrime(primebits, randfunc=get_random_bytes) z=[0]*t X=[0]*t r=[0]*t K=[0]*t for i in range(0,t): r[i] = random.randint(0,p) z[i]=pow(g,r[i],p) for i in range (0,t): X[i]=pow(g,r[(i+1) % t]*r[i]-r[i]*r[(i-1) % t],p) for i in range(0,t): K[i] = pow(z[(i-1) % t],(t)*r[i],p) for j in range(i+1,i+1+t): if (i==j): continue K[i]= (K[i]* pow(X[(j-1)%t],(t-j),p))% p print ("Keys:",K) res=r[0]*r[1]+r[1]*r[2]+r[2]*r[3]+r[3]*r[4]+r[4]*r[0] print ("Computing keys check: ",pow(g,res,p))
A sample run is:
Random values (r): [226589242101802, 189829639746726, 188625714155186, 184735699686400, 116440993319309] Public values (z): [267704455905509, 50015333919247, 15916535078749, 264135697727188, 206738438540103] X values: [112085216125079, 87590296821257, 260726071053053, 50830423926144, 23766863138958] Keys: [155751430205915, 155751430205915, 155751430205915, 155751430205915, 155751430205915] Computing keys check: 155751430205915
Reference
[1] Burmester, M., & Desmedt, Y. (1994, May). A secure and efficient conference key distribution system. In Workshop on the Theory and Application of of Cryptographic Techniques (pp. 275-286). Springer, Berlin, Heidelberg [here].