Securely Sharing Secrets Like Passwords

1::AUdGaXBfJSuesQ==:AYXQQ1vlZS9ABxiYi+rJLuMj2uoOuXzP++v3+vA37DEO::979834518720

==> ==>  you may have to scroll  ==> ==>

{
  "part number"   : 1,
  "part of secret": "AfBJw7gpZcxCdQ==",
  "part of hash"  : "AVUZQjFENeWOEypU6MGjpXLUpcwsu/mmHZH5dER6nRmG",
  "identifier"    : "723966166016"
}

==> ==>  you may have to scroll  ==> ==>

Below are the shares for your secret or password. Beneath that is a suggestion for how to share them with people so they know what they have received - and have a chance of remembering it in ten years' time.

Include index   Include hash   Include identifier

---

---

The following is an example of how you might share these shares with people - modify or abbreviate as needed.

This is a so-called share of a secret string, for example a password. DYNAMIC TEXT: description Please keep it in a safe place, such as your password safe. You have been given this share so that, in an emergency, you - along with other people who have been given other shares - can reconstruct the secret or password and do whatever is necessary. This is one of DYNAMIC TEXT: number shares created on DYNAMIC TEXT: date. To reconstruct the secret or password, DYNAMIC TEXT: number different shares are needed. For the actual reconstruction, this text is not needed - you only need the following data:

[Replace this paragraph with the share from above you want to hand over.]

This share was created using the share tool at https://gdiet.github.io/secret-sharing/. On the same site, you will find the tool for recovering the password or other secret from a number of shares. For sharing and recovering, Shamir's secret sharing algorithm with an optional verification extension is used.

Technical description: The share above can consist of one to four parts concatenated like this:
[part number]::[part of secret]:[part of hash]::[identifier]

Actually, the share above contains the following field(s):
[part number]::[part of secret]:[part of hash]::[identifier]

The "part of secret" is a Base64 encoded byte array. The first byte of the array is the "x" value, all subsequent bytes are "y" values. To reconstruct the first byte of the original secret, you combine the "x" value of each "part of secret" share you have with its second byte as "y" value. This gives you a number of "x/y" pairs. Then you do a Lagrangian interpolation to calculate the "y" value for "x = 0". This "y" value is the first byte of the original secret. In the same way, you combine the "x" values with the third bytes to calculate the second byte of the secret, and so on. Ignore any trailing zeros in the reconstructed secret - they have been added as a security measure and are not part of the original secret. Note that the Lagrangian interpolation must be computed in the "GF(256)" Galois field with "x^8 + x^4 + x^3 + x^1 + x^0" (or 0x11b) as the reducing polynomial. By the way: This is the same field and polynomial used for AES encryption calculations.

From the "part of hash", you can reconstruct the SHA-256 hash of the original secret (without any zero padding) in the same way. This can be used to verify that the reconstructed secret is indeed the same as the original. The "identifier" field can be used to check whether the shares can be combined at all: if the identifiers are different, the shares most likely belong to different instances or even different original secrets, and combining them will not yield meaningful results. The "part number" field is the same as the "x" value of the shares. It is there to make it easier for humans to check that the shares are different - it is not evaluated during the reconstruction of the secrets. The approach used to share the secret or password is called "Shamir's Secret Sharing". Strings are converted to byte arrays (and vice versa) using the UTF-8 encoding. Calculations are done in lower-endian order.

/* Example Java code for reconstructing a single byte of the secret. */

/** Lagrange interpolate at x = 0 the polynomial defined by the points. */
int lagrange_interpolate(XY[] points) {
  int y = 0;
  for (int i = 0; i < points.length; i++) {
    int t = 1;
    for (int j = 0; j < points.length; j++) {
      if (i != j) {
        t = gf256_mul(t,
          gf256_div(points[j].x, gf256_sub(points[i].x, points[j].x))
        );
      }
    }
    y = gf256_add(y, gf256_mul(t, points[i].y));
  }
  return y;
}

/** The AES GF(256) addition is the 'xor' operation. */
int gf256_add(int a, int b) { return a ^ b; }

/** The AES GF(256) subtraction is the same 'xor' operation as the addition. */
int gf256_sub(int a, int b) { return add(a, b); }

/** The AES GF(256) multiplication. 0x11b represents the reducing polynomial. */
int gf256_mul(int a, int b) { return calculateMultiplication(a, b, 0); }
int calculateMultiplication(int a, int b, int acc) {
  if (a == 0 || b == 0) return acc;
  else return calculateMultiplication(
    ((a & 0x80) != 0) ? (a << 1) ^ 0x11b : a << 1,
    b >> 1,
    ((b & 0x01) != 0) ? add(a, acc) : acc
  );
}

/** Lookup table for the AES GF(256) multiplicative inverse. */
int[] inverseTable = new int[256];
for (int n = 1; n <= 255; n++) {
  for (int k = 1; k <= 255; k++) {
    if (mul(k, n) == 1) { inverseTable[n] = k; break; }
  }
}

/** The AES GF(256) division: Multiplication with the inverse `b^-1`. */
int div(int a, int b) {
  return mul(a, inverseTable[b]);
}