用C语言手搓一个RSA加密工具：从生成密钥到加解密的完整流程（附完整代码）

用C语言手搓一个RSA加密工具：从生成密钥到加解密的完整流程（附完整代码）

在信息安全领域，RSA算法如同一位沉默的守护者，用数学之美捍卫着数字世界的隐私。本文将带你走进这个诞生于1977年的非对称加密世界，用C语言从零构建一个完整的RSA加密工具。不同于单纯的理论讲解，我们会聚焦于工程实现细节，包括大数处理、汉字编码等实际开发中必然遇到的挑战。

1. 环境准备与基础数学

1.1 开发环境配置

推荐使用以下工具组合：

• 编译器：GCC 9.4.0或更高版本（支持C11标准）
• 调试工具：GDB配合Valgrind内存检测
• 辅助库：

  sudo apt-get install libgmp-dev # 大数运算库 sudo apt-get install libssl-dev # 加密算法参考实现

1.2 RSA核心数学原理

RSA的安全性建立在三个关键数学问题上：

注意：实际应用中素数长度应≥2048位，本文示例使用小素数仅为演示原理

2. 密钥生成实现

2.1 素数检测优化

原始代码的素数检测存在效率问题，改进方案：

#include <stdbool.h> #include <math.h> bool is_prime(int num) { if (num <= 1) return false; if (num == 2) return true; if (num % 2 == 0) return false; int sqrt_num = sqrt(num) + 1; for (int i = 3; i < sqrt_num; i += 2) { if (num % i == 0) return false; } return true; }

2.2 扩展欧几里得算法实现

高效计算模逆元是密钥生成的关键：

int extended_gcd(int a, int b, int *x, int *y) { if (b == 0) { *x = 1; *y = 0; return a; } int x1, y1; int gcd = extended_gcd(b, a % b, &x1, &y1); *x = y1; *y = x1 - (a / b) * y1; return gcd; } int mod_inverse(int e, int phi) { int x, y; int g = extended_gcd(e, phi, &x, &y); if (g != 1) return -1; // 无逆元 else return (x % phi + phi) % phi; // 保证结果为正 }

3. 加密解密核心实现

3.1 支持多字节字符处理

原始代码对汉字处理存在隐患，改进方案：

#include <wchar.h> #include <locale.h> void set_locale() { setlocale(LC_ALL, ""); } size_t get_utf8_length(const char *str) { size_t len = 0; while (*str) { len += ((*str & 0xC0) != 0x80); str++; } return len; }

3.2 快速幂模运算

加解密的核心运算需要优化：

int pow_mod(int base, int exp, int mod) { int result = 1; base = base % mod; while (exp > 0) { if (exp % 2 == 1) result = (result * base) % mod; exp = exp >> 1; base = (base * base) % mod; } return result; }

4. 完整工具链实现

4.1 命令行交互设计

构建用户友好的CLI界面：

void print_menu() { printf("\n==== RSA加密工具 ====\n"); printf("1. 生成新密钥对\n"); printf("2. 加密文本\n"); printf("3. 解密文本\n"); printf("4. 从文件加载密钥\n"); printf("5. 保存密钥到文件\n"); printf("0. 退出\n"); printf("选择操作: "); } void handle_encryption(int e, int n) { wchar_t plaintext[1024]; printf("输入要加密的文本: "); fgetws(plaintext, 1024, stdin); // 加密处理逻辑... }

4.2 文件存储格式设计

密钥存储采用PEM-like格式：

-----BEGIN RSA PRIVATE KEY----- Base64EncodedData... -----END RSA PRIVATE KEY-----

实现示例：

void save_key_to_file(const char *filename, int key, int n, bool is_private) { FILE *fp = fopen(filename, "w"); if (fp) { fprintf(fp, "-----BEGIN RSA %s KEY-----\n", is_private ? "PRIVATE" : "PUBLIC"); // 实际应用应进行Base64编码 fprintf(fp, "n=%d\nkey=%d\n", n, key); fprintf(fp, "-----END RSA %s KEY-----\n", is_private ? "PRIVATE" : "PUBLIC"); fclose(fp); } }

5. 工程化改进与边界处理

5.1 内存安全实践

原始代码存在缓冲区溢出风险，改进方案：

void safe_input(char *buffer, size_t length) { if (fgets(buffer, length, stdin)) { buffer[strcspn(buffer, "\n")] = 0; } else { buffer[0] = 0; } }

5.2 错误处理框架

建立统一的错误处理机制：

#define RSA_ERROR_MEMORY 1 #define RSA_ERROR_INVALID_INPUT 2 #define RSA_ERROR_FILE 3 void handle_error(int error_code) { const char *messages[] = { "操作成功", "内存分配失败", "输入参数无效", "文件操作失败" }; fprintf(stderr, "错误: %s\n", messages[error_code]); }

6. 性能优化技巧

6.1 预计算加速

对于固定密钥的多次操作：

typedef struct { int base; int exp; int mod; int *precomputed; // 预计算结果缓存 } FastExpContext; void init_fast_exp(FastExpContext *ctx, int base, int exp, int mod) { ctx->base = base; ctx->exp = exp; ctx->mod = mod; ctx->precomputed = malloc(sizeof(int) * (exp + 1)); // 初始化预计算值... }

6.2 多线程处理

适用于批量加密场景：

#include <pthread.h> typedef struct { int *data; int start; int end; int e; int n; } ThreadArgs; void *encrypt_thread(void *arg) { ThreadArgs *args = (ThreadArgs *)arg; for (int i = args->start; i < args->end; i++) { args->data[i] = pow_mod(args->data[i], args->e, args->n); } return NULL; }

7. 完整代码结构

最终项目应包含以下模块：

rsa_tool/ ├── include/ │ ├── rsa_math.h # 数学运算函数 │ ├── rsa_io.h # 输入输出处理 │ └── rsa_core.h # 核心算法 ├── src/ │ ├── main.c # 主程序入口 │ ├── keygen.c # 密钥生成 │ └── crypto.c # 加解密实现 ├── Makefile └── README.md

示例Makefile配置：

CC = gcc CFLAGS = -Wall -O2 -I./include LDFLAGS = -lgmp SRC = $(wildcard src/*.c) OBJ = $(SRC:.c=.o) rsa_tool: $(OBJ) $(CC) -o $@ $^ $(LDFLAGS) %.o: %.c $(CC) $(CFLAGS) -c $< -o $@ clean: rm -f src/*.o rsa_tool