I'm getting conflicting information on how the security keys are stored and used. Where are the public and private keys stored? If the private key is stored on the Yubikey itself, how many can it hold?
If the both keys are stored on the service you are authenticating against (Gmail), does it send the yubikey the private key to unencrypt to use the private key for signing?
During the registration process, the key pairs are generated on the device (secure element) but the key pairs are not stored on the YubiKeys. Instead, the key pair (public key and encrypted private key) are stored by each relying party/service that initiated the registration. Therefore, this approach allows for an unlimited number of services to be associated with the U2F-certified YubiKeys.
The U2F device and protocol need to guarantee user privacy and security. At the core of the protocol, the U2F device has a capability (ideally, embodied in a secure element) which mints an origin-specific public/private key pair. The U2F device gives the public key and a Key Handle to the origin online service or website during the user registration step. Later, when the user performs an authentication, the origin online service or website sends the Key Handle back to the U2F device via the browser. The U2F device uses the Key Handle to identify the user's private key, and creates a signature which is sent back to the origin to verify the presence of the U2F device. Thus, the Key Handle is simply an identifier of a particular key on the U2F device.