An ID service on an app server interacts with a corresponding identity app installed on a user device such as a smart phone. At setup, the ID service receives the user's public key and only a segment of the corresponding private key. A special challenge message is created and partially decrypted using the private key segment on the server side, and then decryption is completed on the client app using the remaining segment(s) of the private key to recover the challenge. A token authenticator based on the result of the decryption is sent back to the identity service, for it to verify validity of the result and, if it is valid, enable secure login without requiring a password.