高性能TCP加密通信服务器。
High performance TCP encrypted messaging server.

关键字

• Modern C++(17/20/23)
  
• 并发、异步
  
• Boost.Asio
  
• Thread-per-core+线程池
  
• Post-Quantum Cryptography

巧夺天工

• 撷之当下，收之未来——Kyber768/KEM

• 大道至简的状态机

• 阴阳相生：read_header/read_body循环往复

• Thread-per-core与线程池的共舞

• double free 之奇：data race 暗流再现

• 毫厘千里——debug密钥组合

• cascade：Coroutine-Strand-Lock“串联”之隐
  

• [ ]

阴阳相生

coroutine 的最大魅力在于优雅地让渡。

筑基：struct Msg及消息结构

read_header和read_body

堆上的“栈溢出”

你说得对，但是 coroutine 又不在栈上，怎么栈溢出

大道至简

玲珑妙妙屋之基于std::atomic<Connstate>的状态机

ConnState设计及转换

每个Connection对象都有一个private成员ConnState，表明该连接当前的所处状态。
既然在现代C++中，ConnState自然应为enum class，其定义如下：

1
2
3
4
5
6
7
8
9

enum class ConnState: uint8_t
{
    Connected,
    Handshaking,
    Established,
    Authenticated,
    Closing,
    Rekeying,
};

其中Rekeying又是一个挖了之后无限期咕的坑，玲珑传统艺能

解析：

• 新建立连接都会进入Connected状态；
  
• Client发起第一次Handshake后进入Handshaking状态；
  
• Client发起第二次Handshake后进入Established状态（因为此时会话密钥已经能被导出）；
  
• Client通过身份验证后进入Authenticated状态，亦可主动登出回到Established状态；
  
• 出现致命错误/非致命错误数达到上限，Server关闭该连接时进入Closing状态。

不同阶段的特性如下：

• Connected/Handshaking时，双方的信息都是以明文形式传输的（因为此时安全对称信道尚未建立，双方只是在进行密钥交换）。
  
• 进入Established/Authenticated后，双方信息都会加密后再封装一层进行传输，具体参见struct Msg中消息体结构的实现

明枪暗箭

明枪尚不易躲，暗箭更为难防。

异常处理的基本思路依然是C/C++的“老三样”：

• C-Style的返回值/函数引用传递错误信息；
  
• C++语言既有的异常处理模型；
  
• std::expected为代表的新秀。

TiaoMeng

普渡众生——速通std::expected

In case that someone hasn't used, or even hasn't heard of std::expected yet

std::expected是现代C++中 sum-types 的代表作之一，其是一个类模板，声明为：

1
2

template<class T, class E>
class std::expected<T, E>;

其中 T是任意 object 类型或 void ；E 是任意 object 类型。

除引用外，绝大部分变量类型和指针类型都是 object。

T

在异常消息发送上，有诸多层面的考量：

• 由于“异常”触发时，对称加密信道的建立状态不确定：Established及之后，异常信息是否应加密后发送（仍和其余消息一致，先编码为json格式，形如{"error": "Incorrect schematics"}）？
  
• 对于偶发的非致命错误（如部分 parse error、action error等）是否应设置有限的容错机制（错误次数大于某阈值后再断开连接）？如何对不同错误按其致命与否进行分类？错误计数器的重置条件如何设置？
  
• 若因出错而需断开连接，管道中剩余的消息应如何处理——继续尝试发送还是强行断开连接？若断开连接时还有错误消息，其又应如何发送？

经数轮迭代后，TiaoMeng 设置的错误处理模型如下。

上层接口：三大 helper

设置了三个 helper 函数：send_error、send_raw_error和error_close，其签名分别形如：

1
2
3
4
5
6

void send_raw_error(std::string_view err, CloseMode mode = CloseMode::Graceful);
    
[[nodiscard("Do not discard send_error's value: caller is responsible for co_return upon this function returning true to prevent connection leakage. Use std::ignore or void cast for explicit schematics.")]]
bool send_error(std::string_view err, CloseMode mode = CloseMode::Graceful, bool force_close = false);

void error_and_close(std::string_view err_text);

其中，

• send_raw_error直接发送明文错误消息（且没有json编码），同时立即关闭连接（“defaults to force close”）；

• send_error发送加密+编码后的错误消息，force_close置false时为非致命错误，此时failure_count调用其成员函数自增，同时返回bool指示其是否已经到达fail阈值，该信息通过send_error的返回值继续向上层传递。

其亦为此处放了一长串nodiscard("reason")的理由——send_error的调用者必须保证在底层 failure_count 到达上限时主动从当前函数（无论是普通函数还是coroutine）中(co_)return。
因为send_error在到达上限时会调用close(mode)，此时语义上连接已经失效，若该函数/coroutine未及时退出甚至像read_body/read_header一样还在继续打阴阳相生的太极就会导致std::shared_ptr<Connection>引用计数不归零而继续存在（Connection没有析构）。
不巧的是此时Server已经将该Connection从std::unordered_map中移除，因此其无法被继续追踪，等于发生了 Connection Leak。

若send_error的调用者能保证调用后立即(co_)return，亦可以static_cast<void>等方法显式忽略之。
但玲珑显然还是更喜欢std::ignore——其难道不值得推广咩？语义更清晰且更易读，同时其右侧操作数约束了不能为void——至少在 TiaoMeng 中实践如此：

1 2 3 4 5 6 7 8

