Re: New Rabin-type PK system

tomstdenis_at_gmail.com
Date: 08/23/05


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 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
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



Relevant Pages

  • Re: Points on elliptic curves
    ... also a homomorphism of additive groups. ... What does this have to do with quadratic equations? ... a double root and exists, because all the elements of GFhave a unique square root. ... a "trace condition" splits the quadratic equation into two cases more or less equiprobable cases just like the study of the square root of the discriminant does in the case of characteristic not equal to two. ...
    (sci.math)
  • Re: Marie Jean Faucounau sues me for at least 8,487 Swiss Fr
    ... Your are just talking about the SQUARE ROOT columns, ... I'M ASKING YOU SPECIFICALLY ABOUT THE CUBE ROOT COLUMN: ... mistake is diminishing. ...
    (sci.lang)
  • Fractal Peano Natural Numbers #452 Correcting Math
    ... And the trouble with Hensel P-adics is that they are really a disguised setup of Reals where they crank out Reals under a fancy mechanism. ... And the Hensel P-adics also has some trouble with a native definition of exponentiation and roots. ... And taking the square root of that number we again have: ...
    (sci.math)
  • Re: cube root of a given number
    ... the Householder expressions for the Nth root of any number P. ... Higher-order rational process based on the Rational Mean: ... approximations -by defect and excess-- to the square root of P. ... multiply by THREE the number of exact digits in each iteration. ...
    (sci.math)