123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233 |
- // Copyright (c) 2019 The Go Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style
- // license that can be found in the LICENSE file.
- package edwards25519
- import (
- "bytes"
- "encoding/hex"
- "math/big"
- mathrand "math/rand"
- "reflect"
- "testing"
- "testing/quick"
- )
- // Generate returns a valid (reduced modulo l) Scalar with a distribution
- // weighted towards high, low, and edge values.
- func (Scalar) Generate(rand *mathrand.Rand, size int) reflect.Value {
- s := scZero
- diceRoll := rand.Intn(100)
- switch {
- case diceRoll == 0:
- case diceRoll == 1:
- s = scOne
- case diceRoll == 2:
- s = scMinusOne
- case diceRoll < 5:
- // Generate a low scalar in [0, 2^125).
- rand.Read(s.s[:16])
- s.s[15] &= (1 << 5) - 1
- case diceRoll < 10:
- // Generate a high scalar in [2^252, 2^252 + 2^124).
- s.s[31] = 1 << 4
- rand.Read(s.s[:16])
- s.s[15] &= (1 << 4) - 1
- default:
- // Generate a valid scalar in [0, l) by returning [0, 2^252) which has a
- // negligibly different distribution (the former has a 2^-127.6 chance
- // of being out of the latter range).
- rand.Read(s.s[:])
- s.s[31] &= (1 << 4) - 1
- }
- return reflect.ValueOf(s)
- }
- // quickCheckConfig1024 will make each quickcheck test run (1024 * -quickchecks)
- // times. The default value of -quickchecks is 100.
- var quickCheckConfig1024 = &quick.Config{MaxCountScale: 1 << 10}
- func TestScalarGenerate(t *testing.T) {
- f := func(sc Scalar) bool {
- return isReduced(&sc)
- }
- if err := quick.Check(f, quickCheckConfig1024); err != nil {
- t.Errorf("generated unreduced scalar: %v", err)
- }
- }
- func TestScalarSetCanonicalBytes(t *testing.T) {
- f1 := func(in [32]byte, sc Scalar) bool {
- // Mask out top 4 bits to guarantee value falls in [0, l).
- in[len(in)-1] &= (1 << 4) - 1
- if _, err := sc.SetCanonicalBytes(in[:]); err != nil {
- return false
- }
- return bytes.Equal(in[:], sc.Bytes()) && isReduced(&sc)
- }
- if err := quick.Check(f1, quickCheckConfig1024); err != nil {
- t.Errorf("failed bytes->scalar->bytes round-trip: %v", err)
- }
- f2 := func(sc1, sc2 Scalar) bool {
- if _, err := sc2.SetCanonicalBytes(sc1.Bytes()); err != nil {
- return false
- }
- return sc1 == sc2
- }
- if err := quick.Check(f2, quickCheckConfig1024); err != nil {
- t.Errorf("failed scalar->bytes->scalar round-trip: %v", err)
- }
- b := scMinusOne.s
- b[31] += 1
- s := scOne
- if out, err := s.SetCanonicalBytes(b[:]); err == nil {
- t.Errorf("SetCanonicalBytes worked on a non-canonical value")
- } else if s != scOne {
- t.Errorf("SetCanonicalBytes modified its receiver")
- } else if out != nil {
- t.Errorf("SetCanonicalBytes did not return nil with an error")
- }
- }
- func TestScalarSetUniformBytes(t *testing.T) {
- mod, _ := new(big.Int).SetString("27742317777372353535851937790883648493", 10)
- mod.Add(mod, new(big.Int).Lsh(big.NewInt(1), 252))
- f := func(in [64]byte, sc Scalar) bool {
- sc.SetUniformBytes(in[:])
- if !isReduced(&sc) {
- return false
- }
- scBig := bigIntFromLittleEndianBytes(sc.s[:])
- inBig := bigIntFromLittleEndianBytes(in[:])
- return inBig.Mod(inBig, mod).Cmp(scBig) == 0
- }
- if err := quick.Check(f, quickCheckConfig1024); err != nil {
- t.Error(err)
- }
- }
- func TestScalarSetBytesWithClamping(t *testing.T) {
- // Generated with libsodium.js 1.0.18 crypto_scalarmult_ed25519_base.
- random := "633d368491364dc9cd4c1bf891b1d59460face1644813240a313e61f2c88216e"
- s := new(Scalar).SetBytesWithClamping(decodeHex(random))
- p := new(Point).ScalarBaseMult(s)
- want := "1d87a9026fd0126a5736fe1628c95dd419172b5b618457e041c9c861b2494a94"
- if got := hex.EncodeToString(p.Bytes()); got != want {
- t.Errorf("random: got %q, want %q", got, want)
- }
- zero := "0000000000000000000000000000000000000000000000000000000000000000"
- s = new(Scalar).SetBytesWithClamping(decodeHex(zero))
- p = new(Point).ScalarBaseMult(s)
- want = "693e47972caf527c7883ad1b39822f026f47db2ab0e1919955b8993aa04411d1"
- if got := hex.EncodeToString(p.Bytes()); got != want {
- t.Errorf("zero: got %q, want %q", got, want)
- }
- one := "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
- s = new(Scalar).SetBytesWithClamping(decodeHex(one))
- p = new(Point).ScalarBaseMult(s)
- want = "12e9a68b73fd5aacdbcaf3e88c46fea6ebedb1aa84eed1842f07f8edab65e3a7"
- if got := hex.EncodeToString(p.Bytes()); got != want {
- t.Errorf("one: got %q, want %q", got, want)
- }
- }
- func bigIntFromLittleEndianBytes(b []byte) *big.Int {
- bb := make([]byte, len(b))
- for i := range b {
- bb[i] = b[len(b)-i-1]
- }
- return new(big.Int).SetBytes(bb)
- }
- func TestScalarMultiplyDistributesOverAdd(t *testing.T) {
- multiplyDistributesOverAdd := func(x, y, z Scalar) bool {
- // Compute t1 = (x+y)*z
- var t1 Scalar
- t1.Add(&x, &y)
- t1.Multiply(&t1, &z)
- // Compute t2 = x*z + y*z
- var t2 Scalar
- var t3 Scalar
- t2.Multiply(&x, &z)
- t3.Multiply(&y, &z)
- t2.Add(&t2, &t3)
- return t1 == t2 && isReduced(&t1) && isReduced(&t3)
- }
- if err := quick.Check(multiplyDistributesOverAdd, quickCheckConfig1024); err != nil {
- t.Error(err)
- }
- }
- func TestScalarAddLikeSubNeg(t *testing.T) {
- addLikeSubNeg := func(x, y Scalar) bool {
- // Compute t1 = x - y
- var t1 Scalar
- t1.Subtract(&x, &y)
- // Compute t2 = -y + x
- var t2 Scalar
- t2.Negate(&y)
- t2.Add(&t2, &x)
- return t1 == t2 && isReduced(&t1)
- }
- if err := quick.Check(addLikeSubNeg, quickCheckConfig1024); err != nil {
- t.Error(err)
- }
- }
- func TestScalarNonAdjacentForm(t *testing.T) {
- s := Scalar{[32]byte{
- 0x1a, 0x0e, 0x97, 0x8a, 0x90, 0xf6, 0x62, 0x2d,
- 0x37, 0x47, 0x02, 0x3f, 0x8a, 0xd8, 0x26, 0x4d,
- 0xa7, 0x58, 0xaa, 0x1b, 0x88, 0xe0, 0x40, 0xd1,
- 0x58, 0x9e, 0x7b, 0x7f, 0x23, 0x76, 0xef, 0x09,
- }}
- expectedNaf := [256]int8{
- 0, 13, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, -9, 0, 0, 0, 0, -11, 0, 0, 0, 0, 3, 0, 0, 0, 0, 1,
- 0, 0, 0, 0, 9, 0, 0, 0, 0, -5, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 11, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0,
- -9, 0, 0, 0, 0, 0, -3, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 9, 0,
- 0, 0, 0, -15, 0, 0, 0, 0, -7, 0, 0, 0, 0, -9, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 13, 0, 0, 0, 0, 0, -3, 0,
- 0, 0, 0, -11, 0, 0, 0, 0, -7, 0, 0, 0, 0, -13, 0, 0, 0, 0, 11, 0, 0, 0, 0, -9, 0, 0, 0, 0, 0, 1, 0, 0,
- 0, 0, 0, -15, 0, 0, 0, 0, 1, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 13, 0, 0, 0,
- 0, 0, 0, 11, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, -9, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 7,
- 0, 0, 0, 0, 0, -15, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 15, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
- }
- sNaf := s.nonAdjacentForm(5)
- for i := 0; i < 256; i++ {
- if expectedNaf[i] != sNaf[i] {
- t.Errorf("Wrong digit at position %d, got %d, expected %d", i, sNaf[i], expectedNaf[i])
- }
- }
- }
- type notZeroScalar Scalar
- func (notZeroScalar) Generate(rand *mathrand.Rand, size int) reflect.Value {
- var s Scalar
- for s == scZero {
- s = Scalar{}.Generate(rand, size).Interface().(Scalar)
- }
- return reflect.ValueOf(notZeroScalar(s))
- }
- func TestScalarEqual(t *testing.T) {
- if scOne.Equal(&scMinusOne) == 1 {
- t.Errorf("scOne.Equal(&scMinusOne) is true")
- }
- if scMinusOne.Equal(&scMinusOne) == 0 {
- t.Errorf("scMinusOne.Equal(&scMinusOne) is false")
- }
- }
|