ECC curve
in [Cryptography]
|
From: Scott Fluhrer on 20 Jan 2010 22:26 "Rainer Urian" <rainer(a)urian.eu> wrote in message news:hj7utq$k6o$03$1(a)news.t-online.com... > Thank you for the answer I didn't ask the question :-) > I know the standardized secure curves very well. > > But thats not the point. > Actually, the problem is as follows: > There exists a ECC test specifiction for smartcards which wants to test > that the smartcard should reject a ECC public key of the form (0,0). > Now I wonder if this is a useful test or not. Testing for invalid inputs is always of some use. > Such a point can only occure on curves of the form y^2 = x^3 + a*x That might be the point of the test: what if the device is given a point that's not on the curve? Does it reject it as it ought to? > > > > "Tadek" <tstruk(a)gmail.com> schrieb im Newsbeitrag > news:233846db-5fe5-42bb-8104-430e5da85b70(a)p8g2000yqb.googlegroups.com... > Standards for Efficient Cryptography Group (SECG) published a document > called Recommended Elliptic Curve Domain Parameters: > http://www.secg.org/download/aid-386/sec2_final.pdf > These parameters/curves are safe to use and efficient. > Regards > T > > On Jan 20, 8:14 pm, "Rainer Urian" <rai...(a)urian.eu> wrote: >> ok, >> I meant secure for ECDH and ECDSA algorithm >> >> "Richard Herring" <junk@[127.0.0.1]> schrieb im >> Newsbeitragnews:6ij2VRHY6tVLFwqu(a)baesystems.com... >> >> > In message <hj55tm$81g$0...(a)news.t-online.com>, Rainer Urian >> > <rai...(a)urian.eu> writes >> >>Hello, >> >> >>are elliptic curves of the form y^2 = x^3+ x*a over GF(p) , p > 3, >> >>prime >> >>usable >> >> > Certainly. There are plenty of references in the literature (e.g. with >> > a=1 >> > it's Barreto et al's "cryptographically interesting" curve E_1,0.) But >> > "usable" for what, exactly? ... >> >> >> for cryptography or is it unsafe to use such a curve? >> >> > ... "Cryptography" is a huge field and concepts like "usable" and >> > "unsafe" >> > are ill-defined. You'd need to ask a much more specific question to get >> > a >> > meaningful answer. >> >> > For instance, there are pairing-based attacks on supersingular curves >> > (bad), but the existence of those same pairings facilitates a whole new >> > class of identity-based systems (good (if that's what you need) ;-). >> >> > -- >> > Richard Herring >
From: Rainer Urian on 21 Jan 2010 00:54 > That might be the point of the test: what if the device is given a point > that's not on the curve? Does it reject it as it ought to? yes, of course. But, can anybody please answer my original question instead of posting related suggestions? Or, is it in the group here as in the "Hitchhikers Guide to the Galaxy" "You get an answer but you will never know the right question for it" ;-) Anyway, good bye and thanx for the fish :-) >> >> "Tadek" <tstruk(a)gmail.com> schrieb im Newsbeitrag >> news:233846db-5fe5-42bb-8104-430e5da85b70(a)p8g2000yqb.googlegroups.com... >> Standards for Efficient Cryptography Group (SECG) published a document >> called Recommended Elliptic Curve Domain Parameters: >> http://www.secg.org/download/aid-386/sec2_final.pdf >> These parameters/curves are safe to use and efficient. >> Regards >> T >> >> On Jan 20, 8:14 pm, "Rainer Urian" <rai...(a)urian.eu> wrote: >>> ok, >>> I meant secure for ECDH and ECDSA algorithm >>> >>> "Richard Herring" <junk@[127.0.0.1]> schrieb im >>> Newsbeitragnews:6ij2VRHY6tVLFwqu(a)baesystems.com... >>> >>> > In message <hj55tm$81g$0...(a)news.t-online.com>, Rainer Urian >>> > <rai...(a)urian.eu> writes >>> >>Hello, >>> >>> >>are elliptic curves of the form y^2 = x^3+ x*a over GF(p) , p > 3, >>> >>prime >>> >>usable >>> >>> > Certainly. There are plenty of references in the literature (e.g. with >>> > a=1 >>> > it's Barreto et al's "cryptographically interesting" curve E_1,0.) But >>> > "usable" for what, exactly? ... >>> >>> >> for cryptography or is it unsafe to use such a curve? >>> >>> > ... "Cryptography" is a huge field and concepts like "usable" and >>> > "unsafe" >>> > are ill-defined. You'd need to ask a much more specific question to >>> > get a >>> > meaningful answer. >>> >>> > For instance, there are pairing-based attacks on supersingular curves >>> > (bad), but the existence of those same pairings facilitates a whole >>> > new >>> > class of identity-based systems (good (if that's what you need) ;-). >>> >>> > -- >>> > Richard Herring >> > >
From: Thomas Pornin on 21 Jan 2010 08:03 According to Rainer Urian <rainer(a)urian.eu>: > Actually, the problem is as follows: > There exists a ECC test specifiction for smartcards which wants to test that > the smartcard should reject a ECC public key of the form (0,0). > Now I wonder if this is a useful test or not. > Such a point can only occur on curves of the form y^2 = x^3 + a*x As far as I know, that test has historical roots in some implementations which used (0,0) as a representation of the "point at infinity". The explicit test is meant to avoid interoperability issues. Anyway, a point P = (X,0) on a curve has order 2 (P+P necessarily yields the point at infinity). For ECDH and ECDSA, we use points from a group of prime order q (where q is a sufficiently big integer). That group is either the entire curve or a strict sub-group of the entire curve. Since q is prime and odd, that (sub-)group cannot contain a point or order 2. Therefore, even on a curve where (0,0) is a curve point, that point should not be a possible public key. Therefore, the test rejects no otherwise valid public key. --Thomas Pornin
From: Scott Fluhrer on 21 Jan 2010 08:21 "Rainer Urian" <rainer(a)urian.eu> wrote in message news:hj8q5u$b5o$03$1(a)news.t-online.com... >> That might be the point of the test: what if the device is given a point >> that's not on the curve? Does it reject it as it ought to? > yes, of course. > > But, can anybody please answer my original question instead of posting > related suggestions? > Or, is it in the group here as in the "Hitchhikers Guide to the Galaxy" > "You get an answer but you will never know the right question for it" ;-) > > Anyway, good bye and thanx for the fish :-) Ok, here's what I know (which is probably not complete, I'm not an expert in ECC): - The curve y^2 = x^3 + x*a always has even order (because, as Thomas points out, it contains a point with order 2). Since ECDH/ECDSA wants to run in a prime subgroup q, that means that q is at least one bit less than p. Because the strength of the cryptography depends on the size of q, that means to get an appropriate q, we need a value of p one bit larger than we would otherwise need. A fairly small disadvantage, but it's there - Far worse, if p=3 mod 4, then I believe that curve always has order p+1 (independent of a). This is bad, as it allows a MOV attack (with k=2) to compute the discrete log fairly efficiently. I don't know of any necessary weakness if p=1 mod 4, but I'd stay away from it anyways. > > > >>> >>> "Tadek" <tstruk(a)gmail.com> schrieb im Newsbeitrag >>> news:233846db-5fe5-42bb-8104-430e5da85b70(a)p8g2000yqb.googlegroups.com... >>> Standards for Efficient Cryptography Group (SECG) published a document >>> called Recommended Elliptic Curve Domain Parameters: >>> http://www.secg.org/download/aid-386/sec2_final.pdf >>> These parameters/curves are safe to use and efficient. >>> Regards >>> T >>> >>> On Jan 20, 8:14 pm, "Rainer Urian" <rai...(a)urian.eu> wrote: >>>> ok, >>>> I meant secure for ECDH and ECDSA algorithm >>>> >>>> "Richard Herring" <junk@[127.0.0.1]> schrieb im >>>> Newsbeitragnews:6ij2VRHY6tVLFwqu(a)baesystems.com... >>>> >>>> > In message <hj55tm$81g$0...(a)news.t-online.com>, Rainer Urian >>>> > <rai...(a)urian.eu> writes >>>> >>Hello, >>>> >>>> >>are elliptic curves of the form y^2 = x^3+ x*a over GF(p) , p > 3, >>>> >>prime >>>> >>usable >>>> >>>> > Certainly. There are plenty of references in the literature (e.g. >>>> > with a=1 >>>> > it's Barreto et al's "cryptographically interesting" curve E_1,0.) >>>> > But >>>> > "usable" for what, exactly? ... >>>> >>>> >> for cryptography or is it unsafe to use such a curve? >>>> >>>> > ... "Cryptography" is a huge field and concepts like "usable" and >>>> > "unsafe" >>>> > are ill-defined. You'd need to ask a much more specific question to >>>> > get a >>>> > meaningful answer. >>>> >>>> > For instance, there are pairing-based attacks on supersingular curves >>>> > (bad), but the existence of those same pairings facilitates a whole >>>> > new >>>> > class of identity-based systems (good (if that's what you need) ;-). >>>> >>>> > -- >>>> > Richard Herring >>> >> >> >
From: Rainer Urian on 21 Jan 2010 16:35 Hello Thomas, this was a clear and conclusive argument! merci beaucoup, Rainer "Thomas Pornin" <pornin(a)bolet.org> schrieb im Newsbeitrag news:4b5850ba$0$10135$426a34cc(a)news.free.fr... > According to Rainer Urian <rainer(a)urian.eu>: >> Actually, the problem is as follows: >> There exists a ECC test specifiction for smartcards which wants to test >> that >> the smartcard should reject a ECC public key of the form (0,0). >> Now I wonder if this is a useful test or not. >> Such a point can only occur on curves of the form y^2 = x^3 + a*x > > As far as I know, that test has historical roots in some implementations > which used (0,0) as a representation of the "point at infinity". The > explicit test is meant to avoid interoperability issues. > > Anyway, a point P = (X,0) on a curve has order 2 (P+P necessarily yields > the point at infinity). For ECDH and ECDSA, we use points from a group > of prime order q (where q is a sufficiently big integer). That group is > either the entire curve or a strict sub-group of the entire curve. Since > q is prime and odd, that (sub-)group cannot contain a point or order 2. > Therefore, even on a curve where (0,0) is a curve point, that point > should not be a possible public key. Therefore, the test rejects no > otherwise valid public key. > > > --Thomas Pornin
First
|
Prev
|
Pages: 1 2 Prev: Mixet.se® - International Business Advertising Next: ISP-10 Call for papers |