信息安全之公钥密码体制
- 同余
- 性质
- 除法
- 欧几里德算法(Euclid)
- 保证机密性
- 保证真实性
- 既保证机密性又保证真实性
同余
设整数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
