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:
“There is one safeguard known generally to the wise, which is an advantage and security to all, but especially to democracies as against despots. What is it? Distrust.”
—Demosthenes (c. 384–322 B.C.)
“I feel a sincere wish indeed to see our government brought back to it’s republican principles, to see that kind of government firmly fixed, to which my whole life has been devoted. I hope we shall now see it so established, as that when I retire, it may be under full security that we are to continue free and happy.”
—Thomas Jefferson (1743–1826)
“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)