模运算与欧几里得算法在密码学中应用广泛

模运算与欧几里得算法解析

*仿射密码

• 模数运算
• 最大公因数（GCD）
• 欧几里得计算最大公因数的方法
• 引用资料

Affine Cipher

Affine Cipher是一种以模运算为基础的加密方法，其数学表达式为：
Y = aX + b mod m
密钥由两个参数组成，即(a, b)。

这种加密方式为何能够有效运作呢？

模运算

定义模运算符
a mod n
即为a被n整除后所剩余的数值。
引入“同余”这一概念
a ≡ b (mod n)
例如
100 ≡ 34 (mod 11)
亦可表达为
100 ≡ 1 (mod 11)
因为100除以11后余数为1

b被称作a mod n的余数，其原因在于它可以表示为：a = qn + b。
举例说明：
-12 ≡ -5 ≡ 2 ≡ 9 (mod 7)

定义Zn ={0,1，…，n-1}
若满足a+b ≡ a+c (mod n)，则可推出b ≡ c (mod n)

然而，若ab ≡ ac (mod n)，则只有在a与n互质的情况下，才能得出b ≡ c (mod n)。
举例说明：
7 x 11 ≡ 7 x 5 (mod 6)  11 ≡ 5 (mod 6)
– 9 x 3