// Copyright 2009 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 rsa implements RSA encryption as specified in PKCS #1 and RFC 8017. // // RSA is a single, fundamental operation that is used in this package to // implement either public-key encryption or public-key signatures. // // The original specification for encryption and signatures with RSA is PKCS #1 // and the terms "RSA encryption" and "RSA signatures" by default refer to // PKCS #1 version 1.5. However, that specification has flaws and new designs // should use version 2, usually called by just OAEP and PSS, where // possible. // // Two sets of interfaces are included in this package. When a more abstract // interface isn't necessary, there are functions for encrypting/decrypting // with v1.5/OAEP and signing/verifying with v1.5/PSS. If one needs to abstract // over the public key primitive, the PrivateKey type implements the // Decrypter and Signer interfaces from the crypto package. // // The RSA operations in this package are not implemented using constant-time algorithms. package internal import ( "crypto" cryptoRSA "crypto/rsa" "crypto/subtle" "errors" "io" "math/big" "xdx.jelly/xgcl/api/common" "xdx.jelly/xgcl/gmath" "xdx.jelly/xgcl/internal/randutil" "xdx.jelly/xgcl/sm" ) // A PublicKey represents the public part of an RSA key. type PublicKey struct { N *big.Int // modulus E int // public exponent } func NewPublicKey() *PublicKey { return &PublicKey{ N: new(big.Int), } } type PrecomputedValues = cryptoRSA.PrecomputedValues // type PrecomputedValues struct { // Dp, Dq *big.Int // D mod (P-1) (or mod Q-1) // Qinv *big.Int // Q^-1 mod P // // CRTValues is used for the 3rd and subsequent primes. Due to a // // historical accident, the CRT for the first two primes is handled // // differently in PKCS #1 and interoperability is sufficiently // // important that we mirror this. // CRTValues []CRTValue // } // CRTValue contains the precomputed Chinese remainder theorem values. type CRTValue = cryptoRSA.CRTValue // type CRTValue struct { // Exp *big.Int // D mod (prime-1). // Coeff *big.Int // R·Coeff ≡ 1 mod Prime. // R *big.Int // product of primes prior to this (inc p and q). // } // A PrivateKey represents an RSA key // type PrivateKey = rsa.PrivateKey type PrivateKey struct { PublicKey // public part. D *big.Int // private exponent Primes []*big.Int // prime factors of N, has >= 2 elements. // Precomputed contains precomputed values that speed up private // operations, if available. Precomputed PrecomputedValues } func NewPrivateKey() *PrivateKey { return &PrivateKey{ PublicKey: PublicKey{ N: new(big.Int), }, D: new(big.Int), Primes: []*big.Int{new(big.Int), new(big.Int)}, } } func (pub *PublicKey) From(k *cryptoRSA.PublicKey) { pub.N = k.N pub.E = k.E } func (pub *PublicKey) UnmarshalCryptoRsa(k *cryptoRSA.PublicKey) *PublicKey { pub.From(k) return pub } func (pub *PublicKey) Into() *cryptoRSA.PublicKey { return &cryptoRSA.PublicKey{ N: pub.N, E: pub.E, } } func (pub *PublicKey) Equal(x crypto.PublicKey) bool { switch xx := x.(type) { case *PublicKey: return pub.N.Cmp(xx.N) == 0 && pub.E == xx.E case *cryptoRSA.PublicKey: return pub.N.Cmp(xx.N) == 0 && pub.E == xx.E default: return false } } func (priv *PrivateKey) From(k *cryptoRSA.PrivateKey) *PrivateKey { priv.PublicKey.From(&k.PublicKey) priv.D = k.D priv.Primes = k.Primes priv.Precomputed = k.Precomputed return priv } func (priv *PrivateKey) Into() *cryptoRSA.PrivateKey { return &cryptoRSA.PrivateKey{ PublicKey: cryptoRSA.PublicKey{ N: priv.PublicKey.N, E: priv.PublicKey.E, }, D: priv.D, Primes: priv.Primes, Precomputed: priv.Precomputed, } } var ( errPublicModulus = errors.New("crypto/rsa: missing public modulus") errPublicExponentSmall = errors.New("crypto/rsa: public exponent too small") errPublicExponentLarge = errors.New("crypto/rsa: public exponent too large") ) // checkPub sanity checks the public key before we use it. // We require pub.E to fit into a 32-bit integer so that we // do not have different behavior depending on whether // int is 32 or 64 bits. See also // https://www.imperialviolet.org/2012/03/16/rsae.html. func checkPub(pub *PublicKey) error { if pub.N == nil { return errPublicModulus } if pub.E < 2 { return errPublicExponentSmall } if pub.E > 1<<31-1 { return errPublicExponentLarge } return nil } // Validate performs basic sanity checks on the key. // It returns nil if the key is valid, or else an error describing a problem. func (priv *PrivateKey) Validate() error { if err := checkPub(&priv.PublicKey); err != nil { return err } // Check that Πprimes == n. modulus := new(big.Int).Set(bigOne) for _, prime := range priv.Primes { // Any primes ≤ 1 will cause divide-by-zero panics later. if prime.Cmp(bigOne) <= 0 { return errors.New("crypto/rsa: invalid prime value") } modulus.Mul(modulus, prime) } if modulus.Cmp(priv.N) != 0 { return errors.New("crypto/rsa: invalid modulus") } // Check that de ≡ 1 mod p-1, for each prime. // This implies that e is coprime to each p-1 as e has a multiplicative // inverse. Therefore e is coprime to lcm(p-1,q-1,r-1,...) = // exponent(ℤ/nℤ). It also implies that a^de ≡ a mod p as a^(p-1) ≡ 1 // mod p. Thus a^de ≡ a mod n for all a coprime to n, as required. congruence := new(big.Int) de := new(big.Int).SetInt64(int64(priv.E)) de.Mul(de, priv.D) for _, prime := range priv.Primes { pminus1 := new(big.Int).Sub(prime, bigOne) congruence.Mod(de, pminus1) if congruence.Cmp(bigOne) != 0 { return errors.New("crypto/rsa: invalid exponents") } } return nil } // Precompute performs some calculations that speed up private key operations // in the future. func (priv *PrivateKey) Precompute() { if priv.Precomputed.Dp != nil { return } priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne) priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp) priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne) priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq) priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0]) r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1]) priv.Precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2) for i := 2; i < len(priv.Primes); i++ { prime := priv.Primes[i] values := &priv.Precomputed.CRTValues[i-2] values.Exp = new(big.Int).Sub(prime, bigOne) values.Exp.Mod(priv.D, values.Exp) values.R = new(big.Int).Set(r) values.Coeff = new(big.Int).ModInverse(r, prime) r.Mul(r, prime) } } // UnmarshalSDF import privateKey from SDF type. func (priv *PrivateKey) UnmarshalSDF(sdfPriv *common.RSArefPrivateKey) error { return priv.FromSDF(sdfPriv) } func (priv *PrivateKey) FromSDF(sdfPriv *common.RSArefPrivateKey) error { if priv.PublicKey.N == nil { priv.PublicKey.N = new(big.Int) } priv.N.SetBytes(sdfPriv.M[:]) if priv.D == nil { priv.D = new(big.Int) } priv.D.SetBytes(sdfPriv.D[:]) // E always be 65537 e := new(big.Int).SetBytes(sdfPriv.E[:]) if e.BitLen() > 32 { return common.SDR_KEYERR } priv.E = int(e.Uint64()) priv.Primes = append(priv.Primes[:0], new(big.Int).SetBytes(sdfPriv.Prime[0][:])) priv.Primes = append(priv.Primes, new(big.Int).SetBytes(sdfPriv.Prime[1][:])) priv.Precompute() return priv.Validate() } // Export export privateKey to SDF type. func (priv *PrivateKey) IntoSDF() (*common.RSArefPrivateKey, error) { ret := &common.RSArefPrivateKey{} if err := priv.UnmarshalSDF(ret); err != nil { return nil, err } return ret, nil } func (priv *PrivateKey) MarshalSDF(sdfPriv *common.RSArefPrivateKey) error { if err := priv.Validate(); err != nil { return err } priv.Precompute() sdfPriv.Bits = uint32(priv.N.BitLen()) if sdfPriv.Bits > common.RSAref_MAX_BITS || len(priv.Primes) != 2 { return common.SDR_KEYERR } _ = gmath.FillBytes(priv.N, sdfPriv.M[:]) _ = gmath.FillBytes(new(big.Int).SetInt64(int64(priv.E)), sdfPriv.E[:]) // FIXME _ = gmath.FillBytes(priv.D, sdfPriv.D[:]) _ = gmath.FillBytes(priv.Primes[0], sdfPriv.Prime[0][:]) _ = gmath.FillBytes(priv.Primes[1], sdfPriv.Prime[1][:]) _ = gmath.FillBytes(priv.Precomputed.Dp, sdfPriv.Pexp[0][:]) _ = gmath.FillBytes(priv.Precomputed.Dq, sdfPriv.Pexp[1][:]) _ = gmath.FillBytes(priv.Precomputed.Qinv, sdfPriv.Coef[:]) return nil } // Set set pbulicKey directly by M and E, big-endian bytes. func (pub *PublicKey) Set(M []byte, E []byte) error { if pub.N == nil { pub.N = new(big.Int) } pub.N.SetBytes(M[:]) e := new(Int).SetBytes(E[:]) if e.BitLen() > 32 { return common.SDR_KEYERR } pub.E = int(e.Uint64()) return nil } func (pub *PublicKey) IntoSDF() (*common.RSArefPublicKey, error) { ret := &common.RSArefPublicKey{} if err := pub.MarshalSDF(ret); err != nil { return nil, err } return ret, nil } // MarshalSDF export publicKey to SDF type. func (pub *PublicKey) MarshalSDF(sdfPub *common.RSArefPublicKey) error { if err := checkPub(pub); err != nil { return err } sdfPub.Bits = uint32(pub.N.BitLen()) if sdfPub.Bits > common.RSAref_MAX_BITS { return common.SDR_KEYERR } _ = gmath.FillBytes(pub.N, sdfPub.M[:]) _ = gmath.FillBytes(new(big.Int).SetInt64(int64(pub.E)), sdfPub.E[:]) // FIXME return nil } // UnmarshalSDF import publicKey from SDF type. func (pub *PublicKey) UnmarshalSDF(sdfPub *common.RSArefPublicKey) error { return pub.FromSDF(sdfPub) } func (pub *PublicKey) FromSDF(sdfPub *common.RSArefPublicKey) error { if pub.N == nil { pub.N = new(big.Int) } pub.N.SetBytes(sdfPub.M[:]) e := new(big.Int).SetBytes(sdfPub.E[:]) if e.BitLen() > 32 { return common.SDR_KEYERR } pub.E = int(e.Uint64()) return checkPub(pub) } // Size returns the modulus size in bytes. Raw signatures and ciphertexts // for or by this public key will have the same size. func (pub *PublicKey) Size() int { return (pub.N.BitLen() + 7) / 8 } // GenerateKey generates an RSA keypair of the given bit size using the // random source random (for example, crypto/rand.Reader). func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) { priv, err := cryptoRSA.GenerateKey(random, bits) if err != nil { return nil, err } privateKey := &PrivateKey{} privateKey.From(priv) return privateKey, nil } // ErrDecryption represents a failure to decrypt a message. // It is deliberately vague to avoid adaptive attacks. var ErrDecryption = errors.New("crypto/rsa: decryption error") // ErrVerification represents a failure to verify a signature. // It is deliberately vague to avoid adaptive attacks. var ErrVerification = errors.New("crypto/rsa: verification error") // ErrMessageTooLong is returned when attempting to encrypt a message which is // too large for the size of the public key. var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA public key size") // This file implements encryption and decryption using PKCS #1 v1.5 padding. // PKCS1v15DecrypterOpts is for passing options to PKCS #1 v1.5 decryption using // the crypto.Decrypter interface. type PKCS1v15DecryptOptions = cryptoRSA.PKCS1v15DecryptOptions // EncryptPKCS1v15 encrypts the given message with RSA and the padding // scheme from PKCS #1 v1.5. The message must be no longer than the // length of the public modulus minus 11 bytes. // // The rand parameter is used as a source of entropy to ensure that // encrypting the same message twice doesn't result in the same // ciphertext. // // WARNING: use of this function to encrypt plaintexts other than // session keys is dangerous. Use RSA OAEP in new protocols. func EncryptPKCS1v15(rand io.Reader, pub *PublicKey, msg []byte) ([]byte, error) { // return rsa.EncryptPKCS1v15(rand, pub.Into(), msg) randutil.MaybeReadByte(rand) if err := checkPub(pub); err != nil { return nil, err } k := pub.Size() if len(msg) > k-11 { return nil, ErrMessageTooLong } // EM = 0x00 || 0x02 || PS || 0x00 || M em := make([]byte, k) em[1] = 2 ps, mm := em[2:len(em)-len(msg)-1], em[len(em)-len(msg):] err := nonZeroRandomBytes(ps, rand) if err != nil { return nil, err } em[len(em)-len(msg)-1] = 0 copy(mm, msg) m := new(big.Int).SetBytes(em) c := encrypt(new(big.Int), pub, m) gmath.FillBytes(c, em) return em, nil } // DecryptPKCS1v15 decrypts a plaintext using RSA and the padding scheme from PKCS #1 v1.5. // If rand != nil, it uses RSA blinding to avoid timing side-channel attacks. // // Note that whether this function returns an error or not discloses secret // information. If an attacker can cause this function to run repeatedly and // learn whether each instance returned an error then they can decrypt and // forge signatures as if they had the private key. See // DecryptPKCS1v15SessionKey for a way of solving this problem. func DecryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) ([]byte, error) { // return rsa.DecryptPKCS1v15(rand, priv.Into(), ciphertext) if err := checkPub(&priv.PublicKey); err != nil { return nil, err } valid, out, index, err := decryptPKCS1v15(rand, priv, ciphertext) if err != nil { return nil, err } if valid == 0 { return nil, ErrDecryption } return out[index:], nil } // decryptPKCS1v15 decrypts ciphertext using priv and blinds the operation if // rand is not nil. It returns one or zero in valid that indicates whether the // plaintext was correctly structured. In either case, the plaintext is // returned in em so that it may be read independently of whether it was valid // in order to maintain constant memory access patterns. If the plaintext was // valid then index contains the index of the original message in em. func decryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (valid int, em []byte, index int, err error) { k := priv.Size() if k < 11 { err = ErrDecryption return } c := new(big.Int).SetBytes(ciphertext) m, err := decrypt(rand, priv, c) if err != nil { return } em = m.FillBytes(make([]byte, k)) firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0) secondByteIsTwo := subtle.ConstantTimeByteEq(em[1], 2) // The remainder of the plaintext must be a string of non-zero random // octets, followed by a 0, followed by the message. // lookingForIndex: 1 iff we are still looking for the zero. // index: the offset of the first zero byte. lookingForIndex := 1 for i := 2; i < len(em); i++ { equals0 := subtle.ConstantTimeByteEq(em[i], 0) index = subtle.ConstantTimeSelect(lookingForIndex&equals0, i, index) lookingForIndex = subtle.ConstantTimeSelect(equals0, 0, lookingForIndex) } // The PS padding must be at least 8 bytes long, and it starts two // bytes into em. validPS := subtle.ConstantTimeLessOrEq(2+8, index) valid = firstByteIsZero & secondByteIsTwo & (^lookingForIndex & 1) & validPS index = subtle.ConstantTimeSelect(valid, index+1, 0) return valid, em, index, nil } // nonZeroRandomBytes fills the given slice with non-zero random octets. func nonZeroRandomBytes(s []byte, rand io.Reader) (err error) { _, err = io.ReadFull(rand, s) if err != nil { return } for i := 0; i < len(s); i++ { for s[i] == 0 { _, err = io.ReadFull(rand, s[i:i+1]) if err != nil { return } // In tests, the PRNG may return all zeros so we do // this to break the loop. s[i] ^= 0x42 } } return } // These are ASN1 DER structures: // DigestInfo ::= SEQUENCE { // digestAlgorithm AlgorithmIdentifier, // digest OCTET STRING // } // For performance, we don't use the generic ASN1 encoder. Rather, we // precompute a prefix of the digest value that makes a valid ASN1 DER string // with the correct contents. var hashPrefixes = map[sm.Hash][]byte{ {Hash: crypto.SHA1}: {0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03, 0x02, 0x1a, 0x05, 0x00, 0x04, 0x14}, {Hash: crypto.SHA256}: {0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20}, sm.SM3: {0x30, 0x2e, 0x30, 0x0d, 0x06, 0x09, 0x2a, 0x81, 0x1c, 0xcf, 0x55, 0x01, 0x83, 0x11, 0x01, 0x05, 0x00, 0x04, 0x20}, } func pkcs1v15HashInfo(hash sm.Hash, inLen int) (hashLen int, prefix []byte, err error) { // Special case: crypto.Hash(0) is used to indicate that the data is // signed directly. if hash.Hash == 0 { return inLen, nil, nil } hashLen = hash.Size() if inLen != hashLen { return 0, nil, errors.New("gcl/rsa: input must be hashed message") } prefix, ok := hashPrefixes[hash] if !ok { return 0, nil, errors.New("gcl/rsa: unsupported hash function") } return } // SignPKCS1v15 calculates the signature of hashed using // RSASSA-PKCS1-V1_5-SIGN from RSA PKCS #1 v1.5. Note that hashed must // be the result of hashing the input message using the given hash // function. If hash is zero, hashed is signed directly. This isn't // advisable except for interoperability. // // If rand is not nil then RSA blinding will be used to avoid timing // side-channel attacks. // // This function is deterministic. Thus, if the set of possible // messages is small, an attacker may be able to build a map from // messages to signatures and identify the signed messages. As ever, // signatures provide authenticity, not confidentiality. func SignPKCS1v15(rand io.Reader, priv *PrivateKey, hash sm.Hash, hashed []byte) ([]byte, error) { hashLen, prefix, err := pkcs1v15HashInfo(hash, len(hashed)) if err != nil { return nil, err } tLen := len(prefix) + hashLen k := priv.Size() if k < tLen+11 { return nil, errors.New("rsa: message too long for RSA public key size") } // EM = 0x00 || 0x01 || PS || 0x00 || T em := make([]byte, k) em[1] = 1 for i := 2; i < k-tLen-1; i++ { em[i] = 0xff } copy(em[k-tLen:k-hashLen], prefix) copy(em[k-hashLen:k], hashed) m := new(big.Int).SetBytes(em) c, err := decryptAndCheck(rand, priv, m) if err != nil { return nil, err } return c.FillBytes(em), nil // return rsa.SignPKCS1v15(rand, priv, hash.Hash, hashed) } // VerifyPKCS1v15 verifies an RSA PKCS #1 v1.5 signature. // hashed is the result of hashing the input message using the given hash // function and sig is the signature. A valid signature is indicated by // returning a nil error. If hash is zero then hashed is used directly. This // isn't advisable except for interoperability. func VerifyPKCS1v15(pub *PublicKey, hash sm.Hash, hashed []byte, sig []byte) error { hashLen, prefix, err := pkcs1v15HashInfo(hash, len(hashed)) if err != nil { return err } tLen := len(prefix) + hashLen k := pub.Size() if k < tLen+11 { return ErrVerification } // RFC 8017 Section 8.2.2: If the length of the signature S is not k // octets (where k is the length in octets of the RSA modulus n), output // "invalid signature" and stop. if k != len(sig) { return ErrVerification } c := new(big.Int).SetBytes(sig) m := encrypt(new(big.Int), pub, c) em := m.FillBytes(make([]byte, k)) // EM = 0x00 || 0x01 || PS || 0x00 || T ok := subtle.ConstantTimeByteEq(em[0], 0) ok &= subtle.ConstantTimeByteEq(em[1], 1) ok &= subtle.ConstantTimeCompare(em[k-hashLen:k], hashed) ok &= subtle.ConstantTimeCompare(em[k-tLen:k-hashLen], prefix) ok &= subtle.ConstantTimeByteEq(em[k-tLen-1], 0) for i := 2; i < k-tLen-1; i++ { ok &= subtle.ConstantTimeByteEq(em[i], 0xff) } if ok != 1 { return ErrVerification } return nil // return rsa.VerifyPKCS1v15(pub, hash.Hash, hashed, sig) } func decryptAndCheck(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) { m, err = decrypt(random, priv, c) if err != nil { return nil, err } // In order to defend against errors in the CRT computation, m^e is // calculated, which should match the original ciphertext. check := encrypt(new(big.Int), &priv.PublicKey, m) if c.Cmp(check) != 0 { return nil, errors.New("rsa: internal error") } return m, nil } // PublicKeyOperationRSA RSA公钥运算。数据格式由应用层封装。inData 应该小于 privateKey.Size() func PublicKeyOperationRSA(publicKey *PublicKey, inData []byte) ([]byte, error) { m := new(big.Int).SetBytes(inData) if m.Cmp(publicKey.N) >= 0 { return nil, common.SDR_INARGERR } c := encrypt(new(big.Int), publicKey, m) ret := make([]byte, common.RSAref_MAX_LEN) err := gmath.FillBytes(c, ret) return ret, err } // PrivateKeyOperationRSA RSA私钥运算。数据格式由应用层封装。inData 应该小于 privateKey.Bits/8 func PrivateKeyOperationRSA(privateKey *PrivateKey, inData []byte) ([]byte, error) { c := new(big.Int).SetBytes(inData) if c.Cmp(privateKey.N) >= 0 { return nil, common.SDR_INARGERR } m, err := decrypt(nil, privateKey, c) if err != nil { return nil, err } ret := make([]byte, common.RSAref_MAX_LEN) err = gmath.FillBytes(m, ret) return ret, err } // Sign implements the crypto.Signer interface func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) (signature []byte, err error) { if pssOpts, ok := opts.(*cryptoRSA.PSSOptions); ok { return cryptoRSA.SignPSS(rand, priv.Into(), pssOpts.Hash, digest, pssOpts) } return SignPKCS1v15(rand, priv, sm.Hash{Hash: opts.HashFunc()}, digest) } func (priv *PrivateKey) Public() crypto.PublicKey { return &priv.PublicKey }