From 34e400476221f6e1861db6e3ccc249560f16aa18c48a9d9b410098b439ff921a Mon Sep 17 00:00:00 2001 From: Sergey Matveev Date: Wed, 4 Jun 2025 15:51:43 +0300 Subject: [PATCH] strup761 instead of sntrup4591761 --- go/cm/cmd/cmenctool/main.go | 80 +- go/cm/cmd/cmenctool/multirecipient.t | 4 +- go/cm/cmd/cmenctool/prv-encrypted.t | 2 +- go/cm/cmd/cmenctool/pub.t | 2 +- go/cm/cmd/cmkeytool/kem-generation.t | 2 +- go/cm/cmd/cmkeytool/main.go | 10 +- go/cm/enc/kem.go | 4 +- go/cm/enc/sntrup4591761-x25519/algo.go | 6 - go/cm/enc/sntrup761-x25519/algo.go | 6 + .../kp.go | 24 +- go/cm/enc/sntrup761-x25519/sntrup761/README | 4 + .../enc/sntrup761-x25519/sntrup761/kem/kem.go | 118 +++ .../sntrup761/kem/ntruprime/doc.go | 10 + .../kem/ntruprime/internal/Decode.go | 67 ++ .../kem/ntruprime/internal/Divmod.go | 102 ++ .../kem/ntruprime/internal/Encode.go | 42 + .../kem/ntruprime/sntrup761/ntruprime.go | 971 ++++++++++++++++++ .../sntrup761/pke/ntruprime/kem/kem.go | 21 + .../ntruprime/kem/schemes/sntrup/schemes.go | 39 + .../pke/ntruprime/sntrup761/params.go | 25 + go/cm/go.mod | 1 - go/cm/go.sum | 2 - ...-blake2b => sntrup761-x25519-hkdf-blake2b} | 16 +- spec/cm/prv/sntrup4591761-x25519 | 5 - spec/cm/prv/sntrup761-x25519 | 5 + ...{sntrup4591761-x25519 => sntrup761-x25519} | 10 +- tcl/schemas/kem-with-encap.tcl | 2 +- 27 files changed, 1501 insertions(+), 79 deletions(-) delete mode 100644 go/cm/enc/sntrup4591761-x25519/algo.go create mode 100644 go/cm/enc/sntrup761-x25519/algo.go rename go/cm/enc/{sntrup4591761-x25519 => sntrup761-x25519}/kp.go (66%) create mode 100644 go/cm/enc/sntrup761-x25519/sntrup761/README create mode 100644 go/cm/enc/sntrup761-x25519/sntrup761/kem/kem.go create mode 100644 go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/doc.go create mode 100644 go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/internal/Decode.go create mode 100644 go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/internal/Divmod.go create mode 100644 go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/internal/Encode.go create mode 100644 go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/sntrup761/ntruprime.go create mode 100644 go/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/kem/kem.go create mode 100644 go/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/kem/schemes/sntrup/schemes.go create mode 100644 go/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/sntrup761/params.go rename spec/cm/kem/{sntrup4591761-x25519-hkdf-blake2b => sntrup761-x25519-hkdf-blake2b} (72%) delete mode 100644 spec/cm/prv/sntrup4591761-x25519 create mode 100644 spec/cm/prv/sntrup761-x25519 rename spec/cm/pub/{sntrup4591761-x25519 => sntrup761-x25519} (56%) diff --git a/go/cm/cmd/cmenctool/main.go b/go/cm/cmd/cmenctool/main.go index fd6028c..76bc585 100644 --- a/go/cm/cmd/cmenctool/main.go +++ b/go/cm/cmd/cmenctool/main.go @@ -31,7 +31,6 @@ import ( "os" "strconv" - "github.com/companyzero/sntrup4591761" "github.com/google/uuid" "go.cypherpunks.su/balloon/v3" "golang.org/x/crypto/blake2b" @@ -46,7 +45,9 @@ import ( chapoly "go.cypherpunks.su/keks/cm/enc/chapoly" mceliece6960119x25519 "go.cypherpunks.su/keks/cm/enc/mceliece6960119-x25519" mceliece6960119 "go.cypherpunks.su/keks/cm/enc/mceliece6960119-x25519/mceliece6960119" - sntrup4591761x25519 "go.cypherpunks.su/keks/cm/enc/sntrup4591761-x25519" + sntrup761x25519 "go.cypherpunks.su/keks/cm/enc/sntrup761-x25519" + sntrup761kem "go.cypherpunks.su/keks/cm/enc/sntrup761-x25519/sntrup761/kem" + sntrup761 "go.cypherpunks.su/keks/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/sntrup761" cmhash "go.cypherpunks.su/keks/cm/hash" "go.cypherpunks.su/keks/cm/sign" "go.cypherpunks.su/keks/schema" @@ -246,7 +247,7 @@ func main() { switch kemMap["a"] { case cmballoon.BalloonBLAKE2bHKDF: err = schema.Check("kem-balloon-blake2b-hkdf", cmenc.EncryptedSchemas, kem) - case sntrup4591761x25519.SNTRUP4591761X25519HKDFBLAKE2b: + case sntrup761x25519.SNTRUP761X25519HKDFBLAKE2b: fallthrough case mceliece6960119x25519.ClassicMcEliece6960119X25519HKDFSHAKE256: err = schema.Check("kem-with-encap", cmenc.EncryptedSchemas, kem) @@ -284,7 +285,7 @@ func main() { log.Println(kemIdx, kem.A, "wrong key len, skipping") continue } - case sntrup4591761x25519.SNTRUP4591761X25519HKDFBLAKE2b: + case sntrup761x25519.SNTRUP761X25519HKDFBLAKE2b: if len(prvs) == 0 { log.Println(kemIdx, kem.A, "skipping because no private key specified") continue @@ -292,36 +293,41 @@ func main() { if kem.Encap == nil { log.Fatalln("missing encap") } - if len(kem.Encap) != sntrup4591761.CiphertextSize+X25519KeyLen { + scheme := sntrup761.Scheme() + if len(kem.Encap) != scheme.CiphertextSize()+X25519KeyLen { log.Fatalln("invalid encap len") } for _, prv := range prvs { - if prv.A != sntrup4591761x25519.SNTRUP4591761X25519 { + if prv.A != sntrup761x25519.SNTRUP761X25519 { continue } - if len(prv.V) != sntrup4591761.PrivateKeySize+X25519KeyLen { + if len(prv.V) != scheme.PrivateKeySize()+X25519KeyLen { log.Fatalln("invalid private keys len") } - var ourSNTRUP sntrup4591761.PrivateKey - copy(ourSNTRUP[:], prv.V) + var ourSNTRUP sntrup761kem.PrivateKey + ourSNTRUP, err = scheme.UnmarshalBinaryPrivateKey( + prv.V[:scheme.PrivateKeySize()], + ) + if err != nil { + log.Fatal(err) + } x25519 := ecdh.X25519() var ourX25519 *ecdh.PrivateKey ourX25519, err = x25519.NewPrivateKey( - prv.V[sntrup4591761.PrivateKeySize:], + prv.V[scheme.PrivateKeySize():], ) if err != nil { log.Fatal(err) } - var theirSNTRUP sntrup4591761.Ciphertext - copy(theirSNTRUP[:], kem.Encap) - keySNTRUP, eq := sntrup4591761.Decapsulate(&theirSNTRUP, &ourSNTRUP) - if eq != 1 { - log.Println("can not KEM, skipping") + theirSNTRUP := kem.Encap[:scheme.CiphertextSize()] + var keySNTRUP []byte + keySNTRUP, err = scheme.Decapsulate(ourSNTRUP, theirSNTRUP) + if err != nil { continue } var theirX25519 *ecdh.PublicKey theirX25519, err = x25519.NewPublicKey( - kem.Encap[sntrup4591761.CiphertextSize:], + kem.Encap[scheme.CiphertextSize():], ) if err != nil { log.Fatal(err) @@ -332,9 +338,15 @@ func main() { log.Fatal(err) } { + + var ourSNTRUPPub []byte + ourSNTRUPPub, err = ourSNTRUP.Public().MarshalBinary() + if err != nil { + log.Fatal(err) + } ctHash := blake2b.Sum512(kem.Encap) pkHash := blake2b.Sum512(append( - ourSNTRUP[382:], + ourSNTRUPPub, ourX25519.PublicKey().Bytes()..., )) ikm := bytes.Join([][]byte{ @@ -350,7 +362,7 @@ func main() { blake2bHash, prk, string(append( - []byte(cmenc.SNTRUP4591761X25519Info), + []byte(cmenc.SNTRUP761X25519Info), encrypted.Id[:]...)), chacha20poly1305.KeySize, ) @@ -570,25 +582,29 @@ func main() { } for pubId, pub := range pubs { switch pub.A { - case sntrup4591761x25519.SNTRUP4591761X25519: - if len(pub.V) != sntrup4591761.PublicKeySize+X25519KeyLen { + case sntrup761x25519.SNTRUP761X25519: + scheme := sntrup761.Scheme() + if len(pub.V) != scheme.PublicKeySize()+X25519KeyLen { log.Fatalln("invalid public keys len") } - var theirSNTRUP sntrup4591761.PublicKey - copy(theirSNTRUP[:], pub.V[:sntrup4591761.PublicKeySize]) + var theirSNTRUP sntrup761kem.PublicKey + theirSNTRUP, err = scheme.UnmarshalBinaryPublicKey( + pub.V[:scheme.PublicKeySize()], + ) + if err != nil { + log.Fatal(err) + } x25519 := ecdh.X25519() var theirX25519 *ecdh.PublicKey theirX25519, err = x25519.NewPublicKey( - pub.V[sntrup4591761.PublicKeySize:], + pub.V[scheme.PublicKeySize():], ) if err != nil { log.Fatal(err) } - var ciphertext *sntrup4591761.Ciphertext - var keySNTRUP *sntrup4591761.SharedKey - ciphertext, keySNTRUP, err = sntrup4591761.Encapsulate( - rand.Reader, &theirSNTRUP, - ) + var ciphertext []byte + var keySNTRUP []byte + ciphertext, keySNTRUP, err = scheme.Encapsulate(theirSNTRUP) if err != nil { log.Fatal(err) } @@ -604,14 +620,14 @@ func main() { log.Fatal(err) } kem := cmenc.KEM{ - A: sntrup4591761x25519.SNTRUP4591761X25519HKDFBLAKE2b, - Encap: append(ciphertext[:], ourPubX25519.Bytes()...), + A: sntrup761x25519.SNTRUP761X25519HKDFBLAKE2b, + Encap: append(ciphertext, ourPubX25519.Bytes()...), } { ctHash := blake2b.Sum512(kem.Encap) pkHash := blake2b.Sum512(pub.V) ikm := bytes.Join([][]byte{ - keySNTRUP[:], keyX25519, ctHash[:], pkHash[:], + keySNTRUP, keyX25519, ctHash[:], pkHash[:], }, []byte{}) var prk []byte prk, err = hkdf.Extract(blake2bHash, ikm, nil) @@ -622,7 +638,7 @@ func main() { kek, err = hkdf.Expand( blake2bHash, prk, - string(append([]byte(cmenc.SNTRUP4591761X25519Info), id[:]...)), + string(append([]byte(cmenc.SNTRUP761X25519Info), id[:]...)), chacha20poly1305.KeySize, ) if err != nil { diff --git a/go/cm/cmd/cmenctool/multirecipient.t b/go/cm/cmd/cmenctool/multirecipient.t index 09fa7e3..a37cbab 100755 --- a/go/cm/cmd/cmenctool/multirecipient.t +++ b/go/cm/cmd/cmenctool/multirecipient.t @@ -8,10 +8,10 @@ TMPDIR=${TMPDIR:-/tmp} dd if=/dev/urandom of=$TMPDIR/enc.data bs=300K count=1 2>/dev/null test_expect_success "0: pub generation" "cmkeytool \ - -algo sntrup4591761-x25519 -ku kem -sub N=0 \ + -algo sntrup761-x25519 -ku kem -sub N=0 \ 5>$TMPDIR/enc.0.pub 9>$TMPDIR/enc.0.prv" test_expect_success "1: pub generation" "cmkeytool \ - -algo sntrup4591761-x25519 -ku kem -sub N=1 \ + -algo sntrup761-x25519 -ku kem -sub N=1 \ 5>$TMPDIR/enc.1.pub 9>$TMPDIR/enc.1.prv" test_expect_success "encrypting" " diff --git a/go/cm/cmd/cmenctool/prv-encrypted.t b/go/cm/cmd/cmenctool/prv-encrypted.t index 59f8c99..48ad4e1 100755 --- a/go/cm/cmd/cmenctool/prv-encrypted.t +++ b/go/cm/cmd/cmenctool/prv-encrypted.t @@ -5,7 +5,7 @@ test_description="Check passphrase-encrypted key decryption" TMPDIR=${TMPDIR:-/tmp} -cmkeytool -algo sntrup4591761-x25519 -ku kem -sub A=KEY 5>$TMPDIR/enc.pub 9>$TMPDIR/enc.prv +cmkeytool -algo sntrup761-x25519 -ku kem -sub A=KEY 5>$TMPDIR/enc.pub 9>$TMPDIR/enc.prv dd if=/dev/urandom of=$TMPDIR/enc.data bs=12K count=1 2>/dev/null export CMENCTOOL_PASSPHRASE=$(dd if=/dev/urandom bs=32 count=1 2>/dev/null | xxd -p) balloonparams="-balloon-s 123 -balloon-t 2" diff --git a/go/cm/cmd/cmenctool/pub.t b/go/cm/cmd/cmenctool/pub.t index 19908ee..c1bc7b8 100755 --- a/go/cm/cmd/cmenctool/pub.t +++ b/go/cm/cmd/cmenctool/pub.t @@ -13,7 +13,7 @@ algo0=$algo test_expect_success "$algo: pub generation" "cmkeytool \ -algo $algo -ku kem -sub A=$algo \ 5>$TMPDIR/enc.$algo.pub 9>$TMPDIR/enc.$algo.prv" -algo=sntrup4591761-x25519 +algo=sntrup761-x25519 algo1=$algo test_expect_success "$algo: pub generation" "cmkeytool \ -algo $algo -ku kem -sub A=$algo \ diff --git a/go/cm/cmd/cmkeytool/kem-generation.t b/go/cm/cmd/cmkeytool/kem-generation.t index 8a27669..f25cb7f 100755 --- a/go/cm/cmd/cmkeytool/kem-generation.t +++ b/go/cm/cmd/cmkeytool/kem-generation.t @@ -6,7 +6,7 @@ test_description="Check KEM certificates generation" TMPDIR=${TMPDIR:-/tmp} echo "mceliece6960119-x25519 -sntrup4591761-x25519" | while read algo ; do +sntrup761-x25519" | while read algo ; do test_expect_success "$algo: generation" "cmkeytool \ -algo $algo \ diff --git a/go/cm/cmd/cmkeytool/main.go b/go/cm/cmd/cmkeytool/main.go index 142c09b..9bec662 100644 --- a/go/cm/cmd/cmkeytool/main.go +++ b/go/cm/cmd/cmkeytool/main.go @@ -31,7 +31,7 @@ import ( "go.cypherpunks.su/keks" "go.cypherpunks.su/keks/cm" mceliece6960119x25519 "go.cypherpunks.su/keks/cm/enc/mceliece6960119-x25519" - sntrup4591761x25519 "go.cypherpunks.su/keks/cm/enc/sntrup4591761-x25519" + sntrup761x25519 "go.cypherpunks.su/keks/cm/enc/sntrup761-x25519" cmhash "go.cypherpunks.su/keks/cm/hash" "go.cypherpunks.su/keks/cm/sign" ed25519blake2b "go.cypherpunks.su/keks/cm/sign/ed25519-blake2b" @@ -96,7 +96,7 @@ func main() { ed25519blake2b.Ed25519BLAKE2b, gost.GOST3410256A, gost.GOST3410512C, - sntrup4591761x25519.SNTRUP4591761X25519, + sntrup761x25519.SNTRUP761X25519, mceliece6960119x25519.ClassicMcEliece6960119X25519, slhdsa.SLHDSASHAKE256s, } @@ -176,8 +176,8 @@ func main() { prvRaw, pub, err = ed25519blake2b.NewKeypair() case gost.GOST3410256A, gost.GOST3410512C: prvRaw, pub, err = gost.NewKeypair(*algo) - case sntrup4591761x25519.SNTRUP4591761X25519: - prvRaw, pub, err = sntrup4591761x25519.NewKeypair() + case sntrup761x25519.SNTRUP761X25519: + prvRaw, pub, err = sntrup761x25519.NewKeypair() case mceliece6960119x25519.ClassicMcEliece6960119X25519: prvRaw, pub, err = mceliece6960119x25519.NewKeypair() case slhdsa.SLHDSASHAKE256s: @@ -207,7 +207,7 @@ func main() { } var hasher hash.Hash switch *algo { - case ed25519blake2b.Ed25519BLAKE2b, sntrup4591761x25519.SNTRUP4591761X25519: + case ed25519blake2b.Ed25519BLAKE2b, sntrup761x25519.SNTRUP761X25519: hasher = cmhash.ByName(cmhash.BLAKE2b256) case gost.GOST3410256A, gost.GOST3410512C: hasher = cmhash.ByName(cmhash.Streebog256) diff --git a/go/cm/enc/kem.go b/go/cm/enc/kem.go index a5ca55f..1d1521b 100644 --- a/go/cm/enc/kem.go +++ b/go/cm/enc/kem.go @@ -5,9 +5,9 @@ import ( ) const ( - SNTRUP4591761X25519Info = "cm/encrypted/sntrup4591761-x25519-hkdf-blake2b" - ClassicMcEliece6960119X25519Info = "cm/encrypted/mceliece6960119-x25519-hkdf-shake256" + SNTRUP761X25519Info = "cm/encrypted/sntrup761-x25519-hkdf-blake2b" + ClassicMcEliece6960119X25519Info = "cm/encrypted/mceliece6960119-x25519-hkdf-shake256" ClassicMcEliece6960119X25519DecapInfo = "cm/encrypted/mceliece6960119-x25519-hkdf-shake256/decap" ) diff --git a/go/cm/enc/sntrup4591761-x25519/algo.go b/go/cm/enc/sntrup4591761-x25519/algo.go deleted file mode 100644 index 16caaf0..0000000 --- a/go/cm/enc/sntrup4591761-x25519/algo.go +++ /dev/null @@ -1,6 +0,0 @@ -package sntrup4591761x25519 - -const ( - SNTRUP4591761X25519 = "sntrup4591761-x25519" - SNTRUP4591761X25519HKDFBLAKE2b = "sntrup4591761-x25519-hkdf-blake2b" -) diff --git a/go/cm/enc/sntrup761-x25519/algo.go b/go/cm/enc/sntrup761-x25519/algo.go new file mode 100644 index 0000000..f148ee0 --- /dev/null +++ b/go/cm/enc/sntrup761-x25519/algo.go @@ -0,0 +1,6 @@ +package sntrup761x25519 + +const ( + SNTRUP761X25519 = "sntrup761-x25519" + SNTRUP761X25519HKDFBLAKE2b = "sntrup761-x25519-hkdf-blake2b" +) diff --git a/go/cm/enc/sntrup4591761-x25519/kp.go b/go/cm/enc/sntrup761-x25519/kp.go similarity index 66% rename from go/cm/enc/sntrup4591761-x25519/kp.go rename to go/cm/enc/sntrup761-x25519/kp.go index 0a60666..5d6732a 100644 --- a/go/cm/enc/sntrup4591761-x25519/kp.go +++ b/go/cm/enc/sntrup761-x25519/kp.go @@ -13,19 +13,21 @@ // You should have received a copy of the GNU Lesser General Public // License along with this program. If not, see . -package sntrup4591761x25519 +package sntrup761x25519 import ( "crypto/ecdh" "crypto/rand" - "github.com/companyzero/sntrup4591761" + "go.cypherpunks.su/keks/cm/enc/sntrup761-x25519/sntrup761/kem" + "go.cypherpunks.su/keks/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/sntrup761" ) func NewKeypair() (prv, pub []byte, err error) { - var pubSNTRUP *sntrup4591761.PublicKey - var prvSNTRUP *sntrup4591761.PrivateKey - pubSNTRUP, prvSNTRUP, err = sntrup4591761.GenerateKey(rand.Reader) + s := sntrup761.Scheme() + var pubSNTRUP kem.PublicKey + var prvSNTRUP kem.PrivateKey + pubSNTRUP, prvSNTRUP, err = s.GenerateKeyPair() if err != nil { return } @@ -34,8 +36,16 @@ func NewKeypair() (prv, pub []byte, err error) { if err != nil { return } + prv, err = prvSNTRUP.MarshalBinary() + if err != nil { + return + } + pub, err = pubSNTRUP.MarshalBinary() + if err != nil { + return + } pubX25519 := prvX25519.PublicKey() - prv = append(prvSNTRUP[:], prvX25519.Bytes()...) - pub = append(pubSNTRUP[:], pubX25519.Bytes()...) + prv = append(prv, prvX25519.Bytes()...) + pub = append(pub, pubX25519.Bytes()...) return } diff --git a/go/cm/enc/sntrup761-x25519/sntrup761/README b/go/cm/enc/sntrup761-x25519/sntrup761/README new file mode 100644 index 0000000..e7b08a2 --- /dev/null +++ b/go/cm/enc/sntrup761-x25519/sntrup761/README @@ -0,0 +1,4 @@ +Go/Git is unable to fetch (https://github.com/cloudflare/circl) +pull-request's commit (e8d7edb133624b7fa80e66fd9f6eb97f3f1cd361) to +github.com/cloudflare/circl containing NTRU prime implementation +(https://github.com/cloudflare/circl/pull/384). So copy it here. diff --git a/go/cm/enc/sntrup761-x25519/sntrup761/kem/kem.go b/go/cm/enc/sntrup761-x25519/sntrup761/kem/kem.go new file mode 100644 index 0000000..ede6fee --- /dev/null +++ b/go/cm/enc/sntrup761-x25519/sntrup761/kem/kem.go @@ -0,0 +1,118 @@ +// Package kem provides a unified interface for KEM schemes. +// +// A register of schemes is available in the package +// +// github.com/cloudflare/circl/kem/schemes +package kem + +import ( + "encoding" + "errors" +) + +// A KEM public key +type PublicKey interface { + // Returns the scheme for this public key + Scheme() Scheme + + encoding.BinaryMarshaler + Equal(PublicKey) bool +} + +// A KEM private key +type PrivateKey interface { + // Returns the scheme for this private key + Scheme() Scheme + + encoding.BinaryMarshaler + Equal(PrivateKey) bool + Public() PublicKey +} + +// A Scheme represents a specific instance of a KEM. +type Scheme interface { + // Name of the scheme + Name() string + + // GenerateKeyPair creates a new key pair. + GenerateKeyPair() (PublicKey, PrivateKey, error) + + // Encapsulate generates a shared key ss for the public key and + // encapsulates it into a ciphertext ct. + Encapsulate(pk PublicKey) (ct, ss []byte, err error) + + // Returns the shared key encapsulated in ciphertext ct for the + // private key sk. + Decapsulate(sk PrivateKey, ct []byte) ([]byte, error) + + // Unmarshals a PublicKey from the provided buffer. + UnmarshalBinaryPublicKey([]byte) (PublicKey, error) + + // Unmarshals a PrivateKey from the provided buffer. + UnmarshalBinaryPrivateKey([]byte) (PrivateKey, error) + + // Size of encapsulated keys. + CiphertextSize() int + + // Size of established shared keys. + SharedKeySize() int + + // Size of packed private keys. + PrivateKeySize() int + + // Size of packed public keys. + PublicKeySize() int + + // DeriveKeyPair deterministicallly derives a pair of keys from a seed. + // Panics if the length of seed is not equal to the value returned by + // SeedSize. + DeriveKeyPair(seed []byte) (PublicKey, PrivateKey) + + // Size of seed used in DeriveKey + SeedSize() int + + // EncapsulateDeterministically generates a shared key ss for the public + // key deterministically from the given seed and encapsulates it into + // a ciphertext ct. If unsure, you're better off using Encapsulate(). + EncapsulateDeterministically(pk PublicKey, seed []byte) ( + ct, ss []byte, err error) + + // Size of seed used in EncapsulateDeterministically(). + EncapsulationSeedSize() int +} + +// AuthScheme represents a KEM that supports authenticated key encapsulation. +type AuthScheme interface { + Scheme + AuthEncapsulate(pkr PublicKey, sks PrivateKey) (ct, ss []byte, err error) + AuthEncapsulateDeterministically(pkr PublicKey, sks PrivateKey, seed []byte) (ct, ss []byte, err error) + AuthDecapsulate(skr PrivateKey, ct []byte, pks PublicKey) ([]byte, error) +} + +var ( + // ErrTypeMismatch is the error used if types of, for instance, private + // and public keys don't match + ErrTypeMismatch = errors.New("types mismatch") + + // ErrSeedSize is the error used if the provided seed is of the wrong + // size. + ErrSeedSize = errors.New("wrong seed size") + + // ErrPubKeySize is the error used if the provided public key is of + // the wrong size. + ErrPubKeySize = errors.New("wrong size for public key") + + // ErrCiphertextSize is the error used if the provided ciphertext + // is of the wrong size. + ErrCiphertextSize = errors.New("wrong size for ciphertext") + + // ErrPrivKeySize is the error used if the provided private key is of + // the wrong size. + ErrPrivKeySize = errors.New("wrong size for private key") + + // ErrPubKey is the error used if the provided public key is invalid. + ErrPubKey = errors.New("invalid public key") + + // ErrCipherText is the error used if the provided ciphertext is invalid. + ErrCipherText = errors.New("invalid ciphertext") +) diff --git a/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/doc.go b/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/doc.go new file mode 100644 index 0000000..b55c96f --- /dev/null +++ b/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/doc.go @@ -0,0 +1,10 @@ +//go:generate go run gen.go + +// Package ntruprime implements the NTRU Prime IND-CCA2 secure +// key encapsulation mechanism (KEM) as submitted to round 3 of the NIST PQC +// competition and described in +// +// https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf +// +// The code is translated from the C reference implementation. +package ntruprime diff --git a/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/internal/Decode.go b/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/internal/Decode.go new file mode 100644 index 0000000..7d15e1b --- /dev/null +++ b/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/internal/Decode.go @@ -0,0 +1,67 @@ +package internal + +// TO DO: Optimize the Decode function +/* Decode(R,s,M,len) */ +/* assumes 0 < M[i] < 16384 */ +/* produces 0 <= R[i] < M[i] */ +func Decode(out []uint16, S []uint8, M []uint16, len int) { + index := 0 + if len == 1 { + if M[0] == 1 { + out[index] = 0 + } else if M[0] <= 256 { + out[index] = Uint32ModUint14(uint32(S[0]), M[0]) + } else { + out[index] = Uint32ModUint14(uint32(uint16(S[0])+((uint16(S[1]))<<8)), M[0]) + } + } + if len > 1 { + R2 := make([]uint16, (len+1)/2) + M2 := make([]uint16, (len+1)/2) + bottomr := make([]uint16, len/2) + bottomt := make([]uint32, len/2) + i := 0 + for i = 0; i < len-1; i += 2 { + m := uint32(M[i]) * uint32(M[i+1]) + + if m > 256*16383 { + bottomt[i/2] = 256 * 256 + bottomr[i/2] = uint16(S[0]) + 256*uint16(S[1]) + S = S[2:] + M2[i/2] = uint16((((m + 255) >> 8) + 255) >> 8) + } else if m >= 16384 { + bottomt[i/2] = 256 + bottomr[i/2] = uint16(S[0]) + S = S[1:] + M2[i/2] = uint16((m + 255) >> 8) + } else { + bottomt[i/2] = 1 + bottomr[i/2] = 0 + M2[i/2] = uint16(m) + } + } + if i < len { + M2[i/2] = M[i] + } + + Decode(R2, S, M2, (len+1)/2) + + for i = 0; i < len-1; i += 2 { + r := uint32(bottomr[i/2]) + var r1 uint32 + var r0 uint16 + + r += bottomt[i/2] * uint32(R2[i/2]) + Uint32DivmodUint14(&r1, &r0, r, M[i]) + r1 = uint32(Uint32ModUint14(r1, M[i+1])) /* only needed for invalid inputs */ + + out[index] = r0 + index++ + out[index] = uint16(r1) + index++ + } + if i < len { + out[index] = R2[i/2] + } + } +} diff --git a/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/internal/Divmod.go b/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/internal/Divmod.go new file mode 100644 index 0000000..f84cc43 --- /dev/null +++ b/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/internal/Divmod.go @@ -0,0 +1,102 @@ +package internal + +/* +CPU division instruction typically takes time depending on x. +This software is designed to take time independent of x. +Time still varies depending on m; user must ensure that m is constant. +Time also varies on CPUs where multiplication is variable-time. +There could be more CPU issues. +There could also be compiler issues. +*/ +// q, r = x/m +// Returns quotient and remainder +func Uint32DivmodUint14(q *uint32, r *uint16, x uint32, m uint16) { + var v uint32 = 0x80000000 + + v /= uint32(m) + + *q = 0 + + qpart := uint32(uint64(x) * uint64(v) >> 31) + + x -= qpart * uint32(m) + *q += qpart + + qpart = uint32(uint64(x) * uint64(v) >> 31) + x -= qpart * uint32(m) + *q += qpart + + x -= uint32(m) + *q += 1 + mask := -(x >> 31) + x += mask & uint32(m) + *q += mask + + *r = uint16(x) +} + +// Returns the quotient of x/m +func Uint32DivUint14(x uint32, m uint16) uint32 { + var q uint32 + var r uint16 + Uint32DivmodUint14(&q, &r, x, m) + return q +} + +// Returns the remainder of x/m +func Uint32ModUint14(x uint32, m uint16) uint16 { + var q uint32 + var r uint16 + Uint32DivmodUint14(&q, &r, x, m) + return r +} + +// Calculates quotient and remainder +func Int32DivmodUint14(q *int32, r *uint16, x int32, m uint16) { + var uq, uq2 uint32 + var ur, ur2 uint16 + var mask uint32 + + Uint32DivmodUint14(&uq, &ur, 0x80000000+uint32(x), m) + Uint32DivmodUint14(&uq2, &ur2, 0x80000000, m) + + ur -= ur2 + uq -= uq2 + mask = -(uint32)(ur >> 15) + ur += uint16(mask & uint32(m)) + uq += mask + *r = ur + *q = int32(uq) +} + +// Returns quotient of x/m +func Int32DivUint14(x int32, m uint16) int32 { + var q int32 + var r uint16 + Int32DivmodUint14(&q, &r, x, m) + return q +} + +// Returns remainder of x/m +func Int32ModUint14(x int32, m uint16) uint16 { + var q int32 + var r uint16 + Int32DivmodUint14(&q, &r, x, m) + return r +} + +// Returns -1 if x!=0; else return 0 +func Int16NonzeroMask(x int16) int { + u := uint16(x) /* 0, else 1...65535 */ + v := uint32(u) /* 0, else 1...65535 */ + v = -v /* 0, else 2^32-65535...2^32-1 */ + v >>= 31 /* 0, else 1 */ + return -int(v) /* 0, else -1 */ +} + +// Returns -1 if x<0; otherwise return 0 +func Int16NegativeMask(x int16) int { + u := uint16(x) + u >>= 15 + return -(int)(u) +} diff --git a/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/internal/Encode.go b/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/internal/Encode.go new file mode 100644 index 0000000..6c11fbd --- /dev/null +++ b/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/internal/Encode.go @@ -0,0 +1,42 @@ +package internal + +/* 0 <= R[i] < M[i] < 16384 */ +func Encode(out []uint8, R, M []uint16, len int) { + if len > 1 { + R2 := make([]uint16, (len+1)/2) + M2 := make([]uint16, (len+1)/2) + var i int + for ; len > 1; len = (len + 1) / 2 { + for i = 0; i < len-1; i += 2 { + m0 := uint32(M[i]) + r := uint32(R[i]) + uint32(R[i+1])*m0 + m := uint32(M[i+1]) * m0 + for m >= 16384 { + out[0] = uint8(r) + out = out[1:] + + r >>= 8 + m = (m + 255) >> 8 + } + R2[i/2] = uint16(r) + M2[i/2] = uint16(m) + } + if i < len { + R2[i/2] = R[i] + M2[i/2] = M[i] + } + copy(R, R2) + copy(M, M2) + } + } + if len == 1 { + r := R[0] + m := M[0] + for m > 1 { + out[0] = uint8(r) + out = out[1:] + r >>= 8 + m = (m + 255) >> 8 + } + } +} diff --git a/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/sntrup761/ntruprime.go b/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/sntrup761/ntruprime.go new file mode 100644 index 0000000..6c60ee4 --- /dev/null +++ b/go/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/sntrup761/ntruprime.go @@ -0,0 +1,971 @@ +// Code generated from sntrup.templ.go. DO NOT EDIT. + +// Package sntrup761 implements the IND-CCA2 secure key encapsulation mechanism +// sntrup761 as submitted to round 3 of the NIST PQC competition and +// described in +// +// https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf +package sntrup761 + +import ( + "bytes" + cryptoRand "crypto/rand" + "crypto/sha512" + "io" + + "go.cypherpunks.su/keks/cm/enc/sntrup761-x25519/sntrup761/kem" + "go.cypherpunks.su/keks/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/internal" + sntrupKem "go.cypherpunks.su/keks/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/kem" + ntrup "go.cypherpunks.su/keks/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/sntrup761" +) + +type ( + small int8 + Fq int16 + Inputs [p]small +) + +const ( + p = ntrup.P + q = ntrup.Q + q12 = ((q - 1) / 2) + roundedBytes = ntrup.RoundedBytes + rqBytes = ntrup.RqBytes + w = ntrup.W + + hashBytes = 32 + + smallBytes = ((p + 3) / 4) + + inputsBytes = smallBytes + ciphertextsBytes = roundedBytes + secretKeysBytes = (2 * smallBytes) + publicKeysBytes = rqBytes + + confirmBytes = 32 +) + +const ( + // Size of seed for NewKeyFromSeed + // Note that during keyGen, a random small is generated until a valid one (whose reciprocal succeeds) is found + // The size of keySeed depends on the number of times the reciprocal fails + // This is why DeriveKeyPairFromGen is used to deterministically derive key pair instead of using seed + KeySeedSize = 4*p + p*4 + inputsBytes + + // Size of seed for EncapsulateTo. + EncapsulationSeedSize = 4 * p + + // Size of the established shared key. + SharedKeySize = ntrup.SharedKeySize + + // Size of the encapsulated shared key. + CiphertextSize = ntrup.CiphertextSize + + // Size of a packed public key. + PublicKeySize = ntrup.PublicKeySize + + // Size of a packed private key. + PrivateKeySize = ntrup.PrivateKeySize +) + +// Arithmetic operations over GF(3) + +// A polynomial of R has all of its coefficients in (-1,0,1) +// F3 is always represented as -1,0,1 +// so ZZ_fromF3 is a no-op + +// x must not be close to top int16 +func f3Freeze(x int16) small { + return small(internal.Int32ModUint14(int32(x)+1, 3)) - 1 +} + +// Arithmetic operations over GF(q) + +/* always represented as -q12...q12 */ +/* so ZZ_fromFq is a no-op */ + +/* x must not be close to top int32 */ +func fqFreeze(x int32) Fq { + return Fq(internal.Int32ModUint14(x+q12, q) - q12) +} + +// Calculates reciprocal of Fq +func fqRecip(a1 Fq) Fq { + var i int = 1 + ai := a1 + + for i < (q - 2) { + ai = fqFreeze(int32(a1) * int32(ai)) + i += 1 + } + return ai +} + +// Returns 0 if the weight w is equal to r +// otherwise returns -1 +func weightwMask(r []small) int { + var weight int = 0 + + for i := 0; i < p; i++ { + weight += int(r[i]) & 1 + } + + // returns -1 if non zero + // otherwise returns 0 if weight==w + return internal.Int16NonzeroMask(int16(weight - w)) + +} + +/* R3_fromR(R_fromRq(r)) */ +func r3FromRq(out []small, r []Fq) { + for i := 0; i < p; i++ { + out[i] = small(f3Freeze(int16(r[i]))) + } +} + +// h = f*g in the ring R3 +func r3Mult(h []small, f []small, g []small) { + fg := make([]small, p+p-1) + var result small + var i, j int + + for i = 0; i < p; i++ { + result = 0 + for j = 0; j <= i; j++ { + result = f3Freeze(int16(result + f[j]*g[i-j])) + } + fg[i] = result + } + + for i = p; i < p+p-1; i++ { + result = 0 + for j = i - p + 1; j < p; j++ { + result = f3Freeze(int16(result + f[j]*g[i-j])) + } + fg[i] = result + } + + for i = p + p - 2; i >= p; i-- { + fg[i-p] = f3Freeze(int16(fg[i-p] + fg[i])) + fg[i-p+1] = f3Freeze(int16(fg[i-p+1] + fg[i])) + } + + for i = 0; i < p; i++ { + h[i] = fg[i] + } +} + +// Calculates the reciprocal of R3 polynomials +// Returns 0 if recip succeeded; else -1 +func r3Recip(out []small, in []small) int { + // out := make([]small, p) + f := make([]small, p+1) + g := make([]small, p+1) + v := make([]small, p+1) + r := make([]small, p+1) + + var sign int + + r[0] = 1 + f[0] = 1 + + f[p-1] = -1 + f[p] = -1 + + for i := 0; i < p; i++ { + g[p-1-i] = in[i] + } + + g[p] = 0 + + delta := 1 + + for loop := 0; loop < 2*p-1; loop++ { + for i := p; i > 0; i-- { + v[i] = v[i-1] + } + v[0] = 0 + + sign = int(-g[0] * f[0]) + var swap int = int(internal.Int16NegativeMask(int16(-delta)) & internal.Int16NonzeroMask(int16(g[0]))) + delta ^= swap & int(delta^-delta) + delta += 1 + + for i := 0; i < p+1; i++ { + t := swap & int(f[i]^g[i]) + f[i] ^= small(t) + g[i] ^= small(t) + t = swap & int(v[i]^r[i]) + v[i] ^= small(t) + r[i] ^= small(t) + } + for i := 0; i < p+1; i++ { + g[i] = f3Freeze(int16(int(g[i]) + sign*int(f[i]))) + } + + for i := 0; i < p+1; i++ { + r[i] = f3Freeze(int16(int(r[i]) + sign*int(v[i]))) + } + + for i := 0; i < p; i++ { + g[i] = g[i+1] + } + + g[p] = 0 + + } + sign = int(f[0]) + + for i := 0; i < p; i++ { + + out[i] = small(sign * int(v[p-1-i])) + } + + return internal.Int16NonzeroMask(int16(delta)) + +} + +// Polynomials mod q + +// h = f*g in the ring Rq */ +func rqMultSmall(h []Fq, f []Fq, g []small) { + fg := make([]Fq, p+p-1) + var result Fq + + for i := 0; i < p; i++ { + result = 0 + for j := 0; j <= i; j++ { + result = fqFreeze(int32(result) + int32(f[j])*(int32)(g[i-j])) + } + fg[i] = result + } + + for i := p; i < p+p-1; i++ { + result = 0 + for j := i - p + 1; j < p; j++ { + result = fqFreeze(int32(result) + int32(f[j])*(int32)(g[i-j])) + } + fg[i] = result + } + + for i := p + p - 2; i >= p; i-- { + fg[i-p] = fqFreeze(int32(fg[i-p] + fg[i])) + fg[i-p+1] = fqFreeze(int32(fg[i-p+1] + fg[i])) + + } + + for i := 0; i < p; i++ { + h[i] = fg[i] + } +} + +// h = 3f in Rq +func rqMult3(h []Fq, f []Fq) { + for i := 0; i < p; i++ { + h[i] = fqFreeze(int32(3 * f[i])) + } +} + +// Returns 0 if recip succeeded; else -1 +// out = 1/(3*in) in Rq +func rqRecip3(out []Fq, in []small) int { + f := make([]Fq, p+1) + g := make([]Fq, p+1) + v := make([]Fq, p+1) + r := make([]Fq, p+1) + + var swap, t int + var f0, g0 int32 + + r[0] = fqRecip(3) + f[0] = 1 + f[p-1] = -1 + f[p] = -1 + + for i := 0; i < p; i++ { + g[p-1-i] = Fq(in[i]) + } + g[p] = 0 + + delta := 1 + + for loop := 0; loop < 2*p-1; loop++ { + for i := p; i > 0; i-- { + v[i] = v[i-1] + } + v[0] = 0 + + swap = internal.Int16NegativeMask(int16(-delta)) & internal.Int16NonzeroMask(int16(g[0])) + delta ^= swap & (delta ^ -delta) + delta += 1 + + for i := 0; i < p+1; i++ { + t = swap & int(f[i]^g[i]) + f[i] ^= Fq(t) + g[i] ^= Fq(t) + t = swap & int(v[i]^r[i]) + v[i] ^= Fq(t) + r[i] ^= Fq(t) + } + + f0 = int32(f[0]) + g0 = int32(g[0]) + + for i := 0; i < p+1; i++ { + g[i] = fqFreeze(f0*int32(g[i]) - g0*int32(f[i])) + } + for i := 0; i < p+1; i++ { + r[i] = fqFreeze(f0*int32(r[i]) - g0*int32(v[i])) + } + + for i := 0; i < p; i++ { + g[i] = g[i+1] + } + g[p] = 0 + } + + scale := Fq(fqRecip(f[0])) + for i := 0; i < p; i++ { + out[i] = fqFreeze(int32(scale) * (int32)(v[p-1-i])) + } + + return internal.Int16NonzeroMask(int16(delta)) + +} + +// Rounding all coefficients of a polynomial to the nearest multiple of 3 +// Rounded polynomials mod q +func round(out []Fq, a []Fq) { + for i := 0; i < p; i++ { + out[i] = a[i] - Fq(f3Freeze(int16(a[i]))) + } +} + +// Returns (min(x, y), max(x, y)), executes in constant time +func minmax(x, y *uint32) { + var xi uint32 = *x + var yi uint32 = *y + var xy uint32 = xi ^ yi + var c uint32 = yi - xi + c ^= xy & (c ^ yi ^ 0x80000000) + c >>= 31 + c = -c + c &= xy + *x = xi ^ c + *y = yi ^ c +} + +// Sorts the array of unsigned integers +func cryptoSortUint32(x []uint32, n int) { + if n < 2 { + return + } + top := 1 + + for top < n-top { + top += top + } + + for p := top; p > 0; p >>= 1 { + for i := 0; i < n-p; i++ { + if i&p == 0 { + minmax(&x[i], &x[i+p]) + } + } + for q := top; q > p; q >>= 1 { + for i := 0; i < n-q; i++ { + if i&p == 0 { + minmax(&x[i+p], &x[i+q]) + } + } + } + } +} + +// Sorting to generate short polynomial +func shortFromList(out []small, in []int32) { + L := make([]uint32, p) + + var neg2, neg3 int = -2, -3 + + for i := 0; i < w; i++ { + L[i] = uint32(in[i]) & uint32((neg2)) + } + + for i := w; i < p; i++ { + L[i] = (uint32(in[i]) & uint32((neg3))) | 1 + } + + cryptoSortUint32(L, p) + + for i := 0; i < p; i++ { + out[i] = small((L[i] & 3) - 1) + } +} + +// Underlying hash function + +// The input byte array, in, is prepended by the byte b +// and its SHA-512 hash is calculated +// Only the first 32 bytes of the hash are returned +// e.g., b = 0 means out = Hash0(in) +func hashPrefix(out []byte, b int, in []byte, inlen int) { + x := make([]byte, inlen+1) + h := make([]byte, 64) + + x[0] = byte(b) + copy(x[1:], in) + + hash := sha512.New() + hash.Write([]byte(x)) + h = hash.Sum(nil) + + copy(out, h[:32]) + +} + +// Higher level randomness +// Returns a random unsigned integer +func urandom32(seed []byte) uint32 { + var out [4]uint32 + + out[0] = uint32(seed[0]) + out[1] = uint32(seed[1]) << 8 + out[2] = uint32(seed[2]) << 16 + out[3] = uint32(seed[3]) << 24 + return out[0] + out[1] + out[2] + out[3] +} + +// Generates a random short polynomial +func shortRandom(out []small, seed []byte) { + + L := make([]uint32, p) + + for i := 0; i < p; i++ { + L[i] = urandom32(seed[4*i : 4*i+4]) + } + + // Converts uint32 array to int32 array + L_int32 := make([]int32, p) + for i := 0; i < len(L); i++ { + L_int32[i] = int32(L[i]) + } + shortFromList(out, L_int32) +} + +// Generates a random list of small +func smallRandom(out []small, seed []byte) { + for i := 0; i < p; i++ { + out[i] = small(((urandom32(seed[4*i:4*i+4])&0x3fffffff)*3)>>30) - 1 + } +} + +// Streamlined NTRU Prime Core + +// h,(f,ginv) = keyGen() +func keyGen(h []Fq, f []small, ginv []small, gen *io.Reader) { + g := make([]small, p) + seed := make([]byte, 4*p+4*p) + + if gen == nil { + for { + cryptoRand.Read(seed[:4*p]) + smallRandom(g, seed[:4*p]) + if r3Recip(ginv, g) == 0 { + break + } + } + cryptoRand.Read(seed[4*p:]) + } else { + for { + for i := 0; i < p; i++ { + (*gen).Read(seed[4*i : 4*i+4]) + } + smallRandom(g, seed[:4*p]) + if r3Recip(ginv, g) == 0 { + break + } + } + for i := 0; i < p; i++ { + (*gen).Read(seed[4*p+4*i : 4*p+4*i+4]) + } + } + shortRandom(f, seed[4*p:]) + + finv := make([]Fq, p) + + rqRecip3(finv, f) /* always works */ + rqMultSmall(h, finv, g) +} + +// c = encrypt(r,h) +func encrypt(c []Fq, r []small, h []Fq) { + hr := make([]Fq, p) + + rqMultSmall(hr, h, r) + round(c, hr) +} + +// r = decrypt(c,(f,ginv)) +func decrypt(r []small, c []Fq, f []small, ginv []small) { + cf := make([]Fq, p) + cf3 := make([]Fq, p) + e := make([]small, p) + ev := make([]small, p) + + rqMultSmall(cf, c, f) + rqMult3(cf3, cf) + r3FromRq(e, cf3) + r3Mult(ev, e, ginv) + + mask := weightwMask(ev) /* 0 if weight w, else -1 */ + for i := 0; i < w; i++ { + r[i] = ((ev[i] ^ 1) & small(^mask)) ^ 1 + } + + for i := w; i < p; i++ { + r[i] = ev[i] & small(^mask) + } +} + +// Encoding small polynomials (including short polynomials) + +// Transform polynomial in R to bytes +// these are the only functions that rely on p mod 4 = 1 */ +func smallEncode(s []byte, f []small) { + var x small + var index int = 0 + for i := 0; i < p/4; i++ { + x = f[index] + 1 + index++ + + x += (f[index] + 1) << 2 + index++ + x += (f[index] + 1) << 4 + index++ + x += (f[index] + 1) << 6 + index++ + + s[0] = byte(x) + s = s[1:] + } + x = f[index] + 1 + + s[0] = byte(x) +} + +// Transform bytes into polynomial in R +func smallDecode(f []small, s []byte) { + var index int = 0 + var x byte + + for i := 0; i < p/4; i++ { + x = s[0] + s = s[1:] + + f[index] = ((small)(x & 3)) - 1 + x >>= 2 + index++ + f[index] = ((small)(x & 3)) - 1 + x >>= 2 + index++ + f[index] = ((small)(x & 3)) - 1 + x >>= 2 + index++ + f[index] = ((small)(x & 3)) - 1 + index++ + } + x = s[0] + f[index] = ((small)(x & 3)) - 1 +} + +// Encoding general polynomials + +// Transform polynomials in R/q to bytes +func rqEncode(s []byte, r []Fq) { + R := make([]uint16, p) + M := make([]uint16, p) + + for i := 0; i < p; i++ { + R[i] = uint16(r[i] + q12) + M[i] = q + } + internal.Encode(s, R, M, p) +} + +// Transform polynomials in R/q from bytes +func rqDecode(r []Fq, s []byte) { + R := make([]uint16, p) + M := make([]uint16, p) + + for i := 0; i < p; i++ { + M[i] = q + } + internal.Decode(R, s, M, p) + for i := 0; i < p; i++ { + r[i] = ((Fq)(R[i])) - q12 + } + +} + +// Encoding rounded polynomials + +// Transform rounded polynomials to bytes +func roundedEncode(s []byte, r []Fq) { + + R := make([]uint16, p) + M := make([]uint16, p) + + for i := 0; i < p; i++ { + R[i] = uint16((int32((r[i])+q12) * 10923) >> 15) + M[i] = (q + 2) / 3 + } + internal.Encode(s, R, M, p) +} + +// Transform bytes to rounded polynomials +func roundedDecode(r []Fq, s []byte) { + R := make([]uint16, p) + M := make([]uint16, p) + + for i := 0; i < p; i++ { + M[i] = (q + 2) / 3 + } + internal.Decode(R, s, M, p) + for i := 0; i < p; i++ { + r[i] = Fq(R[i]*3 - q12) + } + +} + +// Streamlined NTRU Prime Core plus encoding + +// Generates public key and private key +// pk,sk = zKeyGen() +func zKeyGen(pk []byte, sk []byte, gen *io.Reader) { + + h := make([]Fq, p) + f := make([]small, p) + v := make([]small, p) + keyGen(h, f, v, gen) + + rqEncode(pk, h) + smallEncode(sk, f) + sk = sk[smallBytes:] + smallEncode(sk, v) + +} + +// C = zEncrypt(r,pk) +func zEncrypt(C []byte, r Inputs, pk []byte) { + h := make([]Fq, p) + c := make([]Fq, p) + rqDecode(h, pk) + encrypt(c, r[:], h) + roundedEncode(C, c) +} + +// r = zDecrypt(C,sk) +func zDecrypt(r *Inputs, C []byte, sk []byte) { + f := make([]small, p) + v := make([]small, p) + c := make([]Fq, p) + + smallDecode(f, sk) + sk = sk[smallBytes:] + smallDecode(v, sk) + roundedDecode(c, C) + + decrypt(r[:], c, f, v) +} + +// Confirmation hash + +// h = hashConfirm(r,pk,cache); cache is Hash4(pk) +func hashConfirm(h []byte, r []byte, pk []byte, cache []byte) { + x := make([]byte, hashBytes*2) + + hashPrefix(x, 3, r, inputsBytes) + + copy(x[hashBytes:], cache[:hashBytes]) + + hashPrefix(h, 2, x, len(x)) + +} + +// Session-key hash + +// k = hashSession(b,y,z) +func hashSession(k []byte, b int, y []byte, z []byte) { + x := make([]byte, hashBytes+ciphertextsBytes+confirmBytes) + + hashPrefix(x, 3, y, inputsBytes) + + copy(x[hashBytes:], z[:ciphertextsBytes+confirmBytes]) + + hashPrefix(k, b, x, len(x)) + +} + +// Streamlined NTRU Prime + +// pk,sk = kemKeyGen() +func kemKeyGen(pk []byte, sk []byte, gen *io.Reader) { + zKeyGen(pk, sk, gen) + sk = sk[secretKeysBytes:] + + copy(sk, pk) + sk = sk[publicKeysBytes:] + + if gen != nil { + (*gen).Read(sk[:inputsBytes]) + + } else { + cryptoRand.Read(sk[:inputsBytes]) + } + sk = sk[inputsBytes:] + hashPrefix(sk, 4, pk, publicKeysBytes) + +} + +// c,r_enc = hide(r,pk,cache); cache is Hash4(pk) +func hide(c []byte, r_enc []byte, r Inputs, pk []byte, cache []byte) { + smallEncode(r_enc, r[:]) + zEncrypt(c, r, pk) + c = c[ciphertextsBytes:] + hashConfirm(c, r_enc, pk, cache) + +} + +// Takes as input a public key +// Returns ciphertext and shared key +// c,k = encap(pk) +func (pub PublicKey) EncapsulateTo(c []byte, k []byte, seed []byte) { + if seed == nil { + seed = make([]byte, 4*p) + cryptoRand.Read(seed) + } + if len(seed) != 4*p { + panic("seed must be of length EncapsulationSeedSize") + } + if len(c) != CiphertextSize { + panic("ct must be of length CiphertextSize") + } + if len(k) != SharedKeySize { + panic("ss must be of length SharedKeySize") + } + + pk := pub.pk[:] + + var r Inputs + r_enc := make([]byte, inputsBytes) + cache := make([]byte, hashBytes) + + hashPrefix(cache, 4, pk, publicKeysBytes) + shortRandom(r[:], seed) + hide(c, r_enc, r, pk, cache) + hashSession(k, 1, r_enc, c) + +} + +// Returns 0 if matching ciphertext+confirm, else -1 +func ciphertexts_diff_mask(c []byte, c2 []byte) int { + var differentbits uint16 = 0 + var len int = ciphertextsBytes + confirmBytes + + for i := 0; i < len; i++ { + differentbits |= uint16((c[i]) ^ (c2[i])) + } + return int((1 & ((differentbits - 1) >> 8)) - 1) + +} + +// Returns shared key from ciphertext and private key +// k = decap(c,sk) +func (priv *PrivateKey) DecapsulateTo(k []byte, c []byte) { + if len(c) != CiphertextSize { + panic("ct must be of length CiphertextSize") + } + + if len(k) != SharedKeySize { + panic("ss must be of length SharedKeySize") + } + + sk := priv.sk[:] + + pk := sk[secretKeysBytes:] + rho := pk[publicKeysBytes:] + cache := rho[inputsBytes:] + var r Inputs + + r_enc := make([]byte, inputsBytes) + cnew := make([]byte, ciphertextsBytes+confirmBytes) + + zDecrypt(&r, c, sk) + hide(cnew, r_enc, r, pk, cache) + var mask int = ciphertexts_diff_mask(c, cnew) + + for i := 0; i < inputsBytes; i++ { + r_enc[i] ^= byte(mask & int(r_enc[i]^rho[i])) + } + hashSession(k, 1+mask, r_enc, c) +} + +// The structure of the private key is given by the following segments: +// The secret key, the public key, entropy and the hash of the public key +type PrivateKey struct { + sk [PrivateKeySize]byte +} + +type PublicKey struct { + pk [PublicKeySize]byte +} + +type scheme struct{} + +var sch sntrupKem.Scheme = &scheme{} + +// Scheme returns a KEM interface. +func Scheme() kem.Scheme { return sch } + +// SntrupScheme returns a sntrup.KEM interface +func SntrupScheme() sntrupKem.Scheme { return sch } + +func (*scheme) Name() string { return "sntrup761" } +func (*scheme) PublicKeySize() int { return PublicKeySize } +func (*scheme) PrivateKeySize() int { return PrivateKeySize } +func (*scheme) SeedSize() int { return KeySeedSize } +func (*scheme) SharedKeySize() int { return SharedKeySize } +func (*scheme) CiphertextSize() int { return CiphertextSize } +func (*scheme) EncapsulationSeedSize() int { return EncapsulationSeedSize } + +func (sk *PrivateKey) Scheme() kem.Scheme { return sch } +func (pk *PublicKey) Scheme() kem.Scheme { return sch } + +func (sk *PrivateKey) MarshalBinary() ([]byte, error) { + var ret [PrivateKeySize]byte + copy(ret[:], sk.sk[:]) + return ret[:], nil +} + +func (sk *PrivateKey) Equal(other kem.PrivateKey) bool { + oth, ok := other.(*PrivateKey) + if !ok { + return false + } + return bytes.Equal(sk.sk[:], oth.sk[:]) +} + +func (pk *PublicKey) Equal(other kem.PublicKey) bool { + oth, ok := other.(*PublicKey) + if !ok { + return false + } + return bytes.Equal(pk.pk[:], oth.pk[:]) +} + +func (sk *PrivateKey) Public() kem.PublicKey { + var pk [PublicKeySize]byte + skey, _ := sk.MarshalBinary() + ppk := skey[secretKeysBytes : secretKeysBytes+publicKeysBytes] + copy(pk[:], ppk[:]) + return &PublicKey{pk: pk} +} + +func (pk *PublicKey) MarshalBinary() ([]byte, error) { + var ret [PublicKeySize]byte + copy(ret[:], pk.pk[:]) + return ret[:], nil +} + +func (*scheme) GenerateKeyPair() (kem.PublicKey, kem.PrivateKey, error) { + var pk [PublicKeySize]byte + var sk [PrivateKeySize]byte + kemKeyGen(pk[:], sk[:], nil) + + return &PublicKey{pk: pk}, &PrivateKey{sk: sk}, nil + +} + +// Not used +func (*scheme) DeriveKeyPair(seed []byte) (kem.PublicKey, kem.PrivateKey) { + return nil, nil +} + +func (*scheme) DeriveKeyPairFromGen(gen *io.Reader) (kem.PublicKey, kem.PrivateKey) { + + if gen == nil { + panic("A nist DRBG must be provided") + } + + var pk [PublicKeySize]byte + var sk [PrivateKeySize]byte + + kemKeyGen(pk[:], sk[:], gen) + + return &PublicKey{pk: pk}, &PrivateKey{sk: sk} +} + +func (*scheme) Encapsulate(pk kem.PublicKey) (ct, ss []byte, err error) { + ct = make([]byte, CiphertextSize) + ss = make([]byte, SharedKeySize) + + pub, ok := pk.(*PublicKey) + if !ok { + return nil, nil, kem.ErrTypeMismatch + } + + pub.EncapsulateTo(ct, ss, nil) + + return ct, ss, nil + +} + +func (*scheme) EncapsulateDeterministically(pk kem.PublicKey, seed []byte) (ct, ss []byte, err error) { + + ct = make([]byte, CiphertextSize) + ss = make([]byte, SharedKeySize) + + pub, ok := pk.(*PublicKey) + if !ok { + return nil, nil, kem.ErrTypeMismatch + } + + pub.EncapsulateTo(ct, ss, seed) + + return ct, ss, nil +} + +func (*scheme) Decapsulate(sk kem.PrivateKey, ct []byte) ([]byte, error) { + ssk, ok := sk.(*PrivateKey) + if !ok { + return nil, kem.ErrTypeMismatch + } + + if len(ct) != CiphertextSize { + return nil, kem.ErrCiphertextSize + } + ss := [SharedKeySize]byte{} + + ssk.DecapsulateTo(ss[:], ct) + + return ss[:], nil +} + +func (*scheme) UnmarshalBinaryPublicKey(buf []byte) (kem.PublicKey, error) { + if len(buf) != PublicKeySize { + return nil, kem.ErrPubKeySize + } + pk := [PublicKeySize]byte{} + copy(pk[:], buf) + return &PublicKey{pk: pk}, nil +} + +func (*scheme) UnmarshalBinaryPrivateKey(buf []byte) (kem.PrivateKey, error) { + if len(buf) != PrivateKeySize { + return nil, kem.ErrPrivKeySize + } + sk := [PrivateKeySize]byte{} + copy(sk[:], buf) + return &PrivateKey{sk: sk}, nil +} diff --git a/go/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/kem/kem.go b/go/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/kem/kem.go new file mode 100644 index 0000000..d391d4a --- /dev/null +++ b/go/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/kem/kem.go @@ -0,0 +1,21 @@ +// Package kem provides a unified interface for Streamlined NTRU Prime KEM schemes. +// +// # A register of Streamlined NTRU Prime schemes is available in the package +// +// go.cypherpunks.su/keks/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/kem/schemes/sntrup +package kem + +import ( + "io" + + "go.cypherpunks.su/keks/cm/enc/sntrup761-x25519/sntrup761/kem" +) + +// A Scheme represents a specific instance of a NTRU PRIME KEM. +type Scheme interface { + kem.Scheme + + // DeriveKeyPairFromGen deterministicallly derives a pair of keys from a nist DRBG. + // Only used for deterministic testing + DeriveKeyPairFromGen(gen *io.Reader) (kem.PublicKey, kem.PrivateKey) +} diff --git a/go/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/kem/schemes/sntrup/schemes.go b/go/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/kem/schemes/sntrup/schemes.go new file mode 100644 index 0000000..7e375c8 --- /dev/null +++ b/go/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/kem/schemes/sntrup/schemes.go @@ -0,0 +1,39 @@ +// Package schemes contains a register of Streamlined NTRU Prime KEM schemes. +// +// # Schemes Implemented +// +// Post-quantum kems: +// +// SNTRUP653, SNTRUP761, SNTRUP857, SNTRUP953, SNTRUP1013, SNTRUP1277 +package sntrupSchemes + +import ( + "strings" + + "go.cypherpunks.su/keks/cm/enc/sntrup761-x25519/sntrup761/kem/ntruprime/sntrup761" + "go.cypherpunks.su/keks/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/kem" +) + +var allSchemes = [...]kem.Scheme{ + sntrup761.SntrupScheme(), +} + +var allSchemeNames map[string]kem.Scheme + +func init() { + allSchemeNames = make(map[string]kem.Scheme) + for _, scheme := range allSchemes { + allSchemeNames[strings.ToLower(scheme.Name())] = scheme + } +} + +// ByName returns the scheme with the given name and nil if it is not +// supported. +// +// Names are case insensitive. +func ByName(name string) kem.Scheme { + return allSchemeNames[strings.ToLower(name)] +} + +// All returns all KEM schemes supported. +func All() []kem.Scheme { a := allSchemes; return a[:] } diff --git a/go/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/sntrup761/params.go b/go/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/sntrup761/params.go new file mode 100644 index 0000000..4e01822 --- /dev/null +++ b/go/cm/enc/sntrup761-x25519/sntrup761/pke/ntruprime/sntrup761/params.go @@ -0,0 +1,25 @@ +// Code generated from sntrup.params.templ.go. DO NOT EDIT. +package ntruprime + +const ( + P = 761 + Q = 4591 + RoundedBytes = 1007 + RqBytes = 1158 + W = 286 +) + +const ( + + // Size of the established shared key. + SharedKeySize = 32 + + // Size of the encapsulated shared key. + CiphertextSize = 1039 + + // Size of a packed public key. + PublicKeySize = 1158 + + // Size of a packed private key. + PrivateKeySize = 1763 +) diff --git a/go/cm/go.mod b/go/cm/go.mod index 6dce99a..d84456d 100644 --- a/go/cm/go.mod +++ b/go/cm/go.mod @@ -3,7 +3,6 @@ module go.cypherpunks.su/keks/cm go 1.24.0 require ( - github.com/companyzero/sntrup4591761 v0.0.0-20220309191932-9e0f3af2f07a github.com/google/uuid v1.6.0 go.cypherpunks.su/balloon/v3 v3.0.0 go.cypherpunks.su/gogost/v6 v6.1.0 diff --git a/go/cm/go.sum b/go/cm/go.sum index 4f4adc1..e66f328 100644 --- a/go/cm/go.sum +++ b/go/cm/go.sum @@ -1,5 +1,3 @@ -github.com/companyzero/sntrup4591761 v0.0.0-20220309191932-9e0f3af2f07a h1:clYxJ3Os0EQUKDDVU8M0oipllX0EkuFNBfhVQuIfyF0= -github.com/companyzero/sntrup4591761 v0.0.0-20220309191932-9e0f3af2f07a/go.mod h1:z/9Ck1EDixEbBbZ2KH2qNHekEmDLTOZ+FyoIPWWSVOI= github.com/google/uuid v1.6.0 h1:NIvaJDMOsjHA8n1jAhLSgzrAzy1Hgr+hNrb57e+94F0= github.com/google/uuid v1.6.0/go.mod h1:TIyPZe4MgqvfeYDBFedMoGGpEw/LqOeaOT+nhxU+yHo= github.com/mitchellh/mapstructure v1.5.0 h1:jeMsZIYE/09sWLaz43PL7Gy6RuMjD2eJVyuac5Z2hdY= diff --git a/spec/cm/kem/sntrup4591761-x25519-hkdf-blake2b b/spec/cm/kem/sntrup761-x25519-hkdf-blake2b similarity index 72% rename from spec/cm/kem/sntrup4591761-x25519-hkdf-blake2b rename to spec/cm/kem/sntrup761-x25519-hkdf-blake2b index 2d2f27b..9362d67 100644 --- a/spec/cm/kem/sntrup4591761-x25519-hkdf-blake2b +++ b/spec/cm/kem/sntrup761-x25519-hkdf-blake2b @@ -1,4 +1,4 @@ -Streamlined NTRU Prime 4591^761 + X25519 + HKDF-BLAKE2b KEM. +Streamlined NTRU Prime 761 + X25519 + HKDF-BLAKE2b KEM. => https://ntruprime.cr.yp.to/ Streamlined NTRU Prime KEM algorithm => https://datatracker.ietf.org/doc/html/rfc7748 X25519 => https://datatracker.ietf.org/doc/html/rfc5869.html RFC 5869, HKDF @@ -6,12 +6,12 @@ Streamlined NTRU Prime 4591^761 + X25519 + HKDF-BLAKE2b KEM. << [schemas/kem-with-encap.tcl] -"/kem/*/a" equals to "sntrup4591761-x25519-hkdf-blake2b". -Recipient public key with [cm/pub/sntrup4591761-x25519] +"/kem/*/a" equals to "sntrup761-x25519-hkdf-blake2b". +Recipient public key with [cm/pub/sntrup761-x25519] algorithm must be used. It should have "kem" key usage set. Recipient's map "/kem/*/encap" field is a concatenation of 1047 -bytes Streamlined NTRU Prime 4591^761's ciphertext, containing +bytes Streamlined NTRU Prime 761's ciphertext, containing ephemeral key, with 32 bytes ephemeral X25519 public key. Recipient performs X25519 and SNTRUP computations to derive/decapsulate @@ -26,16 +26,16 @@ key of the CEK. H = BLAKE2b PRK = HKDF-Extract(H, salt="", ikm= - sntrup4591761-shared-key || es-x25519-shared-key || - H(sntrup4591761-sender-ciphertext || e-x25519-sender-public-key) || - H(sntrup4591761-recipient-public-key || s-x25519-recipient-public-key)) + sntrup761-shared-key || es-x25519-shared-key || + H(sntrup761-sender-ciphertext || e-x25519-sender-public-key) || + H(sntrup761-recipient-public-key || s-x25519-recipient-public-key)) if {specified sender} PRK = HKDF-Extract(H, salt=PRK, ikm= ss-x25519-shared-key || s-x25519-sender-public-key || s-x25519-recipient-public-key) KEK = HKDF-Expand(H, prk=PRK, - info="cm/encrypted/sntrup4591761-x25519-hkdf-blake2b" || /id) + info="cm/encrypted/sntrup761-x25519-hkdf-blake2b" || /id) "/kem/*/cek" is wrapped with [cm/keywrap/xchapoly] mechanism. diff --git a/spec/cm/prv/sntrup4591761-x25519 b/spec/cm/prv/sntrup4591761-x25519 deleted file mode 100644 index 79fc2ff..0000000 --- a/spec/cm/prv/sntrup4591761-x25519 +++ /dev/null @@ -1,5 +0,0 @@ -[cm/prv/] with Streamlined NTRU Prime 4591^761 + X25519. -=> https://ntruprime.cr.yp.to/ NTRU Prime -=> https://datatracker.ietf.org/doc/html/rfc7748 X25519 -It is a concatenation of SNTRUP's 1600-byte and X25519's 32-byte keys. -"sntrup4591761-x25519" algorithm identifier is used. diff --git a/spec/cm/prv/sntrup761-x25519 b/spec/cm/prv/sntrup761-x25519 new file mode 100644 index 0000000..a41dff2 --- /dev/null +++ b/spec/cm/prv/sntrup761-x25519 @@ -0,0 +1,5 @@ +[cm/prv/] with Streamlined NTRU Prime 761 + X25519. +=> https://ntruprime.cr.yp.to/ NTRU Prime +=> https://datatracker.ietf.org/doc/html/rfc7748 X25519 +It is a concatenation of SNTRUP's 1763-byte and X25519's 32-byte keys. +"sntrup761-x25519" algorithm identifier is used. diff --git a/spec/cm/pub/sntrup4591761-x25519 b/spec/cm/pub/sntrup761-x25519 similarity index 56% rename from spec/cm/pub/sntrup4591761-x25519 rename to spec/cm/pub/sntrup761-x25519 index 42a0168..21635e9 100644 --- a/spec/cm/pub/sntrup4591761-x25519 +++ b/spec/cm/pub/sntrup761-x25519 @@ -1,13 +1,13 @@ -[cm/pub/] with Streamlined NTRU Prime 4591^761 + X25519. +[cm/pub/] with Streamlined NTRU Prime 761 + X25519. => https://ntruprime.cr.yp.to/ Streamlined NTRU Prime KEM algorithm => https://datatracker.ietf.org/doc/html/rfc7748 X25519 -Combined Streamlined NTRU Prime 4591^761 and X25519 public keys are +Combined Streamlined NTRU Prime 761 and X25519 public keys are used for KEM purposes, so should have "kem" key usage set. -Its algorithm identifier is "sntrup4591761-x25519". -Its public key value is a concatenation of 1218-byte -SNTRUP4591761 public key and 32-byte X25519 one. +Its algorithm identifier is "sntrup761-x25519". +Its public key value is a concatenation of 1158-byte +SNTRUP761 public key and 32-byte X25519 one. Public key's fingerprint should be calculated using BLAKE2b hash with 256 bit output length specified. diff --git a/tcl/schemas/kem-with-encap.tcl b/tcl/schemas/kem-with-encap.tcl index 618dcfa..0d43e0c 100644 --- a/tcl/schemas/kem-with-encap.tcl +++ b/tcl/schemas/kem-with-encap.tcl @@ -1,5 +1,5 @@ kem-with-encap { - {field a {str} >0} {# sntrup4591761-x25519-hkdf-blake2b} + {field a {str} >0} {# sntrup761-x25519-hkdf-blake2b} {# mceliece6960119-x25519-hkdf-shake256} {field cek {bin} >0} {# wrapped CEK} {field encap {bin} >0} -- 2.50.0