Re: New Rabin-type PK system
Date: 23 Aug 2005 06:11:41 -0700
> so we end up with p == 1 mod 4, IIRC there are algos if it's 3 or 5 mod
> 8 [talking out my ass partly here] neither of which are QRs mod 8
> either...We could force the PSS data to be 1 mod p^2 then the square
> root is trivial and we then only find it in Z_q which is a simple
> The problem is how do you modify PSS so that it doesn't reveal p^2 [or
> specifically p right?].
Forcing it to be any constant k mod p^2 reveals the factorization, we
can force it to be a random k though by computing a "square root" the
Instead of trying to find the root of k mod p^2 we just pick a random k
call that the square root and make k' the quadratic residue.
So signatures would work like
p = random prime
q = random prime (3 mod 4)
1. a = PSS || R [for some random R string which is the size of p^2 with
the msb zeroed]
2. k = random (does not divide p)
3. k' = k^2 mod p^2
4. a = a + (p^2 - (a mod p^2)) + k'
Now compute the square root of a mod p^2q as
5. root in p^2 = k
6. root in q = (a mod q)^((q+1)/4)
7. Verify if q is non-trivial, if it is goto the start
8. Use CRT to combine the roots into s
9. Output s as the signature.
now s^2 mod p^2q should equal a which contains PSS || R'. The verifier
can extract PSS and verify it's correct for the given message digest.
The attacker will know R' but it's offset by k' so the attacker doesn't
know what to subtract to compute the factorization. Suppose k' = 1
then the attacker could just do gcd(n, R' - 1) == p, however they don't
Note this is off the top of my head, [waiting for a HW test to finish]
and I have no plans to deploy this. I'd be surprised if it survived
the day ;-)