Mixing
Calculate inverse square root modulo (Feige-Fiat-Shamir Algo)
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I would like to calculate a secret key, $s$:
$$ s = sqrtfrac1v 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$
cryptography
asked Jul 26 at 7:05
Sirvan Almasi
103
add a comment |Â
up vote
0
down vote
favorite
I would like to calculate a secret key, $s$:
$$ s = sqrtfrac1v 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$
cryptography
asked Jul 26 at 7:05
Sirvan Almasi
103
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I would like to calculate a secret key, $s$:
$$ s = sqrtfrac1v 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$
cryptography
asked Jul 26 at 7:05
Sirvan Almasi
103
I would like to calculate a secret key, $s$:
$$ s = sqrtfrac1v 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$
cryptography
asked Jul 26 at 7:05
Sirvan Almasi
103
asked Jul 26 at 7:05
Sirvan Almasi
103
asked Jul 26 at 7:05
Sirvan Almasi
103
asked Jul 26 at 7:05
Sirvan Almasi
103
103
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
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 pmodn$ 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'=frac1v pmodn= 71$, which is the number whose smallest square we must find:
Modulo $7$: $71 pmod7 = 1$ which has roots $1, -1equiv 6$.
Modulo $11$: $71 pmod11= 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 pmod77$$
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.
answered Jul 28 at 9:16
Henno Brandsma
91.4k34199
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"?)
– Sirvan Almasi
Jul 30 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 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?
– Sirvan Almasi
Aug 3 at 4: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 8 at 10:27
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
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 pmodn$ 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'=frac1v pmodn= 71$, which is the number whose smallest square we must find:
Modulo $7$: $71 pmod7 = 1$ which has roots $1, -1equiv 6$.
Modulo $11$: $71 pmod11= 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 pmod77$$
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.
answered Jul 28 at 9:16
Henno Brandsma
91.4k34199
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"?)
– Sirvan Almasi
Jul 30 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 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?
– Sirvan Almasi
Aug 3 at 4: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 8 at 10:27
add a comment |Â
up vote
0
down vote
accepted
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 pmodn$ 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'=frac1v pmodn= 71$, which is the number whose smallest square we must find:
Modulo $7$: $71 pmod7 = 1$ which has roots $1, -1equiv 6$.
Modulo $11$: $71 pmod11= 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 pmod77$$
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.
answered Jul 28 at 9:16
Henno Brandsma
91.4k34199
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"?)
– Sirvan Almasi
Jul 30 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 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?
– Sirvan Almasi
Aug 3 at 4: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 8 at 10:27
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
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 pmodn$ 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'=frac1v pmodn= 71$, which is the number whose smallest square we must find:
Modulo $7$: $71 pmod7 = 1$ which has roots $1, -1equiv 6$.
Modulo $11$: $71 pmod11= 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 pmod77$$
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.
answered Jul 28 at 9:16
Henno Brandsma
91.4k34199
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 pmodn$ 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'=frac1v pmodn= 71$, which is the number whose smallest square we must find:
Modulo $7$: $71 pmod7 = 1$ which has roots $1, -1equiv 6$.
Modulo $11$: $71 pmod11= 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 pmod77$$
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.
answered Jul 28 at 9:16
Henno Brandsma
91.4k34199
edited Aug 8 at 10:19
answered Jul 28 at 9:16
Henno Brandsma
91.4k34199
answered Jul 28 at 9:16
Henno Brandsma
91.4k34199
answered Jul 28 at 9:16
Henno Brandsma
91.4k34199
91.4k34199
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"?)
– Sirvan Almasi
Jul 30 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 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?
– Sirvan Almasi
Aug 3 at 4: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 8 at 10:27
add a comment |Â
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"?)
– Sirvan Almasi
Jul 30 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 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?
– Sirvan Almasi
Aug 3 at 4: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 8 at 10:27
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"?)
– Sirvan Almasi
Jul 30 at 13:59
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"?)
– Sirvan Almasi
Jul 30 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 at 14:40
@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 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?
– Sirvan Almasi
Aug 3 at 4:01
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?
– Sirvan Almasi
Aug 3 at 4: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 8 at 10:27
@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 8 at 10:27
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2863148%2fcalculate-inverse-square-root-modulo-feige-fiat-shamir-algo%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password