switch(semantic) { //... case MsgSemantic::Session: std::ignore = send_error("Session management not implemented"); co_return; //... }

• error_and_close则是更高一级的接口套娃，又名“代码精简大法”，其一行lambda式的本质就是this->is_established() ? (void)send_error(err_text,CloseMode::Graceful,true) : send_raw_error(err_text, CloseMode::Graceful);

异常计数：嵌套类Connection::FailureCounter

FailureCounter只是简单包装了一个std::atomic_bool<size_t>的计数类，调用其“自增”方法可以返回其当前状态（是否需要

close逻辑：close、close_async与CloseMode

对于出错断开连接的情况，由发起方调用close函数，其将当前状态置为Closing（通过std::atomic+std::memory_order_seq_cst避免竞争），随后通过net::co_spawn调用close_async异步关闭该连接，避免关闭过程中阻塞该线程（此时该线程仍可以处理其它连接）。

close的实现：

1
2
3
4
5
6
7
8
9
10
11
12

void Connection::close(CloseMode mode)
{
    if(this->state.exchange(ConnState::Closing) == ConnState::Closing)
    {
        return;
    }
    net::co_spawn(strand,
        [self = shared_from_this(), mode]() -> net::awaitable<void>
        {
            co_await self->close_async(mode);
        }, net::detached);
}

函数中出现了新的常客CloseMode，其为一个只有两个取值的enum class反正现在是这样，原来还百花齐放来着，对应close_async中不同的处理逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

net::awaitable<void> Connection::close_async(CloseMode mode)
{
    switch (mode)
    {
    case CloseMode::Graceful:
        co_await write();
        break;

    case CloseMode::Immediate:
        shutdown();
        break;
    }
        
    server->remove_connection(id);
    co_return;
}

CloseMode::Graceful会尝试调用write，后者则会根据缓存的消息队列调用net::async_write发送消息，直至消息队列为空；CloseMode::Immediate则会立即通过清空消息队列+调用底层 socket 的部分接口函数取消+关闭连接，同时保证了其noexcept(true)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void Connection::shutdown() noexcept
{
    try
    {
        state.store(ConnState::Closing);

        boost::system::error_code ec;
        socket.cancel(ec);
        write_queue.clear();
        socket.close(ec);
    }
    catch (...)
    {
        // noexcept - swallow all exceptions
    }
}

实际上write的调用链为Connection::write->Connection::write_with_timeout->net::async_write，其中间件的解析下回分晓。

“归元”的其它原子变量

天机道藏

Kyber768: NIST-PQC

两轮KEM：Diffle-Hellman Plus

？

std::expected等 sum-types 作为现代C++组件，相较类似的、更传统的实现能实现更清晰的语义、更好的可读性与拓展性。

御守——简单而不平凡的实例

bool check_password(std::string_view password);

看似平凡的检查密码合规性函数，其在后续拓展时就经历了遭遇瓶颈-迁移至 sum-types 的过程。
具体地，最早的check_password作为一个近似于 placeholder 的存在，只要求密码长度不小于8位：

1
2
3
4

bool check_password(std::string_view password)
{
    return password.size() >= 8;
}

但随之而来的一个问题是，不同的 caller 对其调用返回 false 后的错误消息生成、处理逻辑可谓 万象霜天：

grep实录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

auth/auth_manager.cpp:    if (!auth::check_password(password))
auth/auth_manager.cpp-    {
auth/auth_manager.cpp-        co_return AuthResult{false, false};
--
auth/auth_manager.cpp:    if (!auth::check_password(password))
auth/auth_manager.cpp-    {
auth/auth_manager.cpp-        return false;
--
tools/user_admin.cpp:        if (!auth::check_password(admin_pass))
tools/user_admin.cpp-        {
tools/user_admin.cpp-            std::println(stderr, "Password too short (min 8 chars)");
--
tools/user_admin.cpp:    if (!auth::check_password(pass))
tools/user_admin.cpp-    {
tools/user_admin.cpp-        std::println(stderr, "Insufficient password length");
--
tools/user_admin_2.cpp:    if (!auth::check_password(*admin_pass))
tools/user_admin_2.cpp-    {
tools/user_admin_2.cpp-        return std::unexpected("Admin password too short (min 8 chars)");

其带来的另一个问题是，若此后希望拓展密码检查的逻辑（添加更多约束、根据约束生成TODO式的自定义信息），由于目前生成错误信息的代码被下移至调用方，其维护开销会非常大或者摆烂，留下望着不明所以错误信息而怅然若失的user。

而由于密码校验成功时不需要携带额外信息，因此std::expected<void, std::string>便成了最佳选择：

1
2

镜花水月——std::optional的夭矫空碧

std::optional

碧海归元——从智能指针看 ownership

使用std::unique_ptr等智能指针的意义不仅在于内存安全，更在于显式地明确所有权(ownership)。

回顾一下RAII原则：一个类的对象应当在其构造函数中申请对应的资源，并在析构函数中予以释放。
其中蕴含了非常重要的“所有权”逻辑：
若某资源（文件指针、堆内存等）是被某个对象 拥有(owned) 的，那么只有该对象（或共同管理该资源的同类对象）可以释放之，且这个语义应当得到强化。

经文以述难以见明，仍以具况为佳：

1

void fun(int* ptr);  

看似平平无奇的fun函数，但此处的ptr难免让人心存顾虑——fun究竟是否“拥有”ptr指向的内存？

这点与const语义仍有差分——而且即使是附加顶层const的const int*，delete ptr;一类释放内存的语句依然是合法的——但显然这不符合“语义约束”之目标。

“所有权”传递有几种方式：

• 对于独占资源，依靠移动语义（语言实现上，移动构造/移动赋值函数）转移所有权；
  
• 对于共享资源，可以直接复制所有权，但需要底层计数器的支持（以实现RAII）；
  
• 亦可仅传递一个不拥有所有权的“观察员”，其可视情况“申请”所有权。

上述三个例子在智能指针中对应的实践就分别是 unique_ptr、shared_ptr 和 weak_ptr。

unique_ptr实现明确语义的原理也非常简单，即禁用复制构造函数来实现纯移动语义，在函数中通过传值引用来约束所有权的转移：

1
2
3
4
5
6
7
8

void fun2(std::unique_ptr<int> own);  

std::unique_ptr<int> ptr;

//...

//fun2(ptr); //Not compile: std::unique_ptr<int>'s copy ctor deleted
fun2(std::move(ptr));  //OK, ownership transferred explicitly  

第二行过后，ptr管理的的指针所有权就完全交给了fun2，原函数中ptr置空，因而从语义层面同时避免了内存泄漏和 double free 的问题。

Hint：千万不要写类似于delete ptr.get()之类的语句，若确需中道override，应使用ptr.release()。
启示之一就是智能指针在兼容C样式api的时候需要考虑语义兼容的问题，注释/断点先置为佳。

而对于shared_ptr，其用处在于多个对象共享一个资源，同时保证该资源可以被正确地释放：

1
2
3
4
5
6

net::co_spawn(strand,
    [self = shared_from_this()]() -> net::awaitable<void>
    {
        co_await self->read_header();
    },
    net::detached);

除了read_header以外还有其它函数需要Connection*指针（应用此对象），同时希望所有Coroutines结束后释放掉该Connection的资源，因而选用shared_from_this（封装shared_ptr类）为上策。

而与shared_ptr相伴的还有weak_ptr，应用上其语义最大的不同在于是否 需要 “使用”其对应的资源，即是否 需要 这个所有权。

1
2

特辑：std::default_delete

此前，玲珑还未尝深入探索过智能指针第二参数的奇妙之境。

不知有多少人留意过，std::unique_ptr还有一个鲜有问津的第二（带默认值的）模板参数，参见unique_ptr的类模板声明：

1
2

template<class Ty, class Dx = std::default_delete<Ty>>
class unique_ptr;

Dx默认值是std::default_delete<Ty>，即恰如其名地Ty的默认析构函数。
若Ty不是class/struct，则该默认“析构函数”实际上为空（即free/delete时不会有任何其它行为），否则其对应其析构函数Ty::~Ty()。

尽管default_delete可以应对绝大多数智能指针的使用场景，但依然有二者被遗忘一隅：

若对于非class/struct的类型，依然希望其能依托智能指针实现类似“析构”的操作（尤其对于很多C-Style的指针等）当如何？
若希望更改其执行的析构函数（如自定义了内存池或非虚析构函数下的类继承）呢？

其实default_delete的作用机制也不复杂：
回顾C++的fundamentals，尽管筑基时学过析构函数在对象超出生命周期时被自动调用，但作为类的成员函数之一，任意场景下，其亦可如同一个普通成员函数一样被调用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class SomeClass
{
public:
    SomeClass(int x): n(x){}
    ~SomeClass()
    {
        std::print("{} ", n);
    }

private:
    int n;
};

int main()
{
    SomeClass c(10);
    c.~SomeClass(); 
}

// Compiles
// Output: 10 10 

根本原因是所谓“析构函数”只是另一个会“有条件地触发”的成员函数这也是C++中极不提倡使用goto的原因，scope乱飞警告。

虽然C++中没有类似于Python的显式thisC++23终于有了deducing this, 好耶，但从编译器实现而言，所有非静态成员函数的“隐式”第一参数本质上都是本类的引用：

1
2
3
4
5

class SomeClass
{
public:
    void fn(int x);
};

编译器生成的（仅供参考，原理相同）：

1

void SomeClass::fn(SomeClass& __this,int x);  

感兴趣者可以了解一下C++特有的调用约定 thiscall，即调用非静态成员函数时将相应对象作为第一参数传入。

这种调用方式其实也能在一些wrapper中初见端倪，比如同时适配普通函数和非静态成员函数还有lambda的std::invoke：

1
2

SomeClass obj;
std::invoke(fn, obj, 1); //Equivalent to obj.fn(1); 

后一行和obj.fn(1)是等效的。

说远了，回到析构函数的调用：
无论是栈上还是堆上的变量，无论是在其生命周期内主动调用析构函数，还是故意不调用其析构函数（比如operator new分配的内存使用free释放），这个调用析构函数的行为本身不会有任何影响。
但若析构函数体内涉及资源的释放，则可能存在 double free 的问题虽然很多带有fail-safe组件的类也不一定，比如非常友善地帮你把ptr置nullptr的std::vector：

1
2
3
4
5
6
7
8
9
10
11

SomeClass::~SomeClass()
{
    delete ptr;
}

int main()
{
    SomeClass sc;
    sc.~SomeClass();  

} //Program aborts here: double free

联立一下RAII原则的本质，其实就是某类分配的资源需要“有个函数”去清理八面玲珑，思维极为跳跃，而Dx这一模板参数即提供了一些“外部函数”执行清理任务的窗口。
unique_ptr的构造函数中有一个颇为有趣的重载：

1
2

template<class Ty,class Dx>
unique_ptr<Ty,Dx>::unique_ptr(Ty* __ptr, Dx&& __fn);  

只要requires {std::invoke(__fn, __ptr)；} 为true，这个构造函数就可以成立（即通过编译），效果就是在该unique_ptr析构时，对其管理的指针调用该函数。

默认该函数是该指针类的析构函数，此处只不过是覆写之。

抛开各种花里胡哨的demo code，直接上一个实用的用法：

1

auto ptr = std::unique_ptr<FILE, decltype(&fclose)>(fopen("a.txt", "r"), fclose);  

一行wrapper，直接实现了对FILE*这一让人又爱又恨的C Legacy得到了一个RAII wrapper。

由于默认模板参数的存在，声明变量时的两个模板参数都需要手动指定（不能直接丢一个fclose过去让它推导，因为默认参数优先级高于推导hint：可以试试重载wrapper）。

井井有条——std::atomic与std::memory_order

C++中，程序合法（通过编译不会出现UB、栈溢出/ double free /越界等现象导致abort）是一方面；程序的正确性（执行流程、结果符合预期）则是另一方面。

std::atomic只能保证对变量操作的原子性（即防止了互斥的读写操作同时执行，一般是多个写操作）。
C++中，编译器和CPU可能会将这些指令顺序进行重排，以达成执行层的优化经典pipeline，但其不保证指令顺序的语义正确（只能保证内存访问合法）。

具体地：

1
2
3
4

int x;

void thread_a() {x = 1;}
void thread_b() {x = 2;}

若thread_a和thread_b并发执行，则由于 data race 会产生包括但不限于直接abort的UB。
而若将x的声明改为

1

std::atomic<int> x;

这也只能保证程序不会出现UB，但众所周知undefined并不等于unexpected，程序的执行结果依然不确定——其是由于并发的本性所致。

那如果编写的代码“看似”可以完成顺序执行的语义呢？

1
2
3
4
5
6
7
8
9

std::atomic<int> x;

void thread_xx()
{
    if(x.load(std::memory_order_relaxed) == 1)
    {
        std::println("x = {}", x.load(std::memory_order_relaxed));  //?
    }
}

x被load了两次，但第二次load的结果就已经不一定是1了（中途可能有其它变量对其进行了修改），即由于“缓冲”的存在（实际上是由于cache/pipeline优化的指令重排所致），x在其它线程中的修改不一定立即对本线程可见，比如编译器可能会生成这样的机器代码：

1

对于另一个线程，其对x的修改可能会由于inline cache的优化而被暂存于某寄存器中，此时其对该变量的修改是（对其它线程）不透明的。

std::atomic对多数 trivial types 的特化都支持一些常用的赋值、运算操作符以供操作便利，但其本质上还是底层一些更有趣函数的wrapper。

1
2

信安数基，信安筑基。

离散数学

集合

映射

映射 \(f\) 是从 \(e_1 \in S_1\) 到 \(e_2 \in S_2\) 的一种运算，记作 \(f: S_1 \rightarrow S_2, f(e_1) = e_2\)。

映射的左值（变量）和右值（值）可以有多个，形如 \(f(x_1,x_2) = y, f(x) = \pm y\) 等。

单射、满射、双射

对于映射 \(f: A \rightarrow B, f(x) = y\)，
单射指 \(\forall x \in A, \text{有且只有一个} y \in B \text{满足} f(x) = y\)；
满射指 \(\forall y \in B, \text{有且只有一个} x \in A \text{满足} f(x) = y\)；
双射指既是单射又是满射的 \(f\)。

双射 \(f\) 具有完全且唯一的可逆性，即 \(\exists f^{-1}: B \rightarrow A\)，其性质与 \(f\) 相同。

以初等数学的方程、函数为例，“映射” \(f: Q_x \rightarrow Q_y\)：

• \(f_1: y = x^2\) 是单射（每个 \(x\) 只能对应唯一的 \(y = x^2\)）但不是满射（\(y\) 对应的 \(x\) 数目为 \(\begin{cases} 2, y > 0 \\ 1, y = 0 \\ 0, y < 0 \end{cases}\)。初等数学中，函数依定义均满足单射。
  
• \(f_2: y^2 = x\) 是满射（和 \(f_1\) 相反），依变量约定，\(f_2\) 不是 \(x\) 到 \(y\) 的函数。
  
• \(f_3: y = 2 \cdot x\) 既是满射也是双射，其逆映射为 \(f_3^{-1}: x = \frac{1}{2} y\)。

结合法

群

坐稳扶好.sage

群是近世代数(Modern Algebra)的起点。
近世代数的哲学在于抽象——其将运算等性质符号化，从更上层的角度研究不同集合的运算特征，宛若OOP语言中的较上层类的函数接口。

集合与结合法的概念较为宽泛，其共性太过有限而难以利用——迈入近世代数的山门，则是从约束更多、但也有更多共性与研究价值的“群”开始。

“移进”——从集合到群

速通流可以直接快进到“群”，但请确保充分理解封闭性、结合性、单位元（幺元）、逆元的概念。

结合法与集合、半群、广群、独异点和群是包含递进的关系，即后者一定是前者的子集，以附加条件逐级约束之。

半群

对于定义了结合法 \(\cdot\) 的集合 \(S\) ：
若该运算满足封闭性，即 \(\forall a,b \in S, a \cdot b \in S\)，则该集合成为一个半群。

实例：整数集合 \(\mathbb{Z}\) 上的加法运算 \(+\) （简记为 \((\mathbb{Z}, +)\) ）构成一个半群，但 \((\mathbb{Z},\div)\) 不构成一个半群（因为其不满足封闭性，真分数不在整数集合内）。

广群

若对于半群 \(G\)，其运算 还 满足结合性，即 \(\forall a,b \in G, (a \cdot b) \cdot c = a \cdot (b \cdot c)\)，则称之为一个广群。

实例：老生常谈的 \((\mathbb{Z},+)\) 也是一个广群。\((\mathbb{Q},\div)\) 是半群而不是广群（显然 \((a \div b) \div c \neq a \div (b \div c)\)）。

独异点（又名幺半群）

若对于广群 \(G\)，\(\exists e \in G, \forall a \in G, a \cdot e = e \cdot a = a\)，则称之为一个独异点（又名幺半群）。
其中 \(e\) 称为单位元（或幺元）。

严格地，有左/右单位元之差分：若 \(e\) 满足了 \(a \cdot e = a\)，则其为右单位元；反之则为左单位元，既是右单位元也是左单位元的元素称为单位元。

实例：\((\mathbb{Z},+)\) 是一个独异点（\(e = 0\)）；\((\mathbb{Z_{+}},+)\) 是一个广群（其满足封闭性、结合性），但不是独异点（因为其中不存在单位元）。

群

若对于独异点 \(G\)，\(\forall a \in G, \exists a^{-1} \in G\) 满足 \(a \cdot a^{-1} = e\)，则称之为一个群。
其中 \(a^{-1}\) 称为逆元。

同样 \(a^{-1}\) 理论上亦有左/右逆元之差分，其理同上。

实例：\((\mathbb{Z},+)\) 是群（任意元素的逆元是其相反数）；\((\mathbb{Q/0},\times)\)（零以外的有理数的乘法运算）是群，而 \((\mathbb{Q},\times)\) 不是（显然 \(\mathbb{0}\) 没有逆元）。

小结

集合与群是两个最为重要的数学结构之一。
群是定义了结合法，且满足封闭性、结合性、单位元、可逆性四条件的集合。

同态与同构

同态与同构研究的是两个群之间的关系，其允许我们在几种不同的数学结构之间进行转换。

同态

对 \(f: G_{1} \rightarrow G_{2}\)，若 \(\forall a,b \in A\)，\(f(a \cdot b) = f(a) \cdot f(b)\)，则称 \(f\) 是 \(G_{1}\) 到 \(G_{2}\) 的一个同态映射。

若两侧的运算是“相同”的，可称之为op同态。
如令 \(G = Z_{p} \space p \notin \{0,2\}, f: G \rightarrow G, f(x) = x \cdot 2 \bmod p\)。此时 \(\forall a,b \in Z_{p}, f(a) + f(b) = (2 \cdot a + 2 \cdot b) \equiv f(a + b) = 2 \cdot (a+b) \bmod p\)。可以发现 \(f\) 满足加法同态（即“映射”操作 \(f\) 和该群内的加法操作 \(+\) 的顺序可以任意交换，不影响结果）。

上述实例中的 \(f\) 满足 \(G_1 = G_2\)，由一个群到自身的映射也被称为自映射。有限群内，自映射的重要特点是单射、满射、双射任意一者是另外二者的充要条件。

同构

同构就是满足双射的同态 \(f\)。

子群“系”

子群

对于群 \(G\)，若群 \(H\) 满足 \(\forall a \in H \Rightarrow a \in G\)，且 \(H\) 拥有和 \(G\) 相同的结合法，则称 \(H\) 为 \(G\) 的子群，记作 \(H \subseteq G\)。
显然 \(\{e\}\) 和 \(G\) 一定是 \(G\) 的子群，它们称作 \(G\) 的平凡子群。若 \(H \neq G\)，则称之为 \(G\) 的非平凡子群。

如在普通加法下，对于 \(G = Z_{6} = \{0,1,2,3,4,5\}\) 而言，\(H = \{0,2,4\}\) 即为其子群（\(\{0,3\}\) 等显然也是）。

相同的结合法在部分场景下极为关键：如对于普通加法， \(2Z \subseteq Z\)，但 \(Z_{+} \nsubseteq Z\)，因为 \(Z_{+}\) 不是群（其没有单位元）。

子群的重要定理之一是拉格朗日定理群论版：\(H \subseteq G, |G| \neq \inf \Rightarrow |H| | |G|\)。

若 \(H \subseteq G\)，记 \([H:G] = \frac{|H|}{|G|}\)，称 \([H:G] \in Z_{+}\) 为H对G的指标。

其证明需要用到陪集的知识，后置咕一下。

陪集

设 \(H \subseteq G, a \in G\)，定义 \(aH = \{ah : h \in H\}\) 为 \(H\) 的左陪集，类似地可以定义右陪集。显然对于交换群来说左/右陪集是相同的。
依然以 \(G = Z_{6}\)，\(H = \{0,2,4\}\) 为例，可以计算 \(0H = \{0,2,4\}, 1H = \{1,3,5\}, 2H = \{0,2,4\}\) 等。

陪集的特殊性在于：

• 设 \(f: H \rightarrow aH, f(h) = ah\)，根据子群定义（相同结合法）可知 \(f\) 是一个同构映射。对于有限群 \(G\)，\(f\) 也一定是双射（群中 \(a^{-1}\) 存在，推定存在唯一的单射逆映射 \(f^{-1}: aH \rightarrow H, f^{-1}(h) = a^{-1}h\)。
  
• \(|aH| = |H|\) 成立，即所有陪集的大小都和子群 \(H\) 相同。
  
• \(\forall g \in G, g \in a_{?}H\)，即 \(G\) 中所有元素都会出现在 某个 陪集中。
  
• \(\forall a_1,a_2 \in G, a_{1}H \Join a_{2}H = \emptyset\) 或 $a_{1}H = a_{2}H $ 成立。

其中第2、3项由 \(f\) 双射的性质可导出。第4项

依然以上述的 \(H\), \(G\) 为例：
\(H = \{0,2,4\}, 1H = \{1,3,5\}\)，显然有 \(|1H| = |0H| = |H|\)。
同时 \(\forall g \in G\)，\(g \in a_{?}H\)，具体地，\(g \in \begin{cases} 0H, g \equiv 0 \bmod 2 \\ 1H, g \equiv 1 \bmod 2 \end{cases}\)。
另 \(\begin{cases} a_1H = a_2H, a_1 \equiv a_2 \bmod 2 \\ a_1H \Join a_2H = \emptyset, a_1 \nequiv a_2 \bmod 2\)。

正规子群

传说中的@正规子群.AI

正规子群(Normal Subgroup)是指陪集满足交换性的子群 \(H\)， \(\forall a \in G, H \subseteq G, \{a \cdot H\} = \{H \cdot a\}\)，则称 \(H\) 为 \(G\) 的正规子群。

不难证明阿贝尔群的子群都具有正规性。

上述条件可进一步写作：\(\forall a \in G, h \in H, a \cdot h \cdot a^{-1} \in H\)。

由上式的对偶性，同右乘 \(a\) 后推广 \(h\) 至 \(H\) 可推定。

商群

只有正规子群可以生成一个商群。

设 \(H \text{为} G\) 的正规子群，则 \(\{aH :a \in G\}\) 上可定义运算 \(\cdot\)：\((aH) \cdot (bH) = (ab)H\)，其亦成为一个群，称之为商群 \(G/H\)。

“商群”的概念较为抽象，依然从较为熟悉百听不厌的整群三剑客 \(Z,mZ,Z_m\) 举实例切入：

对于群 \(G = (Z_{35},+)\)，\(H = \{7k : k \in Z_5\}\) 显然为其子群（省略 \(+\) 运算，下同）。不难验证 \(H\) 也是 \(G\) 的正规子群。
写出 \(H\) 的陪集有 \(0+H,1+H\) 等，即 \(\{0,7,14,21,28\},\{1,8,15,22,29\} \cdots\)；
故商群 \(G/H = \{0+H,1+H,\cdots,k+H : k \in Z_5\}\)，其中商群中的每个元素（也就是 \(H\) 对 \(G\) 的（左）陪集）宏观体现即为 \(Z_35\) 内模 \(7\) 余数相同整数的集合。

其中商群的运算实例亦是水到渠成：\((0+H) + (1+H) = (0+1) + H = (1+H)\)；\((3+H) + (4+H) = (2+H)\) 等，相当于 \((a_1+H)+(a_2+H) = (a_3+H)\) 中 \(a_i\) 的运算只在 \(Z_5\) 下进行，其运算法与 \(H\) 定义中的 \(k\) 一致。

商群的重要判定性质之一是其良定性(well-defined)，即其运算律 \((aH)(bH) = (ab)H\) 成立；其交换性蕴含了商群运算不依赖于代表元 \(a,b\) 的选取。

商群可以理解为一个正规子群对既有群的一个“划分/分区(partition)”。

循环群

若 \(\forall a \in G, \exists i \in \mathbb{Z_{+}}, a^{i} = e\)，则称群 \(G\) 为循环群。
此时 \(\forall a \in G : ord(a) = n\) 的 \(a\) 都是生成元。

实际上

设 \(|G| = n\)，由拉格朗日定理可知 \(i | n\) 一定成立，进一步地，\(\forall a \in G, a^{n} = e\) 亦一定成立。

实例：\((\mathbb{Z_{p}},+)\) 是循环群，\(\forall a \neq \mathbb{0}\) 都是生成元（参考剩余系相关）。

推论：

• 素数阶群一定是循环群。考虑 \(\forall a \in G \space |G| = n\)，\(a\) 生成的子群为 \(H\)，根据拉格朗日定理，\(|H| | n\)，又 \(n\) 为质数 \(\Rightarrow\) \(|H| = 1\) 或 \(|H| = n\)，其中 \(a \neq e\) 时 \(|H| = n \Rightarrow a^{n} = e\)。

交换群

若群 \((G,\cdot)\)，上的运算 \(\cdot\) 还满足交换性，即 \(\forall a,b \in G, a \cdot b = b \cdot a\)，则称之为交换群，又名阿贝尔(Abel)群。

实例：\(\mathbb{Z}\) 上的 \(+\) 显然也是一个交换群；但 \(M_{2 \times 2}\)，即 \(2 \times 2\) 矩阵的乘法运算就不是交换群。

环与域

环

许多时候，对于一个群，我们希望研究其对多种结合法（运算）的特性。
以 \(\mathbb{Z},(+,\cdot)\) 这个妇孺皆知的运算进行迁移，设对于一个群 \(G\) 定义了两种运算（一般就表示为加法 \(+\) 和乘法 \(\cdot\)），若：

• \((G,+)\) 是一个交换群；
  
• \((G,\cdot)\) 是一个广群，即只需满足封闭性和结合性；
  
• \(+\) 对 \(\cdot\) 满足分配律，即 \(a \cdot (b + c) = a \cdot b + a \cdot c\)，

则称 \((G,(+,\cdot))\) 为一个环(Ring)。

进一步地，依据运算 \(\cdot\) 是否满足交换性、环中是否存在乘法单位元 \(\mathbb{1} \neq \mathbb{0}\)，
可以细言一个环为 交换/非交换 含/不含幺 环。

环中加法单位元一定存在（\((G,+)\) 是群的必要条件），记作为 \(\mathbb{0}\)；乘法单位元若存在则记作 \(\mathbb{1}\)。

实例：

• \((\mathbb{Z},(+,\times))\) 是一个交换含幺环（环判定：\((\mathbb{Z},+)\) 是交换群，\((\mathbb{Z},\times)\) 是广群，\((a+b)\times c = a \times c + b \times c\)；特征判定：存在 \(\mathbb{1} = 1 \neq \mathbb{0} = 0\)；\((\mathbb{Z},\times)\) 具备交换性）。
  
• \((\mathbb{M_{2 \times 2} : |M| \neq 0,(+,\cdot)})\) 是一个非交换含幺环（环判定同上；特征判定：存在 \(\mathbb{1} = \mathbb{I}_{2} \neq \mathbb{0} = 0\)，但 \(\cdot\) 不具备交换性。

整环

先介绍零因子(zero divisors)的概念：
设 \(a,b \neq \mathbb{0} \in R\)，若 \(a \cdot b = \mathbb{0}\)，则称 \(a,b\) 为 \(R\) 的零因子。
如在 \((\mathbb{Z_{6},(+,\cdot)})\) 中， $2 = 0 $，其中 \(2,3\) 就是零因子。

整环(Integral Ring)，顾名思义，是 \((\mathbb{Z},(+,\times))\) 概念的拓展。
若一个交换含幺环没有零因子，即 \(\forall a,b \neq \mathbb{0} \in R, a \cdot b \neq \mathbb{0}\)，则称之为整环。

实例：\((\mathbb{Z},(+,\cdot))\) 是整环废话文学.sage；设 \(p,m\) 分别为质数与合数，则 \((\mathbb{Z_{p}},(+,\cdot))\) 也是整环，但 \((\mathbb{Z_{m},(+,\cdot)})\) 不是。

整环除无零因子外的一个重要特性是消去律：\(\forall a,b,c \neq \mathbb{0} \in R, a \cdot b = a \cdot c \rightarrow b = c\)。

某种意义上的初等数学老生常谈

域、理想

域和理想都是环的同级延申。

域

域是更进一步的环。
若整环 \((R,(+,\cdot))\) 下，\((R,\cdot)\) 也满足交换性且具有单位元 \(\mathbb{1}\) ，则称之为一个域。

域可以认为是可以进行各种数学运算（加减乘除，其中除要求非 \(\mathbb{0}\)）的代数结构。

实例：\(\mathbb{Q}\) 显然是域省略 \((+,\cdot)\)，下同；设 \(p,m\) 分别为素数和合数，则 \(\mathbb{Z_{p}}\) 也是域，而 \(\mathbb{Z}\) 和 \(\mathbb{Z_{m}}\) 不是（ \(\forall a \neq \mathbb{1} \in \mathbb{Z}, \nexists a^{-1} \in \mathbb{Z}\)；\(\mathbb{Z_{m}}\) 不是整环（对 \(m\) 的因数分解就是其零因子），同时也不满足可逆性（显然可逆要求 \((a,m) = 1\)））。

由上可以整理出递进关系：
集合 -> 广群 -> 半群 -> 独异点 -> 群 -> 交换群 ；环 -> 整环 -> 域。

理想

理想(Ideal)是一种特殊的子环。
若 \((I,+) \subseteq (R,+)\) 满足吸收性，即 \(\forall r \in R, a \in I, (a \cdot r, r \cdot a) \in R\)（对于交换环可简化为 \(a \cdot r \in R\)），则称 \(I\) 为 \(R\) 的一个理想。

“吸收性”作人话之解，即为能通过乘法（\(\cdot\)）吸收任意元素的子集，可视为“原环的倍数”。
实例：\(\mathbb{Z/2Z}\) 是 \(\mathbb{Z}\) 的一个理想，因为任意整数乘以一个偶数的结果必为偶数。

特别地，显然 \(R\) 亦为自身的理想，此时称其为 \(R\) 的平凡理想，对应满足条件的 \(\forall I \neq R\) 为 \(R\) 的非平凡理想。

主理想和素理想要求原环 \(R\) 必须为交换环。

主理想

主理想是由单个元素 \(a \in R\) 生成的理想 \(\langle a \rangle = R \cdot a = \{r \cdot a | s\forall r \in R\}\)。

实例：\(\mathbb{Z/2Z}\) 就是由 \(2\) 生成的主理想；任意环 \(R\) 的平凡理想的生成元是乘法单位元 \(\mathbb{1}\)。

(反例咕咕中)

素理想

对于环 \(R\) 的非平凡理想 \(I\)，若 \(\forall a,b \in R, a \cdot b \in I \Rightarrow a \in I \text{或} b \in I\)，则称之为 \(R\) 的素理想。

如 \(\mathbb{Z}\) 中的素理想就是 \(\langle p \rangle\)，即素数生成的理想

最大理想

对于环 \(R\) 的非平凡理想 \(I\)，若 \(\forall U \subseteq R, I \subseteq U \subseteq R \Rightarrow U = I \text{或} U = R\)，则称之为 \(R\) 的最（极）大理想。

主理想整环

拼凑而成的概念，字面意义，全是主理想的整环

对于整环 \(R\)，若其中的理想 \(I \subseteq R\) 都是主理想，则称之为主理想整环。

主理想整环中，每个素理想都是极大理想。由于主理想整环中，每个理想都可以表示成 \((d) | d \in R\) 的形式，结合素理想的性质可证明 \((p) \subseteq (d)\) 时 \(d \in \{1,p\}\)（相当于 \((d) \in \{(p),R\}\) ）。

常见的主理想整环包括整数环 \(\mathbb{Z}\) 和多项式环 \(\mathbb{F_{p}/f}\)（其中 \(f\) 为 \(F_{p}\) 下的不可约多项式）。

抽象多项式

常见的 \(n \text{次多项式} f(x)\) 形如 \[c_nx^n + c_{n-1}x^{n-1} + \cdots + c_1x^1 + c_0 = \sum_{i=0}^{n} c_{i}x^{i}\]，其中常有 \(x \in F_{p}\) 。

\(F_{p}\) 是模 \(p\) 整数环形成的域。

回顾常见多项式的运算规则：

• 加法是对应项系数在 \(Z_{p}\) 下相加，即相加后对 \(p\) 取模；
  
• 乘法是普通的多项式乘法，其中系数运算同样在 \(Z_{p}\) 下进行。

如 \(F_{3}\) 下令 \(a = x + 2, b = x + 1\)，则 \(a + b = 2x\)，\(a \cdot b = x^2 + 2x\)。

注意此时的多项式运算依然不是一个环，因目前其尚未定义除法（乘法逆运算）和模运算。

定义一个多项式的度(degree)为其最高变量的幂数，简记作 \(d(f) = n \forall f = \sum_{i=0}^{n} c_{i}x^{i}\)。

为使这个多项式群能拓展为一个环，需要将多项式群对一个度为 \(n\) 的不可约多项式 \(f\) 取模，使之形成一个商环(Quotient Ring)，记作 \(Z_{p} / f\)。

不可约多项式具体参阅下一小节，先简记为 \(F_p\) 下不能再“约分”的多项式即可；\(f\) 为任意非零多项式时 \(Z_{p} / f\) 都能称为一个商环，但 \(f\) 为不可约多项式时其方为一个整环，参考抽象代数中的二级结论：对于交换含幺环 \(R\)，\(P\) 为素理想的充要条件为 \(R/P\) 为整环。

类比 \(Z/mZ\) 给出的相似代数结构有助于理解。
如 \(Z_{m} \subseteq Z \text{，定义} f: Z \rightarrow Z_{m}, f(x) = x \bmod m, ker(f) = mZ\)，则这个商群和 \(im(f)\)，即 \(Z_{m}\) 同构。
同样地，\(F_{f}\) （即模 \(f\) 的多项式）亦可进行类似的定义。

对于加法和乘法，每次运算完成后要求对 \(f\) 取模，模运算依长除法进行；
除法相当于乘以乘法逆元，乘法逆元可由扩展欧几里得除法(gcdext)获得。

由于 \(Z_{p}/f\) 为整环，因而其没有零因子，\((f^{'},f) = 1\)必定成立；类比 \(Z_{p}\) 可知环上的多项式都存在乘法逆元。
对多项式的gcdext和对整数的gcdext本质无异（从抽象运算而言），注意此处多项式除法的结果、余数均为多项式，且通过长除法给出（此时并未进入到 \(F_{f}\) 中）。

举例：设 \(f_i \in F_2 / (x^2 + x + 1), f_0 = x, f_1 = x^2 + 1,f_2 = x^2 + x\)。
运算示例：\[f_0 \cdot f_1 = (x^3 + x) \bmod (x^2 + x + 1) = x + 1\]

不可约多项式

效仿 \(Z\) 中素数的概念，引入“不可约多项式”：
若 \(f,f_a,f_b \in Z_p d(f_a),d(f_b) \leq d(f),\forall f_a \cdot f_b = f \Rightarrow f_a = f \text{或} f_b = f\)（且显然另一者为 \(1\)），则称 \(f\) 为不可约多项式。
与素数a.k.a.不可约数的差分在于，\(f\) 是否为不可约亦取决于 \(x\) 的所在环（域），如 \(x^2 + 1 \in F_{3}\) 是不可约多项式，但 \(x^2 + 1 \in F_{2} = (x+1)^{2}\)。

不可约多项式的测试法与素数判断类似：满足以下条件的 \(d(f) = n\) 的多项式 \(f\) 为 \(F_{p} \text{下的 } n\) 次不可约多项式：

• 其不能被所有 \(d(f^{'}) \leq \lfloor \frac{n}{2} \rfloor \text{的不可约多项式} f^{'}\) 整除，
  
• 其在 \(F_{p}\) 内没有根（此项不适用于 \(n = 1\)，故 \(\forall k \in F_p, x + k\) 均为 \(F_p\) 下的不可约多项式）。

//???

举例： 判断 \(f = x^3 + x + 1 \in F_{3}\) 是否为不可约多项式？注意到 \(f\) 有一个根 \(x = 1\) （满足 \(f(x) = 0\)），故其不是不可约多项式。
若将之转移至 \(F_{2}\)：首先确定其没有根，随后检验 \[\begin{cases} f \bmod x = 1 \neq 0 \\ f \bmod (x+1) = 1 \neq 0 \end{cases}\] ，检验通过，确定其为不可约多项式。

环阶与本原多项式

若 \(d(f) = n\)，则商环 \(F_{p}/f\) 的最大阶为 \(p^n - 1\)。

“最大阶”的理解：\(x\) 的阶显然为 \(p\)；\(n\) 次项之间相互独立，因而 \(n\) 次多项式的取值个数不会超过 \(p^{n}\)，即其阶数上界为 \(p^{n} - 1\)（因为阶数定义为满足 \(f^{n} = \mathbb{0}\text{（单位元）} = 1\) 的最小整数 \(n\)）。

而商环的实际阶数 \(n\) 定义为满足 \(f^n = x^{}\)

定义拓展

进一步地，由于域中元素可以进行各类数学运算，故 \(x\) 亦可被定义在任何域 \(F\) 中。

现记定义在域 \(F\) 中的“自变量” \(x\) 构成的多项式 \(f \in F[X]\)。\(F[X]\) 构成一个多项式环(Polynomial Ring)，\(F[X]\) 中的元素个数显然是无限的。
同样引入抽象的模不可约多项式 \(f_q\)，构建商环 \(F[X]/f_q\)，若 域 \(F\) 的阶为 \(p\)，，则 \(F/f_q\) 的最大阶数为 \(p^{n} - 1\)。

格

格(Lattice)是指一个拥有最大上界和最小下界的偏序关系集。

数论

笔者学习信安数基、密码学等相关知识时，多数教材均选择将数论先全盘托出，随后再讲解离散数学（抽象代数）相关内容。
但数论中部分关键概念（如中国剩余定理、模n整数的原根等）本质上是抽象代数在模n整数下的实例；通过调整部分内容，可以将之置于代数之后，作为其实例之一进行理解，对抽象代数的消化吸收和数论相关分析、推导的接受度均大有裨益。

模n高次同余式

指数与原根

设 \(p\) 为质数，\((a,p) = 1\)，\(a\) 在 \(Z_p\) 下的指数定义为满足 \(a^{k} \equiv 1 (\bmod p)\) 的最小正整数 \(k\)，记作 \(ord_p(a)\)（亦可简记作 \(ord(a)\)）。
若 \(ord_p(a) = \varphi(p) = p-1\)，则称之为 \(Z_m\) 下的原根。

本质上其就是群 \((Z_m,\times)\)，原根即 \(Z_m\) 下乘法群的生成元。

根据费马小定理，\(\forall (a,p) = 1, a^{p-1} \equiv 1 (\bmod p)\) 必定成立，因此“原根”只是 \(ord(a)\) 达到了其上界。同时数论分析和拉格朗日定理都可以给出，\(\forall (a,p) = 1, ord(a) | p-1\) 同样成立。

同时对任意一个原根 \(g\)，\(\forall i \in \{c_i\}, g^{i}\) 亦为其原根，其中 \(\{c_{i}\}\) 为 \(p-1\) 的简化剩余系。
由同余相关分析可以导出检验 \(a\) 是否为 \(Z_p\) 原根的快捷方法：设 \[p-1 = 2 \times \prod_{i=1}^{n}p_{i}^{e_{i}}\]
其中 \(p_i\) 为奇质数，若 \[\forall k = \prod_{i=1}^{n} p_{i}^{s_{i}}, 0 \leq s_{i} \leq e_{i}, k < \frac{p-1}{2}, a^{k} \neq \pm 1 (\bmod p)\]
则 \(a\) 为其原根。
同时此步可用于计算 \(a\) 的指数：将测试的 \(k\) 升序排序，得到最小的满足条件 \(k\)，则 \[ord_m(a) = \begin{cases} k, a^k \equiv 1 \bmod p \\ 2k, a^k \equiv -1 \bmod p \end{cases}\]

\(a^{p-1} \equiv 1 \bmod p \Rightarrow a^{\frac{p-1}{2}} \equiv \pm 1 \bmod p\)，此为余-1的“截断”依据。

若 \(ord(a) = m\)，则 \(ord(a^i) = \frac{m}{gcd(i,m)}\)，具体原因仍然可以参考剩余系相关——构造一个同态映射 \(f: Z_{p-1} \rightarrow Z_{p}, f(x) = g^{x}\)，观察其“逆映射”的指数即可。

可推导出 \(Z_{p}\) 下的原根个数为 \(\varphi{\varphi{N}}\)，同时从任一原根可推出其全部原根——对于任意群亦是如此，已知单个生成元和群阶，即可推出其全部的生成元前提是群的阶不被打造成RSA一般的极难分解的大整数

运算示例

以 \(Z_{43}\) 下的运算为例。

求 \(ord(2)\)：
存在 \(\varphi{43} = 43 - 1 = 42 = 2 \times 3 \times 7\)；计算 \(Z_{43}\) 下 \(2^3 = 8, 2^7 = 42 = -1\)，因而 \(ord_43(2) = 7 \times 2 = 14\)。
再试求 \(Z_{43}\) 下的所有原根：
已知 \(2\) 不是其原根，再尝试 \(3\)：
\(3^3 = 27, 3^7 = 37\)，说明 \(3\) 是 \(Z_{43}\) 的原根（检验：\(3^{21} \equiv -1 \bmod 43 \rightarrow 3^{42} \equiv 1 \bmod 43\)）。

再列出 \(42\) 的简化剩余系：
\(\{c_i\} = \{1,5,11,13,17,19,23,25,29,31,37,41\}\)，计算得 \(Z_{43}\) 原根有 \(3,28,30,12,26,19,34,5,18,33,20,29\)。

密码学实例

RSA

RSA的基础知识不再赘述，详见RSA。
其部分“联动”的性质如下：

• RSA的加密 \(e\) 和解密 \(d\) 都是 \(Z_N \rightarrow Z_N\) 的映射，且均满足乘法同态；RSA运算在一个交换含幺环上进行，其零因子为 \(N\) 的因数分解 \(p,q\)，故其不是整环。
  
• RSA中，\(Z_{N}\) 下原根构成的乘法群的阶是 \(\varphi{N}\)，而根据拉格朗日定理，任意元素构成的乘法群阶一定能整除 \(\varphi{N}\)。此点是RSA正确解密的基础，因为 \(ed \equiv 1 \bmod \varphi{N}\)，其保证了 \(\forall c \in Z_{N}, m^{k \cdot \varphi{N} + 1} = c^d \equiv m \bmod N\)。

DLP

尽管DLP(Discrete Logorithm Problem,离散对数问题)极少被直接用于加密等，但其思想及在各种域(\(Z_p,E,F_p[X]/f\) 等)中的应用，依然是大量现代密码学算法的安全性的基石之一。

其核心思想为：

• 给定一个群 \((G,\cdot)\) 和 \(P \in G\)
  
• 给定 \(n \in Z\)，正向数乘计算，即计算 \(Q = nP\) 非常高效（可以通过快速幂/乘拓展来实现，即将 \(nP\) 中的 \(n\) 转化为二进制）
  
• 但给定 \((Q,P)\)，找到 \(n\) 满足 \(nP = Q\) 是非常困难的

典型的群实例包括 \((Z_{p},\times)\) 和 \((E,+)\)，后者亦被称为ECDLP。
计算难度的单向性使其可被用于设计陷门函数(trapdoor function)，即加密等操作时可以将关键信息隐藏于 \(n\) 中，攻击者即使知道 \((P,Q)\) 也无法倒推出 \(n\)，同时 \(Q\) 数学上携带了 \(n\) 的信息且可传递。

DH

DLP最著名的应用实例之一当属Diffle-Hellman密钥交换：
对于一个安全的群 \((G,\cdot), |G| = n\)，通信双方选择 \(a,b \in Z_{n}\) 作为私钥，选择 \(G\) 的一个生成元 \(P\)，计算 \(A = aP, B = bP\) 并发送给对方。
对方接收到 \(A\) 或 \(B\) 后将之与自己的私钥再相乘：
\(aB = a(bP) = (ab)P, bA = b(aP) = (ba)P\)，又 \(Z\) 下的乘法满足交换性，显然由此双方获得了相同的点 \(S = abP\)。
而全程双方传递的信息只有 \((A,B,P)\)，攻击者即使截获之，因计算 \(n\) 的困难性，亦无法计算出 \(S\)。

安全群与攻击

对于DLP的攻击，在Brute-force（逐个尝试 \(n\) 直至命中）以外亦有些许技巧；相应地，为了保证DLP问题的应用安全性，其对群的设计也提出了一些要求。

Pohlig-Hellman

Pohlig-Hellman攻击又名“子群攻击”，其核心就是拉格朗日定理的“拓展版”。

由拉格朗日定理，设 \(|G| = n\)，则 \(\exists H \subseteq G, H = n^{'} \forall n^{'} | n\)。进一步地，设 \(G\) 的生成元为 \(g\)，则 \(|\langle k \cdot \rangle| = \frac{n}{gcd(n,k)}\)，其表明了可以通过控制 \(k\) 来生成不同大小的子群—— \(gcd(n,k) = 1\) 时其转化为 \(\frac{n}{k}\)。

而 \(f: G \rightarrow H, f(x) = k \cdot x\) 是一个同态映射，因此若 \(Q = xP\)，则 \(f(Q) = x^{'}'f(P)\) 且 \(x^{'} \equiv x \bmod \frac{n}{k}\)。

解出大量如此的 \(x^{'} \equiv x \bmod \frac{n}{k}\) 后，根据中国剩余定理即可解出 \(x\)。
结合CRT对于模数互质的要求，设 \(n = \prod_{i=1}^{n} p_{i}^{e_{i}}\)，推定其宏观上的时间复杂度会由 \(O(n)\) 降低至 \(O(\sum_{i=1}^{n} p_{i})\)。

不要问指数 \(e_{i}\) 去哪了，问就是在模 \(p\) 下拿同余式解后直接lift

故对于任意群 \(G\) 上的离散对数问题，其难解性是与其最大素因子 \(p_{i}\) 紧密相关的——若 \(\max{p_{i}}\) 过小，则攻击者通过在小阶子群上解DLP即可“拼凑”出原问题的解，此所谓Pohlig-Hellman攻击（亦称小子群攻击）。
另外若一个群阶的小因子过多，只要其积大于（或略小于）\(x\) 的上界，由CRT可知其较小模的“既有通解”就是特解。

由于DLP问题在密码学应用的广泛性，在不同群上的DLP为抵抗该攻击均需精心设计参数：

• \(Z_{p}\) 要求 \(p\) 为强质数，即 \(p-1\) 其实还有 \(p+1\) 必须至少有一个大因子（其一定有一个因子 \(2\)，不过此点无伤大雅，较简易的生成强质数的方式之一就是随机选取素数 \(p\) 并检验 \(2p+1\) 是否为质数）。补档：好像这个是防RSA的光滑数攻击的
• \(E\) 要求计算得曲线的阶 \(|E|\) 为质数，防止构造子群攻击。

对于EC-DLP亦需在应用时增加点的校验来防止无效曲线攻击，即检验待加密的点是否在给定的曲线上。
简化的椭圆曲线点运算系统（尤其在计算资源有限的小型设备上），为追求效率最大化会常会直接利用传入的点参数进行计算。参考椭圆曲线的点加规则，可以发现其群性质只依赖于参数 \((x,y,a,p)\)，而附加常数 \(b\) 本质上被“隐藏”于 \((x,y)\) 中。
改变 \(b\) 不会影响点加计算的逻辑，，相当于原设备会在另一条（\(a,p\) 相同，\(b\) 不同）的曲线上进行点的计算。
但通过更改 \(b\)，攻击者可以将这个点转移至更弱的椭圆曲线上，并进行涉及私钥（离散对数解）的点乘计算，在子群下得到足够多的 \(x^{'} \bmod p_{i}\)，最终通过CRT即可解出原解 \(x\)。
本质上，上述过程即为诱导拓展的Pohlig-Hellman攻击。

BSGS

若 \(|G| = n\)，则直接爆破 \(G\) 上的DLP问题的时间复杂度为 \(O(n)\)，而其空间复杂度为 \(O(1)\)。
BSGS(Baby Step Giant Step，小步大步法)则是一种“分摊”时间和空间复杂度的方法：
将待求式转化至 \(Q = x \cdot P \space{3} 0 \leq x < n\)。则

• \(x = x_1 \cdot \lfloor \sqrt{n} \rfloor + x_0 \space{3} x_1,x_2 \leq \lceil \sqrt{n} \rceil\)
  
• 计算 \(\{P^{'}_{i}\} = \{x_0 \cdot P \forall x_{0} \leq \lceil \sqrt{n} \rceil\}\)
  
• 再 \(\forall x_1 \leq \lceil \sqrt{n} \rceil\)，计算 \(Q^{'} = x_{1} \cdot Q^{-1}\)，若 \(Q^{'} \in \{P^{'}_{i}\}\)，则命中解 \(x = x_1 \cdot \lfloor \sqrt{n} \rfloor + x_0\)。

其中第三步“命中”校验可以采用访问时间复杂度为 \(O(1)\) 的数据结构进行（散列表等）。
可以看出其通过将空间复杂度提高为 \(O(\sqrt{n})\) 来将时间复杂度降低为 \(O(\sqrt{n})\)。

椭圆曲线

满足方程 \[y^2 = x^3 + ax + b \space{5} (x,y \in F, 4a^3 + 27b^2 \neq 0)\] 的点集合为椭圆曲线，通常选取 \(x,y \in F_p\)。

理论上 \(x,y\) 亦可被定义在任意域中（密码学应用要求其为有限域）。

定义点集合 \(E\) 上的结合法 \(+\)，\((E,+)\) 是一个交换群（Abel群）。

• \(\forall a,b \in E\)，\((a + b) + c = a + (b + c)\)（结合律），\(a + b = b + a\)（交换性）
  
• 单位元 \(e = \mathbb{O}\)，其是无穷远的一个点，\(\forall P \in E, P + \mathbb{O} = P\)
  
• 逆元 \(a^{-1} = \begin{cases} \mathbb{O}, a = \mathbb{O} \\ (x,-y), a = (x,y) \neq \mathbb{O} \end{cases}\)
  
• 加法规则：设 \(A = (x_1,y_1), B = (x_2,y,2) \in E\)，满足 \[A + B = \begin{cases} \mathbb{O}, y_1 + y_2 = 0 \\ (k^2 - (x_1 + x_2), k \cdot (x_1 - x_3) - y_1), y_1 + y_2 \neq 0 \end{cases} \text{其中}k = \begin{cases}\frac{y_2-y_1}{x_2-x_1}, A \neq B \\ \frac{3x_1^2 + a}{2y_1}, A=B \end{cases} \]
  
• 点只能进行数乘，\(kP\) 即为 \(k\) 个点之和，\(P\) 在 \(E\) 上的阶定义为使得 \(nP = \mathbb{O}\) 最小正整数 \(n\)，同样有 \(n | ord(E)\)
  
• \(E\) 还是一个循环群，\(\forall P \in E, nP = \mathbb{O}\)不仔细看还以为这是环的表达式

AES

AES 的“字节”运算全部在有限域\(F_{2^8}= \mathbb{F}_2[x]/(m(x))\) 下进行，其中 \(m(x)=x^8+x^4+x^3+x+1\) 是 8 次不可约（也是本原）多项式。

注意形若 \(F_{p^{n}}\) 的计算都不是对 \(p^{n}\) 取模，事实上 \(Z_{p^{n}}\) 亦无法构成一个域。
本质上，其是在模degree为8的多项式 \(f\) 构成的商环 \(F_{2}[X]/f\) 环下进行运算。
宏观上的“字节”由其对应多项式的系数“拼凑”而成（\(p\) 进制转化），即：\[a_{i} = \sum_{i=0}^{7} s_{i}2^{i} \in F_{2^{8}} \Leftrightarrow \sum_{i=0}^{7} s_{i}x^{i} \in F_{2}[X] / (m(x))\]
如，\(\text{0xab} = 171 = 2^7 + 2^5 + 2^3 + 2 + 1\)，对应多项式 \(a(x)=x^7+x^5+x^3+x+1\)。

AES的商环诱导的代数运算结构：
对于加法，两个字节直接异或即可：对应多项式系数在 \(\mathbb{F}_2\) 上相加—— \(F_{2}\) 的优雅之处即在此，无进/借位。
对于乘法，转化为多项式乘法后对 \(m(x)\) 取模。转化为宏观“字节”的计算，可以采用快速乘的思想，溢出时的“魔数”模数为 \(\text{0x1b} = 27\)。
实现形如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Byte
{
    using value_t = unsigned char;
public:
    static constexpr void _gf256_mul(value_t& x, unsigned long long y)
    {
        value_t res = 1, mul = x;
        while(y)
        {
            if(y&1)
            {
                res *= mul;
                res ^= (res >> 2 ? 0x1b : 0x00);
                res &= 0xff;
            }
            mul *= mul;
            mul ^= (mul >> 2 ? 0x1b : 0x00);
            mul &= 0xff;
        }
        x = res;
    }

    friend constexpr Byte operator+(Byte x,Byte y)
    {
        return Byte(x.value^y.value);
    }

    //...

private:
    value_t value;

};

\(\forall a \neq e, \exists a^{-1} \in GF(2^{8}), a \cdot a^{-1} = 1\)，即对于0x00外的元素，乘法逆元存在且唯一（为保证兼容，AES定义了0x00的逆元为其自身，进而其在S-Box内的映射为0x63，推导见下）。
同时由于定义域和值域很小，因此实际的AES实现中常会预计算乘法表以加快运行速率。

AES的几个组件都依赖于元素在 \(GF(2^{8})\) 上的矩阵/向量运算，其中元素对应的向量是 \(GF(2)\) 上定义的 \(8 \times 8\) 矩阵，一般按低位优先(LSB)顺序排列。
三种表示方式（字节值、多项式、向量）的转化示例：\[ 232 = 2^{3} + 2^{5} + 2^{6} + 2^{7} \in GF(2^{8}) \leftrightarrow x^{3} + x^{5} + x^{6} + x^{7} \in F_{2}[x] / (x^8 + x^4 + x^3 + x + 1) \leftrightarrow \begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \end{bmatrix}^{T}\]
如记S-Box的双射为 \(f: GF(2^{8}) \rightarrow GF(2^{8})\)，则 \(f(x) = x^{-4} + x^{-3} + x^{-2} + x^{-1} + 63\)不先替换一下逆元就直接表达be like
其对应的矩阵乘法形式为：\[\begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ b_7 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{bmatrix}\]

LFSR

LFSR，Linear Feedback Shift Register，线性反馈移位寄存器，其广泛应用于流密码序列的生成。
整个LFSR可以视为在 \(F_{2}[X]/f_q\) 下运行的多项式商环（其和另一种解析LFSR的方式，即 \(F_{2}\) 下的矩阵运算是同构的）。

具体地，假设反馈值 \[s_{n} = \sum_{i=0}^{n-1} f_{i}s_{i} \bmod 2\]
矩阵形式下，其亦可表示作 \[s_{n} = \begin{bmatrix} f_{n-1} & f_{n-2} & \cdots & f_{0} \end{bmatrix} \cdot \begin{bmatrix} s_{n-1} & s_{n-2} & \cdots & s_{0} \end{bmatrix}^{T} \]

若从 \(F_{2}[X]/f_q\) 的角度出发，每个状态下的多项式可以表示为 \[f_{k} = \sum_{i=0}^{n-1} s_{i}x^{i}\]
令 \[f_q = \sum_{i=0}^{n-1} f_{i}x^{i}\]
推导多项式为 \[f_{k+1} = x \cdot f_{k} \bmod f_q\]

其和多项式环相关知识的关联：

欲令该生成器的数列（即结果多项式）的周期最大，\(f_q\) 应为本原多项式，理论最大周期与该多项式环的阶一致，为 \(2^{n} - 1\)（从矩阵亦可推导之，相互校验）
若 \(f_q\) 是可约的，则其周期与其因式的阶有关，可以根据中国剩余定理推导之
即使多项式是本原的，若起始的多项式 \(f_{0}\) 选择不当（即其不是 \(F_{2}/f_q\) 的生成元），其生成序列的周期依然小于 \(|F_{2}/f_q|\)