Secret Shares with CRT (Mignotte threshold secret sharing)We can use CRT for secret shares. One method is the Mignotte threshold secret sharing [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 make sure that: \(m_{n-k+1} ... m_n < m_0 ... m_{k-1}\). For example if, \(k=3\) and \(n=4\), we make sure that: \(m_2 \times m_3 < m_0 \times m_1 \times m_2\).W e start with a secret (\(S\)) within a given range, and then compute the shares of: \(s_i=S \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 Mignotte threshold secret sharing [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 make sure that:
\(m_{n-k+1} ... m_n < m_0 ... m_{k-1}\)
For example if, \(k=3\) and \(n=4\), we make sure that:
\(m_2 \times m_3 < m_0 \times m_1 \times m_2\)
We start with a secret (\(S\)) within a given range, and then compute the shares of:
\(s_i=S \pmod {m_i}\)
We can then bring together a number of shares and solve for CRT.
Code
The code is:
# https://asecuritysite.com/encryption/sss_crt2?val1=999 from libnum import solve_crt,generate_prime from random import randint import sys bitsize=60 # 60-bit primes m=[0] * 4 # Array with five values share=[0] * 4 # 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 = sorted(m) while ((m[0]*m[1]*m[2] < m[2]*m[3]) and m[3]<m[2]): m[3]=generate_prime(bitsize) # for 3 from 4 we must have m0*m1*m2>m2xm3 secret=5 if (len(sys.argv)>1): secret=int(sys.argv[1]) rand= randint(m[2]*m[3],m[0]*m[1]*m[2]) secret=rand+secret share[0] = (secret) % m[0] share[1] = (secret) % m[1] share[2] = (secret) % m[2] share[3] = (secret) % m[3] print ("Secret: ",secret) print ("\nPrime0: ",m[0]) print ("Prime1: ",m[1]) print ("Prime2: ",m[2]) print ("Prime3: ",m[3]) print ("\nShare 1 (s1,m1): ",share[0],m[0]) print ("Share 2 (s2,m2): ",share[1],m[1]) print ("Share 3 (s3,m3): ",share[2],m[2]) print ("Share 4 (s4,m4): ",share[3],m[3]) print ("\nNow using the first three shares and solve CRT") mod=[m[0],m[1],m[2]] rem=[share[0],share[1],share[2]] res=solve_crt(rem,mod) print ("Secret: ",res-rand) print ("\nNow using the first two shares and solve CRT") mod=[m[0],m[1]] rem=[share[0],share[1]] res=solve_crt(rem,mod) print ("Secret: ",res-rand)
A sample run with 60-bit primes:
Secret: 573145165887294485616490175405566692787387450499289968 Prime0: 757959770631913757 Prime1: 863172167552175001 Prime2: 943433622614114917 Prime3: 1008828436269265511 Share 1 (s1,m1): 748494740768369398 757959770631913757 Share 2 (s2,m2): 706690164490024 863172167552175001 Share 3 (s3,m3): 291772956089299981 943433622614114917 Share 4 (s4,m4): 690231746071021246 1008828436269265511 Now using the first three shares and solve CRT Secret: 5 Now using the first two shares and solve CRT Secret: -573145165887294485241420322814546302198249471625984773