RSA公钥加密和数字签名实验

2023-01-29 约 3388 字预计阅读 7 分钟

SeedLab密码学RSA公钥加密和数字签名实验过程记录整理，还有待进一步补充，存疑之处欢迎指正和探讨！

实验来源：seed-labs

实验环境：SEEDUbuntu 20.04 VM

API文档：Big Number APIs

PRELIMINARY

A Complete Example of BIGNUM APIs.

In this example, we initialize three BIGNUM variables, a, b, and n; we then compute a ∗ b and ($a^b mod n$).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


/* bn_sample.c */
#include <stdio.h>
#include <openssl/bn.h>
#define NBITS 256
void printBN(char *msg, BIGNUM * a)
{
    /* Use BN_bn2hex(a) for hex string
    * Use BN_bn2dec(a) for decimal string */
    char * number_str = BN_bn2hex(a);
    printf("%s %s\n", msg, number_str);
    OPENSSL_free(number_str);
}
int main ()
{
    BN_CTX *ctx = BN_CTX_new();
    BIGNUM *a = BN_new();
    BIGNUM *b = BN_new();
    BIGNUM *n = BN_new();
    BIGNUM *res = BN_new();
    // Initialize a, b, n
    BN_generate_prime_ex(a, NBITS, 1, NULL, NULL, NULL);
    BN_dec2bn(&b, "273489463796838501848592769467194369268");
    BN_rand(n, NBITS, 0, 0);
    // res = a*b
    BN_mul(res, a, b, ctx);
    printBN("a * b = ", res);
    // res = aˆb mod n
    BN_mod_exp(res, a, b, n, ctx);
    printBN("aˆc mod n = ", res);
    return 0;
}

编译：gcc -o example1 example1.c -lcrypto

运行：./example1

Task1: Deriving the Private Key

Let p, q, and e be three prime numbers. Let n = p*q. We will use (e, n) as the public key. Please calculate the private key d. The hexadecimal values of p, q, and e are listed in the following. It should be noted that although p and q used in this task are quite large numbers, they are not large enough to be secure. We intentionally make them small for the sake of simplicity. In practice, these numbers should be at least 512 bits long (the one used here are only 128 bits).

1
2
3


p = F7E75FDC469067FFDC4E847C51F452DF
q = E85CED54AF57E53E092113E62F436F4F
e = 0D88C3

推导RSA私钥：

计算N值

pesudo random number generator => p,q => large prime number $$ N=p\times q $$
求L $$ L=lcm(p-1,q-1) $$
求E $$ 1<E<L $$

$$ gcd(E,L)=1 $$
求D $$ 1<D<L $$

$$ E\times D\mod L =1 $$

根据已给p,q,e值，利用下述c语言代码计算私钥值：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


#include <stdio.h>
#include <openssl/bn.h>

void printBN(char *msg, BIGNUM *a){//输出大数
	/*Use BN_bn2hex(a) for hex string
	 *Use BN_bn2dec(a) for decimal string*/
	char *number_str = BN_bn2hex(a);//BN => hex string
	printf("%s %s\n", msg, number_str);
	OPENSSL_free(number_str);
}

void printKEYS(char *msg, BIGNUM *a, BIGNUM *b){//输出完整公/私钥
	char *number_str1 = BN_bn2hex(a);
	char *number_str2 = BN_bn2hex(b);
	printf("%s: (%s,%s)\n", msg, number_str1, number_str2);
	OPENSSL_free(number_str1);
	OPENSSL_free(number_str2);
}

int main (){
	BN_CTX *ctx = BN_CTX_new();
	BIGNUM *p = BN_new();
	BIGNUM *q = BN_new();
	BIGNUM *n = BN_new();
	BIGNUM *e = BN_new();
	BIGNUM *d = BN_new();
	BIGNUM *l = BN_new();
	BIGNUM *p_one = BN_new();
	BIGNUM *q_one = BN_new();
  //16进制字符串转换成大数BN
	BN_hex2bn(&p, "F7E75FDC469067FFDC4E847C51F452DF");
	BN_hex2bn(&q, "E85CED54AF57E53E092113E62F436F4F");
	BN_hex2bn(&e, "0D88C3");
	BN_mul(n, p, q, ctx);//计算n，n=p*q
	printBN("n = p*q = ", n);//输出n
	BN_sub(p_one,p,BN_value_one());//计算p-1
	BN_sub(q_one,q,BN_value_one());//计算q-1
	BN_mul(l,p_one,q_one,ctx);//计算l，l=lcm(p-1,q-1)
	BN_mod_inverse(d,e,l,ctx);//计算d，e * d mod l = 1
	printBN("d = ",d);
	printKEYS("PUBLIC KEY",e,n);//输出公钥
	printKEYS("PRIVATE KEY",d,n);//输出私钥
	BN_clear_free(p);
	BN_clear_free(q);
	BN_clear_free(n);
	BN_clear_free(e);
	BN_clear_free(d);
	BN_clear_free(l);
	BN_clear_free(p_one);
	BN_clear_free(q_one);
	return 0;
}

编译运行：

