七月 4

DES 与 RSA 密码算法实现代码

这个学期上信息安全课,期末课程设计是用任意编程语言实现 DES 和 RSA 两个加密 / 解密算法。花了几天时间研究了一下,照着 Wiki 和参考文档用 C++ 写出来了。因为实现比较简单,就不传 Github 了,现在想在博客保存一下代码副本,免得将来丢失了。

DES 加密/解密算法实现

#include <iostream>

/* 循环左移 */
#define ROL(_x_, _b_, _s_) (((_x_) << (_b_)) | ((_x_) >> ((_s_) - (_b_))))

static inline /* 高效求 2 的 p 次方函数 */
uint64_t pow2(int p) {
	if (p == -1) return 0;
	uint64_t ans = 1;
	ans <<= p;
	return ans;
}

static inline /* 置换操作辅助函数 */
uint64_t trans(const uint64_t & src, const char tab[], size_t tabsize, int range) {
	uint64_t obj = 0;
	for (size_t i = 0; i < tabsize; ++i) {
		auto bit = (pow2(range - tab[i]) & src);
		(obj <<= 1) |= (bit ? 1ULL : 0ULL);
	}
	return obj;
}

static inline /* 费斯妥 F 函数 */
uint32_t feistel(uint32_t r, uint64_t k) {
	// 扩展置换
	const static char e[48] = {
		32,  1,  2,  3,  4,  5,
		 4,  5,  6,  7,  8,  9,
		 8,  9, 10, 11, 12, 13,
		12, 13, 14, 15, 16, 17,
		16, 17, 18, 19, 20, 21,
		20, 21, 22, 23, 24, 25,
		24, 25, 26, 27, 28, 29,
		28, 29, 30, 31, 32,  1
	};

	uint64_t er = trans(r, e, sizeof(e), 32);

	// S 盒替代
	const static char s[8][64] = {
		{
			14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
			 0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
			 4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
			15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13
		}, {
			15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
			 3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
			 0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
			13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9
		}, {
			10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
			13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
			13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
			 1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12
		}, {
			 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
			13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
			10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
			 3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14
		}, {
			 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
			14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
			 4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
			11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3
		}, {
			12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
			10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
			 9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
			 4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13
		}, {
			 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
			13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
			 1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
			 6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12
		}, {
			13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
			 1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
			 7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
			 2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11
		}
	};

	uint64_t s_input = (er ^ k);
	uint32_t s_output = 0;
	for (int i = 7; i >= 0; --i) {
		auto row = ((s_input & 0x01ULL) ? 1 : 0)
			+ ((s_input & 0x20ULL) ? 1 : 0) * 2;
		auto col = ((s_input & 0x1eULL) >> 1);
		s_input >>= 6;
		s_output >>= 4;
		s_output |= (s[i][row * 16 + col] << 28);
	}

	// P 盒置换
	const static char p[32] = {
		16,  7, 20, 21, 29, 12, 28, 17,  1, 15, 23, 26,  5, 18, 31, 10,
		 2,  8, 24, 14, 32, 27,  3,  9, 19, 13, 30,  6, 22, 11,  4, 25
	};

	uint32_t p_output = static_cast<uint32_t>(trans(s_output, p, sizeof(p), 32));

	return p_output;
}

