This program implements a basic version of Adi Shamir's secret-sharing algorithm. You tell the encryption program what your secret message is and how many keys to generate. The program will then generate those keys, which can be handed out to multiple people. These keys can be used to decrypt your secret message; however, the decryption algorithm requires 2 keys to work, so that no single person can get the secret on their own. There must be two people willing to enter their keys.
Obviously, if you have a really REALLY important secret then you should NOT use this dinky little program to store it.
This program requires Python 3.
Run python shamir.py from the command line and follow the prompts.
Adi Shamir's elegant solution to the secret-sharing problem is based on the fact that a given polynomial of degree n is defined by at least n+1 unique points, but that the polynomial itself consists of an infinite number of points. The secret and its corresponding keys are represented by points in 2D space, with n+1 keys defining a polynomial of degree n on which the secret point lies. With only n keys, it's possible to create an infinite number of polynomials of degree n containing those points, making it impossible to determine which polynomial the secret point actually lies on. However, it's trivial to generate more than n+1 keys, since there are infinite points on the polynomial to choose from. The secret is arbitrarily chosen to be the y-intercept of the polynomial. The keys are generated by solving the polynomial for x=1, x=2, etc.
This implementation only supports polynomials of degree 1 (i.e. straight lines) since linear interpolation is way easier than higher-order interpolation. The program first converts the secret message into a number (more on that below), which represents the y-intercept of the line. Then a random number is chosen for the slope of the line. The intercept and slope are substituted in for b and m, respectively, in the classic equation y = mx+b, and then the keys are generated by evaluating the equation at x=1, 2, and so on for however many keys the user requested. The resulting coordinate pair is encoded in Base64, because it looks cooler than a plain old (x,y) pair.
To retrieve the secret number, two keys must be provided. The coordinate pairs (x1, y1) and (x2,y2) are extracted and then we use (y2-y1)/(x2-x1) to find the slope of the line, and then we solve for b = y1-mx1 to find the y-intercept, which is our secret number.
For a visual explanation, check out this great video by Art of the Problem.
To turn a message into a number, the ASCII values of each character in the message are combined into one long bit string. For example, let's encode "hello". In ASCII (using hex values), h = 0x68, e = 0x65, l = 0x6C, and o = 0x6F, so they become the number 0x68656C6C6F, which represents 448,378,203,247. Thank goodness Python is able to handle arbitrarily large numbers, because these numbers get big pretty quickly. However, this huge number is reflected in the key length, so encrypting a long note would result in ginormous keys, which isn't very user-friendly. This is why there's a separate method for encrypting a file.
To encrypt an entire file, the program uses the concept of a one-time pad. A secret number is randomly chosen as the seed of a random-number generator, and then each character in the file is XOR'd with a random number between 0 and 255 (the maximum value for a character) produced by the generator. Then the secret seed is encrypted and the corresponding keys are created. To decrypt the file, the secret seed is retrieved from the keys and used to seed the random-number generator, which will now produce the same stream of numbers that were used to encrypt the file, and since the XOR operation operation is able to undo itself (i.e. if a ^ q = b, then b ^ q = a), XORing these random numbers with the encrypted file will undo the encryption and produce the original file. Notice that, as long as the seed is kept secret, it is impossible to determine the original contents of an encrypted file, since the original data was mixed with random numbers. For example, if the encrypted file contains the text "igohj", it might have originally been "hello" XOR'd with the numbers 1, 2, 3, 4, 5, or it might have been "adios" XOR'd with the numbers 8, 3, 6, 7, 25. There's no way to know which stream of numbers was used unless you have the seed for the random-number generator, which is protected by the keys.