/
rsa.go
168 lines (149 loc) · 4.02 KB
/
rsa.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package rsa
import (
"crypto/rand"
"crypto/rsa"
"errors"
"io"
"math/big"
)
// DecryptFunc describes an external decrypt function.
type DecryptFunc func(c *big.Int) (m *big.Int, err error)
// PrivateKey is a wrapper around rsa.PrivateKey and DecryptFunc in an attempt
// to showcase a possibly way to use RSA encryption with an external private
// key store.
type PrivateKey struct {
rsa.PrivateKey
DecryptFunc DecryptFunc
}
var bigZero = big.NewInt(0)
var bigOne = big.NewInt(1)
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
// http://www.imperialviolet.org/2012/03/16/rsae.html.
func checkPub(pub *rsa.PublicKey) error {
if pub.N == nil {
return errPublicModulus
}
if pub.E < 2 {
return errPublicExponentSmall
}
if pub.E > 1<<31-1 {
return errPublicExponentLarge
}
return nil
}
// decrypt performs an RSA decryption, resulting in a plaintext integer. If a
// random source is given, RSA blinding is used.
func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
if priv.DecryptFunc != nil {
return priv.DecryptFunc(c)
}
// TODO(agl): can we get away with reusing blinds?
if c.Cmp(priv.N) > 0 {
err = rsa.ErrDecryption
return
}
if priv.N.Sign() == 0 {
return nil, rsa.ErrDecryption
}
var ir *big.Int
if random != nil {
// Blinding enabled. Blinding involves multiplying c by r^e.
// Then the decryption operation performs (m^e * r^e)^d mod n
// which equals mr mod n. The factor of r can then be removed
// by multiplying by the multiplicative inverse of r.
var r *big.Int
for {
r, err = rand.Int(random, priv.N)
if err != nil {
return
}
if r.Cmp(bigZero) == 0 {
r = bigOne
}
var ok bool
ir, ok = modInverse(r, priv.N)
if ok {
break
}
}
bigE := big.NewInt(int64(priv.E))
rpowe := new(big.Int).Exp(r, bigE, priv.N) // N != 0
cCopy := new(big.Int).Set(c)
cCopy.Mul(cCopy, rpowe)
cCopy.Mod(cCopy, priv.N)
c = cCopy
}
if priv.Precomputed.Dp == nil {
m = new(big.Int).Exp(c, priv.D, priv.N)
} else {
// We have the precalculated values needed for the CRT.
m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0])
m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1])
m.Sub(m, m2)
if m.Sign() < 0 {
m.Add(m, priv.Primes[0])
}
m.Mul(m, priv.Precomputed.Qinv)
m.Mod(m, priv.Primes[0])
m.Mul(m, priv.Primes[1])
m.Add(m, m2)
for i, values := range priv.Precomputed.CRTValues {
prime := priv.Primes[2+i]
m2.Exp(c, values.Exp, prime)
m2.Sub(m2, m)
m2.Mul(m2, values.Coeff)
m2.Mod(m2, prime)
if m2.Sign() < 0 {
m2.Add(m2, prime)
}
m2.Mul(m2, values.R)
m.Add(m, m2)
}
}
if ir != nil {
// Unblind.
m.Mul(m, ir)
m.Mod(m, priv.N)
}
return
}
// leftPad returns a new slice of length size. The contents of input are right
// aligned in the new slice.
func leftPad(input []byte, size int) (out []byte) {
n := len(input)
if n > size {
n = size
}
out = make([]byte, size)
copy(out[len(out)-n:], input)
return
}
// modInverse returns ia, the inverse of a in the multiplicative group of prime
// order n. It requires that a be a member of the group (i.e. less than n).
func modInverse(a, n *big.Int) (ia *big.Int, ok bool) {
g := new(big.Int)
x := new(big.Int)
y := new(big.Int)
g.GCD(x, y, a, n)
if g.Cmp(bigOne) != 0 {
// In this case, a and n aren't coprime and we cannot calculate
// the inverse. This happens because the values of n are nearly
// prime (being the product of two primes) rather than truly
// prime.
return
}
if x.Cmp(bigOne) < 0 {
// 0 is not the multiplicative inverse of any element so, if x
// < 1, then x is negative.
x.Add(x, n)
}
return x, true
}