static inline /* DES 核心算法 */
uint64_t des(const uint64_t &m, const uint64_t &key, bool encrypt) {
	/* ******************** 初始置换 ******************** */
	const static char ip[64] = {
		58, 50, 42, 34, 26, 18, 10, 2,
		60, 52, 44, 36, 28, 20, 12, 4,
		62, 54, 46, 38, 30, 22, 14, 6,
		64, 56, 48, 40, 32, 24, 16, 8,
		57, 49, 41, 33, 25, 17,  9, 1,
		59, 51, 43, 35, 27, 19, 11, 3,
		61, 53, 45, 37, 29, 21, 13, 5,
		63, 55, 47, 39, 31, 23, 15, 7
	};

	uint64_t m_ = trans(m, ip, sizeof(ip), 64);

	// 初始子密钥
	uint32_t l[17] = { 0 };
	uint32_t r[17] = { 0 };
	l[0] = ((uint32_t*)&m_)[1];
	r[0] = ((uint32_t*)&m_)[0];

	/* ******************* 生成子密钥 ******************* */
	const static char pc_1[56] /* 1~64 */ = {
		57, 49, 41, 33, 25, 17,  9,
		 1, 58, 50, 42, 34, 26, 18,
		10,  2, 59, 51, 43, 35, 27,
		19, 11,  3, 60, 52, 44, 36,
		63, 55, 47, 39, 31, 23, 15,
		 7, 62, 54, 46, 38, 30, 22,
		14,  6, 61, 53, 45, 37, 29,
		21, 13,  5, 28, 20, 12,  4
	};

	uint64_t k[17] = { 0 }; /* 0: 56, 1~16: 48 */

	uint64_t &k_ = k[0]; /* 56, 48, 48... */ 
	k_ = trans(key, pc_1, sizeof(pc_1), 64);
	uint32_t c[17], d[17]; /* 28 */
	c[0] = static_cast<uint32_t>((k_ >> 28) & 0x0fffffffULL); // 前 28 位
	d[0] = static_cast<uint32_t>(k_ & 0x0fffffffULL); // 后 28 位
	
	const static char shift[17] = {
		0, /* 保留 */
		1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
	};

	const static char pc_2[48] /* 1~56 */ = {
		14, 17, 11, 24,  1,  5,
		 3, 28, 15,  6, 21, 10,
		23, 19, 12,  4, 26,  8,
		16,  7, 27, 20, 13,  2,
		41, 52, 31, 37, 47, 55,
		30, 40, 51, 45, 33, 48,
		44, 49, 39, 56, 34, 53,
		46, 42, 50, 36, 29, 32
	};

	for (int i = 1; i <= 16; ++i) {
		c[i] = ((ROL(c[i - 1], shift[i], 28) & 0xfffffffUL)); // 前 28 位
		d[i] = ((ROL(d[i - 1], shift[i], 28) & 0xfffffffUL)); // 后 28 位
		uint64_t ans = 0;
		ans |= c[i]; 
		ans <<= 28;
		ans |= d[i];
		k[i] = trans(ans, pc_2, sizeof(pc_2), 56);
 	}

	/* ******************** 迭代过程 ******************** */
	if (encrypt) // 加密或者解密,它们的密钥顺序是颠倒的
		for (int i = 1; i <= 16; ++i) {
			l[i] = r[i - 1];
			r[i] = (l[i - 1] ^ feistel(r[i - 1], k[i]));
		}
	else
		for (int i = 1; i <= 16; ++i) {
			l[i] = r[i - 1];
			r[i] = (l[i - 1] ^ feistel(r[i - 1], k[17 - i]));
		}

	/* ******************** 逆向置换 ******************** */
	const static char rev[64] = {
		40, 8, 48, 16, 56, 24, 64, 32,
		39, 7, 47, 15, 55, 23, 63, 31,
		38, 6, 46, 14, 54, 22, 62, 30,
		37, 5, 45, 13, 53, 21, 61, 29,
		36, 4, 44, 12, 52, 20, 60, 28,
		35, 3, 43, 11, 51, 19, 59, 27,
		34, 2, 42, 10, 50, 18, 58, 26,
		33, 1, 41,  9, 49, 17, 57, 25
	};

	uint64_t rev_input = 0;
	rev_input |= r[16];
	rev_input <<= 32;
	rev_input |= l[16];
	uint64_t rev_output = trans(rev_input, rev, sizeof(rev), 64);
	return rev_output;
}

/* 导出函数表 */
extern "C" __declspec(dllexport) inline
uint64_t des_encrypt(uint64_t m, uint64_t k) {
	return des(m, k, true);
}
extern "C" __declspec(dllexport) inline
uint64_t des_decrypt(uint64_t m, uint64_t k) {
	return des(m, k, false);
}

