I'd scrap the direct syncing option and simply allow the user to export their private key to a location of their choice, e.g. iCloud, DropBox, internal storage, etc., in an encrypted format.
On export I'd do something like this:
- Ask the user for a password to use. Don't impose any restrictions on them - it's their job to use a good password!
- Use a strong key-derivation algorithm such as PBKDF2 to generate a storage key. Use a decent number of rounds.
- Prefix the private key blob in memory with four known bytes (a magic number), e.g. 'NATG', to form your plaintext.
- Encrypt the plaintext with AES-128 or a similar block cipher, in CBC mode, using the storage key and a randomly generated IV.
- Export the ciphertext and IV into a file.
On import:
- Extract the ciphertext and IV from the file.
- Ask the user for the password and generate the same key using PBKDF2.
- Decrypt the ciphertext using the IV and key.
- Check that the first four bytes of plaintext match your known bytes. If not, it's the wrong password. If so, we're in the money!
- Remove the first four bytes and you've got the private key!
This allows users to quickly and easily sync private keys via the communications service they want, whether it be iCloud or DropBox or even email, with a reasonable level of security. If their account gets broken into, the attacker still has to crack their password. If they've used a decent one, PBKDF2 should do a decent job of making their cracking attempt infeasible.