序言

  密码一般被分为两类:古典密码现代密码。两者的区别是,后者是二十世纪后期才逐渐发展起来的。相对于古典密码,现代密码有更完整的理论体系和基础。而数学,是其中很重要的一个基础。我们在前面说过的RSA加密算法中读者就肯定有所体会了。本文的内容是为了方便理解后续要讲的AES加密算法而准备的。

  特别声明,由于笔者水平有限,本节内容若有所错误敬请指教。你可以通过文章下方的评论区提出宝贵意见。下面,我们开始。

整除性和除法

整除性

  对于整数$a,b,m$,如果有等式$a=mb$成立,那么我们说$b$整除$a$,我们还可以记作$b\mid a$。

  关于整除,我们需要给出一些性质。这些性质都是很容易证明的,请读者自证。

定理
如果$a\mid 1$,那么有$a=\pm 1$。
如果$a\mid b$并且$b\mid a$,那么$a=\pm b$。
任意非零整数都整除$0$。
如果$a\mid b$,并且$b\mid c$,那么一定有$a\mid c$。
如果$b\mid g$且$b\mid h$,那么对于任意整数有$b\mid (mg+nh)$。

除法

  对于任意给定的正整数$n$和任意的非负整数$a$,如果我们用$n$去除$a$,得到一个整数商$q$和一个整数余数$r$,它们服从关系

这样的算法我们称为除法。值得注意的是,这里的除法表示为一个定理而不是一种算法,但传统上,我们称该定理为除法。

欧几里得(Euclid)算法

最大公因数

  最大公因数的定理我们不多赘述,我们在这里只介绍一个新的二元运算符$\textrm{gcd}(a,b)$,它表示求整数$a,b$的最大公因数。特别地,我们定义$\textrm{gcd}(0,0)=0$。

  如果对于整数$a,b$有$\textrm{gcd}(a,b)=1$,那么我们称这两个数是互质的

欧几里得算法

  当我们引入一个新的运算符时,我们总希望能够解决其运算方式,对于求最大公因数运算也是如此。我们先给出欧几里得算法的结论,然后再尝试证明之。

  欧几里得算法:如果满足除法$a=nb+r$,那么我们有

  证明:我们不妨设$d=\textrm{gcd}(a,b)$。那么我们显然要先证明$d$是$r$的因子。由于$d\mid a$并且$d\mid b$,$r=a-nb$,那么我们由前面整除性的定理可以知道$d\mid (a-nb)=r$。我们设$c$是能够整除$b,r$的尽可能大的整数,那么由整除性定理可以知道$c$能够整除$a$和$b$,所以$c$是$a,b$的因子。考虑到我们假设其尽可能大,所以得出$c=\textrm{gcd}(a,b)=d$。于是,欧几里得算法证毕。

  利用这个算法层层迭代,我们可以算得两整数的最大公因数。这个算法的能力是很强的,读者可以选取足够大的整数尝试。

模运算

模数

  我们观察上一节对于除法的定义,如果满足除法,那么我们将余数$r$称为$a$模$n$的结果,$n$称为模数,即若除法$a=nb+r$,那么

  如果$(a\ \textrm{mod}\ n)=(b\ \textrm{mod}\ n)$,那么我们就称整数$a,b$是同余的。这种关系还有一种更为简便的记法即

参考文献

[1]密码编码学与网络安全:原理与实践:第5版/(美)斯托林斯(Stallings,W.)著;王张宜等译.
[2]AES加密过程详解;up:可厉害的土豆.