2
$\begingroup$

Alice has a RSA 2048 private key and Bob has corresponding public key. They have a secure connection, but Alice can transmit only 256bit to Bob (Bob can transmit any amount of data to Alice).

Is there a way how Alice can proof to Bob that she is in possession of the private key?

$\endgroup$
4
$\begingroup$

Is there a way how Alice can proof to Bob that she is in possession of the private key?

Here is one possible way:

Bob selects a random 2048 bit value $m < n$ and computes $m^e \bmod n$ and sends that and $\text{SHA3_256}(m )$ to Alice.

Alice, with the private key, recovers $m$, and verifies that $\text{SHA3_256}(m)$ matches the value she received from Bob. If so, she computes and sends $\text{SHA3_256}(m || m)$; that's 256 bits.

Bob compares that with the hash of the duplicated value he originally selected; if they match, then either Alice was improbably lucky, or she really does have the private key.

Bob cannot use this protocol as an Oracle to compute the hashes of RSA decryptions, because he would need to already know the hash of the plaintext.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.