密码学 - RSA签名算法

实验九 RSA签名算法-

一、实验目的

通过实验掌握GMP开源软件的用法，理解RSA数字签名算法，学会RSA数字签名算法程序设计，提高一般数字签名算法的设计能力。

二、实验要求

(1)基于GMP开源软件，实现RSA签名算法。

(2)要求有对应的程序调试记录和验证记录。

三、实验内容

1.密钥生成算法

这一步骤将为每个用户生成公钥和相应私钥，执行如下操作:

(1) 产生两个不同的大素数p和q。

(2)计算n=pq和φ=(p-1)(q-1)。

(3)选择一个随机数e(1<e<q),满足ged(e,p)=1。

(4)使用扩展欧几里得算法计算d(1<d<q)使得ed = l(modp)。

(5)那么用户得公钥为(n,e),私钥为d。

2.签名生成算法

假设用户A对消息m∈M签名，执行操作如下:

(1)存在一个函数R(* ),将消息m映射为范围[0,n-1]的一个数m，即m=R(m)。

(2)计算s=m“modn。

(3)A对消息m的签名为s。

(4)恢复消息m=R~'(m)。

四、算法实现：

RSA签名算法可以分为三个部分:生成密钥、签名和解签名。关键函数

生成满足gcd(e,p)=1的随机数e(1<e<φ):实现该功能的函数为void e_ gen(mpz_ _t e, mpz_ t fn),第一个参数e为函数的输出。函数过程为:设立flag=1,然后在while循环内部，使用void random_ num(mpz_ .t ran_num, mpz_ t m, mpz_ .t n)函数产生在[2, φ-1]的随机数字e，接着求该数字e与φ(n)的最大公约数，判断该最大公约数是否等于1。如果等于1,则flag=0, while循环结束;否则，继续做循环。循环结束即输出满足需求的随机数e(1<e<<φ)。函数的实现代码如下:

1.密钥生成算法：

#include <iostream>
#include <cmath>// 函数声明
int gcd(int a, int b);
int modInverse(int a, int m);int main() {// 步骤1: 产生两个不同的大素数p和qint p = 61; // 替换为实际生成的素数int q = 53; // 替换为实际生成的素数// 步骤2: 计算n=pq和φ=(p-1)(q-1)int n = p * q;int phi = (p - 1) * (q - 1);// 步骤3: 选择一个随机数e(1<e<φ)，满足gcd(e, φ) = 1int e = 17; // 替换为实际选择的e// 步骤4: 使用扩展欧几里得算法计算d(1<d<φ)使得(ed ≡ 1 (mod φ))int d = modInverse(e, phi);// 输出公钥和私钥std::cout << "公钥 (n, e): (" << n << ", " << e << ")" << std::endl;std::cout << "私钥 d: " << d << std::endl;return 0;
}// 辅助函数: 计算最大公约数
int gcd(int a, int b) {if (b == 0)return a;return gcd(b, a % b);
}// 辅助函数: 计算模反元素
int modInverse(int a, int m) {for (int x = 1; x < m; x++) {if ((a * x) % m == 1) {return x;}}return -1; // 如果不存在模反元素
}

2.签名生成算法

#include <iostream>
#include <cmath>// 函数声明
int modPow(int base, int exponent, int modulus);int main() {// 用户A对消息m签名int m = 42; // 替换为实际的消息// 步骤1: 将消息m映射为范围[0, n-1]的数int n = 3233; // 替换为实际的nm = m % n;// 步骤2: 计算s = m^e mod nint e = 17; // 替换为实际的eint s = modPow(m, e, n);// 步骤3: A对消息m的签名为sstd::cout << "用户A对消息m的签名为: " << s << std::endl;return 0;
}// 辅助函数: 计算模幂运算
int modPow(int base, int exponent, int modulus) {int result = 1;base = base % modulus;while (exponent > 0) {if (exponent % 2 == 1)result = (result * base) % modulus;exponent = exponent >> 1;base = (base * base) % modulus;}return result;
}