pbrsa.go

Documentation: github.com/cloudflare/circl/blindsign/blindrsa/partiallyblindrsa

     1  // Package partiallyblindrsa implements a partially blind RSA protocol.
     2  package partiallyblindrsa
     3  
     4  import (
     5  	"crypto"
     6  	"crypto/rand"
     7  	"crypto/rsa"
     8  	"encoding/binary"
     9  	"errors"
    10  	"hash"
    11  	"io"
    12  	"math/big"
    13  
    14  	"github.com/cloudflare/circl/blindsign/blindrsa/internal/common"
    15  	"github.com/cloudflare/circl/blindsign/blindrsa/internal/keys"
    16  	"golang.org/x/crypto/hkdf"
    17  )
    18  
    19  func encodeMessageMetadata(message, metadata []byte) []byte {
    20  	lenBuffer := []byte{'m', 's', 'g', 0, 0, 0, 0}
    21  
    22  	binary.BigEndian.PutUint32(lenBuffer[3:], uint32(len(metadata)))
    23  	framedMetadata := append(lenBuffer, metadata...)
    24  	return append(framedMetadata, message...)
    25  }
    26  
    27  // A randomizedVerifier represents a Verifier in the partially blind RSA signature protocol.
    28  // It carries state needed to produce and validate an RSA signature produced
    29  // using the blind RSA protocol.
    30  type randomizedVerifier struct {
    31  	// Public key of the Signer
    32  	pk *keys.BigPublicKey
    33  
    34  	// Identifier of the cryptographic hash function used in producing the message signature
    35  	cryptoHash crypto.Hash
    36  
    37  	// Hash function used in producing the message signature
    38  	hash hash.Hash
    39  }
    40  
    41  // NewVerifier creates a new PBRSAVerifier using the corresponding Signer parameters.
    42  // This corresponds to the RSAPBSSA-SHA384-PSS-Deterministic variant. See the specification for more details:
    43  // https://datatracker.ietf.org/doc/html/draft-amjad-cfrg-partially-blind-rsa#name-rsapbssa-variants
    44  func NewVerifier(pk *rsa.PublicKey, hash crypto.Hash) Verifier {
    45  	h := common.ConvertHashFunction(hash)
    46  	return randomizedVerifier{
    47  		pk:         keys.NewBigPublicKey(pk),
    48  		cryptoHash: hash,
    49  		hash:       h,
    50  	}
    51  }
    52  
    53  // derivePublicKey tweaks the public key based on the input metadata.
    54  //
    55  // See the specification for more details:
    56  // https://datatracker.ietf.org/doc/html/draft-amjad-cfrg-partially-blind-rsa-00#name-public-key-augmentation
    57  //
    58  // See the following issue for more discussion on HKDF vs hash-to-field:
    59  // https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/issues/202
    60  func derivePublicKey(h crypto.Hash, pk *keys.BigPublicKey, metadata []byte) *keys.BigPublicKey {
    61  	// expandLen = ceil((ceil(log2(\lambda)/2) + k) / 8), where k is the security parameter of the suite (e.g., k = 128).
    62  	// We stretch the input metadata beyond \lambda bits s.t. the output bytes are indifferentiable from truly random bytes
    63  	lambda := pk.N.BitLen() / 2
    64  	expandLen := uint((lambda + 128) / 8)
    65  
    66  	hkdfSalt := make([]byte, (pk.N.BitLen()+7)/8)
    67  	pk.N.FillBytes(hkdfSalt)
    68  	hkdfInput := append([]byte("key"), append(metadata, 0x00)...)
    69  
    70  	hkdf := hkdf.New(h.New, hkdfInput, hkdfSalt, []byte("PBRSA"))
    71  	bytes := make([]byte, expandLen)
    72  	_, err := hkdf.Read(bytes)
    73  	if err != nil {
    74  		panic(err)
    75  	}
    76  
    77  	// H_MD(D) = 1 || G(x), where G(x) is output of length \lambda-2 bits
    78  	// We do this by sampling \lambda bits, clearing the top two bits (so the output is \lambda-2 bits)
    79  	// and setting the bottom bit (so the result is odd).
    80  	newE := new(big.Int).SetBytes(bytes[:lambda/8])
    81  	newE.SetBit(newE, 0, 1)
    82  	newE.SetBit(newE, lambda-1, 0)
    83  	newE.SetBit(newE, lambda-2, 0)
    84  
    85  	// Compute e_MD = e * H_MD(D)
    86  	return &keys.BigPublicKey{
    87  		N: pk.N,
    88  		E: newE,
    89  	}
    90  }
    91  
    92  // deriveKeyPair tweaks the private key using the metadata as input.
    93  //
    94  // See the specification for more details:
    95  // https://datatracker.ietf.org/doc/html/draft-amjad-cfrg-partially-blind-rsa-00#name-private-key-augmentation
    96  func deriveKeyPair(h crypto.Hash, sk *keys.BigPrivateKey, metadata []byte) *keys.BigPrivateKey {
    97  	// pih(N) = (p-1)(q-1)
    98  	pm1 := new(big.Int).Set(sk.P)
    99  	pm1.Sub(pm1, new(big.Int).SetInt64(int64(1)))
   100  	qm1 := new(big.Int).Set(sk.Q)
   101  	qm1.Sub(qm1, new(big.Int).SetInt64(int64(1)))
   102  	phi := new(big.Int).Mul(pm1, qm1)
   103  
   104  	// d = e^-1 mod phi(N)
   105  	pk := derivePublicKey(h, sk.Pk, metadata)
   106  	bigE := new(big.Int).Mod(pk.E, phi)
   107  	d := new(big.Int).ModInverse(bigE, phi)
   108  	return &keys.BigPrivateKey{
   109  		Pk: pk,
   110  		D:  d,
   111  		P:  sk.P,
   112  		Q:  sk.Q,
   113  	}
   114  }
   115  
   116  func fixedPartiallyBlind(message, salt []byte, r, rInv *big.Int, pk *keys.BigPublicKey, hash hash.Hash) ([]byte, VerifierState, error) {
   117  	encodedMsg, err := common.EncodeMessageEMSAPSS(message, pk.N, hash, salt)
   118  	if err != nil {
   119  		return nil, VerifierState{}, err
   120  	}
   121  
   122  	m := new(big.Int).SetBytes(encodedMsg)
   123  
   124  	bigE := pk.E
   125  	x := new(big.Int).Exp(r, bigE, pk.N)
   126  	z := new(big.Int).Set(m)
   127  	z.Mul(z, x)
   128  	z.Mod(z, pk.N)
   129  
   130  	kLen := (pk.N.BitLen() + 7) / 8
   131  	blindedMsg := make([]byte, kLen)
   132  	z.FillBytes(blindedMsg)
   133  
   134  	return blindedMsg, VerifierState{
   135  		encodedMsg: encodedMsg,
   136  		pk:         pk,
   137  		hash:       hash,
   138  		salt:       salt,
   139  		rInv:       rInv,
   140  	}, nil
   141  }
   142  
   143  // Verifier is a type that implements the client side of the partially blind RSA
   144  // protocol, described in https://datatracker.ietf.org/doc/html/draft-amjad-cfrg-partially-blind-rsa-00
   145  type Verifier interface {
   146  	// Blind initializes the partially blind RSA protocol using an input message and source of
   147  	// randomness. The signature includes a randomly generated PSS salt whose length equals the
   148  	// size of the underlying hash function. This function fails if randomness was not provided.
   149  	Blind(random io.Reader, message, metadata []byte) ([]byte, VerifierState, error)
   150  
   151  	// FixedBlind initializes the partially blind RSA protocol using an input message, metadata, and randomness values.
   152  	FixedBlind(message, metadata, salt, blind, blindInv []byte) ([]byte, VerifierState, error)
   153  
   154  	// Verify verifies the input (message, signature) pair using the augmented public key
   155  	// and produces an error upon failure.
   156  	Verify(message, signature, metadata []byte) error
   157  
   158  	// Hash returns the hash function associated with the Verifier.
   159  	Hash() hash.Hash
   160  }
   161  
   162  // Blind initializes the partially blind RSA protocol using an input message and source of randomness. The
   163  // signature includes a randomly generated PSS salt whose length equals the size of the underlying
   164  // hash function. This function fails if randomness was not provided.
   165  //
   166  // See the specification for more details:
   167  // https://datatracker.ietf.org/doc/html/draft-amjad-cfrg-partially-blind-rsa-00#name-blind
   168  func (v randomizedVerifier) Blind(random io.Reader, message, metadata []byte) ([]byte, VerifierState, error) {
   169  	if random == nil {
   170  		return nil, VerifierState{}, common.ErrInvalidRandomness
   171  	}
   172  
   173  	salt := make([]byte, v.hash.Size())
   174  	_, err := io.ReadFull(rand.Reader, salt)
   175  	if err != nil {
   176  		return nil, VerifierState{}, err
   177  	}
   178  
   179  	r, rInv, err := common.GenerateBlindingFactor(random, v.pk.N)
   180  	if err != nil {
   181  		return nil, VerifierState{}, err
   182  	}
   183  
   184  	return v.FixedBlind(message, metadata, salt, r.Bytes(), rInv.Bytes())
   185  }
   186  
   187  // FixedBlind initializes the partially blind RSA using fixed randomness as input.
   188  func (v randomizedVerifier) FixedBlind(message, metadata, salt, blind, blindInv []byte) ([]byte, VerifierState, error) {
   189  	r := new(big.Int).SetBytes(blind)
   190  	rInv := new(big.Int).SetBytes(blindInv)
   191  	metadataKey := derivePublicKey(v.cryptoHash, v.pk, metadata)
   192  	inputMsg := encodeMessageMetadata(message, metadata)
   193  	return fixedPartiallyBlind(inputMsg, salt, r, rInv, metadataKey, v.hash)
   194  }
   195  
   196  // Verify verifies the input (message, signature) pair using the augmented public key
   197  // and produces an error upon failure.
   198  //
   199  // See the specification for more details:
   200  // https://datatracker.ietf.org/doc/html/draft-amjad-cfrg-partially-blind-rsa-00#name-verification-2
   201  func (v randomizedVerifier) Verify(message, metadata, signature []byte) error {
   202  	metadataKey := derivePublicKey(v.cryptoHash, v.pk, metadata)
   203  	inputMsg := encodeMessageMetadata(message, metadata)
   204  	return common.VerifyMessageSignature(inputMsg, signature, v.hash.Size(), metadataKey, v.cryptoHash)
   205  }
   206  
   207  // Hash returns the hash function associated with the Verifier.
   208  func (v randomizedVerifier) Hash() hash.Hash {
   209  	return v.hash
   210  }
   211  
   212  // A VerifierState carries state needed to complete the blind signature protocol
   213  // as a verifier.
   214  type VerifierState struct {
   215  	// Public key of the Signer
   216  	pk *keys.BigPublicKey
   217  
   218  	// Hash function used in producing the message signature
   219  	hash hash.Hash
   220  
   221  	// The hashed and encoded message being signed
   222  	encodedMsg []byte
   223  
   224  	// The salt used when encoding the message
   225  	salt []byte
   226  
   227  	// Inverse of the blinding factor produced by the Verifier
   228  	rInv *big.Int
   229  }
   230  
   231  // Finalize computes and outputs the final signature, if it's valid. Otherwise, it returns an error.
   232  //
   233  // See the specification for more details:
   234  // https://datatracker.ietf.org/doc/html/draft-amjad-cfrg-partially-blind-rsa-00#name-finalize
   235  func (state VerifierState) Finalize(data []byte) ([]byte, error) {
   236  	kLen := (state.pk.N.BitLen() + 7) / 8
   237  	if len(data) != kLen {
   238  		return nil, common.ErrUnexpectedSize
   239  	}
   240  
   241  	z := new(big.Int).SetBytes(data)
   242  	s := new(big.Int).Set(state.rInv)
   243  	s.Mul(s, z)
   244  	s.Mod(s, state.pk.N)
   245  
   246  	sig := make([]byte, kLen)
   247  	s.FillBytes(sig)
   248  
   249  	err := common.VerifyBlindSignature(state.pk, state.encodedMsg, sig)
   250  	if err != nil {
   251  		return nil, err
   252  	}
   253  
   254  	return sig, nil
   255  }
   256  
   257  // CopyBlind returns an encoding of the blind value used in the protocol.
   258  func (state VerifierState) CopyBlind() []byte {
   259  	r := new(big.Int).ModInverse(state.rInv, state.pk.N)
   260  	return r.Bytes()
   261  }
   262  
   263  // CopySalt returns an encoding of the per-message salt used in the protocol.
   264  func (state VerifierState) CopySalt() []byte {
   265  	salt := make([]byte, len(state.salt))
   266  	copy(salt, state.salt)
   267  	return salt
   268  }
   269  
   270  // An Signer represents the Signer in the blind RSA protocol.
   271  // It carries the raw RSA private key used for signing blinded messages.
   272  type Signer struct {
   273  	// An RSA private key
   274  	sk *keys.BigPrivateKey
   275  	h  crypto.Hash
   276  }
   277  
   278  // isSafePrime returns true if the input prime p is safe, i.e., p = (2 * q) + 1 for some prime q
   279  func isSafePrime(p *big.Int) bool {
   280  	q := new(big.Int).Set(p)
   281  	q.Sub(q, big.NewInt(1))
   282  	q.Div(q, big.NewInt(2))
   283  	return q.ProbablyPrime(20)
   284  }
   285  
   286  // NewSigner creates a new Signer for the blind RSA protocol using an RSA private key.
   287  func NewSigner(sk *rsa.PrivateKey, h crypto.Hash) (Signer, error) {
   288  	bigSk := keys.NewBigPrivateKey(sk)
   289  	if !(isSafePrime(bigSk.P) && isSafePrime(bigSk.Q)) {
   290  		return Signer{}, ErrInvalidPrivateKey
   291  	}
   292  
   293  	return Signer{
   294  		sk: bigSk,
   295  		h:  h,
   296  	}, nil
   297  }
   298  
   299  // BlindSign blindly computes the RSA operation using the Signer's private key on the blinded
   300  // message input, if it's of valid length, and returns an error should the function fail.
   301  //
   302  // See the specification for more details:
   303  // https://datatracker.ietf.org/doc/html/draft-amjad-cfrg-partially-blind-rsa-00#name-blindsign
   304  func (signer Signer) BlindSign(data, metadata []byte) ([]byte, error) {
   305  	kLen := (signer.sk.Pk.N.BitLen() + 7) / 8
   306  	if len(data) != kLen {
   307  		return nil, common.ErrUnexpectedSize
   308  	}
   309  
   310  	m := new(big.Int).SetBytes(data)
   311  	if m.Cmp(signer.sk.Pk.N) > 0 {
   312  		return nil, common.ErrInvalidMessageLength
   313  	}
   314  
   315  	skPrime := deriveKeyPair(signer.h, signer.sk, metadata)
   316  
   317  	s, err := common.DecryptAndCheck(rand.Reader, skPrime, m)
   318  	if err != nil {
   319  		return nil, err
   320  	}
   321  
   322  	blindSig := make([]byte, kLen)
   323  	s.FillBytes(blindSig)
   324  
   325  	return blindSig, nil
   326  }
   327  
   328  var (
   329  	// ErrInvalidPrivateKey is the error used if a private key is invalid
   330  	ErrInvalidPrivateKey    = errors.New("blindsign/blindrsa/partiallyblindrsa: invalid private key")
   331  	ErrUnexpectedSize       = common.ErrUnexpectedSize
   332  	ErrInvalidMessageLength = common.ErrInvalidMessageLength
   333  	ErrInvalidRandomness    = common.ErrInvalidRandomness
   334  )
   335
View as plain text