[数据结构与算法]2021-10-10

SEAL全同态加密开源库(二) 原理初探与源代码分析

2021SC@SDUSC

2021-10-10

密码学原理初探

由于全同态对理论知识的要求较高，因此，后续的每一篇博客的开头，我都会循序渐进的补充一些密码学原理，以及全同态加密的原理知识，以期温故而知新。

本篇博客，我们开一个密码学的初探。写得比较浅显，入门尚可。

密码学又分为密码编码学（Cryptography）和密码分析学（Cryptanalysis）。

在密码学中，一个密码体制或密码系统是指由明文、密文、密钥、加密算法和解密算法所组成的五元组。

明文是指未经过任何变换处理的原始消息，通常用m(message)或p( plaintext)表示。所有可能的明文有限集组成明文空间,通常用M或P表示。

密文是指明文加密后的消息，通常用c(ciphertext)表示。所有可能的密文有限集组成密文空间.通常用C表示。

密钥是指进行加密或解密操作所需的秘密/公开参数或关键信息,通常用k(key)表示。所有可能的密钥有限集组成密钥空间，通常用K表示。

加密算法是指在密钥的作用下将明文消息从明文空间映射到密文空间的一种变换方法,该变换过程称为加密,通常用字母E表示，即c= EK(m)。

解密算法是指在密钥的作用下将密文消息从密文空间映射到明文空间的一种变换方法，该变换过程称为解密,通常用字母D表示。

用下面这张图可以清晰的概括：

密码按照体制分类，分为非对称密码（公钥密码），对称密码（私钥密码），

其他内容详见参考文章，继续写下去有水字数之嫌疑。

明文存储简介

按照组内分工，本篇博客我将重点分析seal/native/src/plaintext.h(& .cpp)，也即源代码目录下的明文存储模块，其中又以头文件为主。

先介绍一下所谓的明文存储。下面引自官方文档：

plaintext是用于存储纯文本元素的类。 明文数据是一个多项式，其系数以明文模数为模。 明文多项式的次数必须比多项式模的次数小1。 支持数组始终为多项式的每个系数分配一个 64 位字。

Class to store a plaintext element. The data for the plaintext is a polynomial with coefficients modulo the plaintext modulus. The degree of the plaintext polynomial must be one less than the degree of the polynomial modulus. The backing array always allocates one 64-bit word per each coefficient of the polynomial.

前文也刚好介绍了明文，这里不再赘述。总之该类的功能就是简单的四个字，存储明文。

源代码分析

首先是一堆构造函数。

默认构造函数如下：

Plaintext(MemoryPoolHandle pool = MemoryManager::GetPool()) : data_(std::move(pool))
{	}

构造一个不分配内存的空明文。 pool 指向有效内存池的 MemoryPool，如果池未初始化，抛出std::invalid_argument错误。

然后参数里可以含有count参数：

explicit Plaintext(std::size_t coeff_count, MemoryPoolHandle pool = MemoryManager::GetPool())
            : coeff_count_(coeff_count), data_(coeff_count_, std::move(pool))
        {}

补充：explicit：explicit的作用是表明该构造函数是显示的，而非隐式的，跟它相对应的另一个关键字是implicit，意思是隐藏的，类构造函数默认情况下即声明为implicit。

构造一个表示常数多项式 0 的明文。将多项式的系数计数设置为给定值。 容量设置为相同的值。

参数@param[in] coeff_count：明文多项式中（归零）系数的数量。

下面这个构造函数同理：

explicit Plaintext(
            std::size_t capacity, std::size_t coeff_count, MemoryPoolHandle pool = MemoryManager::GetPool())
            : coeff_count_(coeff_count), data_(capacity, coeff_count_, std::move(pool))
        {}

构造表示常数多项式 0 的明文。多项式的系数计数和容量设置为给定值。

多了一个参数，@param[in] capacity ：表示容量。

后面给了一个#ifdef的编译判定，当然构造函数其实作用大同小异：

#ifdef SEAL_USE_MSGSL
        explicit Plaintext(
            gsl::span<const pt_coeff_type> coeffs, std::size_t capacity,
            MemoryPoolHandle pool = MemoryManager::GetPool())
            : coeff_count_(coeffs.size()), data_(coeffs, capacity, std::move(pool))
        {}

        explicit Plaintext(gsl::span<const pt_coeff_type> coeffs, MemoryPoolHandle pool = MemoryManager::GetPool())
            : coeff_count_(coeffs.size()), data_(coeffs, std::move(pool))
        {}
#endif

下面是压轴的构造器：

Plaintext(const std::string &hex_poly, MemoryPoolHandle pool = MemoryManager::GetPool())
            : data_(std::move(pool))
        {
            operator=(hex_poly);
        }

从描述明文多项式的给定十六进制字符串构造明文。

多项式的字符串描述必须遵循to_string()返回的格式，格式为“7FFx^3 + 1x^1 + 3”，总结如下规则：

       1. 术语按指数严格递减的顺序列出
       2. 数值为非负且为十六进制格式（支持大小写字母）
       3. 指数为正数且为十进制格式
       4. 系数项（包括常数项）可以（但不是必须）省略
       5. 指数值为1的项必须准确地写成x^1
       6. 数值为零的项（常数项）必须写成一个没有指数的十六进制数
       7. 术语必须用 <space>+<space> 分隔，不允许使用减号
       8. 除了 + 之外，没有其他术语应该有空格

    @param[in] hex_poly 指定明文的格式化多项式字符串多项式

最后是几个复制构造函数：

        Plaintext(const Plaintext &copy) = default;

        Plaintext(Plaintext &&source) = default;

        Plaintext(const Plaintext &copy, MemoryPoolHandle pool) : Plaintext(std::move(pool))
        {
            *this = copy;
        }

前两个都是复制构造函数，作用是创建新的明文，但是使用的方式不同。一个是通过直接复制的方式产生新的明文，另一个是通过移动原有明文的方式产生新的明文。第三个也是属于复制构造函数，不过该函数指定了复制之后的位置，也就是参数pool生成的密文空间中。