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
|
/*
* Copyright (C) 1998 by the FundsXpress, INC.
*
* All rights reserved.
*
* Export of this software from the United States of America may require
* a specific license from the United States Government. It is the
* responsibility of any person or organization contemplating export to
* obtain such a license before exporting.
*
* WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
* distribute this software and its documentation for any purpose and
* without fee is hereby granted, provided that the above copyright
* notice appear in all copies and that both that copyright notice and
* this permission notice appear in supporting documentation, and that
* the name of FundsXpress. not be used in advertising or publicity pertaining
* to distribution of the software without specific, written prior
* permission. FundsXpress makes no representations about the suitability of
* this software for any purpose. It is provided "as is" without express
* or implied warranty.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
* WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
*/
#include "k5-int.h"
#ifdef HAVE_MEMORY_H
#include <memory.h>
#endif
/*
n-fold(k-bits):
l = lcm(n,k)
r = l/k
s = k-bits | k-bits rot 13 | k-bits rot 13*2 | ... | k-bits rot 13*(r-1)
compute the 1's complement sum:
n-fold = s[0..n-1]+s[n..2n-1]+s[2n..3n-1]+..+s[(k-1)*n..k*n-1]
*/
/* representation: msb first, assume n and k are multiples of 8, and
that k>=16. this is the case of all the cryptosystems which are
likely to be used. this function can be replaced if that
assumption ever fails. */
/* input length is in bits */
void
krb5int_nfold(unsigned int inbits, const unsigned char *in, unsigned int outbits,
unsigned char *out)
{
int a,b,c,lcm;
int byte, i, msbit;
/* the code below is more readable if I make these bytes
instead of bits */
inbits >>= 3;
outbits >>= 3;
/* first compute lcm(n,k) */
a = outbits;
b = inbits;
while(b != 0) {
c = b;
b = a%b;
a = c;
}
lcm = outbits*inbits/a;
/* now do the real work */
memset(out, 0, outbits);
byte = 0;
/* this will end up cycling through k lcm(k,n)/k times, which
is correct */
for (i=lcm-1; i>=0; i--) {
/* compute the msbit in k which gets added into this byte */
msbit = (/* first, start with the msbit in the first, unrotated
byte */
((inbits<<3)-1)
/* then, for each byte, shift to the right for each
repetition */
+(((inbits<<3)+13)*(i/inbits))
/* last, pick out the correct byte within that
shifted repetition */
+((inbits-(i%inbits))<<3)
)%(inbits<<3);
/* pull out the byte value itself */
byte += (((in[((inbits-1)-(msbit>>3))%inbits]<<8)|
(in[((inbits)-(msbit>>3))%inbits]))
>>((msbit&7)+1))&0xff;
/* do the addition */
byte += out[i%outbits];
out[i%outbits] = byte&0xff;
#if 0
printf("msbit[%d] = %d\tbyte = %02x\tsum = %03x\n", i, msbit,
(((in[((inbits-1)-(msbit>>3))%inbits]<<8)|
(in[((inbits)-(msbit>>3))%inbits]))
>>((msbit&7)+1))&0xff, byte);
#endif
/* keep around the carry bit, if any */
byte >>= 8;
#if 0
printf("carry=%d\n", byte);
#endif
}
/* if there's a carry bit left over, add it back in */
if (byte) {
for (i=outbits-1; i>=0; i--) {
/* do the addition */
byte += out[i];
out[i] = byte&0xff;
/* keep around the carry bit, if any */
byte >>= 8;
}
}
}
|