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.
I have learnt to do it the other way round $ v = (\pm 1) (s^2)^{-1} \mod n$
Best Answer
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.