0

I would like to calculate a secret key, $s$:

$$ s = \sqrt{\frac{1}{v}} \mod n $$

where v is the public key, n is a product of two primes p and q. (maybe we can use something simple like 7 in this example?)
Can someone please provide a step by step example (short prime numbers so that we can calculate it by hand)? Much appreciated.

It's based from this:

Precalculation: An arbitrator generates a random modulus n (512-1024 bits) which is the product of two large primes.The arbitrator generates a public and private key pair for Peggy, by choosing a number, v, which is a quadratic residue mod n (i.e. x^2 = v mod n has a solution, and v^-1 mod n exists). This number, v , is the public key. The private key is then the smallest s for which s = sqrt(1/v) mod n.

Source

I have learnt to do it the other way round $ v = (\pm 1) (s^2)^{-1} \mod n$

hairybear
  • 15

1 Answers1

1

The other way is entirely equivalent: it just starts with a private key $s$ which has gcd $1$ with $n$, and computes the square of the inverse modulo $n$ (or the inverse of the square, which is the same). That way you're sure that the public key will be a square residue because that's how you made it.

If you know $p$ and $q$ prime such that $pq=n$ you can compute the $s$ from the public value $v$ in the standard way: compute $v'=v^{-1} \pmod{n}$ using the extended Euclidean algorithm and compute the square roots of $v'$ modulo $p$ and $q$ and combine them via the Chinese remainder theorem to find all 4 square roots of $v'$ modulo $n$.

Small example: $n=77$ and $v=64$. Clearly $p=7,q=11$ will do. $v'=\frac{1}{v} \pmod{n}= 71$, which is the number whose smallest square we must find:

Modulo $7$: $71 \pmod{7} = 1$ which has roots $1, -1\equiv 6$.

Modulo $11$: $71 \pmod{11}= 5$ which has roots $4, -4 \equiv 7$.

The Bézout coefficients for $7$ and $11$ are also easy to find by hand:

$$8 \cdot 7 + (-5) \cdot 11 = 1$$

So by the CRT, the four square roots of $71$ are

$$(\pm 4) \cdot 8 \cdot 7 + (\pm 1) \cdot (-5) \cdot 11 \pmod{77}$$

for all $4$ choices of signs.

That gave me $(++): 15, (-+): 29, (--): 62, (+-) 48$ as the solutions, so the smallest is $15$. This indeed has square $71$ modulo $n$, as required.

Henno Brandsma
  • 242,131
  • Thank you for the clear answer, so in this case $n$ can be public? My other quick question is, if that I create an identity-based system and have a trusted centre create the private keys $s$, would they have to use the same $n$? (if they do that, people can collude and find secret keys , e.g. if i have the privat key for "A" then i can collude with person having private key for "B", and form a private key for "AB"?) – hairybear Jul 30 '18 at 13:59
  • @SirvanAlmasi $n$ is always public, and should be hard to factor like in RSA. Everyone should have its own $n$ I think. – Henno Brandsma Jul 30 '18 at 14:40
  • May thanks for your help! Is it possible to try with v = 67? and keeping p and q the same? What answer do you get? – hairybear Aug 03 '18 at 04:01
  • @SirvanAlmasi $v=67$ gives $v'= 23$. This has roots $\pm 3$ modulo $7$ and $\pm 1$ modulo $11$ and so the same formula gives roots $10,32,45,67$ of which $10$ is the smallest (and thus the secret key corresponding to $v=67$ in your notation. – Henno Brandsma Aug 08 '18 at 10:27