Crypto Basic

1.HASH算法

1.1 SHA1

1.1.1 特点

• 生成的hash串长度为20字节
• 原始消息长度不能超过2的64次方减1

1.1.2 原理

1.1.2.1 原理图

1.1.2.2 消息分组补位

通过补位使明文串满足对512取模为448，补位规则为第一位补1，其余位补0，448 + 64刚好为512，其中64bit为原始消息长度。

1.1.2.3 生成W分组

循环处理每一个512bit分组，将每一个分组按照32bit分成16份，依次为MT[0], MT[1]……MT[15]，再生成80份32bit的W分组，依次为W[0], W[1]……W[79]，W分组生成算法如下：

其中那个ROTL是左移运算，W之间是异或运算。

1.1.2.4 处理分组

根据5个常数，进行80轮运算，最终得到5个数，最后这5个数分别与5个原始常数做加法后取模2的32次方，最终拼接即可获取首轮hash值

根据5个初始hash变量，进行80轮运算，初始值如下：

上述的H分别对应a, b, c, d, e，hash生成算法如下：

其中K公式如下：

其中f1函数定义如下：

最终根据新的a, b, c, d, e生成新的H，作为下一轮运算的初始值，公式如下：

其中的 “ + “ 符号表示 x = (a + b) % 2的32次方。

最终根据512bit分组的份数进行多次运算，最终生成的H拼接在一起即为结果hash。

1.1.3 代码实现

/*
sha1.hpp - source code of
============
SHA-1 in C++
============
100% Public Domain.
Original C Code
-- Steve Reid <steve@edmweb.com>
Small changes to fit into bglibs
-- Bruce Guenter <bruce@untroubled.org>
Translation to simpler C++ Code
-- Volker Diels-Grabsch <v@njh.eu>
Safety fixes
-- Eugene Hopkinson <slowriot at voxelstorm dot com>
Header-only library
-- Zlatko Michailov <zlatko@michailov.org>
*/

#ifndef SHA1_HPP
#define SHA1_HPP


#include <cstdint>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>

#include <string>
#include <iostream>


class SHA1
{
public:
	SHA1();
	void update(const std::string &s);
	void update(std::istream &is);
	std::string final();
	static std::string from_file(const std::string &filename);

private:
	uint32_t digest[5];
	std::string buffer;
	uint64_t transforms;
};


static const size_t BLOCK_INTS = 16;  /* number of 32bit integers per SHA1 block */
static const size_t BLOCK_BYTES = BLOCK_INTS * 4;


inline static void reset(uint32_t digest[], std::string &buffer, uint64_t &transforms)
{
	/* SHA1 initialization constants */
	digest[0] = 0x67452301;
	digest[1] = 0xefcdab89;
	digest[2] = 0x98badcfe;
	digest[3] = 0x10325476;
	digest[4] = 0xc3d2e1f0;

	/* Reset counters */
	buffer = "";
	transforms = 0;
}


inline static uint32_t rol(const uint32_t value, const size_t bits)
{
	return (value << bits) | (value >> (32 - bits));
}


inline static uint32_t blk(const uint32_t block[BLOCK_INTS], const size_t i)
{
	return rol(block[(i + 13) & 15] ^ block[(i + 8) & 15] ^ block[(i + 2) & 15] ^ block[i], 1);
}


/*
* (R0+R1), R2, R3, R4 are the different operations used in SHA1
*/

inline static void R0(const uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
	z += ((w&(x^y)) ^ y) + block[i] + 0x5a827999 + rol(v, 5);
	w = rol(w, 30);
}


inline static void R1(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
	block[i] = blk(block, i);
	z += ((w&(x^y)) ^ y) + block[i] + 0x5a827999 + rol(v, 5);
	w = rol(w, 30);
}


inline static void R2(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
	block[i] = blk(block, i);
	z += (w^x^y) + block[i] + 0x6ed9eba1 + rol(v, 5);
	w = rol(w, 30);
}


inline static void R3(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
	block[i] = blk(block, i);
	z += (((w | x)&y) | (w&x)) + block[i] + 0x8f1bbcdc + rol(v, 5);
	w = rol(w, 30);
}


inline static void R4(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
	block[i] = blk(block, i);
	z += (w^x^y) + block[i] + 0xca62c1d6 + rol(v, 5);
	w = rol(w, 30);
}


