Debian Codegraph @

crypto/rsa/core.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 // The following code was initially ported from BearSSL.
5 //
6 // Copyright (c) 2016 Thomas Pornin <[email protected]>
7 //
8 // Permission is hereby granted, free of charge, to any person obtaining
9 // a copy of this software and associated documentation files (the
10 // "Software"), to deal in the Software without restriction, including
11 // without limitation the rights to use, copy, modify, merge, publish,
12 // distribute, sublicense, and/or sell copies of the Software, and to
13 // permit persons to whom the Software is furnished to do so, subject to
14 // the following conditions:
15 //
16 // The above copyright notice and this permission notice shall be
17 // included in all copies or substantial portions of the Software.
18 //
19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
22 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
23 // BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
24 // ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
25 // CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
26 // SOFTWARE.
27 use bytes;
28 use crypto::bigint::*;
29 use crypto::math::{divu32};
30 use errors;
31 use types;
32
33 // Maximum factor size of a key of [[BITSZ]].
34 def MAXFACTOR: size = ((BITSZ + 64) >> 1);
35
36 // Required buf size for the [[pubexp]] operation.
37 def PUBEXP_BUFSZ: size = size(word) * (1 + (4 * (2
38 + ((BITSZ + WORD_BITSZ - 1) / WORD_BITSZ))));
39
40 // Requried buf size for the [[privexp]] operation.
41 def PRIVEXP_BUFSZ: size = size(word) * (1 + (8 * (2
42 + ((MAXFACTOR + WORD_BITSZ - 1) / WORD_BITSZ))));
43
44 // Performs the modular exponentiation of 'x' with the public exponent of 'pub'.
45 // 'x' is modified in place. 'x' must be the same length as the actual length
46 // of 'pub.n'.
47 //
48 // For the size of 'buf' see [[PUBEXP_BUFSZ]]. If the buffer is not large
49 // enough, [[errors::overflow]] will be returned. In case of 'x' being not of
50 // required length or if 'x' is not modulo 'pub.n' [[errors::invalid]] is
51 // returned and 'x' will be zeroed.
52 fn pubexp(pub: *pubparams, x: []u8, buf: []u8) (void | error) = {
53 // supported key length leaks. But that is not a problem.
54 const wbuflen = len(buf) / size(word);
55 let wbuf: []word = (buf: *[*]word)[..wbuflen];
56 let n = pub.n;
57
58 // get the maximal allowed key size for given buffer. Reverse of the
59 // [[PUBEXP_BUFSZ]] equation.
60 const maxkeybits = (((wbuflen - 1) / 4) - 2) * WORD_BITSZ;
61
62 if (len(n) == 0 || len(n) > (maxkeybits >> 3)) {
63 return errors::overflow;
64 };
65
66 if (len(x) != len(n)) {
67 bytes::zero(x);
68 return errors::invalid;
69 };
70
71 // add word size - 1 to ceil required words in the division that follows
72 const maxnbitlen = (len(n) << 3) + WORD_BITSZ: size - 1;
73 assert(maxnbitlen <= types::U32_MAX);
74 let bwordlen = 1 + divu32(0, maxnbitlen: u32, WORD_BITSZ).0;
75
76 // make it even
77 bwordlen += bwordlen & 1;
78
79 let nenc = wbuf[..bwordlen];
80 let xenc = wbuf[bwordlen..2 * bwordlen];
81 let t = wbuf[2 * bwordlen..];
82
83 // From now on, buf will be indirectly used via slices borrowed from
84 // wbuf. Therefore make sure it gets cleared in the end.
85 defer bytes::zero(buf);
86
87 encode(nenc, n);
88 const n0i = ninv(nenc[1]);
89
90 // if m is odd, n0i is also.
91 let result: word = n0i & 1;
92 result &= encodemod(xenc, x, nenc);
93
94 modpow(xenc, pub.e, nenc, n0i, t);
95
96 decode(x, xenc);
97
98 if (result == 0: word) {
99 bytes::zero(x);
100 return errors::invalid;
101 };
102 };
103
104 // Performs modular exponentiation of 'x' with the private exponent of 'priv'.
105 // 'x' is modified in place. 'x' must be the same length as the actual length
106 // of the modulus n (see [[privkey_nsize]]).
107 //
108 // For size of 'buf' see [[PRIVEXP_BUFSZ]]. If the buffer is not large enough
109 // [[errors::overflow]] will be returned. In case of an invalid size of 'x' or
110 // an invalid key, [[errors::invalid]] will be returned and 'x' will be zeroed.
111 fn privexp(priv: *privparams, x: []u8, buf: []u8) (void | error) = {
112 // supported key length leaks. But that is not a problem.
113 const wbuflen = len(buf) / size(word);
114 let wbuf: []word = (buf: *[*]word)[..wbuflen];
115
116 let p = priv.p;
117 let q = priv.q;
118
119 const maxflen = if (len(p) > len(q)) len(p) else len(q);
120
121 // add word size - 1 to ceil required words in the division that follows
122 const maxfbitlen = (maxflen << 3) + WORD_BITSZ: size - 1;
123 assert(maxfbitlen <= types::U32_MAX);
124 let bwordlen = 1 + divu32(0, maxfbitlen: u32, WORD_BITSZ).0;
125
126 // make it even
127 bwordlen += bwordlen & 1;
128
129 // We need at least 6 big integers for the following calculations
130 if (6 * bwordlen > len(wbuf)) {
131 return errors::overflow;
132 };
133
134 // From now on, buf will be indirectly used via wbuf. Therefore make
135 // sure it gets cleared in the end.
136 defer bytes::zero(buf);
137
138 let mq = wbuf[..bwordlen];
139 encode(mq, q);
140
141 let t1 = wbuf[bwordlen..2 * bwordlen];
142 encode(t1, p);
143
144 // compute modulus n
145 let t2 = wbuf[2 * bwordlen..4 * bwordlen];
146 zero(t2, mq[0]);
147 mulacc(t2, mq, t1);
148
149 // ceiled modulus length in bytes
150 const nlen = (priv.nbitlen + 7) >> 3;
151 if(len(x) != nlen) {
152 bytes::zero(x);
153 return errors::invalid;
154 };
155
156 let t3 = wbuf[4 * bwordlen..6 * bwordlen];
157 let t3 = (t3: *[*]u8)[..nlen];
158 decode(t3, t2);
159 let r: u32 = 0;
160
161 // Check if x is mod n.
162 //
163 // We encode the modulus into bytes, to perform the comparison with
164 // bytes. We know that the product length, in bytes, is exactly nlen.
165 //
166 // The comparison actually computes the carry when subtracting the
167 // modulus from the source value; that carry must be 1 for a value in
168 // the correct range. We keep it in r, which is our accumulator for the
169 // error code.
170 for (let u = nlen; u > 0) {
171 u -= 1;
172 r = ((x[u] - (t3[u] + r)) >> 8) & 1;
173 };
174
175 // Move the decoded p to another temporary buffer.
176 let mp = wbuf[2 * bwordlen..3 * bwordlen];
177 mp[..] = t1[..];
178
179 // Compute s2 = x^dq mod q.
180 const q0i = ninv(mq[1]);
181 let s2 = wbuf[bwordlen..bwordlen * 3];
182 encodereduce(s2, x, mq);
183 r &= modpow(s2, priv.dq, mq, q0i, wbuf[3 * bwordlen..]);
184
185 // Compute s1 = x^dp mod p.
186 const p0i = ninv(mp[1]);
187 let s1 = wbuf[bwordlen * 3..];
188 encodereduce(s1, x, mp);
189 r &= modpow(s1, priv.dp, mp, p0i, wbuf[4 * bwordlen..]);
190
191 // Compute:
192 // h = (s1 - s2)*(1/q) mod p
193 // s1 is an integer modulo p, but s2 is modulo q. PKCS#1 is
194 // unclear about whether p may be lower than q (some existing,
195 // widely deployed implementations of RSA don't tolerate p < q),
196 // but we want to support that occurrence, so we need to use the
197 // reduction function.
198 //
199 // Since we use br_i31_decode_reduce() for iq (purportedly, the
200 // inverse of q modulo p), we also tolerate improperly large
201 // values for this parameter.
202 let t1 = wbuf[4 * bwordlen..5 * bwordlen];
203 let t2 = wbuf[5 * bwordlen..];
204
205 reduce(t2, s2, mp);
206 add(s1, mp, sub(s1, t2, 1));
207 tomonty(s1, mp);
208 encodereduce(t1, priv.iq, mp);
209 montymul(t2, s1, t1, mp, p0i);
210
211 // h is now in t2. We compute the final result:
212 // s = s2 + q*h
213 // All these operations are non-modular.
214 //
215 // We need mq, s2 and t2. We use the t3 buffer as destination.
216 // The buffers mp, s1 and t1 are no longer needed, so we can
217 // reuse them for t3. Moreover, the first step of the computation
218 // is to copy s2 into t3, after which s2 is not needed. Right
219 // now, mq is in slot 0, s2 is in slot 1, and t2 is in slot 5.
220 // Therefore, we have ample room for t3 by simply using s2.
221 let t3 = s2;
222 mulacc(t3, mq, t2);
223
224 // Encode the result. Since we already checked the value of xlen,
225 // we can just use it right away.
226 decode(x, t3);
227
228 if ((p0i & q0i & r) != 1) {
229 bytes::zero(x);
230 return errors::invalid;
231 };
232 };