md5coll.c

用c语言实现得用于测试/md4md5散列算法的可碰撞性算法,用于证明md4/md5的可碰撞性

		/* A7 */
		Q0[25] = RL(G(Q0[24], Q0[23], Q0[22]) + Q0[21]
			+ X0[ 9] + 0x21e1cde6,  5) + Q0[24];
		Q1[25] = RL(G(Q1[24], Q1[23], Q1[22]) + Q1[21]
			+ X1[ 9] + 0x21e1cde6,  5) + Q1[24];
		if(Q0[25] != Q1[25])
			continue;

		/* D7 */
		Q0[26] = RL(G(Q0[25], Q0[24], Q0[23]) + Q0[22]
			+ X0[14] + 0xc33707d6,  9) + Q0[25];
		Q1[26] = RL(G(Q1[25], Q1[24], Q1[23]) + Q1[22]
			+ X1[14] + 0xc33707d6,  9) + Q1[25];
		if(Q0[26] != Q1[26])
			continue;

		/* C7 */
		Q0[27] = RL(G(Q0[26], Q0[25], Q0[24]) + Q0[23]
			+ X0[ 3] + 0xf4d50d87, 14) + Q0[26];
		Q1[27] = RL(G(Q1[26], Q1[25], Q1[24]) + Q1[23]
			+ X1[ 3] + 0xf4d50d87, 14) + Q1[26];
		if(Q0[27] != Q1[27])
			continue;

		/* B7 */
		Q0[28] = RL(G(Q0[27], Q0[26], Q0[25]) + Q0[24]
			+ X0[ 8] + 0x455a14ed, 20) + Q0[27];
		Q1[28] = RL(G(Q1[27], Q1[26], Q1[25]) + Q1[24]
			+ X1[ 8] + 0x455a14ed, 20) + Q1[27];
		if(Q0[28] != Q1[28])
			continue;

		/* A8 */
		Q0[29] = RL(G(Q0[28], Q0[27], Q0[26]) + Q0[25]
			+ X0[13] + 0xa9e3e905,  5) + Q0[28];
		Q1[29] = RL(G(Q1[28], Q1[27], Q1[26]) + Q1[25]
			+ X1[13] + 0xa9e3e905,  5) + Q1[28];
		if(Q0[29] != Q1[29])
			continue;

		/* D8 */
		Q0[30] = RL(G(Q0[29], Q0[28], Q0[27]) + Q0[26]
			+ X0[ 2] + 0xfcefa3f8,  9) + Q0[29];
		Q1[30] = RL(G(Q1[29], Q1[28], Q1[27]) + Q1[26]
			+ X1[ 2] + 0xfcefa3f8,  9) + Q1[29];
		if(Q0[30] != Q1[30])
			continue;

		/* C8 */
		Q0[31] = RL(G(Q0[30], Q0[29], Q0[28]) + Q0[27]
			+ X0[ 7] + 0x676f02d9, 14) + Q0[30];
		Q1[31] = RL(G(Q1[30], Q1[29], Q1[28]) + Q1[27]
			+ X1[ 7] + 0x676f02d9, 14) + Q1[30];
		if(Q0[31] != Q1[31])
			continue;

		/* B8 */
		Q0[32] = RL(G(Q0[31], Q0[30], Q0[29]) + Q0[28]
			+ X0[12] + 0x8d2a4c8a, 20) + Q0[31];
		Q1[32] = RL(G(Q1[31], Q1[30], Q1[29]) + Q1[28]
			+ X1[12] + 0x8d2a4c8a, 20) + Q1[31];
		if(Q0[32] != Q1[32])
			continue;

		/* A9 */
		Q0[33] = RL(H(Q0[32], Q0[31], Q0[30]) + Q0[29]
			+ X0[ 5] + 0xfffa3942,  4) + Q0[32];
		Q1[33] = RL(H(Q1[32], Q1[31], Q1[30]) + Q1[29]
			+ X1[ 5] + 0xfffa3942,  4) + Q1[32];
		if(Q0[33] != Q1[33])
			continue;

		/* D9 */
		Q0[34] = RL(H(Q0[33], Q0[32], Q0[31]) + Q0[30]
			+ X0[ 8] + 0x8771f681, 11) + Q0[33];
		Q1[34] = RL(H(Q1[33], Q1[32], Q1[31]) + Q1[30]
			+ X1[ 8] + 0x8771f681, 11) + Q1[33];
		if(Q0[34] != Q1[34])
			continue;

		/* C9 */
		Q0[35] = RL(H(Q0[34], Q0[33], Q0[32]) + Q0[31]
			+ X0[11] + 0x6d9d6122, 16) + Q0[34];
		Q1[35] = RL(H(Q1[34], Q1[33], Q1[32]) + Q1[31]
			+ X1[11] + 0x6d9d6122, 16) + Q1[34];
		if((Q0[35] ^ Q1[35]) != 0x80000000)
			continue;

		/* B9 */
		Q0[36] = RL(H(Q0[35], Q0[34], Q0[33]) + Q0[32]
			+ X0[14] + 0xfde5380c, 23) + Q0[35];
		Q1[36] = RL(H(Q1[35], Q1[34], Q1[33]) + Q1[32]
			+ X1[14] + 0xfde5380c, 23) + Q1[35];
		if((Q0[36] ^ Q1[36]) != 0x80000000)
			continue;

		/* A10 */
		Q0[37] = RL(H(Q0[36], Q0[35], Q0[34]) + Q0[33]
			+ X0[ 1] + 0xa4beea44,  4) + Q0[36];
		Q1[37] = RL(H(Q1[36], Q1[35], Q1[34]) + Q1[33]
			+ X1[ 1] + 0xa4beea44,  4) + Q1[36];
		if((Q0[37] ^ Q1[37]) != 0x80000000)
			continue;

		/* D10 */
		Q0[38] = RL(H(Q0[37], Q0[36], Q0[35]) + Q0[34]
			+ X0[ 4] + 0x4bdecfa9, 11) + Q0[37];
		Q1[38] = RL(H(Q1[37], Q1[36], Q1[35]) + Q1[34]
			+ X1[ 4] + 0x4bdecfa9, 11) + Q1[37];
		if((Q0[38] ^ Q1[38]) != 0x80000000)
			continue;

		/* C10 */
		Q0[39] = RL(H(Q0[38], Q0[37], Q0[36]) + Q0[35]
			+ X0[ 7] + 0xf6bb4b60, 16) + Q0[38];
		Q1[39] = RL(H(Q1[38], Q1[37], Q1[36]) + Q1[35]
			+ X1[ 7] + 0xf6bb4b60, 16) + Q1[38];
		if((Q0[39] ^ Q1[39]) != 0x80000000)
			continue;

		/* B10 */
		Q0[40] = RL(H(Q0[39], Q0[38], Q0[37]) + Q0[36]
			+ X0[10] + 0xbebfbc70, 23) + Q0[39];
		Q1[40] = RL(H(Q1[39], Q1[38], Q1[37]) + Q1[36]
			+ X1[10] + 0xbebfbc70, 23) + Q1[39];
		if((Q0[40] ^ Q1[40]) != 0x80000000)
			continue;

		/* A11 */
		Q0[41] = RL(H(Q0[40], Q0[39], Q0[38]) + Q0[37]
			+ X0[13] + 0x289b7ec6,  4) + Q0[40];
		Q1[41] = RL(H(Q1[40], Q1[39], Q1[38]) + Q1[37]
			+ X1[13] + 0x289b7ec6,  4) + Q1[40];
		if((Q0[41] ^ Q1[41]) != 0x80000000)
			continue;

		/* D11 */
		Q0[42] = RL(H(Q0[41], Q0[40], Q0[39]) + Q0[38]
			+ X0[ 0] + 0xeaa127fa, 11) + Q0[41];
		Q1[42] = RL(H(Q1[41], Q1[40], Q1[39]) + Q1[38]
			+ X1[ 0] + 0xeaa127fa, 11) + Q1[41];
		if((Q0[42] ^ Q1[42]) != 0x80000000)
			continue;

		/* C11 */
		Q0[43] = RL(H(Q0[42], Q0[41], Q0[40]) + Q0[39]
			+ X0[ 3] + 0xd4ef3085, 16) + Q0[42];
		Q1[43] = RL(H(Q1[42], Q1[41], Q1[40]) + Q1[39]
			+ X1[ 3] + 0xd4ef3085, 16) + Q1[42];
		if((Q0[43] ^ Q1[43]) != 0x80000000)
			continue;

		/* B11 */
		Q0[44] = RL(H(Q0[43], Q0[42], Q0[41]) + Q0[40]
			+ X0[ 6] + 0x04881d05, 23) + Q0[43];
		Q1[44] = RL(H(Q1[43], Q1[42], Q1[41]) + Q1[40]
			+ X1[ 6] + 0x04881d05, 23) + Q1[43];
		if((Q0[44] ^ Q1[44]) != 0x80000000)
			continue;

		/* A12 */
		Q0[45] = RL(H(Q0[44], Q0[43], Q0[42]) + Q0[41]
			+ X0[ 9] + 0xd9d4d039,  4) + Q0[44];
		Q1[45] = RL(H(Q1[44], Q1[43], Q1[42]) + Q1[41]
			+ X1[ 9] + 0xd9d4d039,  4) + Q1[44];
		if((Q0[45] ^ Q1[45]) != 0x80000000)
			continue;

		/* D12 */
		Q0[46] = RL(H(Q0[45], Q0[44], Q0[43]) + Q0[42]
			+ X0[12] + 0xe6db99e5, 11) + Q0[45];
		Q1[46] = RL(H(Q1[45], Q1[44], Q1[43]) + Q1[42]
			+ X1[12] + 0xe6db99e5, 11) + Q1[45];
		if((Q0[46] ^ Q1[46]) != 0x80000000)
			continue;

		/* C12 */
		Q0[47] = RL(H(Q0[46], Q0[45], Q0[44]) + Q0[43]
			+ X0[15] + 0x1fa27cf8, 16) + Q0[46];
		Q1[47] = RL(H(Q1[46], Q1[45], Q1[44]) + Q1[43]
			+ X1[15] + 0x1fa27cf8, 16) + Q1[46];
		if((Q0[47] ^ Q1[47]) != 0x80000000)
			continue;

		/* B12 */
		Q0[48] = RL(H(Q0[47], Q0[46], Q0[45]) + Q0[44]
			+ X0[ 2] + 0xc4ac5665, 23) + Q0[47];
		if((Q0[48] ^ Q0[46]) & 0x80000000)
			continue;
		Q1[48] = RL(H(Q1[47], Q1[46], Q1[45]) + Q1[44]
			+ X1[ 2] + 0xc4ac5665, 23) + Q1[47];
		if((Q0[48] ^ Q1[48]) != 0x80000000)
			continue;

		/* A13 */
		Q0[49] = RL(I(Q0[48], Q0[47], Q0[46]) + Q0[45]
			+ X0[ 0] + 0xf4292244,  6) + Q0[48];
		if((Q0[49] ^ Q0[47]) & 0x80000000)
			continue;
		Q1[49] = RL(I(Q1[48], Q1[47], Q1[46]) + Q1[45]
			+ X1[ 0] + 0xf4292244,  6) + Q1[48];
		if((Q0[49] ^ Q1[49]) != 0x80000000)
			continue;

		/* D13 */
		Q0[50] = RL(I(Q0[49], Q0[48], Q0[47]) + Q0[46]
			+ X0[ 7] + 0x432aff97, 10) + Q0[49];
		if(!((Q0[50] ^ Q0[48]) & 0x80000000))
			continue;
		Q1[50] = RL(I(Q1[49], Q1[48], Q1[47]) + Q1[46]
			+ X1[ 7] + 0x432aff97, 10) + Q1[49];
		if((Q0[50] ^ Q1[50]) != 0x80000000)
			continue;

		/* C13 */
		Q0[51] = RL(I(Q0[50], Q0[49], Q0[48]) + Q0[47]
			+ X0[14] + 0xab9423a7, 15) + Q0[50];
		if((Q0[51] ^ Q0[49]) & 0x80000000)
			continue;
		Q1[51] = RL(I(Q1[50], Q1[49], Q1[48]) + Q1[47]
			+ X1[14] + 0xab9423a7, 15) + Q1[50];
		if((Q0[51] ^ Q1[51]) != 0x80000000)
			continue;

		/* B13 */
		Q0[52] = RL(I(Q0[51], Q0[50], Q0[49]) + Q0[48]
			+ X0[ 5] + 0xfc93a039, 21) + Q0[51];
		if((Q0[52] ^ Q0[50]) & 0x80000000)
			continue;
		Q1[52] = RL(I(Q1[51], Q1[50], Q1[49]) + Q1[48]
			+ X1[ 5] + 0xfc93a039, 21) + Q1[51];
		if((Q0[52] ^ Q1[52]) != 0x80000000)
			continue;

		/* A14 */
		Q0[53] = RL(I(Q0[52], Q0[51], Q0[50]) + Q0[49]
			+ X0[12] + 0x655b59c3,  6) + Q0[52];
		if((Q0[53] ^ Q0[51]) & 0x80000000)
			continue;
		Q1[53] = RL(I(Q1[52], Q1[51], Q1[50]) + Q1[49]
			+ X1[12] + 0x655b59c3,  6) + Q1[52];
		if((Q0[53] ^ Q1[53]) != 0x80000000)
			continue;

		/* D14 */
		Q0[54] = RL(I(Q0[53], Q0[52], Q0[51]) + Q0[50]
			+ X0[ 3] + 0x8f0ccc92, 10) + Q0[53];
		if((Q0[54] ^ Q0[52]) & 0x80000000)
			continue;
		Q1[54] = RL(I(Q1[53], Q1[52], Q1[51]) + Q1[50]
			+ X1[ 3] + 0x8f0ccc92, 10) + Q1[53];
		if((Q0[54] ^ Q1[54]) != 0x80000000)
			continue;

		/* C14 */
		Q0[55] = RL(I(Q0[54], Q0[53], Q0[52]) + Q0[51]
			+ X0[10] + 0xffeff47d, 15) + Q0[54];
		if((Q0[55] ^ Q0[53]) & 0x80000000)
			continue;
		Q1[55] = RL(I(Q1[54], Q1[53], Q1[52]) + Q1[51]
			+ X1[10] + 0xffeff47d, 15) + Q1[54];
		if((Q0[55] ^ Q1[55]) != 0x80000000)
			continue;

		/* B14 */
		Q0[56] = RL(I(Q0[55], Q0[54], Q0[53]) + Q0[52]
			+ X0[ 1] + 0x85845dd1, 21) + Q0[55];
		if((Q0[56] ^ Q0[54]) & 0x80000000)
			continue;
		Q1[56] = RL(I(Q1[55], Q1[54], Q1[53]) + Q1[52]
			+ X1[ 1] + 0x85845dd1, 21) + Q1[55];
		if((Q0[56] ^ Q1[56]) != 0x80000000)
			continue;

		/* A15 */
		Q0[57] = RL(I(Q0[56], Q0[55], Q0[54]) + Q0[53]
			+ X0[ 8] + 0x6fa87e4f,  6) + Q0[56];
		if((Q0[57] ^ Q0[55]) & 0x80000000)
			continue;
		Q1[57] = RL(I(Q1[56], Q1[55], Q1[54]) + Q1[53]
			+ X1[ 8] + 0x6fa87e4f,  6) + Q1[56];
		if((Q0[57] ^ Q1[57]) != 0x80000000)
			continue;

		/* D15 */
		Q0[58] = RL(I(Q0[57], Q0[56], Q0[55]) + Q0[54]
			+ X0[15] + 0xfe2ce6e0, 10) + Q0[57];
		if((Q0[58] ^ Q0[56]) & 0x80000000)
			continue;
		Q1[58] = RL(I(Q1[57], Q1[56], Q1[55]) + Q1[54]
			+ X1[15] + 0xfe2ce6e0, 10) + Q1[57];
		if((Q0[58] ^ Q1[58]) != 0x80000000)
			continue;

		/* C15 */
		Q0[59] = RL(I(Q0[58], Q0[57], Q0[56]) + Q0[55]
			+ X0[ 6] + 0xa3014314, 15) + Q0[58];
		if((Q0[59] ^ Q0[57]) & 0x80000000)
			continue;
		Q1[59] = RL(I(Q1[58], Q1[57], Q1[56]) + Q1[55]
			+ X1[ 6] + 0xa3014314, 15) + Q1[58];
		if((Q0[59] ^ Q1[59]) != 0x80000000)
			continue;

		/* B15 */
		Q0[60] = RL(I(Q0[59], Q0[58], Q0[57]) + Q0[56]
			+ X0[13] + 0x4e0811a1, 21) + Q0[59];
		if(Q0[60] & 0x02000000)
			continue;
		Q1[60] = RL(I(Q1[59], Q1[58], Q1[57]) + Q1[56]
			+ X1[13] + 0x4e0811a1, 21) + Q1[59];
		if((Q0[60] ^ Q1[60]) != 0x80000000)
			continue;

		/* A16 */
		Q0[61] = RL(I(Q0[60], Q0[59], Q0[58]) + Q0[57]
			+ X0[ 4] + 0xf7537e82,  6) + Q0[60];
		A0 = IV[0] + Q0[61];
		Q1[61] = RL(I(Q1[60], Q1[59], Q1[58]) + Q1[57]
			+ X1[ 4] + 0xf7537e82,  6) + Q1[60];
		A1 = IV[0] + Q1[61];
		if((A0 ^ A1) != 0x80000000)
			continue;

		/* D16 */
		Q0[62] = RL(I(Q0[61], Q0[60], Q0[59]) + Q0[58]
			+ X0[11] + 0xbd3af235, 10) + Q0[61];
		D0 = IV[3] + Q0[62];
		if(D0 & 0x02000000)
			continue;
		Q1[62] = RL(I(Q1[61], Q1[60], Q1[59]) + Q1[58]
			+ X1[11] + 0xbd3af235, 10) + Q1[61];
		D1 = IV[3] + Q1[62];
		if((D0 - D1) != 0x7e000000)
			continue;

		/* C16 */
		Q0[63] = RL(I(Q0[62], Q0[61], Q0[60]) + Q0[59]
			+ X0[ 2] + 0x2ad7d2bb, 15) + Q0[62];
		C0 = IV[2] + Q0[63];
		if((C0 & 0x86000000) != ((D0 & 0x80000000) | 0x02000000))
			continue;
		Q1[63] = RL(I(Q1[62], Q1[61], Q1[60]) + Q1[59]
			+ X1[ 2] + 0x2ad7d2bb, 15) + Q1[62];
		C1 = IV[2] + Q1[63];
		if((C0 - C1) != 0x7e000000)
			continue;

		/* B16 */
		Q0[64] = RL(I(Q0[63], Q0[62], Q0[61]) + Q0[60]
			+ X0[ 9] + 0xeb86d391, 21) + Q0[63];
		B0 = IV[1] + Q0[64];
		if((B0 & 0x86000020) != (C0 & 0x80000000))
			continue;
		Q1[64] = RL(I(Q1[63], Q1[62], Q1[61]) + Q1[60]
			+ X1[ 9] + 0xeb86d391, 21) + Q1[63];
		B1 = IV[1] + Q1[64];
		if((B0 - B1) != 0x7e000000)
			continue;
	
		break;
	}
	if(i >= LOOP_12)
		goto block1_again;
	return;
}

const unsigned int mask22[30] = {
	0x00000001, 0x00000002, 0x00000004, 0x00000008,
	0x00000010, 0x00000020, 0x00000040, 0x00000080,
	0x00000100, 0x00000200, 0x00000400, 0x00000800, 
	0x00001000, 0x00002000, 0x00004000, 0x00008000, 
	0x00010000, 0x00020000, 0x00040000, 0x00080000,
	0x00100000, 0x00200000, 0x00400000, 0x00800000,
	0x01000000, 0x02000000, 0x04000000, 0x08000000,
	0x10000000, 0x40000000
};

void block2(void)
{
	size_t i;

block2_again:
	for(;;)
	{
                /* A1 */
                Q0[ 1] = (random() | 0x84200000) & ~0x0a000820;
		Q1[ 1] = Q0[ 1] - 0x7e000000;

                X0[16] = RR(Q0[ 1] - B0,  7) - F(B0, C0, D0)
                        - A0 - 0xd76aa478;
                X1[16] = RR(Q1[ 1] - B1,  7) - F(B1, C1, D1)
                        - A1 - 0xd76aa478;
                if(X0[16] != X1[16])
                        continue;
		break;
	}

	for(i = 0; i < 10; i++)
	{
                /* D1 */