Filter
Top Products
CCA Release 2.54
Master-Key-Splitting Algorithm
This section describes the mathematical and cryptographic basis for the m-of-n key
shares scheme.
The key splitting is based on Shamir's secret sharing algorithm:
The value to be shared is the master key, Km, which is a triple-DES key and thus
168 bits long. Let P be the first prime number larger than 2
168
. All operations are
carried out modulo P.
Shamir's secret sharing allows the sharing of Km among n trustees in a way that
no set of t or less of trustees will have ANY information about Km, while t+1
trustees (or more) will be able to reconstruct Km.
Sharing phase:
1. Randomly choose a_t,...,a_1 in [0..P-1]
2. Consider the polynomial f(x) = a_t x
t
+ ... + a_1 x + a_0, where a_0=Km.
Compute mk_i = f(i) mod P for all i=1,...n
3. Proceed to distribute the values mk_i as described above.
Reconstruction phase:
1. After generating the set of authentic values (above sharing phase) proceed as
follows:
2. Take t+1 such values and interpolate the polynomial f(x) of degree t passing
through these values using Lagrange interpolation. This will define a
polynomial f(x) such that: f(i)=mk_i, and further more f(0) = MK. As we are
only interested in Km, we present the mathematical formula to reconstruct the
free term of the polynomial f(x). Let k_1,...,k_{t+1} be the indices of the mk_i's
used for reconstruction. Then
a_0=SUM_j( b_{k_j} PROD_h (x_{k_h} / (x_{k_h}- x_{k_j}))) mod P
3. Proceed to install Km = a_0 = f(0) mod P.
D-18 IBM 4758 CCA Basic Services, Release 2.54, February 2005