12345678910111213141516171819202122232425262728293031323334353637 |
- #!/usr/bin/ruby
- /*
- Rabin's protocol is equivalent to factoring: Suppose you have a procedure P
- which, given a quadratic residue, gives one of its square roots mod pq. The
- four nsquare roots of a quadratic residue y=x^2 mod pq is -x, x, -gamma x,
- gamma x, where gamma is the nontrivial square root of unity mod pq.
- Aside: you can find gamma if you know p and q by using the Chinese
- Remainder Theorem (CRT) and solving the system of equations
- x = -1 mod p
- x = 1 mod q
- [ You can see where the other square roots of unity comes from: they are the
- other possible patterns of signs on the 1's in the system of eqns for CRT. ]
- Now, given P, you choose a random r between 1 and pq-1 inclusive and compute
- y = P(r^2). With 1/2 probability, y = +/- gamma r. Since you knew r, you
- can find g = y/r = +/- gamma. Now, since g-1 is either 0 mod q or 0 mod p,
- so GCD(g-1,pq) will give you p or q.
- [ To find 1/r mod pq, use EGCD: The extended Euclidean algorithm, given
- m,n, will find GCD(m,n) as well as the pair a,b such that am+bn=GCD(m,n).
- When GCD(m,n)=1, we have a=1/m mod n. ]
- Note that this can be simplfied a little, since with very high probability r
- does not divide pq: r(g-1) = r(y/r - 1) = y - r, so GCD(y-r,pq) will work
- just as well. If r divides pq, you've already (accidentally) factored the
- modulus.
- */
- # See also:
- # https://ratthing.com/files/textfiles.com/programming/CRYPTOGRAPHY/rabin-al.txt
- # TODO: implement it
|