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