青少年编程与数学 02-018 C++数据结构与算法 24课题、密码学算法

课题摘要
密码学是信息安全的重要组成部分，广泛应用于数据保护、身份验证和信息完整性等领域。

---

一、对称加密算法

对称加密算法使用相同的密钥进行加密和解密，其特点是加密速度快，适合处理大量数据。

AES（高级加密标准）

AES 是目前广泛使用的对称加密算法，支持128、192和256位密钥长度。

代码示例（C++）：

#include <iostream>
#include <openssl/aes.h>
#include <vector>std::vector<unsigned char> aes_encrypt(const std::vector<unsigned char>& key, const std::vector<unsigned char>& data) {AES_KEY enc_key;AES_set_encrypt_key(key.data(), key.size() * 8, &enc_key);std::vector<unsigned char> ciphertext(data.size());AES_encrypt(data.data(), ciphertext.data(), &enc_key);return ciphertext;
}std::vector<unsigned char> aes_decrypt(const std::vector<unsigned char>& key, const std::vector<unsigned char>& ciphertext) {AES_KEY dec_key;AES_set_decrypt_key(key.data(), key.size() * 8, &dec_key);std::vector<unsigned char> plaintext(ciphertext.size());AES_decrypt(ciphertext.data(), plaintext.data(), &dec_key);return plaintext;
}int main() {std::vector<unsigned char> key = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f};std::vector<unsigned char> data = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f};auto ciphertext = aes_encrypt(key, data);auto plaintext = aes_decrypt(key, ciphertext);std::cout << "Plaintext: ";for (auto c : plaintext) {std::cout << std::hex << (int)c << " ";}std::cout << std::endl;return 0;
}

DES（数据加密标准）

DES 是早期的对称加密算法，现已被认为不够安全，通常不再使用。

代码示例（C++）：

#include <iostream>
#include <openssl/des.h>
#include <vector>std::vector<unsigned char> des_encrypt(const std::vector<unsigned char>& key, const std::vector<unsigned char>& data) {DES_cblock key_block;std::copy(key.begin(), key.end(), key_block);DES_key_schedule schedule;DES_set_key_unchecked(&key_block, &schedule);std::vector<unsigned char> ciphertext(data.size());DES_ecb_encrypt((const_DES_cblock*)data.data(), (DES_cblock*)ciphertext.data(), &schedule, DES_ENCRYPT);return ciphertext;
}std::vector<unsigned char> des_decrypt(const std::vector<unsigned char>& key, const std::vector<unsigned char>& ciphertext) {DES_cblock key_block;std::copy(key.begin(), key.end(), key_block);DES_key_schedule schedule;DES_set_key_unchecked(&key_block, &schedule);std::vector<unsigned char> plaintext(ciphertext.size());DES_ecb_encrypt((const_DES_cblock*)ciphertext.data(), (DES_cblock*)plaintext.data(), &schedule, DES_DECRYPT);return plaintext;
}int main() {std::vector<unsigned char> key = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07};std::vector<unsigned char> data = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07};auto ciphertext = des_encrypt(key, data);auto plaintext = des_decrypt(key, ciphertext);std::cout << "Plaintext: ";for (auto c : plaintext) {std::cout << std::hex << (int)c << " ";}std::cout << std::endl;return 0;
}

3DES（三重数据加密标准）

3DES 是对DES的增强版，通过三次加密提高安全性，但速度较慢。

代码示例（C++）：

#include <iostream>
#include <openssl/des.h>
#include <vector>std::vector<unsigned char> des3_encrypt(const std::vector<unsigned char>& key, const std::vector<unsigned char>& data) {DES_cblock key_block;std::copy(key.begin(), key.end(), key_block);DES_key_schedule schedule;DES_set_key_unchecked(&key_block, &schedule);std::vector<unsigned char> ciphertext(data.size());DES_ede3_cbc_encrypt(data.data(), ciphertext.data(), data.size(), &schedule, &schedule, &schedule, (const_DES_cblock*)"\0\0\0\0\0\0\0\0", DES_ENCRYPT);return ciphertext;
}std::vector<unsigned char> des3_decrypt(const std::vector<unsigned char>& key, const std::vector<unsigned char>& ciphertext) {DES_cblock key_block;std::copy(key.begin(), key.end(), key_block);DES_key_schedule schedule;DES_set_key_unchecked(&key_block, &schedule);std::vector<unsigned char> plaintext(ciphertext.size());DES_ede3_cbc_encrypt(ciphertext.data(), plaintext.data(), ciphertext.size(), &schedule, &schedule, &schedule, (const_DES_cblock*)"\0\0\0\0\0\0\0\0", DES_DECRYPT);return plaintext;
}int main() {std::vector<unsigned char> key = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17};std::vector<unsigned char> data = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f};auto ciphertext = des3_encrypt(key, data);auto plaintext = des3_decrypt(key, ciphertext);std::cout << "Plaintext: ";for (auto c : plaintext) {std::cout << std::hex << (int)c << " ";}std::cout << std::endl;return 0;
}

