【BUUCTF】Crypto_RSA（铜锁/openssl使用系列）

1、题目

在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
求解出d作为flga提交

2、解析

RSA加密过程：
1）选择素数：选择两个不同的大素数，通常记为p和q；
2）计算N：将这两个素数相乘，得到一个大整数N，即N = p * q。（N为RSA的模数）
3）计算欧拉函数φ(N)：φ(N) = (p-1) * (q-1)。（欧拉函数φ(N)表示小于N且与N互质的正整数的个数)
4）选择公钥e：选择一个与φ(N)互质的小整数e，通常选择65537（即2^16 + 1），这个值常用因为它只有两个非零位，加速了加密运算。
5）计算私钥d：(e * d) mod φ(N) = 1。（使用扩展的欧几里得算法计算e对于φ(N)的模逆d）

3、编码

#include <openssl/rsa.h>
#include <openssl/pem.h>
#include <iostream>using namespace std;int RSA_D() {// 给定的p、q和e值const char* p_str = "473398607161";const char* q_str = "4511491";const char* e_str = "17";// 将p、q和e转换为BIGNUM类型BIGNUM* p = BN_new();BIGNUM* q = BN_new();BIGNUM* e = BN_new();BN_dec2bn(&p, p_str);BN_dec2bn(&q, q_str);BN_dec2bn(&e, e_str);// 计算N = p * q 和 φ(N) = (p - 1) * (q - 1)BIGNUM* N = BN_new();BN_CTX* ctx = BN_CTX_new();BN_mul(N, p, q, ctx);BIGNUM* phi_N = BN_new();BN_sub(p, p, BN_value_one());BN_sub(q, q, BN_value_one());BN_mul(phi_N, p, q, ctx);// 计算d = e^(-1) mod φ(N)BIGNUM* d = BN_new();BN_mod_inverse(d, e, phi_N, ctx);// 显示d的十进制值char* d_str = BN_bn2dec(d);cout << "d: " << d_str << endl;// 释放资源BN_free(p);BN_free(q);BN_free(e);BN_free(N);BN_free(phi_N);BN_free(d);BN_CTX_free(ctx);return 0;
}int main() {RSA_D();return 0;
}

编译运行：

4、提交

flag{125631357777427553}