# 前言
密码学，一向被人们认为门槛很高，特别高端...这也是实际，但是这决不意味着普通人无法了解它的精髓，对于喜欢画圆的人来讲，即便是理解了密码技术背后的哪怕一点理论，也是激动人心的。
# 规则的抽象
我们小学的时候学习过四则混合运算，后来又将运算的作用范围扩大到了整个实数集 合，再后来又引入了虚数...实际上，这些都不重要，关键点在于运算法则本身。给定一个集合，如果集合内的任意元素在进行四则混合运算(要满足交换率，结 合率...)后的结果仍然在该集合内，如果该集合又是一个有限的集合，那么该集合就可以作为计算机上密码学使用的那个有限的框框。
如何来生成一个有限的集合，方法很多，最显而易见的就是“取模”，即对一个数字做除法然后取余数，比如如果我们将所有的正整数集合内的任意数字对数字5取 模，那么结果无非也就0，1，2，3，4这5个数，不管怎么样结果也跑不出这5个数，就算你用1000和1234相加，结果2234除以5所得的余数4， 也在这个范围内，这就是一个有限的集合，即我们说的那个有限的框框，计算机在这个集合里面做运算刚刚好，对于上一节所举的这个大数而言，任意正整数对它取 模便可以形成一个很大的集合，而计算机密码学的很多运算就是在这类集合内运转的。
到此为止，我们已经知道如何生成一个有限的集合来方便计算机进行任意的运算，但是光这还不够，因为我们仅仅定义了一些运算法则以及一个有限的集合，单位元 我们还没有，对于单位元而言，它可以作为集合内任意元素之间的媒介，事实上它是一个衡量的尺度，比如对于整数加法，单位元就是0，任何一个数字和0相加结 果都是它本身，通过单位元0还可以找到任意一个整数的相反数，与其相加的结果就是单位元，对于乘法而言也类似，乘法的单位元是1，而对应加法相反数的概念 则是倒数，不管是加法的相反数，还是乘法的倒数，都可以被称作逆元。那么对于取模的结果生成的集合内，有没有单位元呢？在回答这个问题之前，必须要声明的 一点就是：对于集合内的任意一个元素，都必须拥有逆元，这样整个集合才可能是闭合的，否则一旦让一个没有逆元的元素参与运算，结果将是不可预知的(跑飞 了...)。理解了这一点之后，我们就可以瞬间理解“为什么在密码学中素数这么重要”，“为什么循环群一定要有生成元”等问题。
# 为什么一定要素数
在密码学中，特别是公钥密钥学中，我们经常要面对生成一个大素数的问题，可是为什么一定要是素数呢？难道就是因为它数量比较少吗？No！难道因为它的分布不确定吗？No！那到底是为什么？
我们再来看上面那个模5的运算，集合为{0,1,2,3,4}，对于乘法，我们看看每一个元素的逆元分别是什么，显然0的逆元不存在，而 11%5=1，23%5=1，32%5=1，44%5=1，这样除了0之外，其它的元素都有逆元，而我们注意到，模数5是一个素数...那么我们 把特殊的元素0抛弃，留下{1,2,3,4}作为我们需要的有限集合，是不是可以呢？当然可以！
然而，我上面的论述有点以偏概全了，毕竟这只是一个特例。那么接下来就要证明一下这是一个普遍的结论：如果模数p为一个素数，那么对整个正整数集合取模的 结果去掉0就能生成一个乘法运算闭合的集合，该集合是个素域，集合中的元素数量是p-1(因为去掉了0。Oh yeah，这不就是朴素的欧拉函数吗？)。证明方法很简单。
假设一个集合N={1,2,3,4....p-1}，p为素数，对于其中任意一个元素a，用a去乘整个集合，得到一个新的集合N'= {1a%p,2a%p,3a%p,4a%p...(p-1)a%p}，我们只需要证明这个新的集合中的某一个元素为1即可。对于集合N而言，有 一个条件我们还没有用过，那就是p为素数！这是关键之关键！p为素数意味着集合N中所有的元素和p都是互素的，即它们没有公约数，同时这也意味着，N'中 的元素和p也是互素的(这很容易用反证法证明！)，再看，N集合和N'集合的元素数量是一致的，而N集合包含了到p为止的正整数全集，我没只需要证明N' 集合中的元素两两不相等，就可以说明N'集合也是到p为止的正整数全集，从而证明N==N'！还是反证法，假设N'即集合中有ma%p==na%p， 其中m>n，设m=rp+x1，n=sp+x2，则x1%p==x2%p，x1和x2均是小于p的数，可以证明m和n模p同余，由于m和n都小 于p，因此m==n，和假设不符。因此N==N'。
这能说明什么呢？这说明集合N'中包含数字1，也就是说对于任何一个N中的元素a，在集合N中均拥有一个元素和其乘积模p等于1，这就说明集合N中的每一 个元素的逆元都是存在的。这就是模数为素数的重要性质！那么，相反地，如果模数不为素数又如何呢？举一个反例即可，如果模数p=ab，即它的因数是 a，b，并且a和b均小于p，那么集合N={1,2,3,4...p-1}中的a和b将不存在逆元，因为它们除模数p的余数始终为0，而不是单位元1！
显然，模数为素数的重要性质就是可以将集合框在一个范围内，在此范围内，四则混合运算照常如旧，乘法单位元1存在！这是模运算的恩惠，也许是上帝的恩惠， 数学如此之美！想想看，在实数范围内的四则混合运算与单位元，在素数模运算中，竟然如此一致，这就是抽象代数，实际上，抽象代数不是被发明的，而是被发现 的！
# 乘法逆元-大数分解
在理解了基本理论后，我们来看一下逆元为何如此重要，简单的说，求逆元在算法上是一个规范性的操作， 比如使用辗转相除法等，然而对于模数p未知的情况下，却是一个在计算上不可能的问题。至于为什么不可能，请不要按照学子们的理论来考究，而要用收益/代价 均衡的理论来考虑。比如你破解一个算法花了30年，有意义吗？在学术环境下是有意义的，那好吧，如果你能把算法强度提高到破解它需要付出300年的时间， 你就可以拿到大奖了。
求逆元是一个甚是简便的做法，可以说是一个协议，试想，加密解密双方在没有任何交互的前提下，怎么知道如何操作。那么运算集中的操作就是协议了，比如就是 求逆元。那么安全性在哪体现？给你两堆沙子，你将它们混合在了一起，然后你能再将它们区分出来吗？这就是大数分解问题的隐喻，这就是有限集合模运算算法安 全性的保障！
素数模数界定了一个有限的集合，提供了可计算性，大数分解提供了计算的单向性。
现在我们步入RSA算法，这是一种常规的非对称密钥算法。首先选择两个比较大的素数p和q，然后计算n=pq，接下来需要界定一个集合，该集合内全部都 是和n互素的数，显然n不是素数，这就意味着必须在集合N={1,2,3,4...n-1}中抛弃和n不互素的数字。那么剩下的集合N'中还剩下多少元素 呢？在进一步讨论之前，我先讲一下前提。
上一节我论述了，如果模数p是一个素数，那么集合{1,2,3,...p-1}构成一个有限集合N，可以用作非对称密钥学计算，那么推广一下，如果p不是 素数，那么这个集合该如何界定呢？结论是，在集合N中抛弃所有和数字p不互素的数。我们假设p=mn，其中m，n均为素数，那么集合 {1,2,3,4...mn-1}中有多少和p互素的数呢？很显然，这些不和p互素的数字分为两类，一类是m的倍数，另一类是n的倍数，m的倍数在集合 中是{m,2m,3m...(n-1)m}，而n的倍数则是{n,2n,3n...(m-1)n}，因此集合{1,2,3,4...p-1}中和p互素的 集合N中数字的数量一共有(p-1)-(n-1)-(m-1)=mn-m-n+1=(m-1)(n-1)。
上述集合N中元素都有逆元吗？答案是肯定的。证明方法和素域p中的元素都有逆元的证明是一样的。首先将待求逆元的元素乘以集合N中的每一个元素并对mn 取模，得到新集合N'，证明这个集N'合和集合N是相等的，因此里面必然有元素1。证明这个只需要两点，首先证明N‘中的元素都是和mn互素的(实际上 代表了全部的和mn互素的数字组成的集合)，其次证明它们两两不相等，这就可以说明两个集合是一样的。
上面的这个结论是极其重要的，毕竟RSA算法的最开始就是要选择两个大素数p，q，然后计算n=pq，并且计算m=(p-1)(q-1)，看看m是什 么，m就是集合{1,2,3...n-1}中和n互素的集合N中数字的数量！RSA的计算将全部在集合N中进行！实际上，前几步的选取大素数p，q以及计 算(p-1)*(q-1)只是界定了一个计算的集合而已。
RSA算法在界定了集合N之后，就会在N中选取一个数字e，显然e的逆元肯定是存在的！那么计算e的逆元，结果就是私钥d！公钥就是e以及n。
n是明确的，但是你很难得到p和q，这就是算法的根本。技术实现上的关键点是，这种算法之所以可行，完全是这些算法过程是建立在一个有限的集合的基础上， 在该集合中存在单位元，满足交换率，计算闭合性。到这里为止，我并没有提到群，环，域的概念，也没有给出任何的定义，定理。但是殊途同归，一个简单的规则 抽象的设想便可以推出基本上所有的定理，定义，只是我没有说哪些是定义，哪些是定理罢了。想了解这些，随便找一本数论，抽象代数的书你就可以学到。读了这 些书的结果如何呢？结果就是你可以拿起笔写下试题的答案，然而即便这样，如果不自己从头到尾的思考，你可能仍然不知所以然，只知道某某学科有一个XX定 理，它的证法是这样的...
这个简单的设想就是在一个集合中，其所有元素乘法逆元的存在性。要存在乘法逆元，素数便登上了舞台，因为我们发现，如果一个集合中的元素和模数均是互素 的，那么乘法逆元就一定存在，最简单的这种集合就是所谓的素域，当然对于模数是任意值的集合而言，欧拉函数给出了集合中元素的个数。请注意，欧拉函数“只 是一种找到元素个数的方法”，而和集合的本质没有太多的关系。
依然本着乘法逆元，我们来看一下它是怎么导出在有限集合中的离散对数问题的。
# 乘法逆元-离散对数问题
我 们依然看最初的那个集合N={1,2,3,4...p-1}，其中p为素数。现在我们知道这个集合中均存在乘法逆元，计算也都是闭合的。我们随便拿出该集 合的一个元素a，用它来乘以集合N中的每一个元素并模p，得到新的集合N'={1a%p,2a%p,3a%p,4a%p...(p- 1)a%p}，我们知道其中肯定有一个元素为1，对应的该元素去掉a后就是a的逆元。好的，一切正常，现在没有完，继续用a乘以集合N'中的元素并模 p得到N''，我们知道N‘’和N是相等的，再进一步，用a去乘N‘’的每一个元素并模p得到N‘’‘，...N’‘’‘’我们可以得出，所有这些 N，N'，N''，N'''，N'''''...等都是相同的集合，因此我们就知道，a的不管多少次方模p的结果都在集合N内。
这个结论很重要，这显然又构成了一个闭合的运算集合，在该集合内，任意一个元素的任意次方模p的结果依然属于该集合，给定一个集合内的元素a以及另一个元 素b，你能算出a的多少次方模p等于b吗？这就是离散对数问题。显然，只有在模运算的情况下才绘出现如此多的有趣特性，显然，钟表上绕圈还是很好玩的。也 许你想知道离散对数问题和乘法逆元有什么关系，关系并不是那么明确，然而，一个集合中每一个元素逆元的存在则是必须的要求。如此好玩的在钟表上绕圈的规则 总结成一门学科就是数论，而密码学则是利用了数论的诸多定理和定义的学科。