数学基础

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为gcd(a，b)，同样的，a，b，c的最大公约数记为gcd(a，b，c)，多个整数的最大公约数也有同样的记号。

如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。

几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。例如：12、16的公约数有1、2、4，其中最大的一个是4，4是12与16的最大公约数，一般记为gcd(12，16)=4

几个自然数公有的倍数，叫做这几个数的公倍数，其中最小的一个自然数，叫做这几个数的最小公倍数。例如：4的倍数有4、8、12、16，……，6的倍数有6、12、18、24，……，4和6的公倍数有12、24，……，其中最小的是12，一般记为[4，6]=12

乘法逆元：是指数学领域群G中任意一个元素a，都在G中有唯一的逆元a‘，具有性质a×a'=a'×a=e，其中e为该群的单位元。

对于整数a、n，如果存在整数b,满足ab mod n =1,则说，b是a的模n乘法逆元。

定理: a存在模n的乘法逆元的充要条件是gcd(a,n) = 1

欧几里德算法

欧几里德算法，用于求解最大公约数；扩展欧几里德算法，主要用于求解不定方程、模线性方程、模的逆元等

（1）欧几里德基本算法，用于求解最大公约数

算法原理：设 a=qb+r，其中 a，b，q，r都是整数，则gcd(a,b)=gcd(b,r)=gcd(b,a%b)

具体算法：

int gcd（int a，int b）

{

while（b != 0）

{

int temp = b;

b = a % b

a= temp;

}

return a;

}

（2）扩展欧几里德算法，主要用于求解不定方程、模线性方程、模的逆元等

算法原理：

对于不完全为0的非负数 a,b,gcd(a,b)表示a,b的最大公约数，必然存在整数对x,y，使得gcd（a,b） =ax+by

用辗转相除法求逆元

求A关于模N的逆元B，即求整数B，使得A*BmodN = 1（要求A和N互素）

（1）对余数进行辗转相除

N = A*a0+r0

A = r0*a1+r1

r0 =r1*a2+r2

r1 =r2*a3+r3

...

rn-2 = rn-1*an+rn

rn-1 = rn*an+1+0

（2）对商数ai（i =0，1...，n）逆向排列（不含余数为0的商数ai+1），并按下列方法生成bi（i =0，1...，n）

b-1 = 1

b0 = an

bi= an-i * bi-1 + bi-2

ai 的逆向排列与bi的生成过程如下

最后：

如果a0，...an为偶数个数，则bn即为所求的逆元B如果a0，...an为奇数个数，则N-bn即为所求的逆元B

举例1：求61关于模105的逆元，即61*B mod 105 = 1

（1）对余数进行辗转相除

105 = 61 * 1 +44

61 = 44 * 1 + 17

44 = 17 * 2 + 10

17 = 10 * 1 +7

10 = 7 * 1+ 3

7 = 3 * 2 + 1

3 = 1 * 3 + 0

（2）对商数逆向排列（不含余数为0的商数）

b1 = a(5-1) * b(1-1) + b(1-2) =a4 * b0 + b-1=1 *2 +1 = 3

b2 = a(5-2) * b(2-1) + b(2-2) =a3 * b1 + b0=1 *3 +2 = 5

b3= a(5-3) * b(3-1) + b(3-2) =a2 * b2 + b1=2 *5 +3 = 13

b4= a(5-4) * b(4-1) + b(4-2) =a1 * b3 + b2=1 *13 +5 = 18

b4= a(5-5) * b(5-1) + b(5-2) =a0 * b2 + b1=1 *18 +13 =31

由于a0，...an为偶数个数，因此31为61关于模105的逆元

举例2：

67 mod 119的逆元是（）

A.52 B.67 C.16 D.19

解：

67*B mod 119= 1

（(67*B）-1)/119 = 整数 （余数为0）

然后将4个选项分别带入

A:(67*52-1)/119 =29.26...

B:(67*67-1)/119 =37.71...

C:(67*16-1)/119 =9

D:(67*19-1)/119 =10.69...

所以答案为C

负数求模

加模再取模

如: -12 mod17

求模:

(-12+17) mod17=5

RSA

RSA（Rivest Shamir Adleman）是典型的非对称加密算法，该算法基于大素数分解

核心是模幂运算。

基于大合数的因子分解的困难性可用于加密可用于数字签名安全性高广泛使用RSA算法加密解密过程

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

欧拉函数φ(n)，表示小于n的正整数中，与n互素的数的个数。

φ(6)=2在小于6的正整数中，只有1和5两个数与6互素

随机地选择两个大素数（质数）p和q，使得 p ≠ q而，且保密;

计算n=pq，将n公开;

计算φ(n)=(p-1)(q-1)，对φ(n)保密;

随机地选取一个正整数e，1<e<φ(n)且gcd (e, φ(n) ) =1,将e公开; （注：gcd(e, φ(n) ) =1 表示e, φ(n)互为素数）

根据ed=1 mod φ(n)，求出d,并对d保密;

公钥:<e,n>

