<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Sat, Jun 13, 2015 at 6:41 AM, Viktor Dukhovni <span dir="ltr"><<a href="mailto:cryptography@dukhovni.org" target="_blank">cryptography@dukhovni.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span class="">On Wed, Jun 10, 2015 at 09:13:17</span></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span class="">
> For a given prime p, the given integer x, y point mod p satisfies<br>
><br>
> (x, y) = s*G mod p<br>
><br>
> where G is a generator point, and s is a secret value. I'm trying to find<br>
> s, which looks doable if I can map (x, y) back to a rational point on the<br>
> circle, (l/n, m/n).<br>
<br>
</span>Since circle arithmetic is just multiplication of complex numbers<br>
on the unit circle the relevant formula is:<br>
<br>
(a,b)*(c,d) = (ac - bd, ad + bc)<br>
<br>
It is easy to verify that if norm((a,b)) = (a^2 + b^2) = 1 =<br>
norm((c,d)), mod p or not, then also norm((a,b)*(c,d)) = 1. The<br>
inverse of any point (a,b) is (a,-b) and the identity is (1,0).<br></blockquote><div><br></div><div>Yes, this is correct.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
In this context, a useful mapping from the circle mod p to the<br>
characteristic 0 (rational) circle needs to preserve the product,<br>
(that is it needs to be a group homomorphism), otherwise the mapping<br>
is of no use in mapping the DLP from (mod p) to the rationals.<br></blockquote><div><br></div><div>The homomorphism is simply taking each rational point in the rational group mod p. If we have P = s*G in the rational group, then we will also have P = s*G mod p. If we find an s that works in the rational group, it also works mod p. Further, we don't even have to represent P in the rational group very accurately. If we have a 2*n digit approximation of m/n, we can trivially solve for s in the circle group (just divide by G), and I believe we can also easily solve for s on an Edwards curve.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Since there are only finitely mod p points, each point has a finite<br>
order, i.e. (x,y)^n = 1 for for some n. The same would have to be<br>
true for any image of (x,y) under a homomorphism into the rational<br>
circle. However, there are only four rational points on the circle<br>
with finite order:<br>
<br>
1, -1, i, -i<br>
<br>
all other rational (p, q) with p^2 + q^2 = 1 have infinite order.<br>
Otherwise, there'd be a primitive n^th root of unity for n > 2,<br>
with rational real and imaginary parts, but all such numbers<br>
have degree 2 over the rationals.<br>
<br>
So the only viable homorphisms are into Z_4, and cannot be injective<br>
for all but the smallest primes.<br>
<br>
So this approach is a dead-end even for the circle, which is much<br>
simpler than an actual Edwards curve with a non-zero "d"<br></blockquote><div><br></div><div>That's the shortest proof I've seen for why all but a few rational points generate infinite groups on the unit circle. I Googled that the other day, and maybe this is a standard proof, but I failed to find such a succinct proof. Nice!</div><div><br></div><div>In reality, we typically do not do elliptic curve crypto on groups homomorphic to rationals over an elliptic curve. We always extend the rationals by certain irrationals and sometimes i, but the math basically seems to work out the same. Given a rational coordinate x, I haven't seen a curve where y is rational, though I've only looked at some NIST curves and curve25519, and a few toy curves I made up.</div><div><br></div><div>However, I'm not trying to map a finite group mod p to another finite group. I was just wondering if we already knew what the difficult problem is in doing the reverse-mapping of the homomorphism from rationals on the unit circle to points mod p. I was guessing this is already well known. I was just wondering if anyone had a useful link where I could learn more about the problem.</div><div><br></div><div>Bill</div></div></div></div>