Refactor private key generation
Private key generation can take advantage of the fact that keyspace for
secret key is (0, 2^x - 1), for some possitivite value of 'x' (see SIKE,
1.3.8). It means that all bytes in the secret key, but the last one, can
take any value between <0x00,0xFF>. Similarily for the last byte, but
generation needs to chop off some bits, to make sure generated value is
an element of a key-space.
Assuming uniform distribution of bytes generated by RNG, secret key is
still chosen uniformly at random, but there is no need to maintain field
specific assembly code.
6 年之前 Refactor private key generation
Private key generation can take advantage of the fact that keyspace for
secret key is (0, 2^x - 1), for some possitivite value of 'x' (see SIKE,
1.3.8). It means that all bytes in the secret key, but the last one, can
take any value between <0x00,0xFF>. Similarily for the last byte, but
generation needs to chop off some bits, to make sure generated value is
an element of a key-space.
Assuming uniform distribution of bytes generated by RNG, secret key is
still chosen uniformly at random, but there is no need to maintain field
specific assembly code.
6 年之前 Refactor private key generation
Private key generation can take advantage of the fact that keyspace for
secret key is (0, 2^x - 1), for some possitivite value of 'x' (see SIKE,
1.3.8). It means that all bytes in the secret key, but the last one, can
take any value between <0x00,0xFF>. Similarily for the last byte, but
generation needs to chop off some bits, to make sure generated value is
an element of a key-space.
Assuming uniform distribution of bytes generated by RNG, secret key is
still chosen uniformly at random, but there is no need to maintain field
specific assembly code.
6 年之前 Refactor private key generation
Private key generation can take advantage of the fact that keyspace for
secret key is (0, 2^x - 1), for some possitivite value of 'x' (see SIKE,
1.3.8). It means that all bytes in the secret key, but the last one, can
take any value between <0x00,0xFF>. Similarily for the last byte, but
generation needs to chop off some bits, to make sure generated value is
an element of a key-space.
Assuming uniform distribution of bytes generated by RNG, secret key is
still chosen uniformly at random, but there is no need to maintain field
specific assembly code.
6 年之前 |
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217 |
- // [SIKE] http://www.sike.org/files/SIDH-spec.pdf
- // [REF] https://github.com/Microsoft/PQCrypto-SIDH
- package sike
-
- import (
- "crypto/subtle"
- "errors"
- "io"
- // TODO: Use implementation from xcrypto, once PR below merged
- // https://go-review.googlesource.com/c/crypto/+/111281/
- . "github.com/cloudflare/sidh/sidh"
- cshake "github.com/henrydcase/nobs/hash/sha3"
- )
-
- // Constants used for cSHAKE customization
- // Those values are different than in [SIKE] - they are encoded on 16bits. This is
- // done in order for implementation to be compatible with [REF] and test vectors.
- var G = []byte{0x00, 0x00}
- var H = []byte{0x01, 0x00}
- var F = []byte{0x02, 0x00}
-
- // Generates cShake-256 sum
- func cshakeSum(out, in, S []byte) {
- h := cshake.NewCShake256(nil, S)
- h.Write(in)
- h.Read(out)
- }
-
- func encrypt(skA *PrivateKey, pkA, pkB *PublicKey, ptext []byte) ([]byte, error) {
- var n [40]byte // n can is max 320-bit (see 1.4 of [SIKE])
- var ptextLen = len(ptext)
-
- if pkB.Variant() != KeyVariant_SIKE {
- return nil, errors.New("wrong key type")
- }
-
- j, err := DeriveSecret(skA, pkB)
- if err != nil {
- return nil, err
- }
-
- cshakeSum(n[:ptextLen], j, F)
- for i, _ := range ptext {
- n[i] ^= ptext[i]
- }
-
- ret := make([]byte, pkA.Size()+ptextLen)
- copy(ret, pkA.Export())
- copy(ret[pkA.Size():], n[:ptextLen])
- return ret, nil
- }
-
- // -----------------------------------------------------------------------------
- // PKE interface
- //
-
- // Uses SIKE public key to encrypt plaintext. Requires cryptographically secure PRNG
- // Returns ciphertext in case encryption succeeds. Returns error in case PRNG fails
- // or wrongly formated input was provided.
- func Encrypt(rng io.Reader, pub *PublicKey, ptext []byte) ([]byte, error) {
- var params = pub.Params()
- var ptextLen = uint(len(ptext))
- // c1 must be security level + 64 bits (see [SIKE] 1.4 and 4.3.3)
- if ptextLen != (params.KemSize + 8) {
- return nil, errors.New("Unsupported message length")
- }
-
- skA := NewPrivateKey(params.Id, KeyVariant_SIDH_A)
- err := skA.Generate(rng)
- if err != nil {
- return nil, err
- }
-
- pkA := skA.GeneratePublicKey()
- return encrypt(skA, pkA, pub, ptext)
- }
-
- // Uses SIKE private key to decrypt ciphertext. Returns plaintext in case
- // decryption succeeds or error in case unexptected input was provided.
- // Constant time
- func Decrypt(prv *PrivateKey, ctext []byte) ([]byte, error) {
- var params = prv.Params()
- var n [40]byte // n can is max 320-bit (see 1.4 of [SIKE])
- var c1_len int
- var pk_len = params.PublicKeySize
-
- if prv.Variant() != KeyVariant_SIKE {
- return nil, errors.New("wrong key type")
- }
-
- // ctext is a concatenation of (pubkey_A || c1=ciphertext)
- // it must be security level + 64 bits (see [SIKE] 1.4 and 4.3.3)
- c1_len = len(ctext) - pk_len
- if c1_len != (int(params.KemSize) + 8) {
- return nil, errors.New("wrong size of cipher text")
- }
-
- c0 := NewPublicKey(params.Id, KeyVariant_SIDH_A)
- err := c0.Import(ctext[:pk_len])
- if err != nil {
- return nil, err
- }
- j, err := DeriveSecret(prv, c0)
- if err != nil {
- return nil, err
- }
-
- cshakeSum(n[:c1_len], j, F)
- for i, _ := range n[:c1_len] {
- n[i] ^= ctext[pk_len+i]
- }
-
- return n[:c1_len], nil
- }
-
- // -----------------------------------------------------------------------------
- // KEM interface
- //
-
- // Encapsulation receives the public key and generates SIKE ciphertext and shared secret.
- // The generated ciphertext is used for authentication.
- // The rng must be cryptographically secure PRNG.
- // Error is returned in case PRNG fails or wrongly formated input was provided.
- func Encapsulate(rng io.Reader, pub *PublicKey) (ctext []byte, secret []byte, err error) {
- var params = pub.Params()
- // Buffer for random, secret message
- var ptext = make([]byte, params.MsgLen)
- // r = G(ptext||pub)
- var r = make([]byte, params.A.SecretByteLen)
- // Resulting shared secret
- secret = make([]byte, params.KemSize)
-
- // Generate ephemeral value
- _, err = io.ReadFull(rng, ptext)
- if err != nil {
- return nil, nil, err
- }
-
- h := cshake.NewCShake256(nil, G)
- h.Write(ptext)
- h.Write(pub.Export())
- h.Read(r)
-
- // cSHAKE256 implementation is byte oriented. Ensure bitlength is not bigger then to 2^e2-1
- r[len(r)-1] &= (1 << (params.A.SecretBitLen % 8)) - 1
-
- // (c0 || c1) = Enc(pkA, ptext; r)
- skA := NewPrivateKey(params.Id, KeyVariant_SIDH_A)
- err = skA.Import(r)
- if err != nil {
- return nil, nil, err
- }
-
- pkA := skA.GeneratePublicKey()
- ctext, err = encrypt(skA, pkA, pub, ptext)
- if err != nil {
- return nil, nil, err
- }
-
- // K = H(ptext||(c0||c1))
- h = cshake.NewCShake256(nil, H)
- h.Write(ptext)
- h.Write(ctext)
- h.Read(secret)
-
- return ctext, secret, nil
- }
-
- // Decapsulate given the keypair and ciphertext as inputs, Decapsulate outputs a shared
- // secret if plaintext verifies correctly, otherwise function outputs random value.
- // Decapsulation may fail in case input is wrongly formated.
- // Constant time for properly initialized input.
- func Decapsulate(prv *PrivateKey, pub *PublicKey, ctext []byte) ([]byte, error) {
- var params = pub.Params()
- var r = make([]byte, params.A.SecretByteLen)
- // Resulting shared secret
- var secret = make([]byte, params.KemSize)
- var skA = NewPrivateKey(params.Id, KeyVariant_SIDH_A)
-
- m, err := Decrypt(prv, ctext)
- if err != nil {
- return nil, err
- }
-
- // r' = G(m'||pub)
- h := cshake.NewCShake256(nil, G)
- h.Write(m)
- h.Write(pub.Export())
- h.Read(r)
-
- // cSHAKE256 implementation is byte oriented: Ensure bitlength is not bigger than 2^e2-1
- r[len(r)-1] &= (1 << (params.A.SecretBitLen % 8)) - 1
-
- // Never fails
- skA.Import(r)
-
- // Never fails
- pkA := skA.GeneratePublicKey()
- c0 := pkA.Export()
-
- h = cshake.NewCShake256(nil, H)
- if subtle.ConstantTimeCompare(c0, ctext[:len(c0)]) == 1 {
- h.Write(m)
- } else {
- // S is chosen at random when generating a key and unknown to other party. It
- // may seem weird, but it's correct. It is important that S is unpredictable
- // to other party. Without this check, it is possible to recover a secret, by
- // providing series of invalid ciphertexts. It is also important that in case
- //
- // See more details in "On the security of supersingular isogeny cryptosystems"
- // (S. Galbraith, et al., 2016, ePrint #859).
- h.Write(prv.S)
- }
- h.Write(ctext)
- h.Read(secret)
- return secret, nil
- }
|