RSA Threshold Signatures

In 1979, Adi Shamir (who represents the “S” in RSA) created a secret sharing algorithm that allows a secret to be split into parts, and only when a number of them are added together, we will be able to recover the secret (paper):

In this article, I will outline how Lagrange interpretation constants — and named after Joseph-Louis Lagrange — are used to recreate the secret, and will use a simple example. These Lagrange polynomial values are used for polynomial interpolation, and where we can derive a polynomial from a given number of points on the curve.

To explain the basics, let’s say that there are six generals who have control over firing a missile, and there are three bases, with two generals on each base. Unfortunately, we are worried that one of the generals might make a rash decision, so we agree that the generals will not get the secret password to fire the missile. We are also worried that a base could be taken over by a malicious force, so we agree that no two generals will be able to gain the password. So to overcome these problems we decide that a least three generals must agree together to generate the correct password to fire the missile.