int _main() {
	/* 测试 */
	using namespace std;
	cout << "请输入要加密的数据(整数):";
	uint64_t plain; cin >> plain;
	cout << "请输入密钥(整数):";
	uint64_t key; cin >> key;

	uint64_t encrypted;
	cout << "加密结果,密文:" << (encrypted = des_encrypt(plain, key)) << endl;
	cout << endl;

	cout << "反向验证解密过程..." << endl << endl;
	cout << "密文:" << encrypted << ":" << endl;
	cout << "使用密钥 " << key << " 解密..." << endl;
	uint64_t decrypted;
	cout << "解密结果,明文:" << (decrypted = des_decrypt(encrypted, key)) << endl << endl;

	cout << (plain == decrypted ? 
		"加解密前后结果一致,DES 算法验证成功!" 
		: "加解密前后结果不一致,DES 算法验证失败!"
	) << endl;


	//des_encrypt(0x0123456789ABCDEFULL, 0x133457799BBCDFF1ULL); // == 0x85E813540F0AB405ULL
	//des_decrypt(0x85E813540F0AB405ULL, 0x133457799BBCDFF1ULL); // == 0x0123456789ABCDEFULL

	return 0;
}

RSA 加密/解密算法实现

#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
#include <boost/fusion/include/pair.hpp>
#include <boost/iostreams/stream.hpp>
#include <boost/fusion/support/pair.hpp>

using namespace boost::random;
using namespace boost::multiprecision;
using namespace std;

//#undef _DEBUG

class RSA {
private:
	static cpp_int EulerFunc(const cpp_int& p, const cpp_int& q) {
		return (p - 1) * (q - 1);
	}

	static cpp_int CalcD(const cpp_int& e, const cpp_int& euler) {
		cpp_int y = 0;
		while ((1 + euler * y) % e != 0) {
			++y;
		}
		cpp_int d = (1 + euler * y) / e;
#if _DEBUG
		cout << "方程解: " << "(" << d.convert_to<string>() << ", " << (-y).convert_to<string>() << ")" << endl << endl;
#endif
		return d;
	}

	struct extgcd_t {
		cpp_int x;
		cpp_int y;
		cpp_int gcd;
	};

	static extgcd_t ExtendedEuclidean(cpp_int a, cpp_int b) {
		struct extgcd_t eg;
		if (b == 0) {
			eg.x = 1;
			eg.y = 0;
			eg.gcd = 0;
			return eg;
		}
		cpp_int old_gcd = a, r = b;
		cpp_int old_x = 1, s = 0;
		cpp_int old_y = 0, t = 1;
		while (r != 0) { // 扩展欧几里得算法
			cpp_int q = old_gcd / r;
			cpp_int temp = old_gcd;
			old_gcd = r;
			r = temp - q * r;
			temp = old_x;
			old_x = s;
			s = temp - q * s;
			temp = old_y;
			old_y = t;
			t = temp - q * t;
		}
		eg.x = old_x;
		eg.y = old_y;
		eg.gcd = old_gcd;
		return eg;
	}

	static cpp_int FastPow(cpp_int n, cpp_int exp, cpp_int m) {
		cpp_int ans = 1;
		n = n % m;
		while (exp != 0) {
			if (exp & 1)
				ans = (ans * n) % m;
			exp >>= 1;
			n = (n * n) % m;
		}
		return ans;
	}

public:
	struct PublicKey {
		cpp_int n;
		cpp_int e;
		PublicKey(const cpp_int& n0, const cpp_int& e0) : n(n0), e(e0) {}
		PublicKey() = default;
	};

	struct PrivateKey {
		cpp_int n;
		cpp_int d;
		PrivateKey(const cpp_int& n0, const cpp_int& d0) : n(n0), d(d0) {}
		PrivateKey() = default;
	};

