001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License. You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing,
013 * software distributed under the License is distributed on an
014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 * KIND, either express or implied. See the License for the
016 * specific language governing permissions and limitations
017 * under the License.
018 *
019 */
020 package org.apache.directory.server.kerberos.shared.crypto.encryption;
021
022
023 /**
024 * An implementation of the n-fold algorithm, as required by RFC 3961,
025 * "Encryption and Checksum Specifications for Kerberos 5."
026 *
027 * "To n-fold a number X, replicate the input value to a length that
028 * is the least common multiple of n and the length of X. Before
029 * each repetition, the input is rotated to the right by 13 bit
030 * positions. The successive n-bit chunks are added together using
031 * 1's-complement addition (that is, with end-around carry) to yield
032 * a n-bit result."
033 *
034 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
035 * @version $Rev$, $Date$
036 */
037 public class NFold
038 {
039 /**
040 * N-fold the data n times.
041 *
042 * @param n The number of times to n-fold the data.
043 * @param data The data to n-fold.
044 * @return The n-folded data.
045 */
046 public static byte[] nFold( int n, byte[] data )
047 {
048 int k = data.length * 8;
049 int lcm = getLcm( n, k );
050 int replicate = lcm / k;
051 byte[] sumBytes = new byte[lcm / 8];
052
053 for ( int i = 0; i < replicate; i++ )
054 {
055 int rotation = 13 * i;
056
057 byte[] temp = rotateRight( data, data.length * 8, rotation );
058
059 for ( int j = 0; j < temp.length; j++ )
060 {
061 sumBytes[j + i * temp.length] = temp[j];
062 }
063 }
064
065 byte[] sum = new byte[n / 8];
066 byte[] nfold = new byte[n / 8];
067
068 for ( int m = 0; m < lcm / n; m++ )
069 {
070 for ( int o = 0; o < n / 8; o++ )
071 {
072 sum[o] = sumBytes[o + ( m * n / 8 )];
073 }
074
075 nfold = sum( nfold, sum, nfold.length * 8 );
076
077 }
078
079 return nfold;
080 }
081
082
083 /**
084 * For 2 numbers, return the least-common multiple.
085 *
086 * @param n1 The first number.
087 * @param n2 The second number.
088 * @return The least-common multiple.
089 */
090 protected static int getLcm( int n1, int n2 )
091 {
092 int temp;
093 int product;
094
095 product = n1 * n2;
096
097 do
098 {
099 if ( n1 < n2 )
100 {
101 temp = n1;
102 n1 = n2;
103 n2 = temp;
104 }
105 n1 = n1 % n2;
106 }
107 while ( n1 != 0 );
108
109 return product / n2;
110 }
111
112
113 /**
114 * Right-rotate the given byte array.
115 *
116 * @param in The byte array to right-rotate.
117 * @param len The length of the byte array to rotate.
118 * @param step The number of positions to rotate the byte array.
119 * @return The right-rotated byte array.
120 */
121 private static byte[] rotateRight( byte[] in, int len, int step )
122 {
123 int numOfBytes = ( len - 1 ) / 8 + 1;
124 byte[] out = new byte[numOfBytes];
125
126 for ( int i = 0; i < len; i++ )
127 {
128 int val = getBit( in, i );
129 setBit( out, ( i + step ) % len, val );
130 }
131 return out;
132 }
133
134
135 /**
136 * Perform one's complement addition (addition with end-around carry). Note
137 * that for purposes of n-folding, we do not actually complement the
138 * result of the addition.
139 *
140 * @param n1 The first number.
141 * @param n2 The second number.
142 * @param len The length of the byte arrays to sum.
143 * @return The sum with end-around carry.
144 */
145 protected static byte[] sum( byte[] n1, byte[] n2, int len )
146 {
147 int numOfBytes = ( len - 1 ) / 8 + 1;
148 byte[] out = new byte[numOfBytes];
149 int carry = 0;
150
151 for ( int i = len - 1; i > -1; i-- )
152 {
153 int n1b = getBit( n1, i );
154 int n2b = getBit( n2, i );
155
156 int sum = n1b + n2b + carry;
157
158 if ( sum == 0 || sum == 1 )
159 {
160 setBit( out, i, sum );
161 carry = 0;
162 }
163 else if ( sum == 2 )
164 {
165 carry = 1;
166 }
167 else if ( sum == 3 )
168 {
169 setBit( out, i, 1 );
170 carry = 1;
171 }
172 }
173
174 if ( carry == 1 )
175 {
176 byte[] carryArray = new byte[n1.length];
177 carryArray[carryArray.length - 1] = 1;
178 out = sum( out, carryArray, n1.length * 8 );
179 }
180
181 return out;
182 }
183
184
185 /**
186 * Get a bit from a byte array at a given position.
187 *
188 * @param data The data to get the bit from.
189 * @param pos The position to get the bit at.
190 * @return The value of the bit.
191 */
192 private static int getBit( byte[] data, int pos )
193 {
194 int posByte = pos / 8;
195 int posBit = pos % 8;
196
197 byte valByte = data[posByte];
198 int valInt = valByte >> ( 8 - ( posBit + 1 ) ) & 0x0001;
199 return valInt;
200 }
201
202
203 /**
204 * Set a bit in a byte array at a given position.
205 *
206 * @param data The data to set the bit in.
207 * @param pos The position of the bit to set.
208 * @param The value to set the bit to.
209 */
210 private static void setBit( byte[] data, int pos, int val )
211 {
212 int posByte = pos / 8;
213 int posBit = pos % 8;
214 byte oldByte = data[posByte];
215 oldByte = ( byte ) ( ( ( 0xFF7F >> posBit ) & oldByte ) & 0x00FF );
216 byte newByte = ( byte ) ( ( val << ( 8 - ( posBit + 1 ) ) ) | oldByte );
217 data[posByte] = newByte;
218 }
219 }