Re: New Rabintype PK system
tomstdenis_at_gmail.com
Date: 08/23/05
 Next message: Unruh: "Re: md5 collisions and speeding tickets"
 Previous message: tomstdenis_at_gmail.com: "Re: New Rabintype PK system"
 In reply to: tomstdenis_at_gmail.com: "Re: New Rabintype PK system"
 Next in thread: tomstdenis_at_gmail.com: "Re: New Rabintype PK system"
 Reply: tomstdenis_at_gmail.com: "Re: New Rabintype PK system"
 Reply: Kristian Gjøsteen: "Re: New Rabintype PK system"
 Reply: Kristian Gjøsteen: "Re: New Rabintype PK system"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 23 Aug 2005 06:11:41 0700
tomstde...@gmail.com wrote:
> 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
> exptmod.
>
> 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
backwards way,
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)
start:
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 nontrivial, 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
know k'
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 ;)
Tom
 Next message: Unruh: "Re: md5 collisions and speeding tickets"
 Previous message: tomstdenis_at_gmail.com: "Re: New Rabintype PK system"
 In reply to: tomstdenis_at_gmail.com: "Re: New Rabintype PK system"
 Next in thread: tomstdenis_at_gmail.com: "Re: New Rabintype PK system"
 Reply: tomstdenis_at_gmail.com: "Re: New Rabintype PK system"
 Reply: Kristian Gjøsteen: "Re: New Rabintype PK system"
 Reply: Kristian Gjøsteen: "Re: New Rabintype PK system"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