/*
* Hash a single 512-bit block. This is the core of the algorithm.
*/

inline static void transform(uint32_t digest[], uint32_t block[BLOCK_INTS], uint64_t &transforms)
{
	/* Copy digest[] to working vars */
	uint32_t a = digest[0];
	uint32_t b = digest[1];
	uint32_t c = digest[2];
	uint32_t d = digest[3];
	uint32_t e = digest[4];

	/* 4 rounds of 20 operations each. Loop unrolled. */
	R0(block, a, b, c, d, e, 0);
	R0(block, e, a, b, c, d, 1);
	R0(block, d, e, a, b, c, 2);
	R0(block, c, d, e, a, b, 3);
	R0(block, b, c, d, e, a, 4);
	R0(block, a, b, c, d, e, 5);
	R0(block, e, a, b, c, d, 6);
	R0(block, d, e, a, b, c, 7);
	R0(block, c, d, e, a, b, 8);
	R0(block, b, c, d, e, a, 9);
	R0(block, a, b, c, d, e, 10);
	R0(block, e, a, b, c, d, 11);
	R0(block, d, e, a, b, c, 12);
	R0(block, c, d, e, a, b, 13);
	R0(block, b, c, d, e, a, 14);
	R0(block, a, b, c, d, e, 15);
	R1(block, e, a, b, c, d, 0);
	R1(block, d, e, a, b, c, 1);
	R1(block, c, d, e, a, b, 2);
	R1(block, b, c, d, e, a, 3);
	R2(block, a, b, c, d, e, 4);
	R2(block, e, a, b, c, d, 5);
	R2(block, d, e, a, b, c, 6);
	R2(block, c, d, e, a, b, 7);
	R2(block, b, c, d, e, a, 8);
	R2(block, a, b, c, d, e, 9);
	R2(block, e, a, b, c, d, 10);
	R2(block, d, e, a, b, c, 11);
	R2(block, c, d, e, a, b, 12);
	R2(block, b, c, d, e, a, 13);
	R2(block, a, b, c, d, e, 14);
	R2(block, e, a, b, c, d, 15);
	R2(block, d, e, a, b, c, 0);
	R2(block, c, d, e, a, b, 1);
	R2(block, b, c, d, e, a, 2);
	R2(block, a, b, c, d, e, 3);
	R2(block, e, a, b, c, d, 4);
	R2(block, d, e, a, b, c, 5);
	R2(block, c, d, e, a, b, 6);
	R2(block, b, c, d, e, a, 7);
	R3(block, a, b, c, d, e, 8);
	R3(block, e, a, b, c, d, 9);
	R3(block, d, e, a, b, c, 10);
	R3(block, c, d, e, a, b, 11);
	R3(block, b, c, d, e, a, 12);
	R3(block, a, b, c, d, e, 13);
	R3(block, e, a, b, c, d, 14);
	R3(block, d, e, a, b, c, 15);
	R3(block, c, d, e, a, b, 0);
	R3(block, b, c, d, e, a, 1);
	R3(block, a, b, c, d, e, 2);
	R3(block, e, a, b, c, d, 3);
	R3(block, d, e, a, b, c, 4);
	R3(block, c, d, e, a, b, 5);
	R3(block, b, c, d, e, a, 6);
	R3(block, a, b, c, d, e, 7);
	R3(block, e, a, b, c, d, 8);
	R3(block, d, e, a, b, c, 9);
	R3(block, c, d, e, a, b, 10);
	R3(block, b, c, d, e, a, 11);
	R4(block, a, b, c, d, e, 12);
	R4(block, e, a, b, c, d, 13);
	R4(block, d, e, a, b, c, 14);
	R4(block, c, d, e, a, b, 15);
	R4(block, b, c, d, e, a, 0);
	R4(block, a, b, c, d, e, 1);
	R4(block, e, a, b, c, d, 2);
	R4(block, d, e, a, b, c, 3);
	R4(block, c, d, e, a, b, 4);
	R4(block, b, c, d, e, a, 5);
	R4(block, a, b, c, d, e, 6);
	R4(block, e, a, b, c, d, 7);
	R4(block, d, e, a, b, c, 8);
	R4(block, c, d, e, a, b, 9);
	R4(block, b, c, d, e, a, 10);
	R4(block, a, b, c, d, e, 11);
	R4(block, e, a, b, c, d, 12);
	R4(block, d, e, a, b, c, 13);
	R4(block, c, d, e, a, b, 14);
	R4(block, b, c, d, e, a, 15);

	/* Add the working vars back into digest[] */
	digest[0] += a;
	digest[1] += b;
	digest[2] += c;
	digest[3] += d;
	digest[4] += e;

	/* Count the number of transformations */
	transforms++;
}


