Either Apple would generate it server-side, or the first device to "sign up" would generate it.
Remember, I'm only explaining a hypothetical method by which the Apple system could work, consistent with Apple's statements and behavior I've observed from my iPhones, iPads, and Macs. It's not an explanation of a strictly secure system.
> would generate it.
where is it stored though?
in the Keychain
sigh
> the private key is decrypted using the password and sent to the device.
wait, where is this private key coming from then? your other devices?