xref: /csrg-svn/lib/libc/gen/crypt.c (revision 17337)
1*17337Sralph /* @(#)crypt.c	4.2 (Berkeley) 11/05/84 */
21958Swnj /*
31958Swnj  * This program implements the
41958Swnj  * Proposed Federal Information Processing
51958Swnj  *  Data Encryption Standard.
61958Swnj  * See Federal Register, March 17, 1975 (40FR12134)
71958Swnj  */
81958Swnj 
91958Swnj /*
101958Swnj  * Initial permutation,
111958Swnj  */
121958Swnj static	char	IP[] = {
131958Swnj 	58,50,42,34,26,18,10, 2,
141958Swnj 	60,52,44,36,28,20,12, 4,
151958Swnj 	62,54,46,38,30,22,14, 6,
161958Swnj 	64,56,48,40,32,24,16, 8,
171958Swnj 	57,49,41,33,25,17, 9, 1,
181958Swnj 	59,51,43,35,27,19,11, 3,
191958Swnj 	61,53,45,37,29,21,13, 5,
201958Swnj 	63,55,47,39,31,23,15, 7,
211958Swnj };
221958Swnj 
231958Swnj /*
241958Swnj  * Final permutation, FP = IP^(-1)
251958Swnj  */
261958Swnj static	char	FP[] = {
271958Swnj 	40, 8,48,16,56,24,64,32,
281958Swnj 	39, 7,47,15,55,23,63,31,
291958Swnj 	38, 6,46,14,54,22,62,30,
301958Swnj 	37, 5,45,13,53,21,61,29,
311958Swnj 	36, 4,44,12,52,20,60,28,
321958Swnj 	35, 3,43,11,51,19,59,27,
331958Swnj 	34, 2,42,10,50,18,58,26,
341958Swnj 	33, 1,41, 9,49,17,57,25,
351958Swnj };
361958Swnj 
371958Swnj /*
381958Swnj  * Permuted-choice 1 from the key bits
391958Swnj  * to yield C and D.
401958Swnj  * Note that bits 8,16... are left out:
411958Swnj  * They are intended for a parity check.
421958Swnj  */
431958Swnj static	char	PC1_C[] = {
441958Swnj 	57,49,41,33,25,17, 9,
451958Swnj 	 1,58,50,42,34,26,18,
461958Swnj 	10, 2,59,51,43,35,27,
471958Swnj 	19,11, 3,60,52,44,36,
481958Swnj };
491958Swnj 
501958Swnj static	char	PC1_D[] = {
511958Swnj 	63,55,47,39,31,23,15,
521958Swnj 	 7,62,54,46,38,30,22,
531958Swnj 	14, 6,61,53,45,37,29,
541958Swnj 	21,13, 5,28,20,12, 4,
551958Swnj };
561958Swnj 
571958Swnj /*
581958Swnj  * Sequence of shifts used for the key schedule.
591958Swnj */
601958Swnj static	char	shifts[] = {
611958Swnj 	1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1,
621958Swnj };
631958Swnj 
641958Swnj /*
651958Swnj  * Permuted-choice 2, to pick out the bits from
661958Swnj  * the CD array that generate the key schedule.
671958Swnj  */
681958Swnj static	char	PC2_C[] = {
691958Swnj 	14,17,11,24, 1, 5,
701958Swnj 	 3,28,15, 6,21,10,
711958Swnj 	23,19,12, 4,26, 8,
721958Swnj 	16, 7,27,20,13, 2,
731958Swnj };
741958Swnj 
751958Swnj static	char	PC2_D[] = {
761958Swnj 	41,52,31,37,47,55,
771958Swnj 	30,40,51,45,33,48,
781958Swnj 	44,49,39,56,34,53,
791958Swnj 	46,42,50,36,29,32,
801958Swnj };
811958Swnj 
821958Swnj /*
831958Swnj  * The C and D arrays used to calculate the key schedule.
841958Swnj  */
851958Swnj 
861958Swnj static	char	C[28];
871958Swnj static	char	D[28];
881958Swnj /*
891958Swnj  * The key schedule.
901958Swnj  * Generated from the key.
911958Swnj  */
921958Swnj static	char	KS[16][48];
931958Swnj 
941958Swnj /*
95*17337Sralph  * The E bit-selection table.
96*17337Sralph  */
97*17337Sralph static	char	E[48];
98*17337Sralph static	char	e[] = {
99*17337Sralph 	32, 1, 2, 3, 4, 5,
100*17337Sralph 	 4, 5, 6, 7, 8, 9,
101*17337Sralph 	 8, 9,10,11,12,13,
102*17337Sralph 	12,13,14,15,16,17,
103*17337Sralph 	16,17,18,19,20,21,
104*17337Sralph 	20,21,22,23,24,25,
105*17337Sralph 	24,25,26,27,28,29,
106*17337Sralph 	28,29,30,31,32, 1,
107*17337Sralph };
108*17337Sralph 
109*17337Sralph /*
1101958Swnj  * Set up the key schedule from the key.
1111958Swnj  */
1121958Swnj 
1131958Swnj setkey(key)
1141958Swnj char *key;
1151958Swnj {
1161958Swnj 	register i, j, k;
1171958Swnj 	int t;
1181958Swnj 
1191958Swnj 	/*
1201958Swnj 	 * First, generate C and D by permuting
1211958Swnj 	 * the key.  The low order bit of each
1221958Swnj 	 * 8-bit char is not used, so C and D are only 28
1231958Swnj 	 * bits apiece.
1241958Swnj 	 */
1251958Swnj 	for (i=0; i<28; i++) {
1261958Swnj 		C[i] = key[PC1_C[i]-1];
1271958Swnj 		D[i] = key[PC1_D[i]-1];
1281958Swnj 	}
1291958Swnj 	/*
1301958Swnj 	 * To generate Ki, rotate C and D according
1311958Swnj 	 * to schedule and pick up a permutation
1321958Swnj 	 * using PC2.
1331958Swnj 	 */
1341958Swnj 	for (i=0; i<16; i++) {
1351958Swnj 		/*
1361958Swnj 		 * rotate.
1371958Swnj 		 */
1381958Swnj 		for (k=0; k<shifts[i]; k++) {
1391958Swnj 			t = C[0];
1401958Swnj 			for (j=0; j<28-1; j++)
1411958Swnj 				C[j] = C[j+1];
1421958Swnj 			C[27] = t;
1431958Swnj 			t = D[0];
1441958Swnj 			for (j=0; j<28-1; j++)
1451958Swnj 				D[j] = D[j+1];
1461958Swnj 			D[27] = t;
1471958Swnj 		}
1481958Swnj 		/*
1491958Swnj 		 * get Ki. Note C and D are concatenated.
1501958Swnj 		 */
1511958Swnj 		for (j=0; j<24; j++) {
1521958Swnj 			KS[i][j] = C[PC2_C[j]-1];
1531958Swnj 			KS[i][j+24] = D[PC2_D[j]-28-1];
1541958Swnj 		}
1551958Swnj 	}
156*17337Sralph 
157*17337Sralph 	for(i=0;i<48;i++)
158*17337Sralph 		E[i] = e[i];
1591958Swnj }
1601958Swnj 
1611958Swnj /*
1621958Swnj  * The 8 selection functions.
1631958Swnj  * For some reason, they give a 0-origin
1641958Swnj  * index, unlike everything else.
1651958Swnj  */
1661958Swnj static	char	S[8][64] = {
1671958Swnj 	14, 4,13, 1, 2,15,11, 8, 3,10, 6,12, 5, 9, 0, 7,
1681958Swnj 	 0,15, 7, 4,14, 2,13, 1,10, 6,12,11, 9, 5, 3, 8,
1691958Swnj 	 4, 1,14, 8,13, 6, 2,11,15,12, 9, 7, 3,10, 5, 0,
1701958Swnj 	15,12, 8, 2, 4, 9, 1, 7, 5,11, 3,14,10, 0, 6,13,
1711958Swnj 
1721958Swnj 	15, 1, 8,14, 6,11, 3, 4, 9, 7, 2,13,12, 0, 5,10,
1731958Swnj 	 3,13, 4, 7,15, 2, 8,14,12, 0, 1,10, 6, 9,11, 5,
1741958Swnj 	 0,14, 7,11,10, 4,13, 1, 5, 8,12, 6, 9, 3, 2,15,
1751958Swnj 	13, 8,10, 1, 3,15, 4, 2,11, 6, 7,12, 0, 5,14, 9,
1761958Swnj 
1771958Swnj 	10, 0, 9,14, 6, 3,15, 5, 1,13,12, 7,11, 4, 2, 8,
1781958Swnj 	13, 7, 0, 9, 3, 4, 6,10, 2, 8, 5,14,12,11,15, 1,
1791958Swnj 	13, 6, 4, 9, 8,15, 3, 0,11, 1, 2,12, 5,10,14, 7,
1801958Swnj 	 1,10,13, 0, 6, 9, 8, 7, 4,15,14, 3,11, 5, 2,12,
1811958Swnj 
1821958Swnj 	 7,13,14, 3, 0, 6, 9,10, 1, 2, 8, 5,11,12, 4,15,
1831958Swnj 	13, 8,11, 5, 6,15, 0, 3, 4, 7, 2,12, 1,10,14, 9,
1841958Swnj 	10, 6, 9, 0,12,11, 7,13,15, 1, 3,14, 5, 2, 8, 4,
1851958Swnj 	 3,15, 0, 6,10, 1,13, 8, 9, 4, 5,11,12, 7, 2,14,
1861958Swnj 
1871958Swnj 	 2,12, 4, 1, 7,10,11, 6, 8, 5, 3,15,13, 0,14, 9,
1881958Swnj 	14,11, 2,12, 4, 7,13, 1, 5, 0,15,10, 3, 9, 8, 6,
1891958Swnj 	 4, 2, 1,11,10,13, 7, 8,15, 9,12, 5, 6, 3, 0,14,
1901958Swnj 	11, 8,12, 7, 1,14, 2,13, 6,15, 0, 9,10, 4, 5, 3,
1911958Swnj 
1921958Swnj 	12, 1,10,15, 9, 2, 6, 8, 0,13, 3, 4,14, 7, 5,11,
1931958Swnj 	10,15, 4, 2, 7,12, 9, 5, 6, 1,13,14, 0,11, 3, 8,
1941958Swnj 	 9,14,15, 5, 2, 8,12, 3, 7, 0, 4,10, 1,13,11, 6,
1951958Swnj 	 4, 3, 2,12, 9, 5,15,10,11,14, 1, 7, 6, 0, 8,13,
1961958Swnj 
1971958Swnj 	 4,11, 2,14,15, 0, 8,13, 3,12, 9, 7, 5,10, 6, 1,
1981958Swnj 	13, 0,11, 7, 4, 9, 1,10,14, 3, 5,12, 2,15, 8, 6,
1991958Swnj 	 1, 4,11,13,12, 3, 7,14,10,15, 6, 8, 0, 5, 9, 2,
2001958Swnj 	 6,11,13, 8, 1, 4,10, 7, 9, 5, 0,15,14, 2, 3,12,
2011958Swnj 
2021958Swnj 	13, 2, 8, 4, 6,15,11, 1,10, 9, 3,14, 5, 0,12, 7,
2031958Swnj 	 1,15,13, 8,10, 3, 7, 4,12, 5, 6,11, 0,14, 9, 2,
2041958Swnj 	 7,11, 4, 1, 9,12,14, 2, 0, 6,10,13,15, 3, 5, 8,
2051958Swnj 	 2, 1,14, 7, 4,10, 8,13,15,12, 9, 0, 3, 5, 6,11,
2061958Swnj };
2071958Swnj 
2081958Swnj /*
2091958Swnj  * P is a permutation on the selected combination
2101958Swnj  * of the current L and key.
2111958Swnj  */
2121958Swnj static	char	P[] = {
2131958Swnj 	16, 7,20,21,
2141958Swnj 	29,12,28,17,
2151958Swnj 	 1,15,23,26,
2161958Swnj 	 5,18,31,10,
2171958Swnj 	 2, 8,24,14,
2181958Swnj 	32,27, 3, 9,
2191958Swnj 	19,13,30, 6,
2201958Swnj 	22,11, 4,25,
2211958Swnj };
2221958Swnj 
2231958Swnj /*
2241958Swnj  * The current block, divided into 2 halves.
2251958Swnj  */
2261958Swnj static	char	L[32], R[32];
2271958Swnj static	char	tempL[32];
2281958Swnj static	char	f[32];
2291958Swnj 
2301958Swnj /*
2311958Swnj  * The combination of the key and the input, before selection.
2321958Swnj  */
2331958Swnj static	char	preS[48];
2341958Swnj 
2351958Swnj /*
2361958Swnj  * The payoff: encrypt a block.
2371958Swnj  */
2381958Swnj 
2391958Swnj encrypt(block, edflag)
2401958Swnj char *block;
2411958Swnj {
2421958Swnj 	int i, ii;
2431958Swnj 	register t, j, k;
2441958Swnj 
2451958Swnj 	/*
2461958Swnj 	 * First, permute the bits in the input
2471958Swnj 	 */
2481958Swnj 	for (j=0; j<64; j++)
2491958Swnj 		L[j] = block[IP[j]-1];
2501958Swnj 	/*
2511958Swnj 	 * Perform an encryption operation 16 times.
2521958Swnj 	 */
2531958Swnj 	for (ii=0; ii<16; ii++) {
2541958Swnj 		/*
2551958Swnj 		 * Set direction
2561958Swnj 		 */
2571958Swnj 		if (edflag)
2581958Swnj 			i = 15-ii;
2591958Swnj 		else
2601958Swnj 			i = ii;
2611958Swnj 		/*
2621958Swnj 		 * Save the R array,
2631958Swnj 		 * which will be the new L.
2641958Swnj 		 */
2651958Swnj 		for (j=0; j<32; j++)
2661958Swnj 			tempL[j] = R[j];
2671958Swnj 		/*
2681958Swnj 		 * Expand R to 48 bits using the E selector;
2691958Swnj 		 * exclusive-or with the current key bits.
2701958Swnj 		 */
2711958Swnj 		for (j=0; j<48; j++)
2721958Swnj 			preS[j] = R[E[j]-1] ^ KS[i][j];
2731958Swnj 		/*
2741958Swnj 		 * The pre-select bits are now considered
2751958Swnj 		 * in 8 groups of 6 bits each.
2761958Swnj 		 * The 8 selection functions map these
2771958Swnj 		 * 6-bit quantities into 4-bit quantities
2781958Swnj 		 * and the results permuted
2791958Swnj 		 * to make an f(R, K).
2801958Swnj 		 * The indexing into the selection functions
2811958Swnj 		 * is peculiar; it could be simplified by
2821958Swnj 		 * rewriting the tables.
2831958Swnj 		 */
2841958Swnj 		for (j=0; j<8; j++) {
2851958Swnj 			t = 6*j;
2861958Swnj 			k = S[j][(preS[t+0]<<5)+
2871958Swnj 				(preS[t+1]<<3)+
2881958Swnj 				(preS[t+2]<<2)+
2891958Swnj 				(preS[t+3]<<1)+
2901958Swnj 				(preS[t+4]<<0)+
2911958Swnj 				(preS[t+5]<<4)];
2921958Swnj 			t = 4*j;
2931958Swnj 			f[t+0] = (k>>3)&01;
2941958Swnj 			f[t+1] = (k>>2)&01;
2951958Swnj 			f[t+2] = (k>>1)&01;
2961958Swnj 			f[t+3] = (k>>0)&01;
2971958Swnj 		}
2981958Swnj 		/*
2991958Swnj 		 * The new R is L ^ f(R, K).
3001958Swnj 		 * The f here has to be permuted first, though.
3011958Swnj 		 */
3021958Swnj 		for (j=0; j<32; j++)
3031958Swnj 			R[j] = L[j] ^ f[P[j]-1];
3041958Swnj 		/*
3051958Swnj 		 * Finally, the new L (the original R)
3061958Swnj 		 * is copied back.
3071958Swnj 		 */
3081958Swnj 		for (j=0; j<32; j++)
3091958Swnj 			L[j] = tempL[j];
3101958Swnj 	}
3111958Swnj 	/*
3121958Swnj 	 * The output L and R are reversed.
3131958Swnj 	 */
3141958Swnj 	for (j=0; j<32; j++) {
3151958Swnj 		t = L[j];
3161958Swnj 		L[j] = R[j];
3171958Swnj 		R[j] = t;
3181958Swnj 	}
3191958Swnj 	/*
3201958Swnj 	 * The final output
3211958Swnj 	 * gets the inverse permutation of the very original.
3221958Swnj 	 */
3231958Swnj 	for (j=0; j<64; j++)
3241958Swnj 		block[j] = L[FP[j]-1];
3251958Swnj }
3261958Swnj 
3271958Swnj char *
3281958Swnj crypt(pw,salt)
3291958Swnj char *pw;
3301958Swnj char *salt;
3311958Swnj {
3321958Swnj 	register i, j, c;
3331958Swnj 	int temp;
3341958Swnj 	static char block[66], iobuf[16];
335*17337Sralph 
3361958Swnj 	for(i=0; i<66; i++)
3371958Swnj 		block[i] = 0;
3381958Swnj 	for(i=0; (c= *pw) && i<64; pw++){
3391958Swnj 		for(j=0; j<7; j++, i++)
3401958Swnj 			block[i] = (c>>(6-j)) & 01;
3411958Swnj 		i++;
3421958Swnj 	}
3431958Swnj 
3441958Swnj 	setkey(block);
3451958Swnj 
3461958Swnj 	for(i=0; i<66; i++)
3471958Swnj 		block[i] = 0;
3481958Swnj 
3491958Swnj 	for(i=0;i<2;i++){
3501958Swnj 		c = *salt++;
3511958Swnj 		iobuf[i] = c;
3521958Swnj 		if(c>'Z') c -= 6;
3531958Swnj 		if(c>'9') c -= 7;
3541958Swnj 		c -= '.';
3551958Swnj 		for(j=0;j<6;j++){
3561958Swnj 			if((c>>j) & 01){
3571958Swnj 				temp = E[6*i+j];
3581958Swnj 				E[6*i+j] = E[6*i+j+24];
3591958Swnj 				E[6*i+j+24] = temp;
3601958Swnj 				}
3611958Swnj 			}
3621958Swnj 		}
3631958Swnj 
3641958Swnj 	for(i=0; i<25; i++)
3651958Swnj 		encrypt(block,0);
3661958Swnj 
3671958Swnj 	for(i=0; i<11; i++){
3681958Swnj 		c = 0;
3691958Swnj 		for(j=0; j<6; j++){
3701958Swnj 			c <<= 1;
3711958Swnj 			c |= block[6*i+j];
3721958Swnj 			}
3731958Swnj 		c += '.';
3741958Swnj 		if(c>'9') c += 7;
3751958Swnj 		if(c>'Z') c += 6;
3761958Swnj 		iobuf[i+2] = c;
3771958Swnj 	}
3781958Swnj 	iobuf[i+2] = 0;
3791958Swnj 	if(iobuf[1]==0)
3801958Swnj 		iobuf[1] = iobuf[0];
3811958Swnj 	return(iobuf);
3821958Swnj }
383