Security
If H is a random oracle, i.e. its output is truly random in then, forging a signature on any message m is as hard as calculating the square root of a random element in . To see that taking a random square root is as hard as factoring, we first note that any square modulo n has four square roots since n has two square roots modulo p and two square roots modulo q, and each pair gives a unique square root modulo n by the chinese remainder theorem. Now, if we have two different square roots, x,y such that but, then this immediately leads to a factorization of n since n divides but it does not divide either factor. Thus taking will lead to a nontrivial factorization of n. Now, there exists an algorithm to take square roots, we pick a random r modulo n and square it, then, using the algorithm to take the square root of R modulo n, we will get a new square root, and with probability half .
Read more about this topic: Rabin Signature Algorithm
Famous quotes containing the word security:
“Learned institutions ought to be favorite objects with every free people. They throw light over the public mind which is the best security against crafty and dangerous encroachments on the public liberty.”
—James Madison (1751–1836)
“It is hard for those who have never known persecution,
And who have never known a Christian,
To believe these tales of Christian persecution.
It is hard for those who live near a Bank
To doubt the security of their money.”
—T.S. (Thomas Stearns)
“The reins of government have been so long slackened, that I fear the people will not quietly submit to those restraints which are necessary for the peace and security of the community.”
—Abigail Adams (1744–1818)