桂电大二 | 从abstract algebra到kyber算法#

为什么要写这篇文章呢，因为前些天莫名其妙心血来潮去研究了一下KEM，也就是是微软现在搞得那个混合加密模式，在Hypertext Transfer Protocol Secure基础上，第二阶段的ECDHE椭圆曲线离散对数加上了后量子KEM的算法，用来协商公钥，然后顺手就往下一直深究到了抽象代数，想来有一些体会，因此来写一篇文章。

首先其实严格来说，kyber算法是基于LWE困难性问题的，abstract algebra也只能算是一个很基础的基石，但是鉴于其实核心也就是这个，无非就是加上了中心二项分布啥的一点概率论知识，核心到底还是底层数学的代数结构，没有发生其他什么变化，所以简单说明一下。

先从LWE困难性问题说起把，这个其实不难理解，无非就是在SIS纯数学基础上，加上了公私钥以及误差项e，并融合进了A和t之中（此处假设t=As+e）

那么，你可能会问，既然LWE这个直接可以用来加解密，为什么不直接拿来就用？嗯确实值得思考，其实并不是这个用不了，而是实际场景下，为了满足安全，其整体公钥参数矩阵会设置的很大，导致计算量暴增，所以实际的真实场景里面并不现实。

好，既然矩阵参数会膨胀，有没有能既保证一定的安全，计算量又不会过于庞大的数学结构呢？这里就要引入抽象代数的环结构了，具体来说是商环，在多项式环的基础上，加上了模运算的限制（此处首先用多项式环是为了做ntt多项式乘法，其次加上模运算使得整体计算结果不会特别膨胀，至于为什么不用有限域或者群结构，可以自己先想一下）

咱们不妨想，既然是一个多项式，按照我们初高中理解，是只有加减和乘法的，那么这里是如何和环结构以及模运算进行结合，从而变成商环的呢？这就要扯到逆元了，其实如果是在简单的有限整数群里面，当q作为素数的时候，每个元素都是有逆元的，这个非常的好证明，那么，当素数变成多项式，整体数学结构会发生改变吗？其实不会，此时的模数会稍微有点变化，也换成了多项式，然后会涉及多项式求逆元的操作，虽然有点吃计算能力，但是好处是，不管是进行多少次的多项式计算，最后的结果，都会因为模运算而映射在对应区间里面。

那么，既然多项式有这样的优点，当我们把传统的LWE里面的矩阵乘法，换成了多项式之后，因为模数存在本原根，并且模数可以分裂成二次因式（这个细节是我后面搜的），所以可以利用ntt加快多项式乘法的整体速度，使得可以在尽量保证安全性的同时，计算层面也不需要过多的算力去支撑。

当然，你可能会想，上述的说明基本都是在abstract algebra的领域，哪里涉及到概率论，也就是中心二项分布的知识呢？

这个其实也不难理解，作为MLWE算法核心，抽象代数是底层数学代数结构无可否认，但是在实际加上密钥加解密的过程当中，其实不管是多项式，还有私钥以及随机数r，都不能凭空生成，这就需要利用中心二项分布去做随机采样，保证具有一定的误差（此处引入随机数，目的是遮蔽消息，毕竟在实际加密过程中，不会直接用公钥去加密明文）。

那么至于实际加解密过程，也就是密钥生成（KeyGen），加密（Encrypt）以及解密（Decrypt），此处就不细说具体过程了，浏览器直接搜就可以搜得到（好吧你怎么知道其实是我懒得打字了，还要用markdown好麻烦）qwq

好吧开玩笑的，不过有一说一确实剩下的都是具体计算，基本就是一个熟练度的问题，自己手搓一遍后，再在电脑上面拿C语言跑一遍，后面印象会清晰很多。

不过实话实说，除开具体计算外，有几个问题确实值得我们去深究。

第一就是，为什么基于格密码的kyber，包括后面加上fo变换得到KEM和HPKE，一定是选择了抽象代数里面的环结构，而不是有限群呢？

这个问题其实不难回答，仔细想想会发现，对于现在仍然在使用有限群结构作为加密手段的算法来说，比如最经典的RSA，以及基于DLP的ECC来说，其在量子算法下可以被很快的分解，所以理所应当不会用这个。

第二，既然有限群用不了，那有限域为什么还是不行？

这个其实仔细想想也不难，虽然纯LWE确实是基于有限域这是事实，毕竟是在离散空间里面寻找最短向量，但是前文也已经说了，如果是在有限域中，利用矩阵乘法进行运算，其通信和存储开销，会高到现实情况难以承受，所以这个也不行，最后剩下的，也就只有基于环上的多项式运算了，并且选取模数为3329也可以保证可约，使得我们可以使用ntt加速矩阵乘法（基于CRT）

所以其实我后面琢磨了一下，kyber算法使用多项式和商环在格上进行计算，其实是无奈之举，只有这样才可以在保证安全性的同时，在工程层面，又可以投入使用，最后得到现在的混合加密模式。

差不多吧，这篇文章就能写到这里了，后面有什么需要补充的，我也会及时更新，同时文章中难免有说法不严谨的地方，也欢迎各位老师及时指出！万分感激！