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 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