d值为：3587A24598E5F2A21DB007D89D18CC50ABA5075BA19A33890FE7C28A9B496AEB

私钥: (3587A24598E5F2A21DB007D89D18CC50ABA5075BA19A33890FE7C28A9B496AEB,E103ABD94892E3E74AFD724BF28E78366D9676BCCC70118BD0AA1968DBB143D1)

Task 2: Encrypting a Message

Let (e, n) be the public key. Please encrypt the message “A top secret!” (the quotations are not included). We need to convert this ASCII string to a hex string, and then convert the hex string to a BIGNUM using the hex-to-bn API BN hex2bn(). The following python command can be used to convert a plain ASCII string to a hex string.

将明文转换成16进制字符串：python3 -c 'print("A top secret!".encode("utf-8").hex())'

16进制字符串：4120746f702073656372657421

使用c语言代码完成加密：

1
2
3
4


n = DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5
e = 010001 (this hex value equals to decimal 65537)
M = A top secret!
d = 74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D

加密过程： $$ ciphertext = plaintext^E \mod N $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


#include <stdio.h>
#include <openssl/bn.h>

void printBN(char *msg, BIGNUM *a){//输出大数
	/*Use BN_bn2hex(a) for hex string
	 *Use BN_bn2dec(a) for decimal string*/
	char *number_str = BN_bn2hex(a);
	printf("%s %s\n", msg, number_str);
	OPENSSL_free(number_str);
}


int main (){
	BN_CTX *ctx = BN_CTX_new();
	BIGNUM *n = BN_new();
	BIGNUM *e = BN_new();
	BIGNUM *d = BN_new();
	BIGNUM *m = BN_new();
	BIGNUM *ciphertext = BN_new();

	//BIGNUM *plaintext = BN_new();
	//16进制字符串转换成大数BN
	BN_hex2bn(&n, "DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5");
	BN_hex2bn(&e, "010001");
	BN_hex2bn(&d, "74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D");
	BN_hex2bn(&m, "4120746f702073656372657421");
	BN_mod_exp(ciphertext,m,e,n,ctx);//加密，密文=明文的e次方 mod n
	printBN("ciphertext = ",ciphertext);//输出密文

  /*
  //解密部分
	BN_mod_exp(plaintext,ciphertext,d,n,ctx);//解密，明文=密文的d次方 mod n
	printBN("plaintext =",plaintext);//输出解密出的明文
	if (!BN_cmp(m,plaintext)){//验证比较解密出的明文和原消息的一致性
		printf("Successful Verification!\n");	
	}else{
		printf("Verification Failed.\n");
	}
	*/

	BN_clear_free(n);
	BN_clear_free(e);
	BN_clear_free(d);
	BN_clear_free(m);
	BN_clear_free(ciphertext);

	//BN_clear_free(plaintext);
	return 0;
}

编译运行：

加密结果为：6FB078DA550B2650832661E14F4F8D2CFAEF475A0DF3A75CACDC5DE5CFC5FADC
利用d验证加密结果

解密过程： $$ plaintext = ciphertext^D \mod N $$ 代码为上述解密部分，编译运行结果如下：

可以发现解密出来的16进制明文字符串和原先第一步中所转换的是一致的，即验证通过！

Task 3: Decrypting a Message

The public/private keys used in this task are the same as the ones used in Task 2. Please decrypt the following ciphertext C, and convert it back to a plain ASCII string.

1

C = 8C0F971DF2F3672B28811407E2DABBE1DA0FEBBBDFC7DCB67396567EA1E2493F

思路同任务2中解密过程，代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


#include <stdio.h>
#include <openssl/bn.h>

void printBN(char *msg, BIGNUM *a){//输出大数
	/*Use BN_bn2hex(a) for hex string
	 *Use BN_bn2dec(a) for decimal string*/
	char *number_str = BN_bn2hex(a);
	printf("%s(Hex)=%s\n", msg, number_str);
	OPENSSL_free(number_str);
}


int main (){
	BN_CTX *ctx = BN_CTX_new();
	BIGNUM *n = BN_new();
	BIGNUM *e = BN_new();
	BIGNUM *d = BN_new();
	BIGNUM *ciphertext = BN_new();
	BIGNUM *plaintext = BN_new();
  //16进制字符串转换成大数BN
	BN_hex2bn(&n, "DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5");
	BN_hex2bn(&e, "010001");
	BN_hex2bn(&d, "74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D");
	BN_hex2bn(&ciphertext, "8C0F971DF2F3672B28811407E2DABBE1DA0FEBBBDFC7DCB67396567EA1E2493F");
	BN_mod_exp(plaintext,ciphertext,d,n,ctx);//解密，明文=密文的d次方 mod n
	printBN("plaintext",plaintext);//输出解密后的明文(16进制)
	BN_clear_free(n);
	BN_clear_free(e);
	BN_clear_free(d);
	BN_clear_free(ciphertext);
	BN_clear_free(plaintext);
	return 0;
}

编译运行：

明文16进制字符串：50617373776F72642069732064656573

16进制字符串转ASCII明文字符串：python3 -c 'print(bytes.fromhex("50617373776F72642069732064656573").decode("ascii"))'

