Is there a way to split up my SSH Key using Shamir's Secret Sharing?
Shamir's Secret Sharing is a nice algorithm to split a secret value into several pieces, and allow recovery with a threshold; meaning that you split (for instance) the secret into ten shares, such that any three shares are sufficient to rebuild the secret.
This calls for two comments:
The algorithm's main advantage is its threshold mechanism; it does not make much sense if all shares are needed to rebuild the secret. In the described scenario, with SSH keys, it is unclear what this threshold mechanism would mean. There is a scenario where you want something like that (I have seen it deployed in production; see below) but it involves several key owners.
Though the shares are separated, the rebuilding process must occur, by necessity, on a single machine which obtains, at some point, the secret itself. In particular, if you do the reassembly on a machine which is evil (i.e. which is under the control of an attacker through some subreptitious malware), then the attacker learns the SSH private key, and you lose.
The scenario where the threshold mechanism with SSH makes sense is the following: there is a very sensitive server somewhere (a Certification Authority), which must never be administered by a single administrator without any witness. However, the server is remote, and some remote administration must still take place. So the idea is to have a special private key, authorized for root login (the public key is in /root/.ssh/authorized_keys). The corresponding private key should be accessible only on a machine which is assumed safe (a machine dedicated for the task and kept safe through normal mechanism -- in that case, a Linux system with sane sysadmin procedures). When remote administration must take place, a quorum of key owner collaborate, enter their "shares" on the machine, and thus unlock the private key. They keep the sysadmin under eye control for the whole duration of the administration procedure.
In that scenario, a secret sharing scheme would make sense. However, the "shares" are big numerical values, which must be stored on physical devices, not in human brains; this was inconvenient. Moreover, usual SSH client software does not allow for plugging arbitrary secret sharing systems (not easily at least). So the practical solution was the following: the private key was stored several times, each time protected by a password split into two halves; each human knew only one half. If there are n share owners, then the private key must be password-encrypted n(n-1)/2 times (so with n = 5, this means 10 copies of the private key, each encrypted with a combination of two password halves). When remote administration must take place, two key owners select the corresponding encrypted private key file; each owner types his password half, and the connection occurs.
The system works in practice. It does not scale well (with n key owners and a quorum of t, it requires O(nt) encrypted files, for all combinations), but for small values it is perfectly workable.