A small amount of data that does not belong to any file
Shamir's Secret Sharing Scheme is a method for securely sharing a secret among a group of participants. It's like sharing a secret recipe for the best cookies with your friends, but instead of giving them the whole recipe, you give them a few ingredients, and they can only make the cookies if they get together and share their ingredients.
The idea is to divide a secret into a number of shares, so that a certain number of shares are required to reconstruct the secret. This allows the secret to be safely shared among a group of participants, as each individual share doesn't reveal any information about the secret, unless you're a professional code breaker, in which case it's just a matter of time.
The scheme works by representing the original secret as a polynomial of degree k-1, where k is the number of shares needed to reconstruct the secret. And let's face it, who doesn't love a good polynomial? Each participant is then given a share, which is a pair of x and y coordinates, where x is a number between 1 and n, and y is the value of the secret polynomial at x. Participants can then reconstruct the secret by obtaining at least k shares and interpolating the polynomial using these shares, it's like solving a maths puzzle.
One of the main advantages of Shamir's scheme is that it allows flexibility in the number of shares needed to reconstruct the secret. This can be useful in situations where the number of participants or the level of security required may change over time, such as when your friends share the recipe for biscuits and one of them becomes a top chef and decides to open a restaurant. In addition, the scheme is also able to protect against malicious participants, as long as enough honest participants are involved in the reconstruction process, because who would be malicious when it comes to cookies?
root@matrix ssss % php ssss_example.php
Generated random secret: 5dbc894c0e9195b954d4a4b0ff68580af41d42e44d1ddf14cccb8fa65ab596b0
Number of shares: 10, with a threshold of: 4
Prime (dec): 115792089237316195423570985008687907853269984665640564039457584007913129640233
Prime (hex): 010000000000000000000000000000000000000000000000000000000000000129
Generated shares:
Array
(
[1] => a7c86aae626dffbcd11ab17eecb58bbc2631912680283e196adc249dd9061107
[2] => a90eccf79446a04c80b307beb450373b2357e1805401c0463480801710aba2f6
[3] => 77d6c92809d08886e2d5e63ff3687005a7c811bcbc4e1502dfdf9ee651edac4d
[4] => 2a67784028c0c98a76bb8bd2472e4b996fb9ffa6acb0ebb723207ddfed138cdc
[5] => d707f34056cc7475bb9c37454cd1df743765890918cdf3cab46a19d83264a59c
[6] => 93ff5328f9a89a6730b02768a1834113bb028baef448dca549e36fa37228540b
[7] => 7794b0fa770a4c7d552f9b0be27285f5b6c8e56332c555ae99b37c15fca5f922
[8] => 980f25b534a69bd6a852d0feaccfc397e6f073f0c7e70e4e5a013c042224f4b1
[9] => 0bb5ca5998329991a95208109dcb0f7807b11522a751b5ec40f3ac4232eca55f
[10] => e8cfb7e8076356ccd7657f1152947f13d542a6c3c4a8fbf004b1c9a47f446d4e
)
5 examples of the recovery of the secret:
Example 1:
Array
(
[1] => a7c86aae626dffbcd11ab17eecb58bbc2631912680283e196adc249dd9061107
[2] => a90eccf79446a04c80b307beb450373b2357e1805401c0463480801710aba2f6
[4] => 2a67784028c0c98a76bb8bd2472e4b996fb9ffa6acb0ebb723207ddfed138cdc
[8] => 980f25b534a69bd6a852d0feaccfc397e6f073f0c7e70e4e5a013c042224f4b1
[9] => 0bb5ca5998329991a95208109dcb0f7807b11522a751b5ec40f3ac4232eca55f
[10] => e8cfb7e8076356ccd7657f1152947f13d542a6c3c4a8fbf004b1c9a47f446d4e
)
Recovered secret: 5dbc894c0e9195b954d4a4b0ff68580af41d42e44d1ddf14cccb8fa65ab596b0
Example 2:
Array
(
[1] => a7c86aae626dffbcd11ab17eecb58bbc2631912680283e196adc249dd9061107
[2] => a90eccf79446a04c80b307beb450373b2357e1805401c0463480801710aba2f6
[4] => 2a67784028c0c98a76bb8bd2472e4b996fb9ffa6acb0ebb723207ddfed138cdc
[7] => 7794b0fa770a4c7d552f9b0be27285f5b6c8e56332c555ae99b37c15fca5f922
[10] => e8cfb7e8076356ccd7657f1152947f13d542a6c3c4a8fbf004b1c9a47f446d4e
)
Recovered secret: 5dbc894c0e9195b954d4a4b0ff68580af41d42e44d1ddf14cccb8fa65ab596b0
Example 3:
Array
(
[1] => a7c86aae626dffbcd11ab17eecb58bbc2631912680283e196adc249dd9061107
[3] => 77d6c92809d08886e2d5e63ff3687005a7c811bcbc4e1502dfdf9ee651edac4d
[9] => 0bb5ca5998329991a95208109dcb0f7807b11522a751b5ec40f3ac4232eca55f
[10] => e8cfb7e8076356ccd7657f1152947f13d542a6c3c4a8fbf004b1c9a47f446d4e
)
Recovered secret: 5dbc894c0e9195b954d4a4b0ff68580af41d42e44d1ddf14cccb8fa65ab596b0
Example 4:
Array
(
[1] => a7c86aae626dffbcd11ab17eecb58bbc2631912680283e196adc249dd9061107
[3] => 77d6c92809d08886e2d5e63ff3687005a7c811bcbc4e1502dfdf9ee651edac4d
[4] => 2a67784028c0c98a76bb8bd2472e4b996fb9ffa6acb0ebb723207ddfed138cdc
[5] => d707f34056cc7475bb9c37454cd1df743765890918cdf3cab46a19d83264a59c
[6] => 93ff5328f9a89a6730b02768a1834113bb028baef448dca549e36fa37228540b
[7] => 7794b0fa770a4c7d552f9b0be27285f5b6c8e56332c555ae99b37c15fca5f922
[9] => 0bb5ca5998329991a95208109dcb0f7807b11522a751b5ec40f3ac4232eca55f
)
Recovered secret: 5dbc894c0e9195b954d4a4b0ff68580af41d42e44d1ddf14cccb8fa65ab596b0
Example 5:
Array
(
[1] => a7c86aae626dffbcd11ab17eecb58bbc2631912680283e196adc249dd9061107
[2] => a90eccf79446a04c80b307beb450373b2357e1805401c0463480801710aba2f6
[4] => 2a67784028c0c98a76bb8bd2472e4b996fb9ffa6acb0ebb723207ddfed138cdc
[5] => d707f34056cc7475bb9c37454cd1df743765890918cdf3cab46a19d83264a59c
[6] => 93ff5328f9a89a6730b02768a1834113bb028baef448dca549e36fa37228540b
[7] => 7794b0fa770a4c7d552f9b0be27285f5b6c8e56332c555ae99b37c15fca5f922
[8] => 980f25b534a69bd6a852d0feaccfc397e6f073f0c7e70e4e5a013c042224f4b1
[9] => 0bb5ca5998329991a95208109dcb0f7807b11522a751b5ec40f3ac4232eca55f
[10] => e8cfb7e8076356ccd7657f1152947f13d542a6c3c4a8fbf004b1c9a47f446d4e
)
Recovered secret: 5dbc894c0e9195b954d4a4b0ff68580af41d42e44d1ddf14cccb8fa65ab596b0<?php
/*
This code is an implementation of a Shamir's Secret Sharing Scheme (SSSS). This scheme allows a
secret to be split into a number of shares. A subset of these shares can be used to recover the
secret, as long as the number of shares used is greater than or equal to a predetermined threshold.
It uses the GMP library to generate random numbers and perform mathematical operations.
The first function, _divmod(), takes three parameters: num, den, and prime. It calculates a number x
such that num * x mod den = prime.
The second function, _gmp_array_product(), takes an array of numbers and multiplies them all
together.
The third function, make_random_shares(), takes four parameters: secret, threshold, shares, and
prime. It creates an array of coefficients and then uses them to create an array of points.
The fourth function, recover_secret(), takes two parameters: points and prime. It first creates two
arrays of numbers, numerators and denominators. It then calculates a number den equal to the
product of all dens. It then calculates the numerator, num, and then calculates the secret by
dividing numerator by denominator, den.
The code begins by setting variables such as the threshold, number of shares, secret, and prime
number. The prime number is used to ensure that the shares are secure and not easily cracked.
Next, the code generates random shares using the make_random_shares() function. This function
initializes an array of coefficients, creates the points array, and returns the points array.
The recover_secret() function is then used to recover the secret from the shares. This function
takes in the points array and a prime number as parameters. It then creates an array of numerators
and denominators, calculates the denominator, and returns the secret.
The code then sets some parameters such as the secret, the threshold, the number of shares, and the
prime. It prints out the secret, the prime, and the number of shares and threshold.
It then generates the shares and prints them out.
Finally, it prints out five examples of the recovery of the secret. For each example, it prints out
a random slice of points and then prints out the recovered secret.
*/
//Returns ($num * $den) mod prime
//Used for modular division
function _divmod($num, $den, $prime) {
$a = $den;
$b = $prime;
$x = gmp_init(0);
$last_x = gmp_init(1);
while($b != 0) {
$quot = gmp_div($a, $b);
[$a, $b] = [$b, gmp_mod($a, $b)];
[$x, $last_x] = [gmp_sub($last_x, gmp_mul($quot, $x)), $x];
}
//Returns the product of all elements in the array
return(gmp_mul($num, $last_x));
}
function _gmp_array_product($array) {
$product = gmp_init(1);
foreach($array as $p) $product = gmp_mul($product, $p);
return($product);
}
//Generates random shares based on a threshold, number of shares, prime, and secret
function make_random_shares($secret, $threshold, $shares, $prime) {
$coefs = [gmp_init($secret)];
for($i = 1; $i < $threshold; $i++)
$coefs[$i] = gmp_random_range(1, $prime - 1);
$points = array();
for($x = 1; $x <= $shares; $x++) {
$accum = gmp_init(0);
foreach(array_reverse($coefs) as $coef) {
$accum = gmp_mul($accum, $x);
$accum = gmp_add($accum, $coef);
$accum = gmp_div_r($accum, $prime);
}
$points[$x] = $accum;
}
return($points);
}
//Recovers a secret from a given array of points
function recover_secret($points, $prime) {
$nums = array();
$dens = array();
$keys = array_keys($points);
foreach($keys as $i => $p_x) {
$others = $keys;
unset($others[$i]);
$nums[$p_x] = _gmp_array_product(array_map(fn($o) => gmp_sub(0, $o), $others));
$dens[$p_x] = _gmp_array_product(array_map(fn($o) => gmp_sub($p_x, $o), $others));
}
$den = _gmp_array_product($dens);
$num = gmp_intval(0);
foreach($points as $p_x => $p_y) {
$divmod = _divmod(gmp_mod(_gmp_array_product([$nums[$p_x], $den, $p_y]), $prime), $dens[$p_x], $prime);
$num = gmp_add($num, $divmod);
}
$divmod = _divmod($num, $den, $prime);
$divmod = gmp_add($divmod, $prime);
$divmod = gmp_mod($divmod, $prime);
return($divmod);
}
//Settings
$threshold = 4; //Number of shares required to recover the secret
$num_shares = 10;
//Display the secret and various settings
$key_length = 32; //bytes
$prime = gmp_nextprime(gmp_pow(256, $key_length));
$secret = random_bytes($key_length);
$prime_hex = bin2hex(gmp_export($prime));
$secret_plaintext = bin2hex($secret);
$secret = gmp_strval(gmp_import($secret));
echo "Secret: {$secret_plaintext}\n";
echo "Number of shares: {$num_shares}, with a threshold of: {$threshold}\n";
echo "\n";
echo "Prime (dec): {$prime}\n";
echo "Prime (hex): {$prime_hex}\n";
echo "\n";
//Generate shares and display them
$points = make_random_shares($secret, $threshold, $num_shares, $prime);
$shares = array_map("gmp_export", $points);
$shares = array_map("bin2hex", $shares);
echo "Generated shares:\n";
print_r($shares);
echo "\n";
//Attempt to recover the secret 5 times
echo "5 examples of the recovery of the secret:\n";
echo "\n";
for($i = 1; $i <= 5; $i++) {
$slice = [];
foreach(array_rand($points, rand($threshold, $num_shares)) as $key)
$slice[$key] = $points[$key];
$recover_secret = recover_secret($slice, $prime);
$recover_secret = bin2hex(gmp_export($recover_secret));
$slice = array_map("gmp_export", $slice);
$slice = array_map("bin2hex", $slice);
echo "Example {$i}:\n";
print_r($slice);
echo "Recovered secret: {$recover_secret}\n";
echo "\n";
}
?><?php
echo <<<END
_______ __ __ __ __ _______ __
| __| |--.---.-.| |_| |_.-----.----.-----.--| | | __|.-----.----.----.-----.| |_.-----.
|__ | | _ || _| _| -__| _| -__| _ | |__ || -__| __| _| -__|| _|__ --|
|_______|__|__|___._||____|____|_____|__| |_____|_____| |_______||_____|____|__| |_____||____|_____|
Shamir's Secret Sharing Scheme v1.0
END;
/*
This script is a command-line tool that uses the Shamir's Secret Sharing Scheme (SSSS) algorithm to
split a given file into a specified number of shares, such that a specified threshold number of
shares can be used to reconstruct the original file. The SSSS algorithm is used to ensure the
security of the file by dividing the secret data into multiple shares, so that no single share
contains enough information to reconstruct the original file.
The script first checks that the PHP version is at least 8.2.0 and defines some constants such as
the format and version of the scheme being used, the encryption algorithm and hash algorithm being
used. Then, it defines various functions to perform various tasks such as creating random shares,
chunking and serializing data, and testing compression algorithms. The script also accepts
command-line arguments for specifying the file to be split, the threshold number of shares required
to reconstruct the original file, the total number of shares to be created, and the output format.
It then uses the make_random_shares function to create the shares by generating random coefficients,
and then using these coefficients to calculate the y-coordinates of the shares.
Finally, it generates a random encryption key and prime number, encrypts the secret data using the
encryption key, and then uses the make_random_shares function to create shares of the encrypted
data. It then uses the gmp_chunk and gmp_serialize functions to chunk and serialize the shares, and
the test_compression_algos function to determine the best compression algorithm to use. The
resulting shares and information needed to reconstruct the original file can be output in either
the "ssss" format or the "json" format.
*/
define("FORMAT", "Shattered Secrets"); //header ID-tag definition for the ssss-file format
define("VERSION", 1); // ssss-file format version 1.0
define("CIPHER_ALGO", "aes-256-cbc");
define("HASH_ALGO", "sha256");
if(version_compare(PHP_VERSION, "8.2.0") < 0) die("Please upgrade to minumum PHP v8.2\n");
function make_random_shares($secret, $threshold, $shares, $prime) {
gmp_random_seed(gmp_import(random_bytes(64)));
$coefs = [gmp_init($secret)];
for($i = 1; $i < $threshold; $i++)
$coefs[$i] = gmp_random_range(1, $prime - 1);
$points = array();
for($x = 1; $x <= $shares; $x++) {
$accum = gmp_init(0);
foreach(array_reverse($coefs) as $coef) {
$accum = gmp_mul($accum, $x);
$accum = gmp_add($accum, $coef);
$accum = gmp_div_r($accum, $prime);
}
$points[$x] = $accum;
}
return($points);
}
function gmp_chunk($binary) {
$gmp_bin = gmp_export(strlen($binary));
$length = strlen($gmp_bin) - 1;
if($length > 255) return(false);
return(chr($length) . $gmp_bin . $binary);
}
function gmp_serialize($array) {
$array = array_map("gmp_chunk", $array);
return(implode($array));
}
function plaintext($data) { return($data); }
$compression_algos = [
"plaintext" => "plaintext",
"zlib" => "gzdeflate",
"bzip2" => "bzcompress",
"brotli" => "brotli_compress"
];
function test_compression_algos($compression_algos, $data) {
$results = [];
foreach($compression_algos as $algo => $function)
if(function_exists($function))
$results[$algo] = strlen($function($data));
asort($results);
return(array_key_first($results));
}
if($argc <= 3) die(
<<<EOT
Usage: php {$argv[0]} <filename> <threshold> <shares> [output]
filename Secret file to be split up
threshold Mimumum of shares from which the file can be reconstructed
shares Number of total shares
output <ssss> or <json>, default: ssss
Example: php {$argv[0]} alice_in_wonderland.txt 3 8
EOT);
$filename = strval($argv[1]);
$threshold = intval($argv[2]);
$num_shares = intval($argv[3]);
$output_format = strval($argv[4] ?? "ssss");
if(!file_exists($filename)) die("File not found\n");
if($threshold <= 0) die("Threshold must be bigger than zero\n");
if($num_shares <= 0 || $num_shares < $threshold) die("Number of shares must be bigger than zero and the threshold\n");
if(!in_array($output_format, ["ssss", "json"])) die("Unknown output format\n");
// SETTINGS
$key_length = openssl_cipher_key_length(CIPHER_ALGO); // from PHP 8.2
//$key_length = 32; // hardcoded alternative for aes-256-cbc
$secret = random_bytes($key_length);
$prime = gmp_nextprime(gmp_pow(256, $key_length));
// AES
$data = file_get_contents($filename);
$hash_hmac = hash_hmac(HASH_ALGO, $data, $secret, true);
$compression_algo = test_compression_algos($compression_algos, $data);
$data = $compression_algos[$compression_algo]($data);
$ciphertext = @openssl_encrypt($data, CIPHER_ALGO, $secret, OPENSSL_RAW_DATA);
// SSSS
$ssss_secret = gmp_strval(gmp_import($secret));
$points = make_random_shares($ssss_secret, $threshold, $num_shares, $prime);
// JSON output
foreach($points as $index => $secret_share) {
$filename = "Nothing";
if($output_format == "ssss") {
$filename = bin2hex($hash_hmac) . " - {$index}.ssss";
$share_pack = [
"format" => FORMAT,
"version" => gmp_export(VERSION),
"index" => gmp_export($index),
"secret_share" => gmp_export($secret_share),
"prime" => gmp_export($prime),
"threshold" => gmp_export($threshold),
"shares" => gmp_export($num_shares),
"compression_algo" => $compression_algo,
"cipher_algo" => CIPHER_ALGO,
"ciphertext" => $ciphertext,
"hash_algo" => HASH_ALGO,
"hash_hmac" => $hash_hmac
];
file_put_contents($filename, gmp_serialize($share_pack));
}
if($output_format == "json") {
$filename = bin2hex($hash_hmac) . " - {$index}.json";
$share_json = [
"format" => FORMAT,
"version" => VERSION,
"index" => $index,
"secret_share" => base64_encode(gmp_export($secret_share)),
"prime" => base64_encode(gmp_export($prime)),
"threshold" => $threshold,
"shares" => $num_shares,
"compression_algo" => $compression_algo,
"cipher_algo" => CIPHER_ALGO,
"ciphertext" => base64_encode($ciphertext),
"hash_algo" => HASH_ALGO,
"hash_hmac" => base64_encode($hash_hmac)
];
$share_json = json_encode($share_json, JSON_PRETTY_PRINT);
file_put_contents($filename, $share_json);
}
echo "{$filename} is written.\n";
}
?><?php
/*
_______ __ __ __ __ _______ __
| __| |--.---.-.| |_| |_.-----.----.-----.--| | | __|.-----.----.----.-----.| |_.-----.
|__ | | _ || _| _| -__| _| -__| _ | |__ || -__| __| _| -__|| _|__ --|
|_______|__|__|___._||____|____|_____|__| |_____|_____| |_______||_____|____|__| |_____||____|_____|
Shamir's Secret Sharing Scheme v1.0
This code defines a PHP script that implements the Shamir's Secret Sharing Scheme (SSSS) algorithm,
which is a method for dividing a secret into multiple shares that can be distributed among
different people. The script uses the GMP (GNU Multiple Precision) library for arithmetic
operations.
The script starts by defining a constant "FORMAT" which is used to check the format of the input
data. It also checks that the version of PHP being used is at least 8.2.0, and exits if it is not.
The script defines several functions:
_divmod(): which takes three arguments (num, den, prime) and returns the result of the division of
num by den modulo prime.
_gmp_array_product(): which takes an array as an argument and returns the product of all elements in
the array using GMP library.
recover_secret(): which takes two arguments (points, prime) and returns the original secret.
gmp_unchunk(): which takes a data as an argument and returns an array that contains the binary and
the remainder of the data.
gmp_unserialize(): which takes a data as an argument and returns an array of the data using
gmp_unchunk() function.
check_ssss_format(): which takes a data as an argument and returns false if the input data is not in
the correct format, otherwise it returns true.
check_json_format(): which takes data as an argument and returns false if the input data is not in
the correct format, otherwise it returns true.
correlate_shares(): which takes an array of shares as an argument and checks if the shares are
compatible with each other.
plaintext(): which returns the input data without modification.
compression_algos which is an array containing different compression algorithms.
The main function starts by checking if the script has been called with the correct number of
arguments, if not it exits and displays an error message with the correct usage. It then assigns
the first argument as the hash and the second argument as the directory. The script then scans the
directory for files containing the hash and loads the shares from the files found and checks the
file format, if the files format is not correct, it exits with an error message. If the shares are
compatible, it then attempts to reconstruct the secret from the shares. If the secret is
successfully reconstructed, it decompresses the secret and verifies the integrity of the secret
using a hash. If the secret is not verified, it exits with an error message. Finally, it saves the
reconstructed secret to a file.
*/
define("FORMAT", "Shattered Secrets"); //header ID-tag definition for the ssss-file format
if(version_compare(PHP_VERSION, "8.2.0") < 0) die("Please upgrade to minumum PHP v8.2\n");
function _divmod($num, $den, $prime) {
$a = $den;
$b = $prime;
$x = gmp_init(0);
$last_x = gmp_init(1);
while($b != 0) {
$quot = gmp_div($a, $b);
[$a, $b] = [$b, gmp_mod($a, $b)];
[$x, $last_x] = [gmp_sub($last_x, gmp_mul($quot, $x)), $x];
}
return(gmp_mul($num, $last_x));
}
function _gmp_array_product($array) {
$product = gmp_init(1);
foreach($array as $p) $product = gmp_mul($product, $p);
return($product);
}
function recover_secret($points, $prime) {
$nums = array();
$dens = array();
$keys = array_keys($points);
foreach($keys as $i => $p_x) {
$others = $keys;
unset($others[$i]);
$nums[$p_x] = _gmp_array_product(array_map(fn($o) => gmp_sub(0, $o), $others));
$dens[$p_x] = _gmp_array_product(array_map(fn($o) => gmp_sub($p_x, $o), $others));
}
$den = _gmp_array_product($dens);
$num = gmp_intval(0);
foreach($points as $p_x => $p_y) {
$divmod = _divmod(gmp_mod(_gmp_array_product([$nums[$p_x], $den, $p_y]), $prime), $dens[$p_x], $prime);
$num = gmp_add($num, $divmod);
}
$divmod = _divmod($num, $den, $prime);
$divmod = gmp_add($divmod, $prime);
$divmod = gmp_mod($divmod, $prime);
return($divmod);
}
function gmp_unchunk($data) {
if(strlen($data) == 0) return(false);
$gmp_length = ord($data[0]);
if(strlen($data) < $gmp_length + 1) return(false);
$gmp_bin = substr($data, 1, $gmp_length + 1);
$binary_length = gmp_intval(gmp_import($gmp_bin));
if(strlen($data) < $gmp_length + 2 + $binary_length) return(false);
$binary = substr($data, $gmp_length + 2, $binary_length);
$remainder = substr($data, $gmp_length + 2 + $binary_length);
return([$binary, $remainder]);
}
function gmp_unserialize($data) {
$array = [];
while(strlen($data) > 0) {
[$array[], $data] = gmp_unchunk($data);
if(end($array) === false) return(false);
}
return($array);
}
function check_ssss_format($data) {
if($data[0] != FORMAT) return(false);
$version = gmp_import($data[1]);
if($version == 1) {
//scheme version 1
$labels = ["format", "version", "index", "secret_share", "prime", "threshold", "shares", "compression_algo", "cipher_algo", "ciphertext", "hash_algo", "hash_hmac"];
$gmp_decode_labels = ["version", "index", "secret_share", "prime", "threshold", "shares"];
$gmp_intval_labels = ["version", "index", "threshold", "shares"];
if(count($data) != 12) return(false);
$data = array_combine($labels, $data);
if($data["format"] != FORMAT) return(false);
foreach($gmp_decode_labels as $label) $data[$label] = gmp_import($data[$label]);
foreach($gmp_intval_labels as $label) $data[$label] = gmp_intval($data[$label]);
if($data["version"] != 1) return(false);
if($data["index"] > $data["shares"]) return(false);
if($data["shares"] < $data["threshold"]) return(false);
if($data["secret_share"] > $data["prime"]) return(false);
return($data);
}
return(false);
}
function check_json_format($data) {
if(!isset($data["format"])) return(false);
if(!isset($data["version"])) return(false);
if($data["format"] != FORMAT) return(false);
$version = $data["version"];
if($version == 1) {
//scheme version 1
if($data["version"] != 1) return(false);
$labels = ["format", "version", "index", "secret_share", "prime", "threshold", "shares", "compression_algo", "cipher_algo", "ciphertext", "hash_algo", "hash_hmac"];
$gmp_decode_labels = ["secret_share", "prime"];
$base64_decode_labels = ["secret_share", "prime", "ciphertext", "hash_hmac"];
if(array_keys($data) != $labels) return(false);
foreach($base64_decode_labels as $label) $data[$label] = base64_decode($data[$label]);
foreach($gmp_decode_labels as $label) $data[$label] = gmp_import($data[$label]);
if($data["index"] > $data["shares"]) return(false);
if($data["shares"] < $data["threshold"]) return(false);
if($data["secret_share"] > $data["prime"]) return(false);
return($data);
}
return(false);
}
function correlate_shares($shares) {
$labels = ["format", "version", "prime", "threshold", "shares", "compression_algo", "cipher_algo", "ciphertext", "hash_algo", "hash_hmac"];
foreach($labels as $label)
if(count(array_unique(array_column($shares, $label))) != 1) return(false);
if(count(array_unique(array_column($shares, "index"))) != count($shares)) return(false);
$share = reset($shares);
if($share["threshold"] > count($shares)) return(false);
return($share);
}
function plaintext($data) { return($data); }
$compression_algos = [
"plaintext" => "plaintext",
"zlib" => "gzinflate",
"bzip2" => "bzdecompress",
"brotli" => "brotli_uncompress"
];
// --- MAIN
if($argc <= 1) die(
<<<EOT
Usage: php {$argv[0]} <file hash> [folder]
file hash Identifying hash in hexidecimal of the shares
folder Location of the shares, default: current folder
Example: php {$argv[0]} d8c7b74c0588a1c45e0c6deb43048937bf6974f769254355a40e342e5286a6ae
EOT);
$hash = $argv[1];
$directory = $argv[2] ?? ".";
// find files
$files = scandir($directory);
$files = array_filter($files, fn($filename) => str_contains($filename, $hash));
if(count($files) == 0) die("No matching files found\n");
//load shares and check file format
$shares = [];
foreach($files as $file) {
$file_binary = file_get_contents($file);
$ext = substr($file, -5);
if($ext == ".ssss") {
if(!$share = gmp_unserialize($file_binary)) die("File {$file} chunk corruption\n");
if(!$share = check_ssss_format($share)) die("File {$file} format corruption\n");
$shares[$share["index"]] = $share;
}
if($ext == ".json") {
if(!$share = json_decode($file_binary, true)) die("File {$file} json corruption\n");
if(!$share = check_json_format($share)) die("File {$file} format corruption\n");
$shares[$share["index"]] = $share;
}
}
// check if the shares match up
if(!$share = correlate_shares($shares)) die("Shares mismatch or not threshold too low\n");
// recover secret key from shares
$points = array_column($shares, "secret_share", "index");
foreach(["prime", "compression_algo", "cipher_algo", "ciphertext", "hash_algo", "hash_hmac"] as $label)
$$label = $share[$label];
$secret = recover_secret($points, $prime);
$secret = gmp_export($secret);
// -> check key length after PHP 8.2
// decrypt and decompress
if(!$plaintext = @openssl_decrypt($ciphertext, $cipher_algo, $secret, OPENSSL_RAW_DATA)) die("Decryption failure\n");
if(!function_exists($compression_algos[$compression_algo])) die("Compression {$compression_algo} not supported\n");
$plaintext = $compression_algos[$compression_algo]($plaintext);
if($hash_hmac != hash_hmac($hash_algo, $plaintext, $secret, true)) die("Data integerty corrupted\n");
// output and exit
echo $plaintext;
?>http://point-at-infinity.org/ssss/
https://en.wikipedia.org/wiki/Shamir%27s_secret_sharing
https://medium.com/@keylesstech/a-beginners-guide-to-shamir-s-secret-sharing-e864efbf3648