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 a common curve (sepc256k1).
Conference Keying (Burmester-Desmedt method) - Elliptic Curve |
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} \)
To convert to an elliptic curve method, we take the exponents and convert to point multiplication and take the multiplications and make then point additions. We have \(t\) users and then need to generate a common key (\(K\)). First, everyone agrees on the elliptic curve (secp256k1). Next, for each participant \(i\), each user generates a random number (\(r_i\)), and then compute a public value:
\(z_i={r_i}G\)
and where \(G\) is the base point of the curve. Each user then shares this value with the rest of the participants. Each participant then
\(X_i={r_{i+1} r_i - r_i r_{i-1}} G \)
Finally each participant will compute the same key as:
\( K_i = (t) r_i{(z_{i-1})} \cdot ({t-1}){X_i} \cdot ({t-2}) {X_{i+1}}... X_{i+(t-2)} \)
In the end the key should be:
\(K = {r_0 r_1 + r_1 r_2 + ... r_{t-1} r_0} G \)
Coding
The coding is here:
import random from secp256k1 import curve,scalar_mult,point_add t=5 # Number of parties z=[0]*t X=[0]*t r=[0]*t K=[0]*t for i in range(0,t): r[i] = random.randint(0,curve.n-1) z[i]=scalar_mult(r[i],curve.g) for i in range (0,t): X[i]=scalar_mult( r[(i+1) % t]*r[i]-r[i]*r[(i-1) % t] ,curve.g) for i in range(0,t): K[i] = scalar_mult((t)*r[i],z[(i-1) % t]) for j in range(i+1,i+1+t): if (i==j): continue print (i,j) K[i]= point_add(K[i],scalar_mult(t-j,X[(j-1)%t] )) print ("Random values:",r) print ("Public values:",z) print ("X values:",X) print ("\nKeys:",K) res=0 # res=r[0]*r[1]+r[1]*r[2]+r[2]*r[3]+r[3]*r[4]+r[4]*r[0] for i in range(0,t): print (i) res=res+r[i]*r[(i+1) % t] print ("\nComputing keys check: ",scalar_mult(res,curve.g))
A sample run is:
Random values: [4463755533774846637602847786757967242760690701307412228130857643967381735961, 96741168467817540081715654301555320158700388867341434828721393650453255123598, 61717472230239991980587257980114017418350116704648873039341165979823722071908, 31396563891021751196251791277695734072399130657200351619892753198581696606358, 94974630673319814151666749055588197124805370415672083005559727772301913543049] Public values: [(90998925973083513632524330963385502701735581109878497335329151079303020577062, 70476537201409353199423621118851831820916810206517759824278218573427123274854), (102856868652781612746571171973939143500320236409384393268847771909963184530815, 13965495275489018774649599026486194870140041286252697791560233811209331936429), (99427446516467715961185033565252932237546785658238480036817281660874998037690, 82251641136334087997353903825716793391136726060564762099059018320882765839735), (16911560158753047673799685404669901591458309596275429611503718364197714304782, 98607243930441122214101848630482213064773819153199493507981140339018033703075), (80996244729840843346182126920131238615639835161760630079777852677521978441245, 96197448374393385713664339442731699552686581860563691777163087626748519797778)] X values: [(100680773417056826796392972836368412942881478846041580947365227405336566099931, 81252703976782592443579928624901987165854250176997629439296479043515298170128), (16101859607536982072129354380897450431003353688964803707285331126652803561385, 112732197441811842906576112962764519089814958065782324313472455813793822069074), (15074040894883837781822534409993380373612978732311008136641548386000483940722, 109804456866678370366478104442243995459528193807709717970358142489076870096883), (22429915282361565376998416497359492372245028015609505651696750498280574308999, 72404092627159191603983409751568832688200126539081793183662988703011651518525), (97399537878596411031231666990291110758010935851808295555449530907457625436801, 97965381662004412161182160421748694350030391472605996320673526195132304679086)] Keys: [(30936135514666477810243436584887087257015238035391107280540936531549604687442, 69281525411964621344251301477793480609976500259298981379672706210590877300194), (30936135514666477810243436584887087257015238035391107280540936531549604687442, 69281525411964621344251301477793480609976500259298981379672706210590877300194), (30936135514666477810243436584887087257015238035391107280540936531549604687442, 69281525411964621344251301477793480609976500259298981379672706210590877300194), (30936135514666477810243436584887087257015238035391107280540936531549604687442, 69281525411964621344251301477793480609976500259298981379672706210590877300194), (30936135514666477810243436584887087257015238035391107280540936531549604687442, 69281525411964621344251301477793480609976500259298981379672706210590877300194)] Computing keys check: (30936135514666477810243436584887087257015238035391107280540936531549604687442, 69281525411964621344251301477793480609976500259298981379672706210590877300194)
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].