On the Security of the PKCS#1 v1.5 Signature Scheme

摘要: The RSA PKCS#1 v1.5 signature algorithm is the most widely used digital scheme in practice. Its two main strengths are its extreme simplicity, which makes it very easy to implement, and that verification of signatures significantly faster than for DSA or ECDSA. Despite huge practical importance signatures, providing formal evidence their security based on plausible cryptographic hardness assumptions has turned out be difficult. Therefore recent version (RFC 8017) even recommends a replacement more complex less efficient RSA-PSS, as provably secure therefore considered robust. obstacle use deterministic padding scheme, standard proof techniques not applicable. We introduce new technique enables first RSA-PKCS#1 signatures. prove full existential unforgeability against adaptive chosen-message attacks (EUF-CMA) under assumption. Furthermore, we give tight Phi-Hiding These proofs random oracle model parameters deviate slightly from use, because require larger output length hash function. However, also show how can instantiated practice such our apply. In order draw complete picture precise model, but with respect weaker attacker models (key-only attacks) known complexity assumptions. conclusion work provable perspective safely used, if function chosen appropriately.