二、非对称加密算法

非对称加密算法使用一对密钥：公钥和私钥。公钥用于加密，私钥用于解密。

RSA

RSA 是最常用的非对称加密算法，基于大数分解的数学难题。

代码示例（C++）：

#include <iostream>
#include <openssl/rsa.h>
#include <openssl/pem.h>
#include <openssl/err.h>
#include <vector>std::vector<unsigned char> rsa_encrypt(RSA* rsa, const std::vector<unsigned char>& data) {std::vector<unsigned char> ciphertext(RSA_size(rsa));int result = RSA_public_encrypt(data.size(), data.data(), ciphertext.data(), rsa, RSA_PKCS1_PADDING);if (result == -1) {ERR_print_errors_fp(stderr);exit(EXIT_FAILURE);}return ciphertext;
}std::vector<unsigned char> rsa_decrypt(RSA* rsa, const std::vector<unsigned char>& ciphertext) {std::vector<unsigned char> plaintext(RSA_size(rsa));int result = RSA_private_decrypt(ciphertext.size(), ciphertext.data(), plaintext.data(), rsa, RSA_PKCS1_PADDING);if (result == -1) {ERR_print_errors_fp(stderr);exit(EXIT_FAILURE);}return std::vector<unsigned char>(plaintext.begin(), plaintext.begin() + result);
}int main() {RSA* rsa = RSA_new();BIGNUM* bne = BN_new();BN_set_word(bne, RSA_F4);rsa = RSA_generate_key(2048, RSA_F4, nullptr, nullptr);std::vector<unsigned char> data = {'H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l', 'd'};auto ciphertext = rsa_encrypt(rsa, data);auto plaintext = rsa_decrypt(rsa, ciphertext);std::cout << "Plaintext: ";for (auto c : plaintext) {std::cout << c;}std::cout << std::endl;RSA_free(rsa);BN_free(bne);return 0;
}

ECC（椭圆曲线密码学）

ECC 基于椭圆曲线数学，提供相同安全级别下更小的密钥尺寸。

代码示例（C++）：

#include <iostream>
#include <openssl/ec.h>
#include <openssl/ecdsa.h>
#include <openssl/obj_mac.h>
#include <vector>std::vector<unsigned char> ecdsa_sign(EC_KEY* eckey, const std::vector<unsigned char>& data) {unsigned char* sig = nullptr;size_t sig_len = 0;ECDSA_sign(0, data.data(), data.size(), &sig, &sig_len, eckey);return std::vector<unsigned char>(sig, sig + sig_len);
}bool ecdsa_verify(EC_KEY* eckey, const std::vector<unsigned char>& data, const std::vector<unsigned char>& signature) {return ECDSA_verify(0, data.data(), data.size(), signature.data(), signature.size(), eckey) == 1;
}int main() {EC_KEY* eckey = EC_KEY_new_by_curve_name(NID_secp256k1);if (!eckey) {std::cerr << "Failed to create EC key" << std::endl;exit(EXIT_FAILURE);}if (!EC_KEY_generate_key(eckey)) {std::cerr << "Failed to generate EC key" << std::endl;exit(EXIT_FAILURE);}std::vector<unsigned char> data = {'H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l', 'd'};auto signature = ecdsa_sign(eckey, data);bool verified = ecdsa_verify(eckey, data, signature);std::cout << "Signature verified: " << (verified ? "Yes" : "No") << std::endl;EC_KEY_free(eckey);return 0;
}

三、哈希算法

哈希算法将任意长度的数据映射为固定长度的哈希值，广泛用于数据完整性验证和数字签名。

SHA-256

