Short Answer
Use the XOR of multiple keys as the actual encryption key. Give each of those keys to the parties. To decrypt they each must reveal their key, XOR all values together, decrypt.
Long Answer
- X people has N characters of a password that is X*N characters long
The problem with this scheme is that if X-1 people come together, they only need to brute force N characters (the last portion of the share). Depending on your parameters, this could be achievable.
What you really want is a method where if less than X people try to decrypt, they have no additional information about the secret encryption key. An easy way to achieve this would be to give each of the X parties an X*N character string which is completely random. Then set the secret encryption key to the XOR of these strings. If X-1 parties try to decrypt, they will have to brute force an X*N character random string which would be infeasible if you set the parameters correctly (say X*N is 128 bits long and use AES-128 for encryption).
- Re-encrypt the message with PGP or some PKI/RSA etc
PKI should never be used for bulk encryption (encrypting a long message). PKI is typically used (in this scenario) to distribute a key.
Now, say you modify this to instead use PKI to distribute X secret keys of length X*N (same as above). Then you send out C=E(K1, E(K2, E(...E(Kn, M)))). This would work, but the computational overhead is pretty big if n is large. For 2 or 3 parties this would probably be fine.
Threshold Decryption
The above is only valid if you require that all X people be present to decrypt. What if you only wanted it such that t out of X are required. This is when you could use Shamir Secret Sharing (see logicalscope's answer).
Note that Shamir Secret Sharing will work if t==X, but is not as simple as the method I outlined.
