]>
git.proxmox.com Git - mirror_ubuntu-artful-kernel.git/blob - drivers/usb/host/dwc_common_port/dwc_modpow.c
1 /* Bignum routines adapted from PUTTY sources. PuTTY copyright notice follows.
3 * PuTTY is copyright 1997-2007 Simon Tatham.
5 * Portions copyright Robert de Bath, Joris van Rantwijk, Delian
6 * Delchev, Andreas Schultz, Jeroen Massar, Wez Furlong, Nicolas Barry,
7 * Justin Bradford, Ben Harris, Malcolm Smith, Ahmad Khalifa, Markus
8 * Kuhn, and CORE SDI S.A.
10 * Permission is hereby granted, free of charge, to any person
11 * obtaining a copy of this software and associated documentation files
12 * (the "Software"), to deal in the Software without restriction,
13 * including without limitation the rights to use, copy, modify, merge,
14 * publish, distribute, sublicense, and/or sell copies of the Software,
15 * and to permit persons to whom the Software is furnished to do so,
16 * subject to the following conditions:
18 * The above copyright notice and this permission notice shall be
19 * included in all copies or substantial portions of the Software.
21 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
22 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
23 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
24 * NONINFRINGEMENT. IN NO EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE
25 * FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
26 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
27 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
32 #ifndef CONFIG_MACH_IPMATE
34 #include "dwc_modpow.h"
36 #define BIGNUM_INT_MASK 0xFFFFFFFFUL
37 #define BIGNUM_TOP_BIT 0x80000000UL
38 #define BIGNUM_INT_BITS 32
41 static void *snmalloc(void *mem_ctx
, size_t n
, size_t size
)
45 if (size
== 0) size
= 1;
46 p
= dwc_alloc(mem_ctx
, size
);
50 #define snewn(ctx, n, type) ((type *)snmalloc((ctx), (n), sizeof(type)))
51 #define sfree dwc_free
55 * * Do not call the DIVMOD_WORD macro with expressions such as array
56 * subscripts, as some implementations object to this (see below).
57 * * Note that none of the division methods below will cope if the
58 * quotient won't fit into BIGNUM_INT_BITS. Callers should be careful
60 * If this condition occurs, in the case of the x86 DIV instruction,
61 * an overflow exception will occur, which (according to a correspondent)
62 * will manifest on Windows as something like
63 * 0xC0000095: Integer overflow
64 * The C variant won't give the right answer, either.
67 #define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)
69 #if defined __GNUC__ && defined __i386__
70 #define DIVMOD_WORD(q, r, hi, lo, w) \
72 "=d" (r), "=a" (q) : \
73 "r" (w), "d" (hi), "a" (lo))
75 #define DIVMOD_WORD(q, r, hi, lo, w) do { \
76 BignumDblInt n = (((BignumDblInt)hi) << BIGNUM_INT_BITS) | lo; \
85 #define BIGNUM_INT_BYTES (BIGNUM_INT_BITS / 8)
87 #define BIGNUM_INTERNAL
89 static Bignum
newbn(void *mem_ctx
, int length
)
91 Bignum b
= snewn(mem_ctx
, length
+ 1, BignumInt
);
93 //abort(); /* FIXME */
94 DWC_MEMSET(b
, 0, (length
+ 1) * sizeof(*b
));
99 void freebn(void *mem_ctx
, Bignum b
)
102 * Burn the evidence, just in case.
104 DWC_MEMSET(b
, 0, sizeof(b
[0]) * (b
[0] + 1));
110 * Input is in the first len words of a and b.
111 * Result is returned in the first 2*len words of c.
113 static void internal_mul(BignumInt
*a
, BignumInt
*b
,
114 BignumInt
*c
, int len
)
119 for (j
= 0; j
< 2 * len
; j
++)
122 for (i
= len
- 1; i
>= 0; i
--) {
124 for (j
= len
- 1; j
>= 0; j
--) {
125 t
+= MUL_WORD(a
[i
], (BignumDblInt
) b
[j
]);
126 t
+= (BignumDblInt
) c
[i
+ j
+ 1];
127 c
[i
+ j
+ 1] = (BignumInt
) t
;
128 t
= t
>> BIGNUM_INT_BITS
;
130 c
[i
] = (BignumInt
) t
;
134 static void internal_add_shifted(BignumInt
*number
,
135 unsigned n
, int shift
)
137 int word
= 1 + (shift
/ BIGNUM_INT_BITS
);
138 int bshift
= shift
% BIGNUM_INT_BITS
;
141 addend
= (BignumDblInt
)n
<< bshift
;
144 addend
+= number
[word
];
145 number
[word
] = (BignumInt
) addend
& BIGNUM_INT_MASK
;
146 addend
>>= BIGNUM_INT_BITS
;
153 * Input in first alen words of a and first mlen words of m.
154 * Output in first alen words of a
155 * (of which first alen-mlen words will be zero).
156 * The MSW of m MUST have its high bit set.
157 * Quotient is accumulated in the `quotient' array, which is a Bignum
158 * rather than the internal bigendian format. Quotient parts are shifted
159 * left by `qshift' before adding into quot.
161 static void internal_mod(BignumInt
*a
, int alen
,
162 BignumInt
*m
, int mlen
,
163 BignumInt
*quot
, int qshift
)
175 for (i
= 0; i
<= alen
- mlen
; i
++) {
177 unsigned int q
, r
, c
, ai1
;
191 /* Find q = h:a[i] / m0 */
196 * To illustrate it, suppose a BignumInt is 8 bits, and
197 * we are dividing (say) A1:23:45:67 by A1:B2:C3. Then
198 * our initial division will be 0xA123 / 0xA1, which
199 * will give a quotient of 0x100 and a divide overflow.
200 * However, the invariants in this division algorithm
201 * are not violated, since the full number A1:23:... is
202 * _less_ than the quotient prefix A1:B2:... and so the
203 * following correction loop would have sorted it out.
205 * In this situation we set q to be the largest
206 * quotient we _can_ stomach (0xFF, of course).
210 /* Macro doesn't want an array subscript expression passed
211 * into it (see definition), so use a temporary. */
212 BignumInt tmplo
= a
[i
];
213 DIVMOD_WORD(q
, r
, h
, tmplo
, m0
);
215 /* Refine our estimate of q by looking at
216 h:a[i]:a[i+1] / m0:m1 */
218 if (t
> ((BignumDblInt
) r
<< BIGNUM_INT_BITS
) + ai1
) {
221 r
= (r
+ m0
) & BIGNUM_INT_MASK
; /* overflow? */
222 if (r
>= (BignumDblInt
) m0
&&
223 t
> ((BignumDblInt
) r
<< BIGNUM_INT_BITS
) + ai1
) q
--;
227 /* Subtract q * m from a[i...] */
229 for (k
= mlen
- 1; k
>= 0; k
--) {
230 t
= MUL_WORD(q
, m
[k
]);
232 c
= (unsigned)(t
>> BIGNUM_INT_BITS
);
233 if ((BignumInt
) t
> a
[i
+ k
])
235 a
[i
+ k
] -= (BignumInt
) t
;
238 /* Add back m in case of borrow */
241 for (k
= mlen
- 1; k
>= 0; k
--) {
244 a
[i
+ k
] = (BignumInt
) t
;
245 t
= t
>> BIGNUM_INT_BITS
;
250 internal_add_shifted(quot
, q
, qshift
+ BIGNUM_INT_BITS
* (alen
- mlen
- i
));
256 * The most significant word of mod MUST be non-zero.
257 * We assume that the result array is the same size as the mod array.
258 * We optionally write out a quotient if `quotient' is non-NULL.
259 * We can avoid writing out the result if `result' is NULL.
261 void bigdivmod(void *mem_ctx
, Bignum p
, Bignum mod
, Bignum result
, Bignum quotient
)
265 int plen
, mlen
, i
, j
;
267 /* Allocate m of size mlen, copy mod to m */
268 /* We use big endian internally */
270 m
= snewn(mem_ctx
, mlen
, BignumInt
);
272 //abort(); /* FIXME */
273 for (j
= 0; j
< mlen
; j
++)
274 m
[j
] = mod
[mod
[0] - j
];
276 /* Shift m left to make msb bit set */
277 for (mshift
= 0; mshift
< BIGNUM_INT_BITS
-1; mshift
++)
278 if ((m
[0] << mshift
) & BIGNUM_TOP_BIT
)
281 for (i
= 0; i
< mlen
- 1; i
++)
282 m
[i
] = (m
[i
] << mshift
) | (m
[i
+ 1] >> (BIGNUM_INT_BITS
- mshift
));
283 m
[mlen
- 1] = m
[mlen
- 1] << mshift
;
287 /* Ensure plen > mlen */
291 /* Allocate n of size plen, copy p to n */
292 n
= snewn(mem_ctx
, plen
, BignumInt
);
294 //abort(); /* FIXME */
295 for (j
= 0; j
< plen
; j
++)
297 for (j
= 1; j
<= (int)p
[0]; j
++)
300 /* Main computation */
301 internal_mod(n
, plen
, m
, mlen
, quotient
, mshift
);
303 /* Fixup result in case the modulus was shifted */
305 for (i
= plen
- mlen
- 1; i
< plen
- 1; i
++)
306 n
[i
] = (n
[i
] << mshift
) | (n
[i
+ 1] >> (BIGNUM_INT_BITS
- mshift
));
307 n
[plen
- 1] = n
[plen
- 1] << mshift
;
308 internal_mod(n
, plen
, m
, mlen
, quotient
, 0);
309 for (i
= plen
- 1; i
>= plen
- mlen
; i
--)
310 n
[i
] = (n
[i
] >> mshift
) | (n
[i
- 1] << (BIGNUM_INT_BITS
- mshift
));
313 /* Copy result to buffer */
315 for (i
= 1; i
<= (int)result
[0]; i
++) {
317 result
[i
] = j
>= 0 ? n
[j
] : 0;
321 /* Free temporary arrays */
322 for (i
= 0; i
< mlen
; i
++)
325 for (i
= 0; i
< plen
; i
++)
333 Bignum
bigmod(void *mem_ctx
, Bignum a
, Bignum b
)
335 Bignum r
= newbn(mem_ctx
, b
[0]);
336 bigdivmod(mem_ctx
, a
, b
, r
, NULL
);
341 * Compute (base ^ exp) % mod.
343 Bignum
dwc_modpow(void *mem_ctx
, Bignum base_in
, Bignum exp
, Bignum mod
)
345 BignumInt
*a
, *b
, *n
, *m
;
351 * The most significant word of mod needs to be non-zero. It
352 * should already be, but let's make sure.
354 //assert(mod[mod[0]] != 0);
357 * Make sure the base is smaller than the modulus, by reducing
358 * it modulo the modulus if not.
360 base
= bigmod(mem_ctx
, base_in
, mod
);
362 /* Allocate m of size mlen, copy mod to m */
363 /* We use big endian internally */
365 m
= snewn(mem_ctx
, mlen
, BignumInt
);
367 //abort(); /* FIXME */
368 for (j
= 0; j
< mlen
; j
++)
369 m
[j
] = mod
[mod
[0] - j
];
371 /* Shift m left to make msb bit set */
372 for (mshift
= 0; mshift
< BIGNUM_INT_BITS
- 1; mshift
++)
373 if ((m
[0] << mshift
) & BIGNUM_TOP_BIT
)
376 for (i
= 0; i
< mlen
- 1; i
++)
378 (m
[i
] << mshift
) | (m
[i
+ 1] >>
379 (BIGNUM_INT_BITS
- mshift
));
380 m
[mlen
- 1] = m
[mlen
- 1] << mshift
;
383 /* Allocate n of size mlen, copy base to n */
384 n
= snewn(mem_ctx
, mlen
, BignumInt
);
386 //abort(); /* FIXME */
388 for (j
= 0; j
< i
; j
++)
390 for (j
= 0; j
< base
[0]; j
++)
391 n
[i
+ j
] = base
[base
[0] - j
];
393 /* Allocate a and b of size 2*mlen. Set a = 1 */
394 a
= snewn(mem_ctx
, 2 * mlen
, BignumInt
);
396 //abort(); /* FIXME */
397 b
= snewn(mem_ctx
, 2 * mlen
, BignumInt
);
399 //abort(); /* FIXME */
400 for (i
= 0; i
< 2 * mlen
; i
++)
404 /* Skip leading zero bits of exp. */
406 j
= BIGNUM_INT_BITS
- 1;
407 while (i
< exp
[0] && (exp
[exp
[0] - i
] & (1 << j
)) == 0) {
411 j
= BIGNUM_INT_BITS
- 1;
415 /* Main computation */
418 internal_mul(a
+ mlen
, a
+ mlen
, b
, mlen
);
419 internal_mod(b
, mlen
* 2, m
, mlen
, NULL
, 0);
420 if ((exp
[exp
[0] - i
] & (1 << j
)) != 0) {
421 internal_mul(b
+ mlen
, n
, a
, mlen
);
422 internal_mod(a
, mlen
* 2, m
, mlen
, NULL
, 0);
432 j
= BIGNUM_INT_BITS
- 1;
435 /* Fixup result in case the modulus was shifted */
437 for (i
= mlen
- 1; i
< 2 * mlen
- 1; i
++)
439 (a
[i
] << mshift
) | (a
[i
+ 1] >>
440 (BIGNUM_INT_BITS
- mshift
));
441 a
[2 * mlen
- 1] = a
[2 * mlen
- 1] << mshift
;
442 internal_mod(a
, mlen
* 2, m
, mlen
, NULL
, 0);
443 for (i
= 2 * mlen
- 1; i
>= mlen
; i
--)
445 (a
[i
] >> mshift
) | (a
[i
- 1] <<
446 (BIGNUM_INT_BITS
- mshift
));
449 /* Copy result to buffer */
450 result
= newbn(mem_ctx
, mod
[0]);
451 for (i
= 0; i
< mlen
; i
++)
452 result
[result
[0] - i
] = a
[i
+ mlen
];
453 while (result
[0] > 1 && result
[result
[0]] == 0)
456 /* Free temporary arrays */
457 for (i
= 0; i
< 2 * mlen
; i
++)
460 for (i
= 0; i
< 2 * mlen
; i
++)
463 for (i
= 0; i
< mlen
; i
++)
466 for (i
= 0; i
< mlen
; i
++)
470 freebn(mem_ctx
, base
);
478 static __u32 dh_p
[] = {
578 static __u32 dh_a
[] = {
590 static __u32 dh_b
[] = {
602 static __u32 dh_g
[] = {
611 k
= dwc_modpow(NULL
, dh_g
, dh_a
, dh_p
);
614 for (i
=0; i
<k
[0]; i
++) {
615 __u32 word32
= k
[k
[0] - i
];
616 __u16 l
= word32
& 0xffff;
617 __u16 m
= (word32
& 0xffff0000) >> 16;
618 printf("%04x %04x ", m
, l
);
619 if (!((i
+ 1)%13)) printf("\n");
623 if ((k
[0] == 0x60) && (k
[1] == 0x28e490e5) && (k
[0x60] == 0x5a0d3d4e)) {
632 #endif /* UNITTEST */
634 #endif /* CONFIG_MACH_IPMATE */
636 #endif /*DWC_CRYPTOLIB */