Am 27.04.2015 um 17:32 schrieb JF Jobidon: > Hi > > I use this exemple: http://www.royalforkblog.com/2014/09/04/ecc/ > > elliptic curve: y^2 = x^3 - 3x + 4 (mod 29) > > I want to find y (=9) coordinate from x (=17) coordinate for the point > (17,9) > > x^3 - 3x + 4 (mod 29) = 17^3 - 3*17 + 4 mod 29 = 4866 mod 29 = 23 > So from here you know: y^2 = 23 (mod 29). Calculating the inverse and multiplying by it is pointless after this.
You now have 2 options to calculate y:
1. Brute-Force. Try all y-values in the interval [5;28] and see which
one yields 23.
2. Use an algorithm to calculate square-roots modulo a prime. As I
guess your question is pointing at this I'll explain it.
Assuming you want to know the square root of a (=23) modulo p(=29).
1. Compute J=Jacobi(a,p) and return "a got no square roots" if J=-1
2. Generate random integers b with 1<=b<=p-1 until Jacobi(b,p)=-1 holds.
3. Divide p-1 by 2 until the the result is odd and write p-1=2^s*t, where t is
odd.
4. Compute a^-1 (mod p)
5. Set c = b^t mod p and r=a^((t+1)/2) mod p
6. For i from 1 to s-1 do the following:
6.1 Compute d=(r^2 * a^-1)^(2^(s-i-1)) mod p
6.2 If d=-1 (mod p) set r = r * c mod p
6.3 Set c=c^2 mod p
7. Return r and -r as the two square roots.
Now let's run this algorithm for your case.
1. Jacobi(23,29)=1, so continue
2. Select b=21 as Jacobi(21,29)=-1
3. p-1=28=2^2*7 -> s=2 and t=7
4. (23)^-1 (mod 29) = 24
5. c=21^7 mod 29 = 12 and r=23^((7+1)/2)=23^(4) mod 29 = 20
6. i in interval [1;1]
6. i=1
6.1 d=(20^2*24)^(2^(2-1-1))=(20^2*24) mod 29=1
6.2 d!=-1, don't do anything
6.3 c = 12^2 mod 29 = 28
7. return 20 and -20.
Check: 20^2 mod 29 = 23 as asked.
Check: (-20)^2 mod 29 = 23 as asked.
I think this answers your question.
In the future as you may not get an answer here, as this is primarily
concerned with Crypto++ you can also ask at Cryptography Stackexchange
<https://crypto.stackexchange.com/>. (Crypto version of Stackoverflow)
BR
JPM
> if I compute the multiplicative inverse of 23, I find 24:
>
> 24 * 23 mod 29 = 552 mod 29 = 1
>
> Then I can multiply both sides by 23:
>
> 23 * 24 * 23 mod 29 = 12696 mod 29 = 23
>
> But this number is not the square of another number: y^2 /= 12696
>
> My question: how do I find y such that
>
> y^2 mod 29 = 23
> --
> --
> You received this message because you are subscribed to the "Crypto++
> Users" Google Group.
> To unsubscribe, send an email to
> [email protected].
> More information about Crypto++ and this group is available at
> http://www.cryptopp.com.
> ---
> You received this message because you are subscribed to the Google
> Groups "Crypto++ Users" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to [email protected]
> <mailto:[email protected]>.
> For more options, visit https://groups.google.com/d/optout.
--
--
You received this message because you are subscribed to the "Crypto++ Users"
Google Group.
To unsubscribe, send an email to [email protected].
More information about Crypto++ and this group is available at
http://www.cryptopp.com.
---
You received this message because you are subscribed to the Google Groups
"Crypto++ Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
smime.p7s
Description: S/MIME Cryptographic Signature
