Motivation
Encryption tries to hide a message. A digital signature usually leaves the message public and instead lets anyone verify that it was authorized by the secret-key holder. Reversing an RSA exponentiation equation gives a candidate signature rule, but the security goal must change: an adversary may ask for signatures on messages of its own choice and then try to authorize a new one.
Raw RSA fails this goal by an elementary algebraic attack. Hashing the message before signing is a possible repair, but the word hash is not a security assumption. We analyze an ideal random function taking values throughout the RSA permutation's domain. In that model, a reduction can place an RSA inversion challenge at one unknown oracle query and answer the other queries using known roots.
The proof includes the probability of selecting that query, repeated-query consistency and bounded fair-bit sampling. It gives a conditional theorem in an ideal model. It does not certify a fixed real hash function, a standardized signature encoding or a deployed implementation.
Definitions
Assume a supplied efficiently generated RSA key family with security parameter , supplied publicly as . A modulus is for distinct odd primes, its bit length is polynomial in , and . The exponent is coprime to , and the secret exponent satisfies . Write . Earlier RSA arithmetic proves that is a permutation of with inverse .
The RSA one-way assumption used here says that every bounded probabilistic polynomial-time algorithm, given the public key and uniform in , finds a unit satisfying with only negligible probability, averaged also over generated keys. Negligible has the earlier inverse-polynomial asymptotic definition. The key family and assumption are supplied hypotheses; no equivalence between RSA inversion and factoring is asserted.
In the chosen-message forgery experiment, an adversary receives the public key, may request signatures on polynomially many messages, and finally outputs . It wins if verification accepts and was never requested for signing. This is existential unforgeability under chosen-message attack. Repeating a signature on an already signed message is not a win in this experiment.
For raw RSA, messages belong to and signing returns . For full-domain hash, messages are polynomial-length bit strings and an ideal random oracle maps them to :
A random oracle answers each new string by an independent uniform unit and repeats its saved answer on later calls. It is a mathematical oracle model, not an ordinary fixed hashing algorithm. The adversary has access to both this oracle and the signing oracle.
Theorem/proposition
Theorem 4.3.1
(Correctness does not prevent raw RSA forgery)
Both stated signature rules verify their honestly generated signatures. Raw RSA nevertheless admits a successful forgery without any signing query: choose any unit , form , and output . It also permits multiplication of two signatures to sign the product of their messages.
Theorem 4.3.2
(Conditional security of full-domain hashing)
Fix computable polynomial bounds on the adversary's hash and signing queries. Suppose it forges with probability in the ideal experiment. Put , and let be the least power of two at least . There is a bounded polynomial-time RSA inverter with success at least
Thus the RSA one-way assumption implies negligible forgery probability in this random-oracle model. The final extra query permits verification of a forged message that was never previously hashed.
Proof sketch or proof idea
Proof
(Exponent inversion, and choosing the root first)
For every unit , exponent inversion gives . Apply this with or to prove correctness. But the raw verification equation is also satisfied by choosing the signature first and computing its corresponding message. Existential forgery lets the adversary choose which new message to forge, so it does not need to invert a predetermined target.
Likewise if and , then . When that product is a new message, the pair is a chosen-message forgery. Full-domain hashing changes the required equation to a fresh independent oracle value; the product of two earlier hash values need not be the hash of any chosen new message.
The security proof for full-domain hashing has three parts: a simulation of the hash oracle by chosen roots, a hidden challenge at a guessed table entry, and a bounded sampler whose cost is accounted for by a coupling.
Proof
(Simulate the oracles, plant the challenge, bound the sampling)
Simulate a hash answer by choosing its root. For any ordinary new hash query, choose uniformly in , return as the hash value, and save both numbers. Since exponentiation is a permutation, the returned value is uniform in . Different fresh choices give independent hash answers; collisions are allowed exactly as in a random function. A signing query on that message can be answered by the saved , the unique root required by the signing rule.
If a message is first encountered through a signing request, create its hash-table entry in this same way before returning the root. Repeated hash or signing requests reuse that entry. The total number of new entries, including the final forged-message verification, is at most . Counting only the adversary's explicit hash calls would miss entries created by signing or verification.
Hide an inversion challenge at a random entry. Given an RSA challenge , the reduction chooses uniformly in using exactly fair bits. At the th new table entry it returns instead of a self-generated . Its root is unknown. If that message is requested for signing, the reduction reports failure. All other entries and signatures are simulated as above. If the adversary eventually forges on the special message, the verifying signature is an th root of and solves the inversion challenge.
To see why the chance of success involves even with adaptive queries, analyze first a hypothetical perfect experiment that knows the secret key and can answer even the special signing query. The challenge is uniform, so every hash entry has the correct independent uniform law whichever position was selected. Signatures are the unique roots of their entries. The full adversary transcript in this perfect experiment is therefore independent of .
On any successful forgery transcript, the first table entry for has some index . Since is independent and uniform, the probability it equals this index is . On that event the special message was never signed, by the freshness requirement in the winning experiment. The actual reduction consequently never encounters its special abort and follows exactly the same transcript through the forgery. Its success with ideal unit sampling is at least . The perfect experiment is an analysis device; the implemented reduction never uses a secret exponent.
Make every simulated sampling run bounded. Exact uniform sampling from cannot generally use a fixed number of fair bits without a failure branch. Let . Draw a uniform -bit integer and accept it if it is below and coprime to . Each accepted integer is a uniform unit. Since
each attempt succeeds with probability at least . Coprimality is tested by the polynomial-time Euclidean algorithm and does not require factoring .
Cap each root-sampling call at independent attempts and report inversion failure if the cap is reached. Its failure probability is at most . There are at most calls, so the probability that some cap changes the simulated experiment is at most .
For precision, couple each capped call with the ideal uncapped sampler using the same attempt bits. Until the first cap failure their outputs agree. Conditional on every past transcript, the next fresh attempts have the same success bound, so a union bound controls the probability of the first failure. Subtracting the coupling failure probability from the ideal inversion success proves the theorem, with a polynomial worst-case bound on all sampling, table and exponentiation work.
Since and is polynomially bounded, nonnegligible forging on infinitely many lengths would give nonnegligible inversion on those lengths after subtracting the negligible sampling term. This is the contradiction required by RSA one-wayness.
The guessed index and the coupling are the two places where the argument could silently go wrong, so it is worth isolating them.
Proof X-ray
Where the guess, the freshness rule and the coupling enter
The permutation property of is used once: it makes uniform, so the simulated hash table has exactly the random-oracle law, and it makes the saved the only valid signature. The challenge is uniform for the same reason, which is why the perfect transcript does not depend on . Only after that independence is established may one say that has probability ; conditioning first and asserting unbiased choices afterwards would be circular.
Freshness is the hypothesis that removes the one simulation the reduction cannot perform. A successful forgery is on a message that was never signed, so on the event the special entry is never asked for a signature, and the reduction's abort branch is never reached. Without freshness a replayed signature would win, and the planted entry might have to be signed.
The coupling replaces the tempting but invalid step of conditioning on every capped sampler succeeding: in an adaptive run, later calls depend on earlier outputs, so such conditioning could reweight histories. Comparing capped and uncapped samplers on the same attempt bits needs only the union bound . Finally keeps the loss factor polynomial, which is what turns the inequality into a contradiction with one-wayness.
Worked examples
Worked example 4.3.3
(A signature-first forgery in a toy group)
Take and , with and secret inverse exponent , since . Choose the unit . Its cube is , so passes raw RSA verification without any signing query. The attacker did not invert the prescribed RSA challenge ; it chose a root first and thereby selected the message. This small modulus is a correctness example only and can be factored immediately.
Worked example 4.3.4
(Multiply two requested signatures)
Under the same toy key, the messages and have signatures and respectively, since and . Multiplying gives signature for the new message , because . Asking for two signatures has therefore authorized a third message without the secret exponent.
In full-domain hash, multiplying signatures yields a root of . For a fresh chosen string , its independent hash equals that particular unit with probability , rather than by an algebraic identity. That observation explains why the old attack no longer automatically works; the reduction, not this observation alone, proves the full conditional theorem.
Worked example 4.3.5
(A challenge slot and a late hash query)
Imagine a reduction selecting . The first two new strings receive simulated values and , with saved roots and under the toy key. They can both be signed consistently. The third distinct string receives the inversion challenge . A valid signature for that fresh string would invert the challenge.
The third entry could be created only during final verification if the adversary never explicitly queried that string. It still belongs to the guessed table order, which is why the count includes the extra one. Conversely, if the adversary asked the reduction to sign that special string, the simulation would stop; such a transcript cannot be the matching successful fresh-message event used in the probability lower bound.
Common mistakes
Common mistake
(A random-oracle proof is not a theorem about every fixed hash)
The simulation relies on selecting independent hash outputs and planting a challenge at one of them. A fixed published hash algorithm does not give the reduction that programming ability. The theorem establishes security in its explicit ideal model under RSA one-wayness. Concrete encodings, standards and implementation guarantees require separate analysis.
Common mistake
(One-wayness is about a prescribed random target)
The security assumption concerns inversion on a random prescribed group element, not impossibility of producing any valid signature equation. The raw scheme's signature-first attack produces a valid pair without inverting anything, so it does not contradict one-wayness. Repeated queries, hash collisions and fresh-message verification belong to the experiment; deleting them from the model would simplify away genuine obligations of the proof.
Common mistake
(Counting only the explicit hash queries)
Setting forgets the table entries created by signing requests and by the final verification of . If the forged message was never hashed explicitly, its entry is the last one created, with index up to ; a guess range chosen from alone may stop before that index, and then the guess can never hit it.
Summary
Correct RSA exponentiation alone does not give unforgeable signatures. Full-domain hashing supplies an ideal independent target for each string. A guessed fresh table entry embeds an inversion challenge, while chosen roots answer every other query. Bounded sampling and an explicit coupling complete the conditional random-oracle proof without hiding a non-dyadic random choice or an expected-time assumption.
Exercises
Quick check
(Why does returning an old message with its already obtained signature not win the stated experiment?)
Reread the winning condition of the forgery experiment.
Solution
The experiment requires the forged message never to have been signed. Otherwise an adversary could always win by replaying an authorized message, which is not the authorization failure this definition measures. Stronger security notions can ask additional questions about alternative signatures on old messages.
Quick check
(Why does the reduction save both a simulated hash value and its chosen root?)
Consider a later hash call and a later signing call on the same string.
Solution · Answer
The value must be repeated consistently on later hash calls. The saved root lets the reduction answer a later signing call with the exact unique signature required by that value, without knowing the secret key.
Quick check
(Why is the guess made from a power-of-two range containing , rather than claiming exact bounded-bit uniform sampling from an arbitrary ?)
Count the fair bits needed for a uniform choice among positions.
Solution
A power-of-two range uses a fixed number of fair bits exactly. Unused positions merely reduce the success lower bound to , with , which preserves inverse-polynomial success. No unmentioned variable-time sampler or biased remainder rule is needed for the index.
Quick check
(What would be wrong with simply conditioning on every adaptive capped sampler succeeding and declaring the resulting transcript ideal?)
Later queries may depend on earlier outputs.
Solution
In an adaptive process later sampling behavior can depend on earlier outputs, so global success conditioning can reweight histories. Coupling capped and uncapped executions on the same fresh attempt bits instead bounds the chance that they ever diverge, and requires no such distributional assertion.
Quick check
(Under the toy key , , , compute the raw RSA signature of the message and verify it.)
Compute by repeated squaring, or look for a cube root directly.
Solution
Modulo : , so , because . Then . Check: and , since . So the signature is , and as verification requires.