RSA模重复平方法

2019-04-13 15:07发布

站内文章 / 模拟电子
16516 0 1494

RSA模重复平方法的理解

因课设学习在RSA中使用模重复平方算法进行加快RSA加密解密，因此写这篇博客阐述自己对模重复平方法的理解：

模重复平方法

模重复平方法是一种常用于RSA算法的计算方法，在信息安全数学中有所设计，分为迭代法与非迭代法两种实现方式。 迭代法的时间复杂度为o（n^2）,非迭代法的时间复杂度为o（n）
因为考虑到对于大数运算的实现难度与时间复杂度，此处只实现非迭代法。

模重复平方算法实现代码

void mod_exp(mpz_t result, const mpz_t exponent, const mpz_t base, const mpz_t n) { char exp[2048 + 10]; mpz_get_str(exp, 2, exponent); //把指数e转化为二进制并储存到字符数组exp中 mpz_t x, power; mpz_init(power); mpz_init_set_ui(x, 1); // x = 1 mpz_mod(power, base, n); //power = base mod n for (int i = strlen(exp) - 1; i > -1; i--) { if (exp[i] == '1') { mpz_mul(x, x, power); mpz_mod(x, x, n); //x = x * power mod n } mpz_mul(power, power, power); mpz_mod(power, power, n); //power = power^2 mod n } mpz_set(result, x); //返回结果 } 模重复平方法之所以能加快RSA的速度，是因为减少了模运算的位数，对于大数而言，增强了运算的效率。
附上我自己写的利用模重复平方法的RSA加密模式，此处调用了gmp大数库。相关gmp大数库的函数不再介绍，可以自行了解。 char *mod_Encryption(const char * plain_text, const char * key_n, int key_e)/*处理明文加密*/ { mpz_t M, res, n, e; mpz_init_set_str(M, plain_text, BASE); mpz_init_set_str(n, key_n, BASE); mpz_init_set_ui(res, 0); mpz_init_set_ui(e, key_e); mod_exp(res, e, M, n); //使用GMP中模幂计算函数 char * result = new char[KEY_LENGTH + 10]; mpz_get_str(result, BASE, res); return result; }

热门文章