SHA-256 是属于SHA-2系列的哈希算法，广泛应用于区块链和数字货币。

代码示例（C++）：

#include <iostream>
#include <openssl/sha.h>
#include <iomanip>
#include <sstream>
#include <vector>std::string sha256(const std::string& data) {unsigned char hash[SHA256_DIGEST_LENGTH];SHA256_CTX sha256;SHA256_Init(&sha256);SHA256_Update(&sha256, data.c_str(), data.size());SHA256_Final(hash, &sha256);std::stringstream ss;for (int i = 0; i < SHA256_DIGEST_LENGTH; i++) {ss << std::hex << std::setw(2) << std::setfill('0') << (int)hash[i];}return ss.str();
}int main() {std::string data = "Hello, World!";std::string hash = sha256(data);std::cout << "SHA-256 Hash: " << hash << std::endl;return 0;
}

MD5

MD5 虽然使用广泛，但由于安全性问题，已不再推荐用于安全敏感的应用。

代码示例（C++）：

#include <iostream>
#include <openssl/md5.h>
#include <iomanip>
#include <sstream>
#include <vector>std::string md5(const std::string& data) {unsigned char hash[MD5_DIGEST_LENGTH];MD5_CTX md5;MD5_Init(&md5);MD5_Update(&md5, data.c_str(), data.size());MD5_Final(hash, &md5);std::stringstream ss;for (int i = 0; i < MD5_DIGEST_LENGTH; i++) {ss << std::hex << std::setw(2) << std::setfill('0') << (int)hash[i];}return ss.str();
}int main() {std::string data = "Hello, World!";std::string hash = md5(data);std::cout << "MD5 Hash: " << hash << std::endl;return 0;
}

SHA-1

SHA-1 曾经广泛使用，但由于发现安全漏洞，现已逐渐被淘汰。

代码示例（C++）：

#include <iostream>
#include <openssl/sha.h>
#include <iomanip>
#include <sstream>
#include <vector>std::string sha1(const std::string& data) {unsigned char hash[SHA_DIGEST_LENGTH];SHA_CTX sha;SHA1_Init(&sha);SHA1_Update(&sha, data.c_str(), data.size());SHA1_Final(hash, &sha);std::stringstream ss;for (int i = 0; i < SHA_DIGEST_LENGTH; i++) {ss << std::hex << std::setw(2) << std::setfill('0') << (int)hash[i];}return ss.str();
}int main() {std::string data = "Hello, World!";std::string hash = sha1(data);std::cout << "SHA-1 Hash: " << hash << std::endl;return 0;
}

四、消息认证码（MAC）

消息认证码是一种用于验证消息完整性和身份的算法，通常结合哈希算法或对称加密算法使用。

HMAC（基于哈希的消息认证码）

HMAC 结合哈希函数和密钥生成的MAC，安全性高。

代码示例（C++）：

#include <iostream>
#include <openssl/hmac.h>
#include <iomanip>
#include <sstream>
#include <vector>std::string hmac_sha256(const std::string& key, const std::string& data) {unsigned char hmac[EVP_MAX_MD_SIZE];unsigned int hmac_len;HMAC(EVP_sha256(), key.c_str(), key.size(), (unsigned char*)data.c_str(), data.size(), hmac, &hmac_len);std::stringstream ss;for (int i = 0; i < hmac_len; i++) {ss << std::hex << std::setw(2) << std::setfill('0') << (int)hmac[i];}return ss.str();
}int main() {std::string key = "secret_key";std::string data = "Hello, World!";std::string mac = hmac_sha256(key, data);std::cout << "HMAC-SHA256: " << mac << std::endl;return 0;
}

五、密钥交换算法

密钥交换算法用于在不安全的通信渠道上，帮助双方协商出一个共享的密钥，后续用于对称加密。

DH（Diffie-Hellman）

DH 基于离散对数问题的数学困难性，双方通过交换公开参数生成共享密钥。

代码示例（C++）：

