Timeline for Is it ever unsafe to compress an EC point?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 18, 2020 at 22:29 | comment | added | Pierre | Cipolla-Lehmer modular square root works for all prime moduli and is easier to implement compared to Shanks-Tonelli. en.wikipedia.org/wiki/Cipolla%27s_algorithm | |
| Apr 20, 2015 at 18:47 | comment | added | poncho | @CodesInChaos: actually, there's a deterministic solution in that case as well; it's a tad more complex than the 3 mod 4 solution, but still works. What's tougher is the 1 mod 8 case... | |
| Apr 20, 2015 at 18:42 | comment | added | CodesInChaos | @poncho Curve25519 has $p \equiv 5 \pmod 8$. P-224 has $p \equiv 1 \pmod 4$. But there are efficient algorithms for computer square-roots in both of those fields. | |
| Apr 19, 2015 at 2:12 | comment | added | poncho | Huh? To decompress a point, you need to compute a modular square-root. If $p \equiv 3 \pmod 4$, that's easy to do. If one were to work in a prime field with $p \equiv 1 \pmod 4$, then, yes, it's a bit more difficult, and you will need to find a quadratic nonresidue (which isn't that complicated -- pick random points until you find one works); however we generally work in fields with characteristic 3 mod 4. | |
| Apr 19, 2015 at 0:20 | vote | accept | makerofthings7 | ||
| Apr 19, 2015 at 0:10 | history | answered | user991 | CC BY-SA 3.0 |