消息解密结果：Password is dees

Task 4: Signing a Message

The public/private keys used in this task are the same as the ones used in Task 2. Please generate a signature for the following message (please directly sign this message, instead of signing its hash value):

1

M = I owe you $2000.

用私钥对消息进行签名：

将消息转换成16进制字符串

利用如下代码签名：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


#include <stdio.h>
#include <openssl/bn.h>

void printBN(char *msg, BIGNUM *a){//输出大数
	/*Use BN_bn2hex(a) for hex string
	 *Use BN_bn2dec(a) for decimal string*/
	char *number_str = BN_bn2hex(a);
	printf("%s(Hex)=%s\n", msg, number_str);
	OPENSSL_free(number_str);
}


int main (){
	BN_CTX *ctx = BN_CTX_new();
	BIGNUM *n = BN_new();
	BIGNUM *e = BN_new();
	BIGNUM *d = BN_new();
	BIGNUM *signature = BN_new();
	BIGNUM *plaintext = BN_new();
  //16进制字符串转换成大数BN，Initialize BN
	BN_hex2bn(&n, "DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5");
	BN_hex2bn(&e, "010001");
	BN_hex2bn(&d, "74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D");
	BN_hex2bn(&plaintext, "49206f776520796f752024323030302e");
	BN_mod_exp(signature,plaintext,d,n,ctx);//签名，用私钥对消息进行加密，signature=plaintext的d次方 mod n
	printBN("signature",signature);//输出数字签名
	BN_clear_free(n);
	BN_clear_free(e);
	BN_clear_free(d);
	BN_clear_free(signature);
	BN_clear_free(plaintext);
	return 0;
}

编译运行

该消息的数字签名为：55A4E7F17F04CCFE2766E1EB32ADDBA890BBE92A6FBE2D785ED6E73CCB35E4CB
修改消息，$2000 => $3000，重新重复上述步骤进行签名，结果如下：

该消息的数字签名为：BCC20FB7568E5D48E434C387C06A6025E90D29D848AF9C3EBAC0135D99305822

比较2个数字签名可以发现：虽然只对消息做了slight change且密钥对相同，但是签名出来的结果(密文)是完全不一样的！

Task 5: Verifying a Signature

Bob receives a message M = “Launch a missile.” from Alice, with her signature S. We know that Alice’s public key is (e, n). Please verify whether the signature is indeed Alice’s or not. The public key and signature (hexadecimal) are listed in the following:

1
2
3
4


M = Launch a missile.
S = 643D6F34902D9C7EC90CB0B2BCA36C47FA37165C0005CAB026C0542CBDB6802F
e = 010001 (this hex value equals to decimal 65537)
n = AE1CD4DC432798D933779FBD46C6E1247F0CF1233595113AA51B450F18116115

将消息转换成16进制字符串

利用如下C代码进行签名验证，公钥验证：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


#include <stdio.h>
#include <openssl/bn.h>

void printBN(char *msg, BIGNUM *a){//输出大数
	/*Use BN_bn2hex(a) for hex string
	 *Use BN_bn2dec(a) for decimal string*/
	char *number_str = BN_bn2hex(a);
	printf("%s(Hex)=%s\n", msg, number_str);
	OPENSSL_free(number_str);
}


int main (){
	BN_CTX *ctx = BN_CTX_new();
	BIGNUM *n = BN_new();
	BIGNUM *e = BN_new();
	BIGNUM *m = BN_new();
	BIGNUM *signature = BN_new();
	BIGNUM *verification = BN_new();
  //16进制字符串转换成大数BN，Initialize BN
	BN_hex2bn(&n, "AE1CD4DC432798D933779FBD46C6E1247F0CF1233595113AA51B450F18116115");
	BN_hex2bn(&e, "010001");
	BN_hex2bn(&m, "4c61756e63682061206d697373696c652e");
	BN_hex2bn(&signature, "643D6F34902D9C7EC90CB0B2BCA36C47FA37165C0005CAB026C0542CBDB6802F");

	BN_mod_exp(verification,signature,e,n,ctx);//验证签名，用公钥验证(解密)签名，verification=signature的e次方 mod n
	printBN("verification",verification);//输出验证后的消息verification
	//验证签名的正确性
	if(!BN_cmp(m,verification)){//比较verification和直接发送的消息m，如果两者一致则签名验证成功
		printf("Successful Verification!\n");
	}else{
		printf("Verification Failed.\n");
	}

	BN_clear_free(n);
	BN_clear_free(e);
	BN_clear_free(m);
	BN_clear_free(signature);
	BN_clear_free(verification);
	return 0;
}

编译运行：

通过公钥验证(解密)签名和直接发送的消息M进行比较可以发现二者是一致的，签名验证成功！

Suppose that the signature above is corrupted, such that the last byte of the signature changes from 2F to 3F, i.e, there is only one bit of change. Please repeat this task, and describe what will happen to the verification process.

代码在signature处略作修改重复上述过程，验证签名：

可以发现签名仅发生了一个bit的改变，签名的验证则不会通过，公钥验证出来的结果和正确结果是天差地别的，一致性不满足，不是正确的签名。