Home | History | Annotate | Download | only in crypto
      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