summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--meta/recipes-devtools/go/go-1.17.13.inc2
-rw-r--r--meta/recipes-devtools/go/go-1.20/CVE-2023-45285.patch110
-rw-r--r--meta/recipes-devtools/go/go-1.20/CVE-2023-45287.patch1695
3 files changed, 1807 insertions, 0 deletions
diff --git a/meta/recipes-devtools/go/go-1.17.13.inc b/meta/recipes-devtools/go/go-1.17.13.inc
index 95c4461d3e..6fc07bb910 100644
--- a/meta/recipes-devtools/go/go-1.17.13.inc
+++ b/meta/recipes-devtools/go/go-1.17.13.inc
@@ -48,6 +48,8 @@ SRC_URI += "\
48 file://CVE-2023-39319.patch \ 48 file://CVE-2023-39319.patch \
49 file://CVE-2023-39318.patch \ 49 file://CVE-2023-39318.patch \
50 file://CVE-2023-39326.patch \ 50 file://CVE-2023-39326.patch \
51 file://CVE-2023-45285.patch \
52 file://CVE-2023-45287.patch \
51" 53"
52SRC_URI[main.sha256sum] = "a1a48b23afb206f95e7bbaa9b898d965f90826f6f1d1fc0c1d784ada0cd300fd" 54SRC_URI[main.sha256sum] = "a1a48b23afb206f95e7bbaa9b898d965f90826f6f1d1fc0c1d784ada0cd300fd"
53 55
diff --git a/meta/recipes-devtools/go/go-1.20/CVE-2023-45285.patch b/meta/recipes-devtools/go/go-1.20/CVE-2023-45285.patch
new file mode 100644
index 0000000000..0459ae0a1a
--- /dev/null
+++ b/meta/recipes-devtools/go/go-1.20/CVE-2023-45285.patch
@@ -0,0 +1,110 @@
1From 46bc33819ac86a9596b8059235842f0e0c7469bd Mon Sep 17 00:00:00 2001
2From: Bryan C. Mills <bcmills@google.com>
3Date: Thu, 2 Nov 2023 15:06:35 -0400
4Subject: [PATCH] cmd/go/internal/vcs: error out if the requested repo does not
5 support a secure protocol
6
7Updates #63845.
8Fixes #63972.
9
10Change-Id: If86d6b13d3b55877b35c087112bd76388c9404b8
11Reviewed-on: https://go-review.googlesource.com/c/go/+/539321
12Reviewed-by: Michael Matloob <matloob@golang.org>
13LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
14Reviewed-by: Roland Shoemaker <roland@golang.org>
15Auto-Submit: Bryan Mills <bcmills@google.com>
16(cherry picked from commit be26ae18caf7ddffca4073333f80d0d9e76483c3)
17Reviewed-on: https://go-review.googlesource.com/c/go/+/540335
18Auto-Submit: Dmitri Shuralyov <dmitshur@google.com>
19Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
20
21CVE: CVE-2023-45285
22
23Upstream-Status: Backport [https://github.com/golang/go/commit/46bc33819ac86a9596b8059235842f0e0c7469bd]
24
25Signed-off-by: Soumya Sambu <soumya.sambu@windriver.com>
26---
27 src/cmd/go/internal/vcs/vcs.go | 25 +++++++++++++----
28 .../script/mod_insecure_issue63845.txt | 28 +++++++++++++++++++
29 2 files changed, 47 insertions(+), 6 deletions(-)
30 create mode 100644 src/cmd/go/testdata/script/mod_insecure_issue63845.txt
31
32diff --git a/src/cmd/go/internal/vcs/vcs.go b/src/cmd/go/internal/vcs/vcs.go
33index ab42424..0e2882d 100644
34--- a/src/cmd/go/internal/vcs/vcs.go
35+++ b/src/cmd/go/internal/vcs/vcs.go
36@@ -891,19 +891,32 @@ func repoRootFromVCSPaths(importPath string, security web.SecurityMode, vcsPaths
37 if !srv.schemelessRepo {
38 repoURL = match["repo"]
39 } else {
40- scheme := vcs.Scheme[0] // default to first scheme
41 repo := match["repo"]
42- if vcs.PingCmd != "" {
43- // If we know how to test schemes, scan to find one.
44+ scheme, err := func() (string, error) {
45 for _, s := range vcs.Scheme {
46 if security == web.SecureOnly && !vcs.isSecureScheme(s) {
47 continue
48 }
49- if vcs.Ping(s, repo) == nil {
50- scheme = s
51- break
52+
53+ // If we know how to ping URL schemes for this VCS,
54+ // check that this repo works.
55+ // Otherwise, default to the first scheme
56+ // that meets the requested security level.
57+ if vcs.PingCmd == "" {
58+ return s, nil
59+ }
60+ if err := vcs.Ping(s, repo); err == nil {
61+ return s, nil
62 }
63 }
64+ securityFrag := ""
65+ if security == web.SecureOnly {
66+ securityFrag = "secure "
67+ }
68+ return "", fmt.Errorf("no %sprotocol found for repository", securityFrag)
69+ }()
70+ if err != nil {
71+ return nil, err
72 }
73 repoURL = scheme + "://" + repo
74 }
75diff --git a/src/cmd/go/testdata/script/mod_insecure_issue63845.txt b/src/cmd/go/testdata/script/mod_insecure_issue63845.txt
76new file mode 100644
77index 0000000..5fa6a4f
78--- /dev/null
79+++ b/src/cmd/go/testdata/script/mod_insecure_issue63845.txt
80@@ -0,0 +1,28 @@
81+# Regression test for https://go.dev/issue/63845:
82+# If 'git ls-remote' fails for all secure protocols,
83+# we should fail instead of falling back to an arbitrary protocol.
84+#
85+# Note that this test does not use the local vcweb test server
86+# (vcs-test.golang.org), because the hook for redirecting to that
87+# server bypasses the "ping to determine protocol" logic
88+# in cmd/go/internal/vcs.
89+
90+[!net] skip
91+[!git] skip
92+[short] skip 'tries to access a nonexistent external Git repo'
93+
94+env GOPRIVATE=golang.org
95+env CURLOPT_TIMEOUT_MS=100
96+env GIT_SSH_COMMAND=false
97+
98+! go get -x golang.org/nonexist.git@latest
99+stderr '^git ls-remote https://golang.org/nonexist$'
100+stderr '^git ls-remote git\+ssh://golang.org/nonexist'
101+stderr '^git ls-remote ssh://golang.org/nonexist$'
102+! stderr 'git://'
103+stderr '^go: golang.org/nonexist.git@latest: no secure protocol found for repository$'
104+
105+-- go.mod --
106+module example
107+
108+go 1.19
109--
1102.40.0
diff --git a/meta/recipes-devtools/go/go-1.20/CVE-2023-45287.patch b/meta/recipes-devtools/go/go-1.20/CVE-2023-45287.patch
new file mode 100644
index 0000000000..477e3c98ee
--- /dev/null
+++ b/meta/recipes-devtools/go/go-1.20/CVE-2023-45287.patch
@@ -0,0 +1,1695 @@
1From 8a81fdf165facdcefa06531de5af98a4db343035 Mon Sep 17 00:00:00 2001
2From: Lúcás Meier <cronokirby@gmail.com>
3Date: Tue Jun 8 21:36:06 2021 +0200
4Subject: [PATCH] crypto/rsa: replace big.Int for encryption and decryption
5
6Infamously, big.Int does not provide constant-time arithmetic, making
7its use in cryptographic code quite tricky. RSA uses big.Int
8pervasively, in its public API, for key generation, precomputation, and
9for encryption and decryption. This is a known problem. One mitigation,
10blinding, is already in place during decryption. This helps mitigate the
11very leaky exponentiation operation. Because big.Int is fundamentally
12not constant-time, it's unfortunately difficult to guarantee that
13mitigations like these are completely effective.
14
15This patch removes the use of big.Int for encryption and decryption,
16replacing it with an internal nat type instead. Signing and verification
17are also affected, because they depend on encryption and decryption.
18
19Overall, this patch degrades performance by 55% for private key
20operations, and 4-5x for (much faster) public key operations.
21(Signatures do both, so the slowdown is worse than decryption.)
22
23name old time/op new time/op delta
24DecryptPKCS1v15/2048-8 1.50ms ± 0% 2.34ms ± 0% +56.44% (p=0.000 n=8+10)
25DecryptPKCS1v15/3072-8 4.40ms ± 0% 6.79ms ± 0% +54.33% (p=0.000 n=10+9)
26DecryptPKCS1v15/4096-8 9.31ms ± 0% 15.14ms ± 0% +62.60% (p=0.000 n=10+10)
27EncryptPKCS1v15/2048-8 8.16µs ± 0% 355.58µs ± 0% +4258.90% (p=0.000 n=10+9)
28DecryptOAEP/2048-8 1.50ms ± 0% 2.34ms ± 0% +55.68% (p=0.000 n=10+9)
29EncryptOAEP/2048-8 8.51µs ± 0% 355.95µs ± 0% +4082.75% (p=0.000 n=10+9)
30SignPKCS1v15/2048-8 1.51ms ± 0% 2.69ms ± 0% +77.94% (p=0.000 n=10+10)
31VerifyPKCS1v15/2048-8 7.25µs ± 0% 354.34µs ± 0% +4789.52% (p=0.000 n=9+9)
32SignPSS/2048-8 1.51ms ± 0% 2.70ms ± 0% +78.80% (p=0.000 n=9+10)
33VerifyPSS/2048-8 8.27µs ± 1% 355.65µs ± 0% +4199.39% (p=0.000 n=10+10)
34
35Keep in mind that this is without any assembly at all, and that further
36improvements are likely possible. I think having a review of the logic
37and the cryptography would be a good idea at this stage, before we
38complicate the code too much through optimization.
39
40The bulk of the work is in nat.go. This introduces two new types: nat,
41representing natural numbers, and modulus, representing moduli used in
42modular arithmetic.
43
44A nat has an "announced size", which may be larger than its "true size",
45the number of bits needed to represent this number. Operations on a nat
46will only ever leak its announced size, never its true size, or other
47information about its value. The size of a nat is always clear based on
48how its value is set. For example, x.mod(y, m) will make the announced
49size of x match that of m, since x is reduced modulo m.
50
51Operations assume that the announced size of the operands match what's
52expected (with a few exceptions). For example, x.modAdd(y, m) assumes
53that x and y have the same announced size as m, and that they're reduced
54modulo m.
55
56Nats are represented over unsatured bits.UintSize - 1 bit limbs. This
57means that we can't reuse the assembly routines for big.Int, which use
58saturated bits.UintSize limbs. The advantage of unsaturated limbs is
59that it makes Montgomery multiplication faster, by needing fewer
60registers in a hot loop. This makes exponentiation faster, which
61consists of many Montgomery multiplications.
62
63Moduli use nat internally. Unlike nat, the true size of a modulus always
64matches its announced size. When creating a modulus, any zero padding is
65removed. Moduli will also precompute constants when created, which is
66another reason why having a separate type is desirable.
67
68Updates #20654
69
70Co-authored-by: Filippo Valsorda <filippo@golang.org>
71Change-Id: I73b61f87d58ab912e80a9644e255d552cbadcced
72Reviewed-on: https://go-review.googlesource.com/c/go/+/326012
73Run-TryBot: Filippo Valsorda <filippo@golang.org>
74TryBot-Result: Gopher Robot <gobot@golang.org>
75Reviewed-by: Roland Shoemaker <roland@golang.org>
76Reviewed-by: Joedian Reid <joedian@golang.org>
77
78CVE: CVE-2023-45287
79
80Upstream-Status: Backport [https://github.com/golang/go/commit/8a81fdf165facdcefa06531de5af98a4db343035]
81
82Signed-off-by: Soumya Sambu <soumya.sambu@windriver.com>
83---
84 src/crypto/rsa/example_test.go | 21 +-
85 src/crypto/rsa/nat.go | 626 +++++++++++++++++++++++++++++++++
86 src/crypto/rsa/nat_test.go | 384 ++++++++++++++++++++
87 src/crypto/rsa/pkcs1v15.go | 47 +--
88 src/crypto/rsa/pss.go | 49 ++-
89 src/crypto/rsa/pss_test.go | 10 +-
90 src/crypto/rsa/rsa.go | 172 ++++-----
91 7 files changed, 1140 insertions(+), 169 deletions(-)
92 create mode 100644 src/crypto/rsa/nat.go
93 create mode 100644 src/crypto/rsa/nat_test.go
94
95diff --git a/src/crypto/rsa/example_test.go b/src/crypto/rsa/example_test.go
96index ce5c2d9..52e5639 100644
97--- a/src/crypto/rsa/example_test.go
98+++ b/src/crypto/rsa/example_test.go
99@@ -12,7 +12,6 @@ import (
100 "crypto/sha256"
101 "encoding/hex"
102 "fmt"
103- "io"
104 "os"
105 )
106
107@@ -36,21 +35,17 @@ import (
108 // a buffer that contains a random key. Thus, if the RSA result isn't
109 // well-formed, the implementation uses a random key in constant time.
110 func ExampleDecryptPKCS1v15SessionKey() {
111- // crypto/rand.Reader is a good source of entropy for blinding the RSA
112- // operation.
113- rng := rand.Reader
114-
115 // The hybrid scheme should use at least a 16-byte symmetric key. Here
116 // we read the random key that will be used if the RSA decryption isn't
117 // well-formed.
118 key := make([]byte, 32)
119- if _, err := io.ReadFull(rng, key); err != nil {
120+ if _, err := rand.Read(key); err != nil {
121 panic("RNG failure")
122 }
123
124 rsaCiphertext, _ := hex.DecodeString("aabbccddeeff")
125
126- if err := DecryptPKCS1v15SessionKey(rng, rsaPrivateKey, rsaCiphertext, key); err != nil {
127+ if err := DecryptPKCS1v15SessionKey(nil, rsaPrivateKey, rsaCiphertext, key); err != nil {
128 // Any errors that result will be “public” – meaning that they
129 // can be determined without any secret information. (For
130 // instance, if the length of key is impossible given the RSA
131@@ -86,10 +81,6 @@ func ExampleDecryptPKCS1v15SessionKey() {
132 }
133
134 func ExampleSignPKCS1v15() {
135- // crypto/rand.Reader is a good source of entropy for blinding the RSA
136- // operation.
137- rng := rand.Reader
138-
139 message := []byte("message to be signed")
140
141 // Only small messages can be signed directly; thus the hash of a
142@@ -99,7 +90,7 @@ func ExampleSignPKCS1v15() {
143 // of writing (2016).
144 hashed := sha256.Sum256(message)
145
146- signature, err := SignPKCS1v15(rng, rsaPrivateKey, crypto.SHA256, hashed[:])
147+ signature, err := SignPKCS1v15(nil, rsaPrivateKey, crypto.SHA256, hashed[:])
148 if err != nil {
149 fmt.Fprintf(os.Stderr, "Error from signing: %s\n", err)
150 return
151@@ -151,11 +142,7 @@ func ExampleDecryptOAEP() {
152 ciphertext, _ := hex.DecodeString("4d1ee10e8f286390258c51a5e80802844c3e6358ad6690b7285218a7c7ed7fc3a4c7b950fbd04d4b0239cc060dcc7065ca6f84c1756deb71ca5685cadbb82be025e16449b905c568a19c088a1abfad54bf7ecc67a7df39943ec511091a34c0f2348d04e058fcff4d55644de3cd1d580791d4524b92f3e91695582e6e340a1c50b6c6d78e80b4e42c5b4d45e479b492de42bbd39cc642ebb80226bb5200020d501b24a37bcc2ec7f34e596b4fd6b063de4858dbf5a4e3dd18e262eda0ec2d19dbd8e890d672b63d368768360b20c0b6b8592a438fa275e5fa7f60bef0dd39673fd3989cc54d2cb80c08fcd19dacbc265ee1c6014616b0e04ea0328c2a04e73460")
153 label := []byte("orders")
154
155- // crypto/rand.Reader is a good source of entropy for blinding the RSA
156- // operation.
157- rng := rand.Reader
158-
159- plaintext, err := DecryptOAEP(sha256.New(), rng, test2048Key, ciphertext, label)
160+ plaintext, err := DecryptOAEP(sha256.New(), nil, test2048Key, ciphertext, label)
161 if err != nil {
162 fmt.Fprintf(os.Stderr, "Error from decryption: %s\n", err)
163 return
164diff --git a/src/crypto/rsa/nat.go b/src/crypto/rsa/nat.go
165new file mode 100644
166index 0000000..da521c2
167--- /dev/null
168+++ b/src/crypto/rsa/nat.go
169@@ -0,0 +1,626 @@
170+// Copyright 2021 The Go Authors. All rights reserved.
171+// Use of this source code is governed by a BSD-style
172+// license that can be found in the LICENSE file.
173+
174+package rsa
175+
176+import (
177+ "math/big"
178+ "math/bits"
179+)
180+
181+const (
182+ // _W is the number of bits we use for our limbs.
183+ _W = bits.UintSize - 1
184+ // _MASK selects _W bits from a full machine word.
185+ _MASK = (1 << _W) - 1
186+)
187+
188+// choice represents a constant-time boolean. The value of choice is always
189+// either 1 or 0. We use an int instead of bool in order to make decisions in
190+// constant time by turning it into a mask.
191+type choice uint
192+
193+func not(c choice) choice { return 1 ^ c }
194+
195+const yes = choice(1)
196+const no = choice(0)
197+
198+// ctSelect returns x if on == 1, and y if on == 0. The execution time of this
199+// function does not depend on its inputs. If on is any value besides 1 or 0,
200+// the result is undefined.
201+func ctSelect(on choice, x, y uint) uint {
202+ // When on == 1, mask is 0b111..., otherwise mask is 0b000...
203+ mask := -uint(on)
204+ // When mask is all zeros, we just have y, otherwise, y cancels with itself.
205+ return y ^ (mask & (y ^ x))
206+}
207+
208+// ctEq returns 1 if x == y, and 0 otherwise. The execution time of this
209+// function does not depend on its inputs.
210+func ctEq(x, y uint) choice {
211+ // If x != y, then either x - y or y - x will generate a carry.
212+ _, c1 := bits.Sub(x, y, 0)
213+ _, c2 := bits.Sub(y, x, 0)
214+ return not(choice(c1 | c2))
215+}
216+
217+// ctGeq returns 1 if x >= y, and 0 otherwise. The execution time of this
218+// function does not depend on its inputs.
219+func ctGeq(x, y uint) choice {
220+ // If x < y, then x - y generates a carry.
221+ _, carry := bits.Sub(x, y, 0)
222+ return not(choice(carry))
223+}
224+
225+// nat represents an arbitrary natural number
226+//
227+// Each nat has an announced length, which is the number of limbs it has stored.
228+// Operations on this number are allowed to leak this length, but will not leak
229+// any information about the values contained in those limbs.
230+type nat struct {
231+ // limbs is a little-endian representation in base 2^W with
232+ // W = bits.UintSize - 1. The top bit is always unset between operations.
233+ //
234+ // The top bit is left unset to optimize Montgomery multiplication, in the
235+ // inner loop of exponentiation. Using fully saturated limbs would leave us
236+ // working with 129-bit numbers on 64-bit platforms, wasting a lot of space,
237+ // and thus time.
238+ limbs []uint
239+}
240+
241+// expand expands x to n limbs, leaving its value unchanged.
242+func (x *nat) expand(n int) *nat {
243+ for len(x.limbs) > n {
244+ if x.limbs[len(x.limbs)-1] != 0 {
245+ panic("rsa: internal error: shrinking nat")
246+ }
247+ x.limbs = x.limbs[:len(x.limbs)-1]
248+ }
249+ if cap(x.limbs) < n {
250+ newLimbs := make([]uint, n)
251+ copy(newLimbs, x.limbs)
252+ x.limbs = newLimbs
253+ return x
254+ }
255+ extraLimbs := x.limbs[len(x.limbs):n]
256+ for i := range extraLimbs {
257+ extraLimbs[i] = 0
258+ }
259+ x.limbs = x.limbs[:n]
260+ return x
261+}
262+
263+// reset returns a zero nat of n limbs, reusing x's storage if n <= cap(x.limbs).
264+func (x *nat) reset(n int) *nat {
265+ if cap(x.limbs) < n {
266+ x.limbs = make([]uint, n)
267+ return x
268+ }
269+ for i := range x.limbs {
270+ x.limbs[i] = 0
271+ }
272+ x.limbs = x.limbs[:n]
273+ return x
274+}
275+
276+// clone returns a new nat, with the same value and announced length as x.
277+func (x *nat) clone() *nat {
278+ out := &nat{make([]uint, len(x.limbs))}
279+ copy(out.limbs, x.limbs)
280+ return out
281+}
282+
283+// natFromBig creates a new natural number from a big.Int.
284+//
285+// The announced length of the resulting nat is based on the actual bit size of
286+// the input, ignoring leading zeroes.
287+func natFromBig(x *big.Int) *nat {
288+ xLimbs := x.Bits()
289+ bitSize := bigBitLen(x)
290+ requiredLimbs := (bitSize + _W - 1) / _W
291+
292+ out := &nat{make([]uint, requiredLimbs)}
293+ outI := 0
294+ shift := 0
295+ for i := range xLimbs {
296+ xi := uint(xLimbs[i])
297+ out.limbs[outI] |= (xi << shift) & _MASK
298+ outI++
299+ if outI == requiredLimbs {
300+ return out
301+ }
302+ out.limbs[outI] = xi >> (_W - shift)
303+ shift++ // this assumes bits.UintSize - _W = 1
304+ if shift == _W {
305+ shift = 0
306+ outI++
307+ }
308+ }
309+ return out
310+}
311+
312+// fillBytes sets bytes to x as a zero-extended big-endian byte slice.
313+//
314+// If bytes is not long enough to contain the number or at least len(x.limbs)-1
315+// limbs, or has zero length, fillBytes will panic.
316+func (x *nat) fillBytes(bytes []byte) []byte {
317+ if len(bytes) == 0 {
318+ panic("nat: fillBytes invoked with too small buffer")
319+ }
320+ for i := range bytes {
321+ bytes[i] = 0
322+ }
323+ shift := 0
324+ outI := len(bytes) - 1
325+ for i, limb := range x.limbs {
326+ remainingBits := _W
327+ for remainingBits >= 8 {
328+ bytes[outI] |= byte(limb) << shift
329+ consumed := 8 - shift
330+ limb >>= consumed
331+ remainingBits -= consumed
332+ shift = 0
333+ outI--
334+ if outI < 0 {
335+ if limb != 0 || i < len(x.limbs)-1 {
336+ panic("nat: fillBytes invoked with too small buffer")
337+ }
338+ return bytes
339+ }
340+ }
341+ bytes[outI] = byte(limb)
342+ shift = remainingBits
343+ }
344+ return bytes
345+}
346+
347+// natFromBytes converts a slice of big-endian bytes into a nat.
348+//
349+// The announced length of the output depends on the length of bytes. Unlike
350+// big.Int, creating a nat will not remove leading zeros.
351+func natFromBytes(bytes []byte) *nat {
352+ bitSize := len(bytes) * 8
353+ requiredLimbs := (bitSize + _W - 1) / _W
354+
355+ out := &nat{make([]uint, requiredLimbs)}
356+ outI := 0
357+ shift := 0
358+ for i := len(bytes) - 1; i >= 0; i-- {
359+ bi := bytes[i]
360+ out.limbs[outI] |= uint(bi) << shift
361+ shift += 8
362+ if shift >= _W {
363+ shift -= _W
364+ out.limbs[outI] &= _MASK
365+ outI++
366+ if shift > 0 {
367+ out.limbs[outI] = uint(bi) >> (8 - shift)
368+ }
369+ }
370+ }
371+ return out
372+}
373+
374+// cmpEq returns 1 if x == y, and 0 otherwise.
375+//
376+// Both operands must have the same announced length.
377+func (x *nat) cmpEq(y *nat) choice {
378+ // Eliminate bounds checks in the loop.
379+ size := len(x.limbs)
380+ xLimbs := x.limbs[:size]
381+ yLimbs := y.limbs[:size]
382+
383+ equal := yes
384+ for i := 0; i < size; i++ {
385+ equal &= ctEq(xLimbs[i], yLimbs[i])
386+ }
387+ return equal
388+}
389+
390+// cmpGeq returns 1 if x >= y, and 0 otherwise.
391+//
392+// Both operands must have the same announced length.
393+func (x *nat) cmpGeq(y *nat) choice {
394+ // Eliminate bounds checks in the loop.
395+ size := len(x.limbs)
396+ xLimbs := x.limbs[:size]
397+ yLimbs := y.limbs[:size]
398+
399+ var c uint
400+ for i := 0; i < size; i++ {
401+ c = (xLimbs[i] - yLimbs[i] - c) >> _W
402+ }
403+ // If there was a carry, then subtracting y underflowed, so
404+ // x is not greater than or equal to y.
405+ return not(choice(c))
406+}
407+
408+// assign sets x <- y if on == 1, and does nothing otherwise.
409+//
410+// Both operands must have the same announced length.
411+func (x *nat) assign(on choice, y *nat) *nat {
412+ // Eliminate bounds checks in the loop.
413+ size := len(x.limbs)
414+ xLimbs := x.limbs[:size]
415+ yLimbs := y.limbs[:size]
416+
417+ for i := 0; i < size; i++ {
418+ xLimbs[i] = ctSelect(on, yLimbs[i], xLimbs[i])
419+ }
420+ return x
421+}
422+
423+// add computes x += y if on == 1, and does nothing otherwise. It returns the
424+// carry of the addition regardless of on.
425+//
426+// Both operands must have the same announced length.
427+func (x *nat) add(on choice, y *nat) (c uint) {
428+ // Eliminate bounds checks in the loop.
429+ size := len(x.limbs)
430+ xLimbs := x.limbs[:size]
431+ yLimbs := y.limbs[:size]
432+
433+ for i := 0; i < size; i++ {
434+ res := xLimbs[i] + yLimbs[i] + c
435+ xLimbs[i] = ctSelect(on, res&_MASK, xLimbs[i])
436+ c = res >> _W
437+ }
438+ return
439+}
440+
441+// sub computes x -= y if on == 1, and does nothing otherwise. It returns the
442+// borrow of the subtraction regardless of on.
443+//
444+// Both operands must have the same announced length.
445+func (x *nat) sub(on choice, y *nat) (c uint) {
446+ // Eliminate bounds checks in the loop.
447+ size := len(x.limbs)
448+ xLimbs := x.limbs[:size]
449+ yLimbs := y.limbs[:size]
450+
451+ for i := 0; i < size; i++ {
452+ res := xLimbs[i] - yLimbs[i] - c
453+ xLimbs[i] = ctSelect(on, res&_MASK, xLimbs[i])
454+ c = res >> _W
455+ }
456+ return
457+}
458+
459+// modulus is used for modular arithmetic, precomputing relevant constants.
460+//
461+// Moduli are assumed to be odd numbers. Moduli can also leak the exact
462+// number of bits needed to store their value, and are stored without padding.
463+//
464+// Their actual value is still kept secret.
465+type modulus struct {
466+ // The underlying natural number for this modulus.
467+ //
468+ // This will be stored without any padding, and shouldn't alias with any
469+ // other natural number being used.
470+ nat *nat
471+ leading int // number of leading zeros in the modulus
472+ m0inv uint // -nat.limbs[0]⁻¹ mod _W
473+}
474+
475+// minusInverseModW computes -x⁻¹ mod _W with x odd.
476+//
477+// This operation is used to precompute a constant involved in Montgomery
478+// multiplication.
479+func minusInverseModW(x uint) uint {
480+ // Every iteration of this loop doubles the least-significant bits of
481+ // correct inverse in y. The first three bits are already correct (1⁻¹ = 1,
482+ // 3⁻¹ = 3, 5⁻¹ = 5, and 7⁻¹ = 7 mod 8), so doubling five times is enough
483+ // for 61 bits (and wastes only one iteration for 31 bits).
484+ //
485+ // See https://crypto.stackexchange.com/a/47496.
486+ y := x
487+ for i := 0; i < 5; i++ {
488+ y = y * (2 - x*y)
489+ }
490+ return (1 << _W) - (y & _MASK)
491+}
492+
493+// modulusFromNat creates a new modulus from a nat.
494+//
495+// The nat should be odd, nonzero, and the number of significant bits in the
496+// number should be leakable. The nat shouldn't be reused.
497+func modulusFromNat(nat *nat) *modulus {
498+ m := &modulus{}
499+ m.nat = nat
500+ size := len(m.nat.limbs)
501+ for m.nat.limbs[size-1] == 0 {
502+ size--
503+ }
504+ m.nat.limbs = m.nat.limbs[:size]
505+ m.leading = _W - bitLen(m.nat.limbs[size-1])
506+ m.m0inv = minusInverseModW(m.nat.limbs[0])
507+ return m
508+}
509+
510+// bitLen is a version of bits.Len that only leaks the bit length of n, but not
511+// its value. bits.Len and bits.LeadingZeros use a lookup table for the
512+// low-order bits on some architectures.
513+func bitLen(n uint) int {
514+ var len int
515+ // We assume, here and elsewhere, that comparison to zero is constant time
516+ // with respect to different non-zero values.
517+ for n != 0 {
518+ len++
519+ n >>= 1
520+ }
521+ return len
522+}
523+
524+// bigBitLen is a version of big.Int.BitLen that only leaks the bit length of x,
525+// but not its value. big.Int.BitLen uses bits.Len.
526+func bigBitLen(x *big.Int) int {
527+ xLimbs := x.Bits()
528+ fullLimbs := len(xLimbs) - 1
529+ topLimb := uint(xLimbs[len(xLimbs)-1])
530+ return fullLimbs*bits.UintSize + bitLen(topLimb)
531+}
532+
533+// modulusSize returns the size of m in bytes.
534+func modulusSize(m *modulus) int {
535+ bits := len(m.nat.limbs)*_W - int(m.leading)
536+ return (bits + 7) / 8
537+}
538+
539+// shiftIn calculates x = x << _W + y mod m.
540+//
541+// This assumes that x is already reduced mod m, and that y < 2^_W.
542+func (x *nat) shiftIn(y uint, m *modulus) *nat {
543+ d := new(nat).resetFor(m)
544+
545+ // Eliminate bounds checks in the loop.
546+ size := len(m.nat.limbs)
547+ xLimbs := x.limbs[:size]
548+ dLimbs := d.limbs[:size]
549+ mLimbs := m.nat.limbs[:size]
550+
551+ // Each iteration of this loop computes x = 2x + b mod m, where b is a bit
552+ // from y. Effectively, it left-shifts x and adds y one bit at a time,
553+ // reducing it every time.
554+ //
555+ // To do the reduction, each iteration computes both 2x + b and 2x + b - m.
556+ // The next iteration (and finally the return line) will use either result
557+ // based on whether the subtraction underflowed.
558+ needSubtraction := no
559+ for i := _W - 1; i >= 0; i-- {
560+ carry := (y >> i) & 1
561+ var borrow uint
562+ for i := 0; i < size; i++ {
563+ l := ctSelect(needSubtraction, dLimbs[i], xLimbs[i])
564+
565+ res := l<<1 + carry
566+ xLimbs[i] = res & _MASK
567+ carry = res >> _W
568+
569+ res = xLimbs[i] - mLimbs[i] - borrow
570+ dLimbs[i] = res & _MASK
571+ borrow = res >> _W
572+ }
573+ // See modAdd for how carry (aka overflow), borrow (aka underflow), and
574+ // needSubtraction relate.
575+ needSubtraction = ctEq(carry, borrow)
576+ }
577+ return x.assign(needSubtraction, d)
578+}
579+
580+// mod calculates out = x mod m.
581+//
582+// This works regardless how large the value of x is.
583+//
584+// The output will be resized to the size of m and overwritten.
585+func (out *nat) mod(x *nat, m *modulus) *nat {
586+ out.resetFor(m)
587+ // Working our way from the most significant to the least significant limb,
588+ // we can insert each limb at the least significant position, shifting all
589+ // previous limbs left by _W. This way each limb will get shifted by the
590+ // correct number of bits. We can insert at least N - 1 limbs without
591+ // overflowing m. After that, we need to reduce every time we shift.
592+ i := len(x.limbs) - 1
593+ // For the first N - 1 limbs we can skip the actual shifting and position
594+ // them at the shifted position, which starts at min(N - 2, i).
595+ start := len(m.nat.limbs) - 2
596+ if i < start {
597+ start = i
598+ }
599+ for j := start; j >= 0; j-- {
600+ out.limbs[j] = x.limbs[i]
601+ i--
602+ }
603+ // We shift in the remaining limbs, reducing modulo m each time.
604+ for i >= 0 {
605+ out.shiftIn(x.limbs[i], m)
606+ i--
607+ }
608+ return out
609+}
610+
611+// expandFor ensures out has the right size to work with operations modulo m.
612+//
613+// This assumes that out has as many or fewer limbs than m, or that the extra
614+// limbs are all zero (which may happen when decoding a value that has leading
615+// zeroes in its bytes representation that spill over the limb threshold).
616+func (out *nat) expandFor(m *modulus) *nat {
617+ return out.expand(len(m.nat.limbs))
618+}
619+
620+// resetFor ensures out has the right size to work with operations modulo m.
621+//
622+// out is zeroed and may start at any size.
623+func (out *nat) resetFor(m *modulus) *nat {
624+ return out.reset(len(m.nat.limbs))
625+}
626+
627+// modSub computes x = x - y mod m.
628+//
629+// The length of both operands must be the same as the modulus. Both operands
630+// must already be reduced modulo m.
631+func (x *nat) modSub(y *nat, m *modulus) *nat {
632+ underflow := x.sub(yes, y)
633+ // If the subtraction underflowed, add m.
634+ x.add(choice(underflow), m.nat)
635+ return x
636+}
637+
638+// modAdd computes x = x + y mod m.
639+//
640+// The length of both operands must be the same as the modulus. Both operands
641+// must already be reduced modulo m.
642+func (x *nat) modAdd(y *nat, m *modulus) *nat {
643+ overflow := x.add(yes, y)
644+ underflow := not(x.cmpGeq(m.nat)) // x < m
645+
646+ // Three cases are possible:
647+ //
648+ // - overflow = 0, underflow = 0
649+ //
650+ // In this case, addition fits in our limbs, but we can still subtract away
651+ // m without an underflow, so we need to perform the subtraction to reduce
652+ // our result.
653+ //
654+ // - overflow = 0, underflow = 1
655+ //
656+ // The addition fits in our limbs, but we can't subtract m without
657+ // underflowing. The result is already reduced.
658+ //
659+ // - overflow = 1, underflow = 1
660+ //
661+ // The addition does not fit in our limbs, and the subtraction's borrow
662+ // would cancel out with the addition's carry. We need to subtract m to
663+ // reduce our result.
664+ //
665+ // The overflow = 1, underflow = 0 case is not possible, because y is at
666+ // most m - 1, and if adding m - 1 overflows, then subtracting m must
667+ // necessarily underflow.
668+ needSubtraction := ctEq(overflow, uint(underflow))
669+
670+ x.sub(needSubtraction, m.nat)
671+ return x
672+}
673+
674+// montgomeryRepresentation calculates x = x * R mod m, with R = 2^(_W * n) and
675+// n = len(m.nat.limbs).
676+//
677+// Faster Montgomery multiplication replaces standard modular multiplication for
678+// numbers in this representation.
679+//
680+// This assumes that x is already reduced mod m.
681+func (x *nat) montgomeryRepresentation(m *modulus) *nat {
682+ for i := 0; i < len(m.nat.limbs); i++ {
683+ x.shiftIn(0, m) // x = x * 2^_W mod m
684+ }
685+ return x
686+}
687+
688+// montgomeryMul calculates d = a * b / R mod m, with R = 2^(_W * n) and
689+// n = len(m.nat.limbs), using the Montgomery Multiplication technique.
690+//
691+// All inputs should be the same length, not aliasing d, and already
692+// reduced modulo m. d will be resized to the size of m and overwritten.
693+func (d *nat) montgomeryMul(a *nat, b *nat, m *modulus) *nat {
694+ // See https://bearssl.org/bigint.html#montgomery-reduction-and-multiplication
695+ // for a description of the algorithm.
696+
697+ // Eliminate bounds checks in the loop.
698+ size := len(m.nat.limbs)
699+ aLimbs := a.limbs[:size]
700+ bLimbs := b.limbs[:size]
701+ dLimbs := d.resetFor(m).limbs[:size]
702+ mLimbs := m.nat.limbs[:size]
703+
704+ var overflow uint
705+ for i := 0; i < size; i++ {
706+ f := ((dLimbs[0] + aLimbs[i]*bLimbs[0]) * m.m0inv) & _MASK
707+ carry := uint(0)
708+ for j := 0; j < size; j++ {
709+ // z = d[j] + a[i] * b[j] + f * m[j] + carry <= 2^(2W+1) - 2^(W+1) + 2^W
710+ hi, lo := bits.Mul(aLimbs[i], bLimbs[j])
711+ z_lo, c := bits.Add(dLimbs[j], lo, 0)
712+ z_hi, _ := bits.Add(0, hi, c)
713+ hi, lo = bits.Mul(f, mLimbs[j])
714+ z_lo, c = bits.Add(z_lo, lo, 0)
715+ z_hi, _ = bits.Add(z_hi, hi, c)
716+ z_lo, c = bits.Add(z_lo, carry, 0)
717+ z_hi, _ = bits.Add(z_hi, 0, c)
718+ if j > 0 {
719+ dLimbs[j-1] = z_lo & _MASK
720+ }
721+ carry = z_hi<<1 | z_lo>>_W // carry <= 2^(W+1) - 2
722+ }
723+ z := overflow + carry // z <= 2^(W+1) - 1
724+ dLimbs[size-1] = z & _MASK
725+ overflow = z >> _W // overflow <= 1
726+ }
727+ // See modAdd for how overflow, underflow, and needSubtraction relate.
728+ underflow := not(d.cmpGeq(m.nat)) // d < m
729+ needSubtraction := ctEq(overflow, uint(underflow))
730+ d.sub(needSubtraction, m.nat)
731+
732+ return d
733+}
734+
735+// modMul calculates x *= y mod m.
736+//
737+// x and y must already be reduced modulo m, they must share its announced
738+// length, and they may not alias.
739+func (x *nat) modMul(y *nat, m *modulus) *nat {
740+ // A Montgomery multiplication by a value out of the Montgomery domain
741+ // takes the result out of Montgomery representation.
742+ xR := x.clone().montgomeryRepresentation(m) // xR = x * R mod m
743+ return x.montgomeryMul(xR, y, m) // x = xR * y / R mod m
744+}
745+
746+// exp calculates out = x^e mod m.
747+//
748+// The exponent e is represented in big-endian order. The output will be resized
749+// to the size of m and overwritten. x must already be reduced modulo m.
750+func (out *nat) exp(x *nat, e []byte, m *modulus) *nat {
751+ // We use a 4 bit window. For our RSA workload, 4 bit windows are faster
752+ // than 2 bit windows, but use an extra 12 nats worth of scratch space.
753+ // Using bit sizes that don't divide 8 are more complex to implement.
754+ table := make([]*nat, (1<<4)-1) // table[i] = x ^ (i+1)
755+ table[0] = x.clone().montgomeryRepresentation(m)
756+ for i := 1; i < len(table); i++ {
757+ table[i] = new(nat).expandFor(m)
758+ table[i].montgomeryMul(table[i-1], table[0], m)
759+ }
760+
761+ out.resetFor(m)
762+ out.limbs[0] = 1
763+ out.montgomeryRepresentation(m)
764+ t0 := new(nat).expandFor(m)
765+ t1 := new(nat).expandFor(m)
766+ for _, b := range e {
767+ for _, j := range []int{4, 0} {
768+ // Square four times.
769+ t1.montgomeryMul(out, out, m)
770+ out.montgomeryMul(t1, t1, m)
771+ t1.montgomeryMul(out, out, m)
772+ out.montgomeryMul(t1, t1, m)
773+
774+ // Select x^k in constant time from the table.
775+ k := uint((b >> j) & 0b1111)
776+ for i := range table {
777+ t0.assign(ctEq(k, uint(i+1)), table[i])
778+ }
779+
780+ // Multiply by x^k, discarding the result if k = 0.
781+ t1.montgomeryMul(out, t0, m)
782+ out.assign(not(ctEq(k, 0)), t1)
783+ }
784+ }
785+
786+ // By Montgomery multiplying with 1 not in Montgomery representation, we
787+ // convert out back from Montgomery representation, because it works out to
788+ // dividing by R.
789+ t0.assign(yes, out)
790+ t1.resetFor(m)
791+ t1.limbs[0] = 1
792+ out.montgomeryMul(t0, t1, m)
793+
794+ return out
795+}
796diff --git a/src/crypto/rsa/nat_test.go b/src/crypto/rsa/nat_test.go
797new file mode 100644
798index 0000000..3e6eb10
799--- /dev/null
800+++ b/src/crypto/rsa/nat_test.go
801@@ -0,0 +1,384 @@
802+// Copyright 2021 The Go Authors. All rights reserved.
803+// Use of this source code is governed by a BSD-style
804+// license that can be found in the LICENSE file.
805+
806+package rsa
807+
808+import (
809+ "bytes"
810+ "math/big"
811+ "math/bits"
812+ "math/rand"
813+ "reflect"
814+ "testing"
815+ "testing/quick"
816+)
817+
818+// Generate generates an even nat. It's used by testing/quick to produce random
819+// *nat values for quick.Check invocations.
820+func (*nat) Generate(r *rand.Rand, size int) reflect.Value {
821+ limbs := make([]uint, size)
822+ for i := 0; i < size; i++ {
823+ limbs[i] = uint(r.Uint64()) & ((1 << _W) - 2)
824+ }
825+ return reflect.ValueOf(&nat{limbs})
826+}
827+
828+func testModAddCommutative(a *nat, b *nat) bool {
829+ mLimbs := make([]uint, len(a.limbs))
830+ for i := 0; i < len(mLimbs); i++ {
831+ mLimbs[i] = _MASK
832+ }
833+ m := modulusFromNat(&nat{mLimbs})
834+ aPlusB := a.clone()
835+ aPlusB.modAdd(b, m)
836+ bPlusA := b.clone()
837+ bPlusA.modAdd(a, m)
838+ return aPlusB.cmpEq(bPlusA) == 1
839+}
840+
841+func TestModAddCommutative(t *testing.T) {
842+ err := quick.Check(testModAddCommutative, &quick.Config{})
843+ if err != nil {
844+ t.Error(err)
845+ }
846+}
847+
848+func testModSubThenAddIdentity(a *nat, b *nat) bool {
849+ mLimbs := make([]uint, len(a.limbs))
850+ for i := 0; i < len(mLimbs); i++ {
851+ mLimbs[i] = _MASK
852+ }
853+ m := modulusFromNat(&nat{mLimbs})
854+ original := a.clone()
855+ a.modSub(b, m)
856+ a.modAdd(b, m)
857+ return a.cmpEq(original) == 1
858+}
859+
860+func TestModSubThenAddIdentity(t *testing.T) {
861+ err := quick.Check(testModSubThenAddIdentity, &quick.Config{})
862+ if err != nil {
863+ t.Error(err)
864+ }
865+}
866+
867+func testMontgomeryRoundtrip(a *nat) bool {
868+ one := &nat{make([]uint, len(a.limbs))}
869+ one.limbs[0] = 1
870+ aPlusOne := a.clone()
871+ aPlusOne.add(1, one)
872+ m := modulusFromNat(aPlusOne)
873+ monty := a.clone()
874+ monty.montgomeryRepresentation(m)
875+ aAgain := monty.clone()
876+ aAgain.montgomeryMul(monty, one, m)
877+ return a.cmpEq(aAgain) == 1
878+}
879+
880+func TestMontgomeryRoundtrip(t *testing.T) {
881+ err := quick.Check(testMontgomeryRoundtrip, &quick.Config{})
882+ if err != nil {
883+ t.Error(err)
884+ }
885+}
886+
887+func TestFromBig(t *testing.T) {
888+ expected := []byte{0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}
889+ theBig := new(big.Int).SetBytes(expected)
890+ actual := natFromBig(theBig).fillBytes(make([]byte, len(expected)))
891+ if !bytes.Equal(actual, expected) {
892+ t.Errorf("%+x != %+x", actual, expected)
893+ }
894+}
895+
896+func TestFillBytes(t *testing.T) {
897+ xBytes := []byte{0xAA, 0xFF, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88}
898+ x := natFromBytes(xBytes)
899+ for l := 20; l >= len(xBytes); l-- {
900+ buf := make([]byte, l)
901+ rand.Read(buf)
902+ actual := x.fillBytes(buf)
903+ expected := make([]byte, l)
904+ copy(expected[l-len(xBytes):], xBytes)
905+ if !bytes.Equal(actual, expected) {
906+ t.Errorf("%d: %+v != %+v", l, actual, expected)
907+ }
908+ }
909+ for l := len(xBytes) - 1; l >= 0; l-- {
910+ (func() {
911+ defer func() {
912+ if recover() == nil {
913+ t.Errorf("%d: expected panic", l)
914+ }
915+ }()
916+ x.fillBytes(make([]byte, l))
917+ })()
918+ }
919+}
920+
921+func TestFromBytes(t *testing.T) {
922+ f := func(xBytes []byte) bool {
923+ if len(xBytes) == 0 {
924+ return true
925+ }
926+ actual := natFromBytes(xBytes).fillBytes(make([]byte, len(xBytes)))
927+ if !bytes.Equal(actual, xBytes) {
928+ t.Errorf("%+x != %+x", actual, xBytes)
929+ return false
930+ }
931+ return true
932+ }
933+
934+ err := quick.Check(f, &quick.Config{})
935+ if err != nil {
936+ t.Error(err)
937+ }
938+
939+ f([]byte{0xFF, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88})
940+ f(bytes.Repeat([]byte{0xFF}, _W))
941+}
942+
943+func TestShiftIn(t *testing.T) {
944+ if bits.UintSize != 64 {
945+ t.Skip("examples are only valid in 64 bit")
946+ }
947+ examples := []struct {
948+ m, x, expected []byte
949+ y uint64
950+ }{{
951+ m: []byte{13},
952+ x: []byte{0},
953+ y: 0x7FFF_FFFF_FFFF_FFFF,
954+ expected: []byte{7},
955+ }, {
956+ m: []byte{13},
957+ x: []byte{7},
958+ y: 0x7FFF_FFFF_FFFF_FFFF,
959+ expected: []byte{11},
960+ }, {
961+ m: []byte{0x06, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0d},
962+ x: make([]byte, 9),
963+ y: 0x7FFF_FFFF_FFFF_FFFF,
964+ expected: []byte{0x00, 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
965+ }, {
966+ m: []byte{0x06, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0d},
967+ x: []byte{0x00, 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
968+ y: 0,
969+ expected: []byte{0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x08},
970+ }}
971+
972+ for i, tt := range examples {
973+ m := modulusFromNat(natFromBytes(tt.m))
974+ got := natFromBytes(tt.x).expandFor(m).shiftIn(uint(tt.y), m)
975+ if got.cmpEq(natFromBytes(tt.expected).expandFor(m)) != 1 {
976+ t.Errorf("%d: got %x, expected %x", i, got, tt.expected)
977+ }
978+ }
979+}
980+
981+func TestModulusAndNatSizes(t *testing.T) {
982+ // These are 126 bit (2 * _W on 64-bit architectures) values, serialized as
983+ // 128 bits worth of bytes. If leading zeroes are stripped, they fit in two
984+ // limbs, if they are not, they fit in three. This can be a problem because
985+ // modulus strips leading zeroes and nat does not.
986+ m := modulusFromNat(natFromBytes([]byte{
987+ 0x3f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
988+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}))
989+ x := natFromBytes([]byte{
990+ 0x3f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
991+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe})
992+ x.expandFor(m) // must not panic for shrinking
993+}
994+
995+func TestExpand(t *testing.T) {
996+ sliced := []uint{1, 2, 3, 4}
997+ examples := []struct {
998+ in []uint
999+ n int
1000+ out []uint
1001+ }{{
1002+ []uint{1, 2},
1003+ 4,
1004+ []uint{1, 2, 0, 0},
1005+ }, {
1006+ sliced[:2],
1007+ 4,
1008+ []uint{1, 2, 0, 0},
1009+ }, {
1010+ []uint{1, 2},
1011+ 2,
1012+ []uint{1, 2},
1013+ }, {
1014+ []uint{1, 2, 0},
1015+ 2,
1016+ []uint{1, 2},
1017+ }}
1018+
1019+ for i, tt := range examples {
1020+ got := (&nat{tt.in}).expand(tt.n)
1021+ if len(got.limbs) != len(tt.out) || got.cmpEq(&nat{tt.out}) != 1 {
1022+ t.Errorf("%d: got %x, expected %x", i, got, tt.out)
1023+ }
1024+ }
1025+}
1026+
1027+func TestMod(t *testing.T) {
1028+ m := modulusFromNat(natFromBytes([]byte{0x06, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0d}))
1029+ x := natFromBytes([]byte{0x40, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01})
1030+ out := new(nat)
1031+ out.mod(x, m)
1032+ expected := natFromBytes([]byte{0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x09})
1033+ if out.cmpEq(expected) != 1 {
1034+ t.Errorf("%+v != %+v", out, expected)
1035+ }
1036+}
1037+
1038+func TestModSub(t *testing.T) {
1039+ m := modulusFromNat(&nat{[]uint{13}})
1040+ x := &nat{[]uint{6}}
1041+ y := &nat{[]uint{7}}
1042+ x.modSub(y, m)
1043+ expected := &nat{[]uint{12}}
1044+ if x.cmpEq(expected) != 1 {
1045+ t.Errorf("%+v != %+v", x, expected)
1046+ }
1047+ x.modSub(y, m)
1048+ expected = &nat{[]uint{5}}
1049+ if x.cmpEq(expected) != 1 {
1050+ t.Errorf("%+v != %+v", x, expected)
1051+ }
1052+}
1053+
1054+func TestModAdd(t *testing.T) {
1055+ m := modulusFromNat(&nat{[]uint{13}})
1056+ x := &nat{[]uint{6}}
1057+ y := &nat{[]uint{7}}
1058+ x.modAdd(y, m)
1059+ expected := &nat{[]uint{0}}
1060+ if x.cmpEq(expected) != 1 {
1061+ t.Errorf("%+v != %+v", x, expected)
1062+ }
1063+ x.modAdd(y, m)
1064+ expected = &nat{[]uint{7}}
1065+ if x.cmpEq(expected) != 1 {
1066+ t.Errorf("%+v != %+v", x, expected)
1067+ }
1068+}
1069+
1070+func TestExp(t *testing.T) {
1071+ m := modulusFromNat(&nat{[]uint{13}})
1072+ x := &nat{[]uint{3}}
1073+ out := &nat{[]uint{0}}
1074+ out.exp(x, []byte{12}, m)
1075+ expected := &nat{[]uint{1}}
1076+ if out.cmpEq(expected) != 1 {
1077+ t.Errorf("%+v != %+v", out, expected)
1078+ }
1079+}
1080+
1081+func makeBenchmarkModulus() *modulus {
1082+ m := make([]uint, 32)
1083+ for i := 0; i < 32; i++ {
1084+ m[i] = _MASK
1085+ }
1086+ return modulusFromNat(&nat{limbs: m})
1087+}
1088+
1089+func makeBenchmarkValue() *nat {
1090+ x := make([]uint, 32)
1091+ for i := 0; i < 32; i++ {
1092+ x[i] = _MASK - 1
1093+ }
1094+ return &nat{limbs: x}
1095+}
1096+
1097+func makeBenchmarkExponent() []byte {
1098+ e := make([]byte, 256)
1099+ for i := 0; i < 32; i++ {
1100+ e[i] = 0xFF
1101+ }
1102+ return e
1103+}
1104+
1105+func BenchmarkModAdd(b *testing.B) {
1106+ x := makeBenchmarkValue()
1107+ y := makeBenchmarkValue()
1108+ m := makeBenchmarkModulus()
1109+
1110+ b.ResetTimer()
1111+ for i := 0; i < b.N; i++ {
1112+ x.modAdd(y, m)
1113+ }
1114+}
1115+
1116+func BenchmarkModSub(b *testing.B) {
1117+ x := makeBenchmarkValue()
1118+ y := makeBenchmarkValue()
1119+ m := makeBenchmarkModulus()
1120+
1121+ b.ResetTimer()
1122+ for i := 0; i < b.N; i++ {
1123+ x.modSub(y, m)
1124+ }
1125+}
1126+
1127+func BenchmarkMontgomeryRepr(b *testing.B) {
1128+ x := makeBenchmarkValue()
1129+ m := makeBenchmarkModulus()
1130+
1131+ b.ResetTimer()
1132+ for i := 0; i < b.N; i++ {
1133+ x.montgomeryRepresentation(m)
1134+ }
1135+}
1136+
1137+func BenchmarkMontgomeryMul(b *testing.B) {
1138+ x := makeBenchmarkValue()
1139+ y := makeBenchmarkValue()
1140+ out := makeBenchmarkValue()
1141+ m := makeBenchmarkModulus()
1142+
1143+ b.ResetTimer()
1144+ for i := 0; i < b.N; i++ {
1145+ out.montgomeryMul(x, y, m)
1146+ }
1147+}
1148+
1149+func BenchmarkModMul(b *testing.B) {
1150+ x := makeBenchmarkValue()
1151+ y := makeBenchmarkValue()
1152+ m := makeBenchmarkModulus()
1153+
1154+ b.ResetTimer()
1155+ for i := 0; i < b.N; i++ {
1156+ x.modMul(y, m)
1157+ }
1158+}
1159+
1160+func BenchmarkExpBig(b *testing.B) {
1161+ out := new(big.Int)
1162+ exponentBytes := makeBenchmarkExponent()
1163+ x := new(big.Int).SetBytes(exponentBytes)
1164+ e := new(big.Int).SetBytes(exponentBytes)
1165+ n := new(big.Int).SetBytes(exponentBytes)
1166+ one := new(big.Int).SetUint64(1)
1167+ n.Add(n, one)
1168+
1169+ b.ResetTimer()
1170+ for i := 0; i < b.N; i++ {
1171+ out.Exp(x, e, n)
1172+ }
1173+}
1174+
1175+func BenchmarkExp(b *testing.B) {
1176+ x := makeBenchmarkValue()
1177+ e := makeBenchmarkExponent()
1178+ out := makeBenchmarkValue()
1179+ m := makeBenchmarkModulus()
1180+
1181+ b.ResetTimer()
1182+ for i := 0; i < b.N; i++ {
1183+ out.exp(x, e, m)
1184+ }
1185+}
1186diff --git a/src/crypto/rsa/pkcs1v15.go b/src/crypto/rsa/pkcs1v15.go
1187index 0cbd6d0..90233bb 100644
1188--- a/src/crypto/rsa/pkcs1v15.go
1189+++ b/src/crypto/rsa/pkcs1v15.go
1190@@ -9,7 +9,6 @@ import (
1191 "crypto/subtle"
1192 "errors"
1193 "io"
1194- "math/big"
1195
1196 "crypto/internal/randutil"
1197 )
1198@@ -58,14 +57,11 @@ func EncryptPKCS1v15(rand io.Reader, pub *PublicKey, msg []byte) ([]byte, error)
1199 em[len(em)-len(msg)-1] = 0
1200 copy(mm, msg)
1201
1202- m := new(big.Int).SetBytes(em)
1203- c := encrypt(new(big.Int), pub, m)
1204-
1205- return c.FillBytes(em), nil
1206+ return encrypt(pub, em), nil
1207 }
1208
1209 // DecryptPKCS1v15 decrypts a plaintext using RSA and the padding scheme from PKCS #1 v1.5.
1210-// If rand != nil, it uses RSA blinding to avoid timing side-channel attacks.
1211+// The random parameter is legacy and ignored, and it can be as nil.
1212 //
1213 // Note that whether this function returns an error or not discloses secret
1214 // information. If an attacker can cause this function to run repeatedly and
1215@@ -76,7 +72,7 @@ func DecryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) ([]byt
1216 if err := checkPub(&priv.PublicKey); err != nil {
1217 return nil, err
1218 }
1219- valid, out, index, err := decryptPKCS1v15(rand, priv, ciphertext)
1220+ valid, out, index, err := decryptPKCS1v15(priv, ciphertext)
1221 if err != nil {
1222 return nil, err
1223 }
1224@@ -87,7 +83,7 @@ func DecryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) ([]byt
1225 }
1226
1227 // DecryptPKCS1v15SessionKey decrypts a session key using RSA and the padding scheme from PKCS #1 v1.5.
1228-// If rand != nil, it uses RSA blinding to avoid timing side-channel attacks.
1229+// The random parameter is legacy and ignored, and it can be as nil.
1230 // It returns an error if the ciphertext is the wrong length or if the
1231 // ciphertext is greater than the public modulus. Otherwise, no error is
1232 // returned. If the padding is valid, the resulting plaintext message is copied
1233@@ -114,7 +110,7 @@ func DecryptPKCS1v15SessionKey(rand io.Reader, priv *PrivateKey, ciphertext []by
1234 return ErrDecryption
1235 }
1236
1237- valid, em, index, err := decryptPKCS1v15(rand, priv, ciphertext)
1238+ valid, em, index, err := decryptPKCS1v15(priv, ciphertext)
1239 if err != nil {
1240 return err
1241 }
1242@@ -130,26 +126,24 @@ func DecryptPKCS1v15SessionKey(rand io.Reader, priv *PrivateKey, ciphertext []by
1243 return nil
1244 }
1245
1246-// decryptPKCS1v15 decrypts ciphertext using priv and blinds the operation if
1247-// rand is not nil. It returns one or zero in valid that indicates whether the
1248-// plaintext was correctly structured. In either case, the plaintext is
1249-// returned in em so that it may be read independently of whether it was valid
1250-// in order to maintain constant memory access patterns. If the plaintext was
1251-// valid then index contains the index of the original message in em.
1252-func decryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (valid int, em []byte, index int, err error) {
1253+// decryptPKCS1v15 decrypts ciphertext using priv. It returns one or zero in
1254+// valid that indicates whether the plaintext was correctly structured.
1255+// In either case, the plaintext is returned in em so that it may be read
1256+// independently of whether it was valid in order to maintain constant memory
1257+// access patterns. If the plaintext was valid then index contains the index of
1258+// the original message in em, to allow constant time padding removal.
1259+func decryptPKCS1v15(priv *PrivateKey, ciphertext []byte) (valid int, em []byte, index int, err error) {
1260 k := priv.Size()
1261 if k < 11 {
1262 err = ErrDecryption
1263 return
1264 }
1265
1266- c := new(big.Int).SetBytes(ciphertext)
1267- m, err := decrypt(rand, priv, c)
1268+ em, err = decrypt(priv, ciphertext)
1269 if err != nil {
1270 return
1271 }
1272
1273- em = m.FillBytes(make([]byte, k))
1274 firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
1275 secondByteIsTwo := subtle.ConstantTimeByteEq(em[1], 2)
1276
1277@@ -221,8 +215,7 @@ var hashPrefixes = map[crypto.Hash][]byte{
1278 // function. If hash is zero, hashed is signed directly. This isn't
1279 // advisable except for interoperability.
1280 //
1281-// If rand is not nil then RSA blinding will be used to avoid timing
1282-// side-channel attacks.
1283+// The random parameter is legacy and ignored, and it can be as nil.
1284 //
1285 // This function is deterministic. Thus, if the set of possible
1286 // messages is small, an attacker may be able to build a map from
1287@@ -249,13 +242,7 @@ func SignPKCS1v15(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed []b
1288 copy(em[k-tLen:k-hashLen], prefix)
1289 copy(em[k-hashLen:k], hashed)
1290
1291- m := new(big.Int).SetBytes(em)
1292- c, err := decryptAndCheck(rand, priv, m)
1293- if err != nil {
1294- return nil, err
1295- }
1296-
1297- return c.FillBytes(em), nil
1298+ return decryptAndCheck(priv, em)
1299 }
1300
1301 // VerifyPKCS1v15 verifies an RSA PKCS #1 v1.5 signature.
1302@@ -282,9 +269,7 @@ func VerifyPKCS1v15(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte)
1303 return ErrVerification
1304 }
1305
1306- c := new(big.Int).SetBytes(sig)
1307- m := encrypt(new(big.Int), pub, c)
1308- em := m.FillBytes(make([]byte, k))
1309+ em := encrypt(pub, sig)
1310 // EM = 0x00 || 0x01 || PS || 0x00 || T
1311
1312 ok := subtle.ConstantTimeByteEq(em[0], 0)
1313diff --git a/src/crypto/rsa/pss.go b/src/crypto/rsa/pss.go
1314index 814522d..aeb6148 100644
1315--- a/src/crypto/rsa/pss.go
1316+++ b/src/crypto/rsa/pss.go
1317@@ -12,7 +12,6 @@ import (
1318 "errors"
1319 "hash"
1320 "io"
1321- "math/big"
1322 )
1323
1324 // Per RFC 8017, Section 9.1
1325@@ -207,19 +206,26 @@ func emsaPSSVerify(mHash, em []byte, emBits, sLen int, hash hash.Hash) error {
1326 // Note that hashed must be the result of hashing the input message using the
1327 // given hash function. salt is a random sequence of bytes whose length will be
1328 // later used to verify the signature.
1329-func signPSSWithSalt(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed, salt []byte) ([]byte, error) {
1330- emBits := priv.N.BitLen() - 1
1331+func signPSSWithSalt(priv *PrivateKey, hash crypto.Hash, hashed, salt []byte) ([]byte, error) {
1332+ emBits := bigBitLen(priv.N) - 1
1333 em, err := emsaPSSEncode(hashed, emBits, salt, hash.New())
1334 if err != nil {
1335 return nil, err
1336 }
1337- m := new(big.Int).SetBytes(em)
1338- c, err := decryptAndCheck(rand, priv, m)
1339- if err != nil {
1340- return nil, err
1341+ // RFC 8017: "Note that the octet length of EM will be one less than k if
1342+ // modBits - 1 is divisible by 8 and equal to k otherwise, where k is the
1343+ // length in octets of the RSA modulus n."
1344+ //
1345+ // This is extremely annoying, as all other encrypt and decrypt inputs are
1346+ // always the exact same size as the modulus. Since it only happens for
1347+ // weird modulus sizes, fix it by padding inefficiently.
1348+ if emLen, k := len(em), priv.Size(); emLen < k {
1349+ emNew := make([]byte, k)
1350+ copy(emNew[k-emLen:], em)
1351+ em = emNew
1352 }
1353- s := make([]byte, priv.Size())
1354- return c.FillBytes(s), nil
1355+
1356+ return decryptAndCheck(priv, em)
1357 }
1358
1359 const (
1360@@ -269,7 +275,7 @@ func SignPSS(rand io.Reader, priv *PrivateKey, hash crypto.Hash, digest []byte,
1361 saltLength := opts.saltLength()
1362 switch saltLength {
1363 case PSSSaltLengthAuto:
1364- saltLength = (priv.N.BitLen()-1+7)/8 - 2 - hash.Size()
1365+ saltLength = (bigBitLen(priv.N)-1+7)/8 - 2 - hash.Size()
1366 case PSSSaltLengthEqualsHash:
1367 saltLength = hash.Size()
1368 }
1369@@ -278,7 +284,7 @@ func SignPSS(rand io.Reader, priv *PrivateKey, hash crypto.Hash, digest []byte,
1370 if _, err := io.ReadFull(rand, salt); err != nil {
1371 return nil, err
1372 }
1373- return signPSSWithSalt(rand, priv, hash, digest, salt)
1374+ return signPSSWithSalt(priv, hash, digest, salt)
1375 }
1376
1377 // VerifyPSS verifies a PSS signature.
1378@@ -291,13 +297,22 @@ func VerifyPSS(pub *PublicKey, hash crypto.Hash, digest []byte, sig []byte, opts
1379 if len(sig) != pub.Size() {
1380 return ErrVerification
1381 }
1382- s := new(big.Int).SetBytes(sig)
1383- m := encrypt(new(big.Int), pub, s)
1384- emBits := pub.N.BitLen() - 1
1385+
1386+ emBits := bigBitLen(pub.N) - 1
1387 emLen := (emBits + 7) / 8
1388- if m.BitLen() > emLen*8 {
1389- return ErrVerification
1390+ em := encrypt(pub, sig)
1391+
1392+ // Like in signPSSWithSalt, deal with mismatches between emLen and the size
1393+ // of the modulus. The spec would have us wire emLen into the encoding
1394+ // function, but we'd rather always encode to the size of the modulus and
1395+ // then strip leading zeroes if necessary. This only happens for weird
1396+ // modulus sizes anyway.
1397+ for len(em) > emLen && len(em) > 0 {
1398+ if em[0] != 0 {
1399+ return ErrVerification
1400+ }
1401+ em = em[1:]
1402 }
1403- em := m.FillBytes(make([]byte, emLen))
1404+
1405 return emsaPSSVerify(digest, em, emBits, opts.saltLength(), hash.New())
1406 }
1407diff --git a/src/crypto/rsa/pss_test.go b/src/crypto/rsa/pss_test.go
1408index c3a6d46..d018b43 100644
1409--- a/src/crypto/rsa/pss_test.go
1410+++ b/src/crypto/rsa/pss_test.go
1411@@ -233,7 +233,10 @@ func TestPSSSigning(t *testing.T) {
1412 }
1413 }
1414
1415-func TestSignWithPSSSaltLengthAuto(t *testing.T) {
1416+func TestPSS513(t *testing.T) {
1417+ // See Issue 42741, and separately, RFC 8017: "Note that the octet length of
1418+ // EM will be one less than k if modBits - 1 is divisible by 8 and equal to
1419+ // k otherwise, where k is the length in octets of the RSA modulus n."
1420 key, err := GenerateKey(rand.Reader, 513)
1421 if err != nil {
1422 t.Fatal(err)
1423@@ -246,8 +249,9 @@ func TestSignWithPSSSaltLengthAuto(t *testing.T) {
1424 if err != nil {
1425 t.Fatal(err)
1426 }
1427- if len(signature) == 0 {
1428- t.Fatal("empty signature returned")
1429+ err = VerifyPSS(&key.PublicKey, crypto.SHA256, digest[:], signature, nil)
1430+ if err != nil {
1431+ t.Error(err)
1432 }
1433 }
1434
1435diff --git a/src/crypto/rsa/rsa.go b/src/crypto/rsa/rsa.go
1436index 6fd59b3..20c1fe1 100644
1437--- a/src/crypto/rsa/rsa.go
1438+++ b/src/crypto/rsa/rsa.go
1439@@ -19,13 +19,17 @@
1440 // over the public key primitive, the PrivateKey type implements the
1441 // Decrypter and Signer interfaces from the crypto package.
1442 //
1443-// The RSA operations in this package are not implemented using constant-time algorithms.
1444+// Operations in this package are implemented using constant-time algorithms,
1445+// except for [GenerateKey], [PrivateKey.Precompute], and [PrivateKey.Validate].
1446+// Every other operation only leaks the bit size of the involved values, which
1447+// all depend on the selected key size.
1448 package rsa
1449
1450 import (
1451 "crypto"
1452 "crypto/rand"
1453 "crypto/subtle"
1454+ "encoding/binary"
1455 "errors"
1456 "hash"
1457 "io"
1458@@ -35,7 +39,6 @@ import (
1459 "crypto/internal/randutil"
1460 )
1461
1462-var bigZero = big.NewInt(0)
1463 var bigOne = big.NewInt(1)
1464
1465 // A PublicKey represents the public part of an RSA key.
1466@@ -50,7 +53,7 @@ type PublicKey struct {
1467 // Size returns the modulus size in bytes. Raw signatures and ciphertexts
1468 // for or by this public key will have the same size.
1469 func (pub *PublicKey) Size() int {
1470- return (pub.N.BitLen() + 7) / 8
1471+ return (bigBitLen(pub.N) + 7) / 8
1472 }
1473
1474 // Equal reports whether pub and x have the same value.
1475@@ -384,10 +387,18 @@ func mgf1XOR(out []byte, hash hash.Hash, seed []byte) {
1476 // too large for the size of the public key.
1477 var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA public key size")
1478
1479-func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
1480- e := big.NewInt(int64(pub.E))
1481- c.Exp(m, e, pub.N)
1482- return c
1483+func encrypt(pub *PublicKey, plaintext []byte) []byte {
1484+ N := modulusFromNat(natFromBig(pub.N))
1485+ m := natFromBytes(plaintext).expandFor(N)
1486+
1487+ e := make([]byte, 8)
1488+ binary.BigEndian.PutUint64(e, uint64(pub.E))
1489+ for len(e) > 1 && e[0] == 0 {
1490+ e = e[1:]
1491+ }
1492+
1493+ out := make([]byte, modulusSize(N))
1494+ return new(nat).exp(m, e, N).fillBytes(out)
1495 }
1496
1497 // EncryptOAEP encrypts the given message with RSA-OAEP.
1498@@ -437,12 +448,7 @@ func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, l
1499 mgf1XOR(db, hash, seed)
1500 mgf1XOR(seed, hash, db)
1501
1502- m := new(big.Int)
1503- m.SetBytes(em)
1504- c := encrypt(new(big.Int), pub, m)
1505-
1506- out := make([]byte, k)
1507- return c.FillBytes(out), nil
1508+ return encrypt(pub, em), nil
1509 }
1510
1511 // ErrDecryption represents a failure to decrypt a message.
1512@@ -484,98 +490,70 @@ func (priv *PrivateKey) Precompute() {
1513 }
1514 }
1515
1516-// decrypt performs an RSA decryption, resulting in a plaintext integer. If a
1517-// random source is given, RSA blinding is used.
1518-func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
1519- // TODO(agl): can we get away with reusing blinds?
1520- if c.Cmp(priv.N) > 0 {
1521- err = ErrDecryption
1522- return
1523+// decrypt performs an RSA decryption of ciphertext into out.
1524+func decrypt(priv *PrivateKey, ciphertext []byte) ([]byte, error) {
1525+ N := modulusFromNat(natFromBig(priv.N))
1526+ c := natFromBytes(ciphertext).expandFor(N)
1527+ if c.cmpGeq(N.nat) == 1 {
1528+ return nil, ErrDecryption
1529 }
1530 if priv.N.Sign() == 0 {
1531 return nil, ErrDecryption
1532 }
1533
1534- var ir *big.Int
1535- if random != nil {
1536- randutil.MaybeReadByte(random)
1537-
1538- // Blinding enabled. Blinding involves multiplying c by r^e.
1539- // Then the decryption operation performs (m^e * r^e)^d mod n
1540- // which equals mr mod n. The factor of r can then be removed
1541- // by multiplying by the multiplicative inverse of r.
1542-
1543- var r *big.Int
1544- ir = new(big.Int)
1545- for {
1546- r, err = rand.Int(random, priv.N)
1547- if err != nil {
1548- return
1549- }
1550- if r.Cmp(bigZero) == 0 {
1551- r = bigOne
1552- }
1553- ok := ir.ModInverse(r, priv.N)
1554- if ok != nil {
1555- break
1556- }
1557- }
1558- bigE := big.NewInt(int64(priv.E))
1559- rpowe := new(big.Int).Exp(r, bigE, priv.N) // N != 0
1560- cCopy := new(big.Int).Set(c)
1561- cCopy.Mul(cCopy, rpowe)
1562- cCopy.Mod(cCopy, priv.N)
1563- c = cCopy
1564- }
1565-
1566+ // Note that because our private decryption exponents are stored as big.Int,
1567+ // we potentially leak the exact number of bits of these exponents. This
1568+ // isn't great, but should be fine.
1569 if priv.Precomputed.Dp == nil {
1570- m = new(big.Int).Exp(c, priv.D, priv.N)
1571- } else {
1572- // We have the precalculated values needed for the CRT.
1573- m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0])
1574- m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1])
1575- m.Sub(m, m2)
1576- if m.Sign() < 0 {
1577- m.Add(m, priv.Primes[0])
1578- }
1579- m.Mul(m, priv.Precomputed.Qinv)
1580- m.Mod(m, priv.Primes[0])
1581- m.Mul(m, priv.Primes[1])
1582- m.Add(m, m2)
1583-
1584- for i, values := range priv.Precomputed.CRTValues {
1585- prime := priv.Primes[2+i]
1586- m2.Exp(c, values.Exp, prime)
1587- m2.Sub(m2, m)
1588- m2.Mul(m2, values.Coeff)
1589- m2.Mod(m2, prime)
1590- if m2.Sign() < 0 {
1591- m2.Add(m2, prime)
1592- }
1593- m2.Mul(m2, values.R)
1594- m.Add(m, m2)
1595- }
1596- }
1597-
1598- if ir != nil {
1599- // Unblind.
1600- m.Mul(m, ir)
1601- m.Mod(m, priv.N)
1602- }
1603-
1604- return
1605+ out := make([]byte, modulusSize(N))
1606+ return new(nat).exp(c, priv.D.Bytes(), N).fillBytes(out), nil
1607+ }
1608+
1609+ t0 := new(nat)
1610+ P := modulusFromNat(natFromBig(priv.Primes[0]))
1611+ Q := modulusFromNat(natFromBig(priv.Primes[1]))
1612+ // m = c ^ Dp mod p
1613+ m := new(nat).exp(t0.mod(c, P), priv.Precomputed.Dp.Bytes(), P)
1614+ // m2 = c ^ Dq mod q
1615+ m2 := new(nat).exp(t0.mod(c, Q), priv.Precomputed.Dq.Bytes(), Q)
1616+ // m = m - m2 mod p
1617+ m.modSub(t0.mod(m2, P), P)
1618+ // m = m * Qinv mod p
1619+ m.modMul(natFromBig(priv.Precomputed.Qinv).expandFor(P), P)
1620+ // m = m * q mod N
1621+ m.expandFor(N).modMul(t0.mod(Q.nat, N), N)
1622+ // m = m + m2 mod N
1623+ m.modAdd(m2.expandFor(N), N)
1624+
1625+ for i, values := range priv.Precomputed.CRTValues {
1626+ p := modulusFromNat(natFromBig(priv.Primes[2+i]))
1627+ // m2 = c ^ Exp mod p
1628+ m2.exp(t0.mod(c, p), values.Exp.Bytes(), p)
1629+ // m2 = m2 - m mod p
1630+ m2.modSub(t0.mod(m, p), p)
1631+ // m2 = m2 * Coeff mod p
1632+ m2.modMul(natFromBig(values.Coeff).expandFor(p), p)
1633+ // m2 = m2 * R mod N
1634+ R := natFromBig(values.R).expandFor(N)
1635+ m2.expandFor(N).modMul(R, N)
1636+ // m = m + m2 mod N
1637+ m.modAdd(m2, N)
1638+ }
1639+
1640+ out := make([]byte, modulusSize(N))
1641+ return m.fillBytes(out), nil
1642 }
1643
1644-func decryptAndCheck(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
1645- m, err = decrypt(random, priv, c)
1646+func decryptAndCheck(priv *PrivateKey, ciphertext []byte) (m []byte, err error) {
1647+ m, err = decrypt(priv, ciphertext)
1648 if err != nil {
1649 return nil, err
1650 }
1651
1652 // In order to defend against errors in the CRT computation, m^e is
1653 // calculated, which should match the original ciphertext.
1654- check := encrypt(new(big.Int), &priv.PublicKey, m)
1655- if c.Cmp(check) != 0 {
1656+ check := encrypt(&priv.PublicKey, m)
1657+ if subtle.ConstantTimeCompare(ciphertext, check) != 1 {
1658 return nil, errors.New("rsa: internal error")
1659 }
1660 return m, nil
1661@@ -587,9 +565,7 @@ func decryptAndCheck(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int
1662 // Encryption and decryption of a given message must use the same hash function
1663 // and sha256.New() is a reasonable choice.
1664 //
1665-// The random parameter, if not nil, is used to blind the private-key operation
1666-// and avoid timing side-channel attacks. Blinding is purely internal to this
1667-// function – the random data need not match that used when encrypting.
1668+// The random parameter is legacy and ignored, and it can be as nil.
1669 //
1670 // The label parameter must match the value given when encrypting. See
1671 // EncryptOAEP for details.
1672@@ -603,9 +579,7 @@ func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext
1673 return nil, ErrDecryption
1674 }
1675
1676- c := new(big.Int).SetBytes(ciphertext)
1677-
1678- m, err := decrypt(random, priv, c)
1679+ em, err := decrypt(priv, ciphertext)
1680 if err != nil {
1681 return nil, err
1682 }
1683@@ -614,10 +588,6 @@ func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext
1684 lHash := hash.Sum(nil)
1685 hash.Reset()
1686
1687- // We probably leak the number of leading zeros.
1688- // It's not clear that we can do anything about this.
1689- em := m.FillBytes(make([]byte, k))
1690-
1691 firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
1692
1693 seed := em[1 : hash.Size()+1]
1694--
16952.40.0
generated by cgit v1.2.3-54-g00ecf (git 2.39.0) at 2026-01-10 17:27:34 +0000