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:
“The horror of class stratification, racism, and prejudice is that some people begin to believe that the security of their families and communities depends on the oppression of others, that for some to have good lives there must be others whose lives are truncated and brutal.”
—Dorothy Allison (b. 1949)
“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)
“We now in the United States have more security guards for the rich than we have police services for the poor districts. If you’re looking for personal security, far better to move to the suburbs than to pay taxes in New York.”
—John Kenneth Galbraith (b. 1908)