agl / ed25519 Goto Github PK

Hi

I want to test if a FieldElement is on the curve.

func onCurve(p *edwards25519.ExtendedGroupElement) bool {
    var recip, x, y, left, one FieldElement
    FeInvert(&recip, &p.Z)
    FeMul(&x, &p.X, &recip)
    FeMul(&y, &p.Y, &recip)
    // Check whether -x^2+y^2==1+d*x^2*y^2
    FeSquare(&x, &x) // x^2
    FeSquare(&y, &y) // y^2
    FeSub(&left, &y, &x) // -x^2+y^2
    FeMul(&x, &x, &y) // x^2*y^2
    FeMul(&x, &x, &d) // d*x^2*y^2
    FeOne(&one) // 1+d*x^2*y^2
    FeAdd(&x, &x, &one)
    return left == x
}

It does not work, though a few of the entries in left and x do match.

What am I doing wrong?

diff --git i/extra25519/extra25519_test.go w/extra25519/extra25519_test.go
index 1e1dbdc..55be8ec 100644
--- i/extra25519/extra25519_test.go
+++ w/extra25519/extra25519_test.go
@@ -9,8 +9,8 @@ import (
        "crypto/rand"
        "testing"

-       "code.google.com/p/go.crypto/curve25519"
        "github.com/agl/ed25519"
+       "golang.org/x/crypto/curve25519"
 )

 func TestCurve25519Conversion(t *testing.T) {

Also, please run gofmt ;)

Making a release would help to package your software by 3rd parties (linux distros, bsds, etc) and it would put an end to a dilemma of which version to put in packages. For example, experimental versions of FreeBSD and OpenBSD packages use 20170116 (the date of the last commit):

https://github.com/torbsd/freebsd-ports/tree/egypcio/security/go-ed25519
https://github.com/torbsd/openbsd-ports/tree/master/security/go-ed25519

I use a made-up version 0.0.1 in pkgsrc:
https://wip.pkgsrc.org/cgi-bin/gitweb.cgi?p=pkgsrc-wip.git;a=commit;h=a22a3c3bd039da8b75f79f12e2ca06e1533324dd

I don't mind if you version your release by date or as n.n.n because my package isn't yet in the main pkgsrc repository but it's probably worth checking how major linux distributions version your software.

Hi,

this request might be slightly beyond the scope of this project, but an answer would be very much gratefully received! This post discusses the use of ed25519 and Schnorr signatures.

https://ripple.com/dev-blog/curves-with-a-twist/

It would be incredibly useful to crypto-novices like myself if your package could be extended with the feature of, or an example provided of how to create the described multi signature and/or threshold signatures using the ed25519 curve.

The aim for my project is to have a transaction which is encoded and then hashed and then multiple private key holders can sign this hash and if at least a majority of signatures from the group do so, the transaction is verified.

I can see that pond does something similar here:

https://github.com/agl/pond/blob/master/bbssig/bbssig.go

But perhaps that is more complicated than the Schnorr signature method due to the membership addition and revocation?

Thanks for any response!

Hi. I just stumbled on a project still importing this. As far as I understand, this code has long since migrated to https://godoc.org/golang.org/x/crypto/ed25519 and this repo may perhaps be used for future experiments (<- #18 (comment) ).

However, this repo still keeps coming up in searches, e.g. https://godoc.org/?q=ed25519 and nothing guides people to the more stable variant. To minimize confusion and likelihood of people picking the wrong one, it would probably be best to neuter this repo somehow. As an outsider, this issue showing up should at least nudge people in the right direction. Hopefully you'll have to time to do something a bit more.

Thanks for all your work!

If I have two edwards25519.ExtendedGroupElement, how do I add them on the curve? I don't see a function for it, but it would be very useful.

Here is an implementation of it in Python:
https://github.com/vbuterin/ed25519/blob/5b4f873bc88de51a3999994e30cb3a3759948308/ed25519.py#L170

I would port it, but I don't know what D is.

Could you tell me under which conditions the code may be used ?

Please expand the "..." and document where does exponents (26, 51, ...) come from.

Please document a bit what the constants mean here:
https://github.com/agl/ed25519/blob/278e1ec8e8a6e017cd07577924d6766039146ced/edwards25519/const.go

Hi,

I learned of this bug was found by @tankf33der. Contrary to the original paper, the Elligator 2 representative of of a public key is not always canonical. That is, this library does not make sure the output stay between 0 and (p-1)/2 (that is, 2²⁵⁴-10).

The mapping is such that for each point on the curve we can map, two representative (r1 and r2) map to that point on the curve, and those points are such that r1+r2=(2²⁵⁵-19). Which means one of them is in [0, 2²⁵⁴-11], and the other is in [2²⁵⁴-10, 2²⁵⁵-18]. We are supposed to chose the smaller of the two. If we don't, there is no guarantee the distribution of canonical and non-canonical output will be even. And if it's not, we'll introduce exactly the kind of bias Elligator was meant to eliminate, and basically ruin everything.

The problem can be reproduced with this code:

package main
import "fmt"
import "github.com/agl/ed25519/extra25519"

func main() {
    var pub, rep, prv [32]byte
    extra25519.ScalarBaseMult(&pub, &rep, &prv)
    fmt.Println("prv", prv)
    fmt.Println("pub", pub)
    fmt.Println("rep", rep)
}

We get this output:

prv [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
pub [47 229 125 163 71 205 98 67 21 40 218 172 95 187 41 7 48 255 246 132 175 196 207 194 237 144 153 95 88 203 59 116]
rep [57 78 64 213 212 109 157 152 11 141 41 37 247 235 7 83 93 151 203 254 156 94 163 90 91 71 179 230 39 79 78 120]

What we are most interested in is the most significant byte of rep, whose value, 120, exceeds 63. Which means the representative as a whole exceeds 2²⁵⁴, and is therefore not canonical. The test suite doesn't spot the error because the round trip works: as I've said two representatives map to the same point, r and p-r.

Pull request #12, which by the way is over 5 years old, aims to fix the issue (I haven't tested). I encourage desperate users to try and merge it on their own.

There can be performance gains on verification if you remove the constant-time operations. I see no reason for verification to have side-channel safety - all of the inputs are public knowledge anyway.

Are there any benchmarks for the number of key generations per second? How does this library compare to https://ed25519.cr.yp.to/index.html?

Hi

It would be great if you tagged the current HEAD with v1.0.0, and in the future, occasionally bump the version and make new tags with new releases. I suggest using the semver.org versioning scheme, where you have major.minor.patch, and you bump the major for incompatible changes and the minor for compatible changes to the API.

It is hard to understand how the paper relates to this function for non-experts. You wrote a nice blog post explaining it in https://www.imperialviolet.org/2013/12/25/elligator.html, which I found through googling only.

Please reference this instead of the paper (the paper is in the blog post, after all).

crypto\ed25519\ed25519.go:32:2: use of internal package golang.org/x/crypto/ed25519/internal/edwards25519 not allowed