信息安全之公钥密码体制
🌊 作者主页:海拥
🌊 简介:🏆CSDN全栈领域优质创作者、🥇HDZ核心组成员、🥈蝉联C站周榜前十
🌊 粉丝福利:粉丝群 每周送6~9本书,不定期送各种小礼品,往期获奖公布
@TOC
同余
设整数a,b,n(n ≠0),如果a-b是n的整数倍,则a≡b(mod n),即a同余于b模n。也可理解为a/n的余数等于b/n的余数。
(mod n)运算将所有的整数(无论小于n还是大于n),都映射到{0,1,…,n-1}组成的集合。
模算术的性质:
(a mod n) + (b mod n) = (a+b) mod n
(a mod n) - (b mod n) = (a-b) mod n
(a mod n) * (b mod n) = (a*b) mod n
性质
性质一、有整数a,b,c,n(n ≠0):
如果a≡b(mod n), b≡c(mod n) 那么a≡c(mod n) (传递性)
==证明==: 因为a≡b(mod n),b≡c(mod n),
即a=b+k1n,b=c+ k2n,
所以a=c+ k2n+k1n=c+(k1+k2)n,
即a等于c加上n的整数倍,即a≡c(mod n)。
性质二、如果a≡b(mod n), c≡d(mod n) 那么:
a+c≡b+d(mod n), a-c≡b-d(mod n), ac≡bd (mod n)
==证明==:ac≡bd (mod n) 因为a≡b(mod n), c≡d(mod n), 即a=b+k1n,c=d+k2n,
所以,ac=(b+k1n)(d+k2n)=bd+(bk2+dk1+nk1k2)n, 其中K=(bk2+dk1+nk1k2)为整数,
即:ac=bd+Kn,即:ac≡bd (mod n)。
除法
设整数a,b,c,n(n ≠0),且gcd(a, n)=1。
如果ab≡ac (mod n),那么b≡c (mod n)(消去律)
==证明==:∵ gcd(a, n)=1,∴有x和y,使ax+ny=1 两边同乘以(b-c): (b-c)(ax+ny)=b-c
即:(ab-ac)x+n(b-c)y=b-c ……① ∵ ab≡ac (mod n), 即ab=ac+k1n, ∴ab-ac
是n的倍数 同时,n(b-c)y显然也是n的倍数 所以,:(ab-ac)x+n(b-c)y也是n的倍数,假设是k2倍 则①式变为:b-c=
k2n 即b≡c (mod n) 模运算消去律基础
欧几里德算法(Euclid)
求最大公约数,辗转相除直到余数为零
对于任意非负整数a和任意正整数b,有: gcd(a,b) = gcd(b,a mod b)
求:gcd(482,1180)
保证机密性
Kae :Alice的加密秘钥
Kad: Alice的解密秘钥
Kbe: Bob的加密秘钥
Kbd :Bob的解密秘钥
保证真实性
Kad: Alice的私钥
Kae :Alice的公钥
既保证机密性又保证真实性
Kad: Alice的私钥
Kae :Alice的公钥
Kbe: Bob的公钥
Kbd :Bob的私钥
选p=7,q=17。
求n=p×q=119,φ(n)=(p-1)(q-1)=96。
取e=5,满足1<e<φ(n),且gcd(φ(n),e)=1。
确定满足d·e=1 mod 96且小于96的d,
因为77×5=385=4×96+1,所以d为77。
因此公开钥为{5,119},秘密钥为{77,119}。
设明文m=19,则由加密过程得密文为
C=195 mod 119≡2476099 mod 119=66
解密为6677mod 119=19
![](https://res.hc-cdn.com/ecology/9.3.130/v2_resources\images\global\blog-dialog.png)
华为开发者空间发布
让每位开发者拥有一台云主机
- 点赞
- 收藏
- 关注作者
评论(0)