SEAL全同态加密开源库(六) 整数运算numth源码解析
2021SC@SDUSC
2021-11-07
前言
这是SEAL开源库代码分析报告第五篇，本篇将首先照例引入一些理论知识，然后本篇将开始分析整数运算部分，numth.cpp的源代码。关于其重要性，在公钥和密钥的生成、明文加密以及密文解密过程中，都需要整数的运算。
举个陈智罡教授博客中的例子，假设已知明文为m，通过加密算法得到m+2r+pq，想要对其解密就需要先通过模p运算把pq消去，模2运算把2r消去，最后剩下明文m。因此整数运算这一部分，有仔细分析的必要。
理论知识补充
推荐一篇很好的初学者入门博客，陈志罡教授写的：科学网—整数上全同态加密方案分析（1）–献给全同态加密的初学者 – 陈智罡的博文 (sciencenet.cn)
本期的理论知识补充，我们介绍整数上的全同态加密。
Enc(m): m+2r+pq
Dec©: (c mod p) mod 2=（c – p*「c/p」）mod 2 = Lsb© XOR Lsb(「c/p」)
上面这个加密方案显然是正确的，模p运算把pq消去，模2运算把2r消去，最后剩下明文m 。这个公式看上去很简单，但是却很耐看，需要多看看。
公式中的p是一个正的奇数，q是一个大的正整数（没有要求是奇数，它比p要大的多），p 和q在密钥生成阶段确定，p看成是密钥。而r是加密时随机选择的一个小的整数（可以为负数）。明文m∈ {0,1}，是对“位”进行加密的，所得密文是整数。
上面方案的明文空间是{0,1}，密文空间是整数集。
全同态加密方案中除了加密、解密还有一个非常重要的算法就是：Evaluate，它的作用就是对于给定的功能函数f以及密文c1,c2,…,ct等做运算f (c1,c2,…,ct)。在这里就是对密文做相应的整数加、减、乘运算。
以上方案可以看成是对称加密方案。下面来考虑公钥加密方案。其实把pq看成公钥就OK。由于q是公开的，所以如果把pq看成公钥，私钥p立刻就被知道了（p=pq/q）。怎么办呢？看上面加密算法中，当对明文0进行加密时，密文为2r+pq, 所以我们可以做一个集合{xi；xi=2ri+pqi}，公钥pk就是这个集合{xi}，加密时随机的从{xi}中选取一个子集S，按如下公式进行加密：
Enc(m): m+2r+sum(S); 其中sum(S)表示对S中的xi进行求和。
由于sum(S)是一些0的加密密文之和，所以对解密并不影响，整个解密过程不变。
这个方案是安全的，就是我们所说的DGHV方案。
numth.cpp源码分析
numth.h文件的解析，详见刘云聪同学的博客。按照分工，我主要负责分析numth.cpp文件。
先是函数conjugate_classes，是通过模数和子群生成器得到群的共轭类。
头文件声明如下：
SEAL_NODISCARD std::vector conjugate_classes( std::uint64_t modulus, std::uint64_t subgroup_generator);先介绍一下如何通过模数和子群生成器得到共轭类：
首先对于共轭类进行了初始化，将与模数互为质数的值放入共轭类:
vector classes{};for (uint64_t i = 0; i 1) {classes.push_back(0); } else { classes.push_back(i); }}然后开始迭代更新共轭类中的数值。先判断该位置是否为零，如果为零，说明该位置和模数不互为质数，直接continue。然后判断共轭类第i个位置的值是否为i，如果不是，说明i不是一个支点。剩下的可能性,就是i是一个支点，然后通过子群生成器和模数构建一个j，以i为支点迭代j对应位置的值。最后返回共轭类。
for (uint64_t i = 0; i < modulus; i++) { if (classes[static_cast(i)] == 0) { continue; } if (classes[static_cast(i)] < i) { // 如果i不是一个支点，更新它的支点 classes[static_cast(i)] = classes[static_cast(classes[static_cast(i)])]; continue; } // 如果 i 是一个支点，更新其他支点以指向它 uint64_t j = (i * subgroup_generator) % modulus; while (classes[static_cast(j)] != i) { // Merge the equivalence classes of j and i // Note: if classes[j] != j then classes[j] will be updated later, // when we get to i = j and use the code for \"i not pivot\". classes[static_cast(classes[static_cast(j)])] = i; j = (j * subgroup_generator) % modulus; } }函数is_prime就是判断是否为素数：
首先检查最简单的情况：
代码来看就是一堆0-13的素数判定。
然后，作所谓的米勒-拉宾试验。
米勒-拉宾素性检验是一种素数判定法则，利用[随机化算法]判断一个数是[合数]还是可能是素数。
下面这个截图比较能说明其原理：
体现在代码上，就是如下的代码：
uint64_t d = value - 1; uint64_t r = 0; while (0 == (d & 0x1)) { d >>= 1; r++; } if (r == 0) { return false; } // 1) Pick a = 2, check a^(value - 1). // 2) Pick a randomly from [3, value - 1], check a^(value - 1). // 3) Repeat 2) for another num_rounds - 2 times. random_device rand; uniform_int_distribution dist(3, value - 1); for (size_t i = 0; i < num_rounds; i++) { uint64_t a = i ? dist(rand) : 2; uint64_t x = exponentiate_uint_mod(a, d, modulus); if (x == 1 || x == value - 1) { continue; } uint64_t count = 0; do { x = multiply_uint_mod(x, x, modulus); count++; } while (x != value - 1 && count < r - 1); if (x != value - 1) { return false; } }后记
还剩一部分源码没有分析完毕，会在下一篇博客解决这一部分的战斗。目前的进度有些怠慢，继续努力！
