Last updated: 2024-August-02

Shamir's Keystore

Abstract

This JCA provider presently implements Shamir's Secret Sharing using Newton Polynomials. Building on this, a KeyStore Engine as defined by the Java Cryptographic Architecture is provided. Such a keystore instance might be unlocked - apart from the master password - by certain subsets of previously computed secret shares. In order to be able to reconstruct the master password a specific number of secret shares equal to (or above) a given threshold must be combined. Shamirs scheme is information-theoretically secure. This means that an attacker does not get any additional information about the original master password with fewer shares as defined by the given threshold. In this way, it is possible to enforce e.g. the four-eye-principle. The provided keystore implementation is PKCS12 compliant and internally relies on the implementation provided by the Java platform.

[ToC]

1. Build

Clone the project (or download and unpack the zip):

Maven and a JDK 11+ is required for the build of the multi-module project:

Above command will compile the sources, run the tests and install the provider into the local Maven repo.

Note that the included demo app makes use of the pkix sub-module from the Bouncy Castle crypto library for programmatically generating self-signed X.509 certificates which is something that cannot be easily done with the JDK alone. The library itself depends on the Scala-Library (since the core module containing the actual algorithm is presently written in Scala) and on Jakarta JSON Processing. The latter is merely the specification of an API and hence you additionally need an implementation for that at runtime, e.g. Eclipse Parsson, if you want to use the JCA provider in your applications. See section 6.2 Maven Coordinates for further details.

The project uses JUnit 5 together with AssertJ or rather ScalaTest for unit testing.

[ToC]

2. Source Control

The source code is hosted in GitHub: https://github.com/chr78rm/shamirs-keystore.

[ToC]

3. The Algorithm

Consider the polynomial

P_k-1(x) = a_k-1x^k-1 + ... + a₂x² + a₁x + a₀

of degree k-1 given in the canonical form. Recall that you need k supporting points to recover a polynomial of degree k-1. Shamir's (k,n) threshold scheme is building upon this property. A trusted authority randomly selects a polynomial P_k-1 and computes n supporting points whereby n >= k applies. The to be shared secret s is encoded as a₀. The n supporting points are distributed among the participants. To compute the original secret s the participants must combine k of the supporting points. In order to avoid that an adversary gains any knowledge about the secret by merging less than k supporting points all computations will by implemented by using finite field arithmetic. That means we choose a finite field 𝔽_p whereby p is prime and a₀ < p applies.

The simplest procedure for reconstructing a polynomial P of degree k-1 with given k supporting points (x₀,y₀),...,(x_k-1,y_k-1) is by devising a system of k linear equations. A parabola, for instance, is defined by three supporting points (x₀,y₀),(x₁,y₁),(x₂,y₂). The coefficients a₀,a₁,a₂ can be computed by solving the system of linear equations below:

y₀ = a₂x₀² + a₁x₀ + a₀
y₁ = a₂x₁² + a₁x₁ + a₀
y₂ = a₂x₂² + a₁x₂ + a₀

There are, however, more efficient algorithms. This distribution uses the Newton interpolation method to recover the secret s. A Newton polynomial of degree k-1 is given by

P_k-1(x) = 𝝨 _i=0 ^k-1 c_iN_i(x)

with Newton coefficients c₀,c₁,...,c_k-1 and the Newton basis polynomials N₀ = 1 and N_i = 𝞟 _j=0 ^i-1 (x - x_j).

This gives

P_k-1(x) = c₀ + c₁(x - x₀) + c₂(x - x₀)(x - x₁) + ⋯ + c_k-1(x - x₀) ⋯ (x - x_k-2)

By applying x ← x₀,x ← x₁,x ← x₂,... it follows

P(x₀) = c₀
P(x₁) = c₀ + c₁(x₁ - x₀)
P(x₂) = c₀ + c₁(x₂ - x₀) + c₂(x₂ - x₀)(x₂ - x₁)
P(x₃) = c₀ + c₁(x₃ - x₀) + c₂(x₃ - x₀)(x₃ - x₁) + c₃(x₃ - x₀)(x₃ - x₁)(x₃ - x₂)
⋮⋮

Since we are interested in recovering the Newton polynomial by using the supporting points we rearrange the equations above:

c₀ = y₀
c₁ = (y₁ - c₀)/(x₁ - x₀)
c₂ = (y₂ - c₀ - c₁(x₂ - x₀))/(x₂ - x₀)(x₂ - x₁)
c₃ = (y₃ - c₀ - c₁(x₃ - x₀) - c₂(x₃ - x₀)(x₃ - x₁))/(x₃ - x₀)(x₃ - x₁)(x₃ - x₂)
⋮⋮

Now we can clearly see a recurring pattern. Thus, the Newton coefficients can be computed by a recursive procedure and by memoizing the already calculated coefficients (dynamic programming), see NewtonInterpolation.scala for details.

We need to evaluate the interpolated polynom at least at one point, namely at P(0) = a₀ to recover the original secret. An efficient way of doing this is by applying Horner's scheme. The Newton polynomial P of degree k-1 can be rewritten as

P_k-1(x) = c₀ + (x - x₀)[c₁ + (x - x₁)[c₂ + ⋯ + c_k-1(x - x_k-2)] ⋯ ]

so that P(x) can be calculated recursively:

b₀ = c₀ + (x - x₀)b₁
b₁ = c₁ + (x - x₁)b₂
b₂ = c₂ + (x - x₂)b₃
⋮⋮
b_k-1 = c_k-1

where P(x) = b₀ .

[ToC]

4. UML Diagrams

4.1 Component Diagrams

4.2 Class Diagram

[ToC]

5. Reports

The two sub modules shamirs-keystore - containing the actual JCA provider - and shamirs-demo are both using JUnit5 for their unit testing. The Maven Surefire Plugin up to version 3.2.5 is confused about JUnit5's nested tests and hence doesn't accurately produce the numbers for the reports. The two linked reports below have been generated by a custom JUnit5 TestExecutionListener during the last build.

JUnit5 reports

Artifact	Report
shamirs-keystore	summary.txt
shamirs-demo	summary.txt

The sub module shamirs-secret-sharing - containing the actual algorithm - is written in Scala and uses ScalaTest for its unit testing. Again a custom Reporter is used to collect the events occurring throughout the execution of the tests. The linked report below has been generated during the last build.

ScalaTest reports

Artifact	Report
shamirs-secret-sharing	summary.txt

[ToC]

6. Download

6.1 Demo App

The demo app has been packaged by the Maven Shade Plugin. The subsequently provided downloads contain the demo app and both the core module with the algorithm and the actual JCA provider.

shamirs-demo

Artifact	Archive	Build Time	sha512 checksum
shamirs-demo-1.0.0-beta	shamirs-demo-1.0.0-beta.zip	2020-05-20 13:50:27.364 +0200	shamirs-demo-1.0.0-beta.zip.sha512
shamirs-demo-1.0.0-rc1	shamirs-demo-1.0.0-rc1.zip	2020-12-18 15:43:09.754 +0100	shamirs-demo-1.0.0-rc1.zip.sha512
shamirs-demo-1.0.0	shamirs-demo-1.0.0.zip	2021-01-06 14:57:47.925 +0100	shamirs-demo-1.0.0.zip.sha512
shamirs-demo-1.1.0	shamirs-demo-1.1.0.zip	2021-05-26 17:20:08.866 +0200	shamirs-demo-1.1.0.zip.sha512
shamirs-demo-1.2.0	shamirs-demo-1.2.0.zip	2022-04-22 14:57:24.886 +0200	shamirs-demo-1.2.0.zip.sha512
shamirs-demo-1.3.0	shamirs-demo-1.3.0.zip	2024-03-12 13:41:47.720 +0100	shamirs-demo-1.3.0.zip.sha512
shamirs-demo-1.3.1	shamirs-demo-1.3.1.zip	2024-06-19 16:36:40.012 +0200	shamirs-demo-1.3.1.zip.sha512
shamirs-demo-1.3.2	shamirs-demo-1.3.2.zip	2024-07-31 15:02:49.280 +0200	shamirs-demo-1.3.2.zip.sha512

Note that the demo app includes binaries from external open source projects, namely the Scala-Library, the Jakarta JSON-Processing implementation Eclipse Parsson and the pkix sub-module from Bouncy Castle. Section 7.1 Demo App explains how to use the demo app.