#include <iostream>
#include <openssl/dh.h>
#include <openssl/bn.h>
#include <openssl/rand.h>
#include <vector>std::vector<unsigned char> dh_generate_public_key(DH* dh) {BIGNUM* priv_key = BN_new();RAND_bytes((unsigned char*)priv_key, sizeof(BIGNUM));BIGNUM* pub_key = DH_compute_key_padded(priv_key, dh);std::vector<unsigned char> public_key(BN_num_bytes(pub_key));BN_bn2bin(pub_key, public_key.data());BN_free(priv_key);BN_free(pub_key);return public_key;
}std::vector<unsigned char> dh_compute_shared_key(DH* dh, const std::vector<unsigned char>& public_key) {BIGNUM* pub_key = BN_bin2bn(public_key.data(), public_key.size(), nullptr);BIGNUM* shared_key = DH_compute_key_padded(pub_key, dh);std::vector<unsigned char> shared_key_bytes(BN_num_bytes(shared_key));BN_bn2bin(shared_key, shared_key_bytes.data());BN_free(pub_key);BN_free(shared_key);return shared_key_bytes;
}int main() {DH* dh = DH_new();BIGNUM* p = BN_new();BIGNUM* g = BN_new();BN_set_word(g, 2);BN_hex2bn(&p, "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AACAA68FFFFFFFFFFFFFFFF");DH_set0_pqg(dh, p, nullptr, g);auto public_key1 = dh_generate_public_key(dh);auto public_key2 = dh_generate_public_key(dh);auto shared_key1 = dh_compute_shared_key(dh, public_key2);auto shared_key2 = dh_compute_shared_key(dh, public_key1);std::cout << "Shared Key 1: ";for (auto c : shared_key1) {std::cout << std::hex << (int)c << " ";}std::cout << std::endl;std::cout << "Shared Key 2: ";for (auto c : shared_key2) {std::cout << std::hex << (int)c << " ";}std::cout << std::endl;DH_free(dh);BN_free(p);BN_free(g);return 0;
}

ECDH（椭圆曲线Diffie-Hellman）

ECDH 基于椭圆曲线离散对数问题（ECDLP），将DH的运算迁移到椭圆曲线群上，效率更高。

代码示例（C++）：

#include <iostream>
#include <openssl/ec.h>
#include <openssl/ecdh.h>
#include <openssl/obj_mac.h>
#include <vector>std::vector<unsigned char> ecdh_generate_public_key(EC_KEY* eckey) {EC_POINT* pub_key = EC_KEY_get0_public_key(eckey);std::vector<unsigned char> public_key(EC_POINT_point2oct(EC_KEY_get0_group(eckey), pub_key, POINT_CONVERSION_UNCOMPRESSED, nullptr, 0, nullptr));EC_POINT_point2oct(EC_KEY_get0_group(eckey), pub_key, POINT_CONVERSION_UNCOMPRESSED, public_key.data(), public_key.size(), nullptr);return public_key;
}std::vector<unsigned char> ecdh_compute_shared_key(EC_KEY* eckey, const std::vector<unsigned char>& public_key) {EC_POINT* pub_key = EC_POINT_new(EC_KEY_get0_group(eckey));EC_POINT_oct2point(EC_KEY_get0_group(eckey), pub_key, public_key.data(), public_key.size(), nullptr);BIGNUM* shared_key = EC_POINT_point2bn(EC_KEY_get0_group(eckey), pub_key, nullptr, nullptr);std::vector<unsigned char> shared_key_bytes(BN_num_bytes(shared_key));BN_bn2bin(shared_key, shared_key_bytes.data());BN_free(shared_key);EC_POINT_free(pub_key);return shared_key_bytes;
}int main() {EC_KEY* eckey1 = EC_KEY_new_by_curve_name(NID_secp256k1);EC_KEY* eckey2 = EC_KEY_new_by_curve_name(NID_secp256k1);EC_KEY_generate_key(eckey1);EC_KEY_generate_key(eckey2);auto public_key1 = ecdh_generate_public_key(eckey1);auto public_key2 = ecdh_generate_public_key(eckey2);auto shared_key1 = ecdh_compute_shared_key(eckey1, public_key2);auto shared_key2 = ecdh_compute_shared_key(eckey2, public_key1);std::cout << "Shared Key 1: ";for (auto c : shared_key1) {std::cout << std::hex << (int)c << " ";}std::cout << std::endl;std::cout << "Shared Key 2: ";for (auto c : shared_key2) {std::cout << std::hex << (int)c << " ";}std::cout << std::endl;EC_KEY_free(eckey1);EC_KEY_free(eckey2);return 0;
}

这些密码学算法在不同的场景下具有各自的优势和适用性，可以根据具体需求选择合适的算法，并注意算法的安全性和效率。