同余

设整数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