6.2 Maven Coordinates

The KeyStore engine together with the relevant artifacts had been deployed to Maven Central and can be used within your applications by referencing the subsequent Maven coordinates:

You will additionally need an implementation for the Jakarta JSON Processing API at runtime, e.g.

Depending on your deployment the latter runtime dependency might not be necessary, e.g. if you are using a Jakarta EE application server. Starting with version 1.3.0 the library uses the new jakarta.json namespace instead of the legacy javax.json and should therefore be compatible with Jakarta EE 9 upwards. An alternative to Eclipse Parsson is Joy but Eclipse Parsson seems to be more actively maintained and it is the reference implementation.

Section 7.2 Keystore Engine explains how to use the provider within your applications.

6.3 Project Dependencies

These are the third-party dependencies of the latest version:

Dependencies

GroupId	ArtifactId	Version	Scope	License
de.christofreichardt	tracelogger	1.10.0	compile	Apache License, Version 2.0
org.scala-lang	scala3-library_3	3.3.3	compile	Apache License, Version 2.0
org.scala-lang	scala-library	2.13.12	compile	Apache License, Version 2.0
jakarta.json	jakarta.json-api	2.1.3	compile	GNU General Public License Version 2 with Classpath Exception, Eclipse Public License 2.0
org.eclipse.parsson	jakarta.json	1.1.5	provided	GNU General Public License Version 2 with Classpath Exception, Eclipse Public License 2.0

The demo app has an additional dependency on Bouncy Castle's pkix sub-module:

Dependencies

GroupId	ArtifactId	Version	Scope	License
org.bouncycastle	bcpkix-jdk18on	1.78.1	compile	MIT License

[ToC]

7. User Manual

7.1 Demo App

Download the demo app and unzip the archive into a directory of your choice. A JDK 11+ is needed for the execution of the app. I am using the Git Bash for this manual but the default command line interpreter of Windows (cmd) works as well. Of course you can use the GNU Bash on Linux systems too. I have tested the distribution with the Git Bash (2.45.2) on Windows 11, with Windows Cmd on Windows 11 and with the GNU Bash on Ubuntu 24.04.6 LTS (Noble Numbat) by randomly using a JDK 11, JDK 17, JDK 21 or JDK 22. I'm using the latest Azul Zulu Builds of OpenJDK for the LTS releases.

After unzipping the distribution exhibits the following structure:

Starting with JDK 22, Java uses an internal JLine instance as the default Console implementation to improve the user experience of programs using the Console API, see JLine As The Default Console Provider. Unfortunately, this change presently seems to break the bulk read operations when using the Reader associated with the Console, see Console#reader() and Reader#read(java.nio.CharBuffer). Furthermore, I have observed a variety of slightly disparate (mis)behaviors across different platforms and JDK versions when using the internal JLine instance in conjunction with the single character operation Reader#read(). Therefore the included launch scripts (see table below) restore the older behavior by default. When using a JDK 22+, you can experiment with the internal JLine instance by passing the argument --jline to the launch scripts. Then you would additionally need --no-bulk and perhaps --echo.

Refer to the table below for the selection of a suitable launch script depending on the environment:

Launch scripts

Git Bash on Windows	Windows Cmd	Linux Bash
run-shamirs-demo.sh [option]...	run-shamirs-demo.bat [option]...	run-shamirs-demo.sh [option]...
winpty-shamirs-demo.sh [option]...

whereby option is one of --jline, --echo or --no-bulk. Older versions of the Git Bash might require winpty-shamirs-demo.sh otherwise there would be no console without using the internal JLine instance.

The string 2024-07-31 left from the arrow denotes the current date and workspace. You automatically get a new one on every day you are using the app. The provided commands are invoked by their given shortcuts. Since this newly created workspace is empty we begin with splitting a password:

The app will make a password proposal (seen within the square brackets). Every user provided input will be matched against the regular expressions given in the round brackets. In our example we instructed to generate 12 shares whereas 4 of them are needed to recover the original password. The shares are grouped within a partition named demo. The 12 shares were divided into 7 slices. The first slice had been given 4 shares. The next two slices had both received 2 shares and the remaining slices had been in each case given 1 share. The found solution can be optionally certified. The preset is no certification at all. A certification by Slices means that all slice combinations with a sharepoint count less than the threshold will be falsified and vice versa all slice combinations with a sharepoint count equal to or above the threshold will be verified. The certification method All means that regardless of the chosen slices all combinations of shares below the threshold will be falsified and all combination of shares that equals the threshold will be verified. These are potentially very expensive operations depending on the number of combinations that have to be considered. You can consult WolframAlpha for the computation of the binomial coefficients, e.g. 12 choose 4 gives 495 as expected. A negative outcome would raise an AssertionError.

(By pure chance a sharepoint combination below the threshold might result in the same y-intercept as the actual solution, that should be almost impossible if you are using long enough passwords which result in correspondingly big-sized finite fields).

Now, open another console and review the content of the your workspace directory (workspace/yyyy-MM-dd):

The file demo.json contains all of the generated shares, demo-0.json four of them, demo-1.json two and so on. The idea is that we have seven participants in our example. Each of them will be given one slice. This means the participant owning the slice demo-0.json is able to recover the password by herself whereas the owner of demo-1.json must team up with the owner of demo-2.json or with two of the owners of the remaining slices and so on. Now switch back to the demo app and invoke (li)st workspace:

We have already seen that. Now lets recover the original password by combining the slices demo-1.json, demo-3.json and demo-6.json:

As expected. Merging works, inter alia, by providing a list of Paths to the different slices and then applying Newtons Interpolation. That means the slices need not necessarily be located together in one directory as in our demo. In fact they could be distributed over the whole filesystem and could be located even on remote devices. Think of plugged-in USB memory sticks or network filesystems. Future versions might interpret the Paths as URIs and could fetch the slices via the internet if required.

Now, let's create a keystore:

We used four of the slices containing a single share to produce the credentials for the keystore. The demo app switched to a submenu regarding keystore functionality. At present the keystore is empty. A Java PKCS12 keystore can contain three different types of entries: Private Key, Secret Key and Certificate entries. Private and Secret Keys need protection whereas certificates need not since latter are public. Hence we will create a Private Key. A Private Key is always accompanied with a certificate that attests the associated Public Key. From the start these certificates are self-signed but could be the result from a PKCS10 certificate request too.

We specified Elliptic Curve (EC) as KeyPairGenerator algorithm and a validity of 100 days for the accompanying self-signed certificate. The remaining parameter constitute the so called Distinguished Name.

Now, list the entries so far:

Go back to main menu:

Now, list the workspace again:

Again, merge some of the slices to recover the password of the keystore:

Switch to a separate console since we want to investigate the keystore with keytool. Note that your own workspace is probably different.

Note that we used the recovered password in combination with keytool. This will be the end of our little tour. There are other options to consider and there are some rough edges as well. For example ChaCha20 secret keys don't work since the underlying keystore implementation of the JDK doesn't recognize them.

[ToC]

7.2 Keystore Engine

See section 6.2 Maven Coordinates for the version of the present distribution. Subsequently, I give a simple example how to use the keystore engine within your application. First, you need to install the provider:

On my system I'm getting the following output:

As can be seen the recently installed provider is the least significant one. The next statement requests the desired keystore engine:

In order to make it simple I'm building upon from the previous section 7.1 Demo App by assuming the over there generated shares and keystore within a subdirectory test-workspace.

Now we have everything together to load the keystore:

For further examples I am referring to the source code of the demo app.

[ToC]

8. API Documentation

APIs

Module	API Documentation
shamirs-secret-sharing	shamirs-secret-sharing 1.3.0 API
shamirs-keystore	shamirs-keystore 1.3.0 API

[ToC]

9. JSON Schema

9.1 Definitions

Partition

Name	Type	Comment
PartitionId	string	An Universally Unique Identifier
Prime	number	Interpreted as BigInteger
Threshold	number	Interpreted as 32-Bit Integer
SharePoints	array of SharePoint

SharePoint

Name	Type	Comment
x	number	Interpreted as BigInteger
y	number	Interpreted as BigInteger

9.2 Example

[ToC]