1 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /*
3 * Copyright (C) 1998 by the FundsXpress, INC.
4 *
5 * All rights reserved.
6 *
7 * Export of this software from the United States of America may require
8 * a specific license from the United States Government. It is the
9 * responsibility of any person or organization contemplating export to
10 * obtain such a license before exporting.
11 *
12 * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
13 * distribute this software and its documentation for any purpose and
14 * without fee is hereby granted, provided that the above copyright
15 * notice appear in all copies and that both that copyright notice and
16 * this permission notice appear in supporting documentation, and that
17 * the name of FundsXpress. not be used in advertising or publicity pertaining
18 * to distribution of the software without specific, written prior
19 * permission. FundsXpress makes no representations about the suitability of
20 * this software for any purpose. It is provided "as is" without express
21 * or implied warranty.
22 *
23 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
24 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
25 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
26 */
27
28 #include "crypto_int.h"
29
30 /*
31 * n-fold(k-bits):
32 * l = lcm(n,k)
33 * r = l/k
34 * s = k-bits | k-bits rot 13 | k-bits rot 13*2 | ... | k-bits rot 13*(r-1)
35 * compute the 1's complement sum:
36 * n-fold = s[0..n-1]+s[n..2n-1]+s[2n..3n-1]+..+s[(k-1)*n..k*n-1]
37 */
38
39 /* representation: msb first, assume n and k are multiples of 8, and
40 * that k>=16. this is the case of all the cryptosystems which are
41 * likely to be used. this function can be replaced if that
42 * assumption ever fails. */
43
44 /* input length is in bits */
45
46 void
krb5int_nfold(unsigned int inbits,const unsigned char * in,unsigned int outbits,unsigned char * out)47 krb5int_nfold(unsigned int inbits, const unsigned char *in, unsigned int outbits,
48 unsigned char *out)
49 {
50 int a,b,c,lcm;
51 int byte, i, msbit;
52
53 /* the code below is more readable if I make these bytes
54 instead of bits */
55
56 inbits >>= 3;
57 outbits >>= 3;
58
59 /* first compute lcm(n,k) */
60
61 a = outbits;
62 b = inbits;
63
64 while(b != 0) {
65 c = b;
66 b = a%b;
67 a = c;
68 }
69
70 lcm = outbits*inbits/a;
71
72 /* now do the real work */
73
74 memset(out, 0, outbits);
75 byte = 0;
76
77 /* this will end up cycling through k lcm(k,n)/k times, which
78 is correct */
79 for (i=lcm-1; i>=0; i--) {
80 /* compute the msbit in k which gets added into this byte */
81 msbit = (/* first, start with the msbit in the first, unrotated
82 byte */
83 ((inbits<<3)-1)
84 /* then, for each byte, shift to the right for each
85 repetition */
86 +(((inbits<<3)+13)*(i/inbits))
87 /* last, pick out the correct byte within that
88 shifted repetition */
89 +((inbits-(i%inbits))<<3)
90 )%(inbits<<3);
91
92 /* pull out the byte value itself */
93 byte += (((in[((inbits-1)-(msbit>>3))%inbits]<<8)|
94 (in[((inbits)-(msbit>>3))%inbits]))
95 >>((msbit&7)+1))&0xff;
96
97 /* do the addition */
98 byte += out[i%outbits];
99 out[i%outbits] = byte&0xff;
100
101 /* keep around the carry bit, if any */
102 byte >>= 8;
103
104 }
105
106 /* if there's a carry bit left over, add it back in */
107 if (byte) {
108 for (i=outbits-1; i>=0; i--) {
109 /* do the addition */
110 byte += out[i];
111 out[i] = byte&0xff;
112
113 /* keep around the carry bit, if any */
114 byte >>= 8;
115 }
116 }
117 }
118