私钥:< >

有些教程会将私钥写成 <p,q,φ(n),d>

M为明文，C为密文

加密运算:

C=M^e mod n

解密运算:

M=C^d mod n

签名： M^d mod n

验证签名：（ M^d）^e mod n

RSA密码的安全性

1) p和q要足够大

一般应用: p和q 建议1024位(二进制数)，重要应用建议2048位

2) p和q 应为强素数

一般应用: p和q 建议1024位(二进制数)，重要应用建议2048位

(p-1)、(p+1) 、(q-1) 、(q+1) 四个数中之一只有小的素因子，n就容易分解。

3) p和q的差要大

4) (p-1)和 (q-1)的最大公因子要小

5) e的选择

随机且含1多更安全，但是计算慢。建议取e=2^16+1=65537

6) d的选择

d不能太小，要足够大

7) 不要许多用户共用一个模n，易受共模攻击

例题

例1:假设RSA密码体制中，p=3，q=11，取加密密钥e为7,

1)求解密密钥d

2)写出相应的加密算法和解密算法

3)对明文M=8加密

解：

1)n = p*q =3*11=33

φ(n) = （p-1）*（q-1） =2*10=20

ed modφ(n) = 1

7*d mod 20 = 1

d=3

2)加密算法:C = M^e mod n

解密算法: M = C^d mod n

3) C = M^e mod n = 8^7 mod 33 = 2

M = C^d mod n =2^3mod33 = 8

例2：令p=47，q=71，求RSA算法加密的公钥e和私钥d

解：

n =p*q =47*71=3337

φ(n) = （p-1）（q-1）= 46*70=3220

取一个正整数e，1<e<φ(n)且gcd (e, φ(n) ) =1

e=79 （与3220互质）

私钥d应满足 79*d =1 mod3220

对余数进行辗转相除

3220 = 79 * 40+60

79 = 60 *1 + 19

60 = 19*3 + 3

19 = 3 * 6 + 1

3 = 1 * 3 + 0

对商数逆向排列（不含余数为0的商数）

由于a0..an的个数是4 为偶数 则1019 即为所求 79关于模3220的逆元，即79*d mod 3220 = 1

d= 1019

公钥（e，n） = （79，3337），私钥（d，n）=（1019，3337）

2020年信安案例分析试题二(共20分)

读下列说明，回答问题1至问题8将解答填入答题纸的对应栏内。

[说明]密码学作为信息安全的关键技术。在信息安全领域有着广泛的应用。密码学中，根据加密和解密过程所采用密钥的特点可以将密码算法分为两类:对称密码算法和非对称密码算法。此外，密码技术还用于信息鉴别、数据完整性检验、 数字签名等，

【问题1】(3分)信息安全的基本目标包括:真实性、保密性、完整性、不可否认性、可控

性、可用性、可审查性等。密码学的三大安全目标C.I.A分别表示什么?

答：机密性(Confidentiality)，完整性(Integrity)，可用性(Availability)：

【问题2】 (3分)RSA公钥密码是一种基 于大整数因子分解难题的公开密钥密码。对于

RSA密码的参数: p，q，n，φ(n)，e，d,哪些参数是可以公开的

答:公开< n，e>

【问题3】 (2分)如有RSA密码算法的公钥为(55, 3),请给出对小王的年龄18进行加密的

密文结果?

答: n=55，则p、q分别为5和11，φ(n)= (5-1) * (11-1) =40

又因ed= 1mod 0(n)，即3d= 1mod40,得d=27

对余数进行辗转相除:

40 = 3*13+1

3 = 1*3 + 0

对商数逆向排列（不含余数为0的商数）

由于a0..an的个数是1 为奇数，则N-b0 = 40-13 =27 即为所求 3关于模40的逆元为27，即79*d mod 3220 = 1

d= 27

加密C=m^emod 55= 18^3 mod55=2

【问题4】 (2分)对于RSA密码算法的公钥(55, 3),请给出对应私钥。

答:私钥d为27

【问题5】 (2分)在RSA公钥算法中，公钥和私钥的关系是什么?

答:公钥和私钥满足:

ed=1mod φ(n)

其中:可以由私钥推出公钥，由公钥无法推出私钥。

【问题6】 (2分)在RSA密码中，消息m的取值有什么限制?

答:消息m的长度小于密钥的长度

【问题7】(3分)是否可以直接使用RSA密码进行数字签名?如果可以，请给出消息m的数字签名的方法。如果不可以，请给出原因。

答案:不能用RSA密码直接对明文进行签名。

原因: 1、直接对明文进行签名存在安全隐患。

【问题8】 (3分).上述RSA签名体制可以实现[问题1]所述的哪3个安全基本目标?

答案:保密性、完整性认证、不可否认性

快速计算a^k mod n

平方:从t0开始算，即a mod n乘:把非0对应的进行相乘，再模n

学习参考资料：

信息安全工程师教程（第二版）

建群网培信息安全工程师系列视频教程

信息安全工程师5天修炼