七月 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;
}


Copyright 2020. 版权所有。

发表 2020/07/04 自 阿龙 类别 "算法与数据结构

发表评论

电子邮件地址不会被公开。 必填项已用*标注