inline static void buffer_to_block(const std::string &buffer, uint32_t block[BLOCK_INTS])
{
	/* Convert the std::string (byte buffer) to a uint32_t array (MSB) */
	for (size_t i = 0; i < BLOCK_INTS; i++)
	{
		block[i] = (buffer[4 * i + 3] & 0xff)
			| (buffer[4 * i + 2] & 0xff) << 8
			| (buffer[4 * i + 1] & 0xff) << 16
			| (buffer[4 * i + 0] & 0xff) << 24;
	}
}


inline SHA1::SHA1()
{
	reset(digest, buffer, transforms);
}


inline void SHA1::update(const std::string &s)
{
	std::istringstream is(s);
	update(is);
}


inline void SHA1::update(std::istream &is)
{
	while (true)
	{
		char sbuf[BLOCK_BYTES];
		is.read(sbuf, BLOCK_BYTES - buffer.size());
		buffer.append(sbuf, (std::size_t)is.gcount());
		if (buffer.size() != BLOCK_BYTES)
		{
			return;
		}
		uint32_t block[BLOCK_INTS];
		buffer_to_block(buffer, block);
		transform(digest, block, transforms);
		buffer.clear();
	}
}


/*
* Add padding and return the message digest.
*/

inline std::string SHA1::final()
{
	/* Total number of hashed bits */
	uint64_t total_bits = (transforms*BLOCK_BYTES + buffer.size()) * 8;

	/* Padding */
	buffer += (char)0x80;
	size_t orig_size = buffer.size();
	while (buffer.size() < BLOCK_BYTES)
	{
		buffer += (char)0x00;
	}

	uint32_t block[BLOCK_INTS];
	buffer_to_block(buffer, block);

	if (orig_size > BLOCK_BYTES - 8)
	{
		transform(digest, block, transforms);
		for (size_t i = 0; i < BLOCK_INTS - 2; i++)
		{
			block[i] = 0;
		}
	}

	/* Append total_bits, split this uint64_t into two uint32_t */
	block[BLOCK_INTS - 1] = (uint32_t)total_bits;
	block[BLOCK_INTS - 2] = (uint32_t)(total_bits >> 32);
	transform(digest, block, transforms);

	/* Hex std::string */
	std::ostringstream result;
	for (size_t i = 0; i < sizeof(digest) / sizeof(digest[0]); i++)
	{
		result << std::hex << std::setfill('0') << std::setw(8);
		result << digest[i];
	}

	/* Reset for next run */
	reset(digest, buffer, transforms);

	return result.str();
}


inline std::string SHA1::from_file(const std::string &filename)
{
	std::ifstream stream(filename.c_str(), std::ios::binary);
	SHA1 checksum;
	checksum.update(stream);
	return checksum.final();
}

int main(int /* argc */, const char ** /* argv */)
{
	const std::string input = "Ymf";

	SHA1 checksum;
	checksum.update(input);
	const std::string hash = checksum.final();

	std::cout << "The SHA-1 of \"" << input << "\" is: " << hash << std::endl;

	return 0;
}

#endif /* SHA1_HPP */

1.1.4 逆向特征

• 可以根据H的初始值来确定
• 可以根据位运算特征来确定

2.随机数算法

2.1 Mersenne Twister

2.1.1 特点

• 基于位运算的伪随机数生成算法

• 使用随机数种子

• 需要一个初始状态

• 每生成一个随机数会转换一次状态

• 下一个随机数生成需要使用上一个状态

2.1.2 原理

分三个阶段：

1. 初始化，获得基础的梅森旋转链
2. 对旋转链进行旋转算法（状态传递）
3. 对旋转算法的结果进行处理（生成随机数）

2.1.3 实现

#include <stdint.h>
#include <stdio.h>

// 定义MT19937-32的常数
enum
{
	// 假定 W = 32 (此项省略)
	N = 624,
	M = 397,
	R = 31,
	A = 0x9908B0DF,

