I am trying to implement a (simplified) RSA-like verification process in my (Java) application. The client sends a request (data + private key signature) and the server either rejects his request or processes it - depending on the signature validity.
But I don't understand how the verification server knows which public key to use for signature decryption. Indeed, no public key - nor public key ID - seem to be sent to the verification server.
Does it actually test all authorized public keys ? Or is the public key stored from a previous communication exchange ?
The figure has several errors and some omissions, because it is probably a simplification:
the hash is digitally signed, not encrypted, and the signature is verified, not decrypted. The underlying cryptographic operation is not equivalent.
the signed data should include the certificate and the certification chain
if you use a known format like CMS, pkcs#7 or XMLDsig the hash to sign usually includes also a reference to the signing certificate and content-type to avoid tampering
To validate a signed document you verify the signature using the public key of the attached certificate but it is mandatory to check that the signing certificate is trusted verifying that the certificate itself or the issuing Certification Authority is present in the client's trustore.
The signature includes the certification chain because usually the truststore does not contain the intermediate CAs. The certificates of the truststore are exchanged previously
Additionaly the verification process should check that the certificate is not expired and not revoked
Note that the verification process is the same for all digital certificates in a public key infrastructure, not just RSA