I am trying to find information on how to encrypt something in such a way that there are n keys, and k of them are needed for decryption. However, I have been searching Google for half an hour but because I do not know what this is called (and am apparently bad at searching), I cannot find it.
EDIT: preferably such that the keys can be chosen, if this exists under a special name.
To complete @Terry's answer:
Shamir's secret sharing works on values in a given field (the mathematical concept). In practice, if you accept that you won't make more than 255 shares (i.e. 1 < k ≤ n ≤ 255) then it is convenient to work in GF(256), the field with 256 elements. This would mean that you actually do the sharing on each byte independently of the others, and thus that you can "share" any secret which fits in a sequence of bytes (so, really, anything which fits in a computer). And it is quite efficient.
Since each share has the same length as the secret data, you may want to optimize things a bit with encryption. This means that if you want to share a big secret value S (e.g. a 3 gigabytes video), then you:
This way, each share holder only has to remember something which is the size of K (16 bytes, easily fits in various places, e.g. a smartcard or even a human brain), while the secret value S can be arbitrarily large and efficiently stored and distributed (since it is encrypted, it can be shown to the public at large, e.g. transferred with a peer-to-peer network).
Now for the choosing the share values, that's an interesting problem. If you have n shares and a threshold of k, the normal description of Shamir's scheme implies that each share is essentially random. The secret splitting outputs the shares, and the share holders can only get them.
The computations can be trivially extended into a scheme where at most k-1 shares are chosen arbitrarily. So some shares must still be random.
User-chosen shares make sense when shares must be remembered, i.e. are passwords. But passwords are subject to brute force. For instance, if an attacker obtained k-1 shares and knows that one of the other shares is a password, then he can run a dictionary attack on that extra share, namely trying out potential passwords (for each password, recomputing the shared secret with that password as extra share, and see if the result "makes sense"). This unfortunately weakens the whole system.
Indeed, a great property of Shamir's scheme is that it is unconditionally secure, meaning that it resists attackers with arbitrary computing power, including computers which have not been invented yet (as long as the source of randomness used in the splitting is really random). This simplifies security analysis, in particular for long-term storage, where you have to predict how much computing power attackers will have decades from now. But if you insert passwords in the mix, this unconditional security vaporizes as dew under the morning Sun.
You are probably thinking of the Shamir's Secret Sharing algorithm.
From the wikipedia article,
Shamir's Secret Sharing is an algorithm in cryptography. It is a form of secret sharing, where a secret is divided into parts, giving each participant its own unique part, where some of the parts or all of them are needed in order to reconstruct the secret. Counting on all participants to combine together the secret might be impractical, and therefore sometimes the threshold scheme is used where any k of the parts are sufficient to reconstruct the original secret.