	static void GenerateKeys(PublicKey& puk, PrivateKey& prk) {
		mt11213b base_gen(clock());
		independent_bits_engine<mt11213b, 512, cpp_int> gen(base_gen);
		mt19937 gen_clk(clock());

		cpp_int p, q;
		while (true) {
			p = gen();
			if (miller_rabin_test(p, 25, gen_clk)) {
#if _DEBUG
				cout << "生成随机大素数 p: " << endl << p.convert_to<string>() << endl << endl;
#endif
				break;
			}
		}

		while (true) {
			q = gen();
			if (miller_rabin_test(q, 25, gen_clk)) {
#if _DEBUG
				cout << "生成随机大素数 q: " << endl << q.convert_to<string>() << endl << endl;
#endif
				break;
			}
		}

		cpp_int n = p * q;
#if _DEBUG
		cout << "计算 p * q = n: " << n.convert_to<string>() << endl << endl;
#endif

		cpp_int euler = EulerFunc(p, q);
#if _DEBUG
		cout << "计算欧拉函数 Φ(n) = " << euler.convert_to<string>() << endl << endl;
#endif

		cpp_int e = 65537; //17

		// solve { e * x + euler * y = 1 }
#if _DEBUG
		cout << "解方程 " << e.convert_to<string>() << " * x + " + euler.convert_to<string>() + " * y = 1" << endl << endl;
#endif
		auto d = CalcD(e, euler);
#if _DEBUG
		cout << "计算模反元素 d: " << d.convert_to<string>() << endl << endl;
#endif

		puk.n = n;
		puk.e = e;

		prk.n = n;
		prk.d = d;
#if _DEBUG
		cout << "生成公钥: " << "(" << n.convert_to<string>() << ", " << e.convert_to<string>() << ")" << endl << endl;
		cout << "生成私钥: " << "(" << n.convert_to<string>() << ", " << d.convert_to<string>() << ")" << endl << endl;
#endif
	}

	static cpp_int Encrypt(cpp_int m, PublicKey puk) {
		auto c = FastPow(m, puk.e, puk.n);
#if _DEBUG
		cout << "计算 (" << m << " ^ " << puk.e << ") mod " << puk.n << " = " << c << endl << endl;
#endif
		return c;
	}

	static cpp_int Decrypt(cpp_int c, PrivateKey prk) {
		auto m = FastPow(c, prk.d, prk.n);
#if _DEBUG
		cout << "计算 (" << c << " ^ " << prk.d << ") mod " << prk.n << " = " << m << endl << endl;
#endif
		return m;
	}
};


//int main() {
//	auto eg = RSA::ExtendedEuclidean(17, 3120);
//	cout << eg.gcd << " " << eg.x << " " << eg.y << endl;
//
//	return 0;
//}



int main() {
	RSA::PublicKey puk;
	RSA::PrivateKey prk;
	RSA::GenerateKeys(puk, prk);

	cout << "请输入要加密的数据(整数):";
	cpp_int m0;
	cin >> m0; cout << endl;

	cpp_int c = RSA::Encrypt(m0, puk);
	cout << "公钥加密结果,密文:" << c << endl << endl;

	cout << "反向验证解密过程..." << endl << endl;
	cout << "密文:" << c << ":" << endl << endl;
	cout << "使用私钥解密..." << endl << endl;

	cpp_int m1 = RSA::Decrypt(c, prk);
	cout << "解密结果,明文:" << m1 << endl << endl;

	cout << (m0 == m1 ?
		"加解密前后结果一致,RSA 算法验证成功!"
		: "加解密前后结果不一致,RSA 算法验证失败!"
		) << endl;

	return 0;
}
三月 24

哈夫曼树

最优二叉树 —— 哈夫曼树

路径与路径长度

  • 路径:从树中一个节点到另一个节点的分支构成这两个节点之间的路径
  • 路径长度:路径上的分支数目
  • 树的路径长度:从树根到每一个节点的路径长度之和

加权路径长度

若考虑节点的权值情况,可以拓宽路径长度的概念。节点的加权路径长度可以定义为路径长度与节点上权值的乘积

树的加权路径长度

树的加权路径长度为树中所有叶子节点的加权路径长度之和

\textit{WPL}=\sum_{k=1}^n(\omega_k \times l_k)

哈夫曼树

