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