	F = 1812433253,

	U = 11,
	// 假定 D = 0xFFFFFFFF (此项省略)

	S = 7,
	B = 0x9D2C5680,

	T = 15,
	C = 0xEFC60000,

	L = 18,

	MASK_LOWER = (1ull << R) - 1,
	MASK_UPPER = (1ull << R)
};

static uint32_t  mt[N];
static uint16_t  index;

// 根据给定的seed初始化旋转链
void Initialize(const uint32_t  seed)
{
	uint32_t  i;
	mt[0] = seed;
	for (i = 1; i < N; i++)
	{
		mt[i] = (F * (mt[i - 1] ^ (mt[i - 1] >> 30)) + i);
	}
	index = N;
}

static void Twist()
{
	uint32_t  i, x, xA;
	for (i = 0; i < N; i++)
	{
		x = (mt[i] & MASK_UPPER) + (mt[(i + 1) % N] & MASK_LOWER);
		xA = x >> 1;
		if (x & 0x1)
		{
			xA ^= A;
		}
		mt[i] = mt[(i + M) % N] ^ xA;
	}

	index = 0;
}

// 产生一个32位随机数
uint32_t ExtractU32()
{
	uint32_t  y;
	int       i = index;
	if (index >= N)
	{
		Twist();
		i = index;
	}
	y = mt[i];
	index = i + 1;
	y ^= (y >> U);
	y ^= (y << S) & B;
	y ^= (y << T) & C;
	y ^= (y >> L);
	return y;
}

int main()
{
	Initialize(234);
	printf("random: %d\n", ExtractU32());

	return 0;
}

2.1.4 逆向特征

初始化函数：

旋转函数：

3.对称加密算法

3.1 RC4算法

3.1.1 特点

• 对称加密
• key长度1-256字节
• 使用KSA生成S盒，使用PRGA生成密钥流
• S盒为256字节的数组

3.1.2 原理

3.1.2.1 原理图

3.1.2.2 KSA

The key-scheduling algorithm算法，用于根据key来生成S盒。

首先初始化长度为256的数组，第一个for循环将0-255的互补重复的元素装入S盒，第二个for循环根据密钥打乱S盒，伪代码如下：

for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

3.1.2.3 PRGA

The pseudo-random generation algorithm算法，用于根据S盒生成与明文长度相同的密钥流，使用密钥加密明文，伪代码如下：

i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    K := S[(S[i] + S[j]) mod 256]
    output K
endwhile

其中3行是以明文长度范围内的循环，4、5行用于定位S盒中的元素，6行在不断的交换S盒的元素，7行在生成密钥流。示意图如下：

3.1.3 代码实现

3.1.3.1 KSA实现

void KSA(char* key, unsigned char* s_box)
{
	memset(s_box, 0, 256);
	int j = 0;
	for (int i = 0; i < 256; i++)
		s_box[i] = i;
	for (int i = 0; i < 256; i++)
	{
		j = (j + s_box[i] + key[i % strlen(key)]) % 256;
		swap(&s_box[i], &s_box[j]);
	}
}

3.1.3.2 PRGA实现

void PRGA(unsigned char* s_box, unsigned char* data, int data_size)
{
	int i = 0, j = 0, index = 0;
	while (data_size)
	{
		i = (i + 1) % 256;
		j = (j + s_box[i]) % 256;
		swap(&s_box[i], &s_box[j]);
		data[index] = s_box[(s_box[i] + s_box[j]) % 256];
		index++;
		data_size--;
	}
}

3.1.3.3 异或加密

void encode(char* key, char* data)
{
	unsigned char s_box[256] = { 0 };
	KSA(key, s_box);
	unsigned char* key_stream = new unsigned char[strlen(data)];
	if (!key_stream) 
		return;
	PRGA(s_box, key_stream, strlen(data));
	for (int i = 0; i < strlen(data); i++)
	{
		data[i] ^= key_stream[i];
	}
	if (key_stream)
	{
		delete[] key_stream;
		key_stream = NULL;
	}
}

3.1.3.4 运行结果

3.1.4 逆向特征

初始化256字节的数组，以及打乱数组元素，可以认为是产生s_box的KSA函数。如下图所示：

定位到s_box再定位PRGA函数会容易的多，如下图所示：

加密函数如下：