设有 n 个权值 ( \omega_1, \omega_2, … , \omega_n ) ,可以构造一棵有 n 个叶子节点的二叉树,其中加权路径长度 WPL 最小的二叉树称作最优二叉树哈夫曼树

例:有 4 个叶子节点 a、b、c、d ,分别带有权值 7、5、2、4 。尝试构造三颗树如下

这些树的 WPL(加权路径长度)分别是

\textit{WPL}_a=7\times2+5\times2+2\times2+4\times2=36
\textit{WPL}_b=7\times3+5\times3+2\times1+4\times2=46
\textit{WPL}_c=7\times1+5\times2+2\times3+4\times3=35

可以验证(也包括其他情况),\textit{WPL}_c 最小,树 c 即是哈夫曼树

应用:最佳判定算法

例如,编制一个将百分制转换为五级分制的程序,一般做法如下

if (score < 60) level = "bad";
else if (score < 70) level = "pass";
    else if (score < 80) level = "general";
        else if (score < 90) level = "good";
            else level = "excellent";

实际生活中,学生的成绩在 5 个等级上的分布是不均匀的

可以看出,80% 的概率需要进行 3 次以及 3 次以上的比较才能得出结果,所以此程序在概率上可以进行优化

可以使用 \text{5, 15, 40, 30, 10} 为权值构造一棵有 5 个叶子节点的哈夫曼树

哈夫曼算法:构造哈夫曼树

  1. 根据给定的 n 个权值 \{ \omega_1, \omega_2, … , \omega_n \} 构成 n 棵二叉树的集合 F = \{ T_1, T_2, … , T_n \} ,其中每棵二叉树 T_i 中只有一个带权的为 \omega_i 的根节点(左右子树皆为空)
  2. F选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树,置新的二叉树的根节点的权值为其左右子树上跟节点的权值之和
  3. F删除这两棵树,并将合成得到的二叉树加入集合 F
  4. 重复第 2、3 步,直到 F 只含一棵树为止,此树即是哈夫曼树

上面的例子构造哈夫曼树的具体过程如下

五月 29

三种排序算法演示

 1 #include 
 2 #include 
 3 
 4 void PopupSort(int *s, int length) 
 5 {
 6     int i, j, swap;
 7 
 8     for(i = 0; i < length - 1; i++)
 9     {
10         for(j = 0; j < 9 - i; j++)
11         {
12             if(s[j] > s[j + 1])
13             {
14                 swap = s[j];
15                 s[j] = s[j + 1];
16                 s[j + 1] = swap;
17             }
18         }
19     }
20 }
21 
22 void SelectionSort(int *s, int length)
23 {
24     int i, j, min, min_index;
25 
26     for(i = 0; i < length - 1; i++)
27     {
28         min = s[i];
29         min_index = i;
30 
31         for(j = i + 1; j < length; j++)
32         {
33             if(min > s[j])
34             {
35                 min = s[j];
36                 min_index = j;
37             }
38         }
39 
40         s[min_index] = s[i];
41         s[i] = min;
42     }
43 }
44 
45 void InsertSort(int *s, int length)
46 {
47     int i, j, k, insert, temp;
48 
49     for(i = 1; i < length; i++)
50     {
51         for(j = 0; j < i; j++)
52         {
53             if(s[j] > s[i])
54             {
55                 insert = s[i];
56                 for(k = i; k >= j + 1; k--)
57                 {
58                     s[k] = s[k - 1];
59                 }
60                 s[j] = insert;
61             }
62         }
63     }
64 }
65 
66 
67 int main()
68 {
69     int s1[] = {7, 9, 8, 6, 4, 5, 2, 3, 1};
70     PopupSort(s1, sizeof(s1) / sizeof(s1[0]));
71 
72     int s2[] = {7, 9, 8, 6, 4, 5, 2, 3, 1};
73     
74     SelectionSort(s2, sizeof(s2) / sizeof(s2[0]));
75 
76     int s3[] = {7, 9, 8, 6, 4, 5, 2, 3, 1};
77     InsertSort(s3, sizeof(s3) / sizeof(s3[0]));
78 
79     system("pause");
80     return 0;
81 }