If I sign the same message twice with RSA

one is not able to discriminate the difference between the two right?

should we add a salt to the signature so that even the signatures of the same message result different?

if so how big should it be?

@Aurelius so you are asking whether signature is usually non-deterministic with RSA?

well, yes, if you are using RSASSA-PSS

no if you use RSA-FDH or RSASSA-PKCS1v15

(PSS is indeed randomized)

@Aurelius note that a) if you salt the message before signing it, you need to publish the salt as well to allow verification and b) anything that prevents collisions is fine

so if you only have one signer an incrementing 32-bit counter will work (assuming you sign less than 4 billion messages in the lifetime of the key)

if you have many signers with the same key, then you probably want to pick the salt at random and for that a 96-bit salt gives you a chance of 2^{-32} of getting a collision at 2^{32} signed messages (you expect a collision at about 2^{48} messages)

adjust the parameters to your liking

@SEJPM thank you very much for the great explanation

I use the standard Java SHA256withRSA

to use SHA256withRSA/PSS I would need to use bouncy castle

is there any advantage between SHA256withRSA/PSS and SHA256withRSA plus a 12 bytes salt?

I know this is another topic but what do you think is better between Curve25519 and RSA 5120-bit?