Secret Shares with CRT (Asmuth-Bloom threshold)We can use CRT for secret shares. One method is the Asmuth-Bloom threshold secret share scheme [1]. For this we create co-prime integers for the number of shares (\(n\)) we need (\(m_0, m_1 ... m_n\)) and where \(m_0 < m_1 < m_2 ... < m_n\). For co-prime, none of the values of \(m_i\) will share a factor. If they are all prime numbers, they will not share any factors. We start with a secret (\(S\)). and then compute the shares of \(s_i=S+\alpha m_0 \pmod {m_i}\). We can then bring together a number of shares and solve for CRT. [Secret shares with CRT (Asmuth-Bloom threshold)][Secret shares with CRT (Mignotte threshold )][Secret shares with Blakley method][Shamir's Secret Sharing][Proactive Secret Sharing] |
Outline
With Chinese Remainder Theory (CRT) we can solve for:
\(x = 45 \pmod {51}\)
\(x = 14 \pmod {14}\)
\(x = 5 \pmod {13}\)
Using Python we get:
from libnum import solve_crt mod=[51,41,13] rem=[45,14,5] res=solve_crt(rem,mod) print (res) print (res % 51) print (res % 41) print (res % 13)
And where the result is:
96 45 14 5
The solution is thus \(x=96\).
We can use CRT for secret shares. One method is the Asmuth-Bloom threshold secret share scheme [1]. For this we create co-prime integers for the number of shares (\(n\)) we need (\(m_0, m_1 ... m_n\)) and where \(m_0 < m_1 < m_2 ... < m_n\). For co-prime, none of the values of \(m_i\) will share a factor. If they are all prime numbers, they will not share any factors. With these values we need to make sure that:
\(\prod^{t}_{i=1} m_i > m_0 \prod^{t-1}_{i=1} m_{n-i+1} \)
We start with a secret (\(S\)), and then compute the shares of:
\(s_i=S+\alpha m_0 \pmod {m_i}\)
We can then bring together a number of shares and solve for CRT, as, for a threshold of three, we can solve:
\(s_0 = (S + \alpha m_0) \pmod {m_1}\)
\(s_1 = (S + \alpha m_0) \pmod {m_2}\)
\(s_2 = (S + \alpha m_0) \pmod {m_3}\)
to give a solution of:
\(res = S + \alpha m_0 \)
and then taking:
\(res \pmod{m_0} \)
will gives us \(S\).
Code
The code is:
# https://asecuritysite.com/encryption/sss_crt?val1=999 from libnum import solve_crt,generate_prime from random import randint import sys bitsize=60 # 60-bit primes m=[0] * 5 # Array with five values share=[0] * 5 # Array with five values m[0]=generate_prime(bitsize) m[1]=generate_prime(bitsize) m[2]=generate_prime(bitsize) m[3]=generate_prime(bitsize) m[4]=generate_prime(bitsize) m = sorted(m) while ((m[1]*m[2]*m[3] < m[0]*m[3]*m[4]) and m[4]<m[3]): m[4]=generate_prime(bitsize) M=m[1]*m[2] # for 3 from 4 we must have m1*m2*m3>m0xm3xm4 secret=5 if (len(sys.argv)>1): secret=int(sys.argv[1]) alpha= randint(1, M) share[0] = (secret+alpha*m[0]) % m[1] share[1] = (secret+alpha*m[0]) % m[2] share[2] = (secret+alpha*m[0]) % m[3] share[3] = (secret+alpha*m[0]) % m[4] print ("Secret: ",secret) print ("Alpha: ",alpha) print ("\nPrime0: ",m[0]) print ("Prime1: ",m[1]) print ("Prime2: ",m[2]) print ("Prime3: ",m[3]) print ("Prime4: ",m[4]) print ("\nShare 1 (s1,m1): ",share[0],m[1]) print ("Share 2 (s2,m2): ",share[1],m[2]) print ("Share 3 (s3,m3): ",share[2],m[3]) print ("Share 4 (s4,m4): ",share[3],m[4]) print ("Public part (m0): ",m[0]) print ("\nNow using the first three shares and solve CRT") mod=[m[1],m[2],m[3]] rem=[share[0],share[1],share[2]] res=solve_crt(rem,mod) % m[0] print ("Secret: ",res) print ("\nNow using the first two shares and solve CRT") mod=[m[1],m[2]] rem=[share[0],share[1]] res=solve_crt(rem,mod) % m[0] print ("Secret: ",res)
A sample run with 60-bit primes:
Secret: 999 Alpha: 444245249422698541346812310673502438 Prime0: 650094581405656027 Prime1: 819353738310908587 Prime2: 906922952045910433 Prime3: 1040280684351465493 Prime4: 1138050480341993861 Share 1 (s1,m1): 354430321238022827 819353738310908587 Share 2 (s2,m2): 19078779414110362 906922952045910433 Share 3 (s3,m3): 912302619083664391 1040280684351465493 Share 4 (s4,m4): 546159951924698171 1138050480341993861 Public part (m0): 650094581405656027 Now using the first three shares and solve CRT Secret: 999 Now using the first two shares and solve CRT Secret: 448948650480899210