C++——与AES-Integrals的双鹭翩舞

书到用时方恨少，事非经过不知难。

本篇针对的是玲珑的第一个独立密码学/C++项目——AES-Integrals。
意在详解利用Modern C++相较传统C/C++对此密码学攻击实现中，代码质量（可读性、维护性与拓展性）及运行效率方面的优化。

有关AES积分攻击的密码学分析，可移步AES积分攻击：霜天

aes.h

aes.h中实现了对称密码学有关的基本函数和配套类、具备多种功能的AES类等，是被复用/拓展的根基。

struct byte：迷雾乱花

struct byte实现的部分节选如下：

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

struct byte 
{
    explicit constexpr byte(unsigned char _val) : value{_val} {}
    constexpr byte() : byte(0) {}

    // Default special member functions
    constexpr byte(const byte&) = default;
    constexpr byte(byte&&) noexcept = default;
    constexpr byte& operator=(const byte&) = default;
    constexpr byte& operator=(byte&&) noexcept = default;
    constexpr ~byte() = default;

    // Conversion
    constexpr operator unsigned char() const noexcept { return value; }

    // Bitwise operators
    friend constexpr byte operator&(byte x, byte y) noexcept
    {
        return byte{ uc(x.value & y.value) };
    }

    //...
};

略去者均为运算符重载等“重复性”内容。

struct byte的几个特点在于：

  • 该struct是 trivial 的，即其只有一个公有数据成员unsigned char value，且其遵循基本类型的复制、移动及析构逻辑，因而该struct在程序中的额外开销相较unsigned char或其它enum类型几乎为零；
  • 其构造函数和转换构造函数采用了单向explicit的设计：由于认为struct byte是一个有限“域”，故其它的整数类型（无论初始值在不在unsigned char的范围内）向byte的转换都应当被显式声明；反之则不然（即允许struct byte向普通的整数类型隐式转换）。
  • 仅重载了位运算符，所有运算符重载的运算对象的返回值都是byte，但移位运算符除外（第二操作数选择了unsigned char）。
1
2
3
4
5

byte a; //OK
byte b = a & 3; //Error: Ambiguious invocation


block_fromhex：万象霜天

简介

本函数意在实现std::string_view（泛“字符串”）向std::array<byte,16>，即所谓“块”的转换。

定义及对比

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
constexpr std::expected<block,std::string> block_fromhex(std::string_view sv)
{
    auto refloc = sv.data();
    block res{};    
    for (auto& bt : res)
    {
        uc temp{};
        if (sv.empty())
        {
            return std::unexpected{ "Insufficient text to generate a block" };
        }

        if (auto val = std::from_chars(sv.data(), sv.data() + 2, temp, 16);val.ptr != sv.data() + 2)
        {
            return std::unexpected{ std::format("Non-hex character at position {}",val.ptr - refloc) };
        }

        bt = byte{ temp };
        auto fn = [](char ch) -> bool {return std::isblank(ch);};
        sv.remove_prefix(2);
        sv = sv.substr(std::ranges::find_if_not(sv, fn) - sv.begin());
    }    

    return res;
}

相比之下，一个传统C++的实现可能会形如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
byte[16] block_fromhex(const char* ch,size_t len)
{
    //...

    if(...)
    {
        throw std::exception("...");
    }

    //...
}

int block_fromhex(const char* ch,size_t len,unsigned char* out)
{
    //...
}

逐行分析改进点：

  • 函数原型声明上，由于block_fromhex默认都会开辟新的栈内存空间来存放“转换”的结果所谓csharp中的out Block result，故显然将结果放在返回值中“传出”是更好的选择。但又由于需要将异常信息传出，则只能依靠throw来解决此问题——潜在的栈回溯的副作用之一，即为极大限制了代码效率上限（编译器需为这个可能的“出口”进行额外分支判断等），起步即逊于能被声明为noexcept的现代C++实现。
    若选择C语言类似的解法，依靠int作为返回值并将目标数组以 out 参数指针置于其中，且不论内存安全性，在调用代码中必须手动检查其返回值——极大增加疏漏风险的同时，使得调用逻辑变得更加繁琐。
    相较之下，本实现（C++23版本）使用了std::expected<block,std::string>，在提高内存和执行效率的同时，调用逻辑也显得更为清晰甚至没算上链式调用：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    if(auto bk = block_fromhex(buf);bk)
    {
        val[i] = *bk;
    }
    else
    {
        std::println("{}",bk.error());
        exit(1);
    }
  • 内部实现直接封装对C++标准库中<charconv>的std::from_chars的调用，保证正确性的同时（参考C++ Core Guidelines之尽量避免“手搓”函数，优先级：标准库>三方库>手搓）。from_chars的返回值直接用 Structural Binding 捕获，通过看ptr是否为其起始位置+2即可快速判断解析是否正确。
  • 循环用auto&来遍历res(std::array<byte,16>)，保证每行只解析前16组有效的十六进制字符，std::string_view在提供对C样式字符串、std::string等较好的适配性的同时，性能比另开std::string/const std::string&高且保证了内存安全所谓view-type的魅力。
  • “移进”扫描点时采取了跳过所有非空格字符的策略，此处封装了对std::isblank的调用（因原函数返回值是int，似乎可以用std::invoke_r更进一步改善？）

该函数的进一步封装和拓展点应在“流”的phase，及对部分异常处理的差分策略。

gmul

创新的定义

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
namespace _gmul 
{
    using table_t = std::array<byte, 2048>;
    constexpr byte gmul_fn(byte a, uc b) noexcept
    {
        byte p{};
        while (b)
        {
            if (b & 1)
            {
                p ^= a;
            }
            byte hi_bit{ a & 0x80_t };
            a <<= 1;
            if (hi_bit)
            {
                a ^= 0x1b_t;
            }
            b >>= 1;
        }
        return p;
    }

    static constexpr std::array<int, 8> val_idxs = { 2,3,1,1,0x0e,0x0b,0x0d,0x09 };

    consteval table_t table_gen() noexcept
    {
        table_t res{};

        for (int i : std::views::iota(0, 2048))
        {
            res[i] = gmul_fn(byte(i % 256), byte(val_idxs[i / 256]));
        }

        return res;
    }

    static constexpr table_t table = table_gen();

    struct gmul_t
    {
        constexpr byte operator()(byte a, int b) const noexcept
        {
            return table[b * 256 + a];
        }
    };

    static constexpr inline gmul_t gmul = {};
}

解析

gmul（ \(GF(2^8)\) 下的乘法）的实现是AES加密的重要组成部分。既有C/C++对这一模块的实现基本分三种思路：

  • 只实现gmul的计算逻辑（如上述gmul_fn所述），所有数值全部在运行时计算；
  • 利用AES类中乘法的第二操作数只有8个选项（2,3,1,1及其“逆元”）的特性，将待获取的乘法结果（256*8种组合）“打表”备用；具体实现或为静态字面量悉数枚举（即常量初始化之），或为程序运行开始时完成计算并置于静态存储区种。

这几种实现思路各有优劣，综合来看第三种实现较好；但现代C++引入的constexpr、consteval和对编译期计算的全面支持，使另一种可能性浮出水面——将计算逻辑使用编译期函数表述之，并在编译期完成全部计算（形如上述的consteval table_t table_gen();，consteval约束其解析一定在编译期完成）。

另外，gmul这个外部调用“接口”的函数采用了 ranges algorithm “同款”的函数对象实现。

此处“函数”gmul的实现照顾了待在AES类中调用所需的乘数，使其调用逻辑更为简洁。

AES类

主要实现了AES类的加/解密公开接口及内部组件的私有函数。节选形如：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
using block = std::array<byte, 16>;
using block_vw = std::span<byte, 16>;
using block_rvw = std::span<const byte, 16>;

template<size_t Rounds = 10> requires (Rounds >= 1)
class AES
{
public:
    using rnd_key_t = std::array<block, Rounds + 1>;
    constexpr AES(block_rvw key) :rnd_keys(key_expansion(key)) {}

    constexpr block encrypt(block_rvw plain)
    {
        block state{};
        for (int i : std::views::iota(0, 16))
        {
            state[i] = plain[i];
        }

        add_round_key(state, 0);

        for (auto i : std::views::iota(1ull, Rounds))
        {
            sub_bytes(state);
            shift_rows(state);
            mix_columns(state);
            add_round_key(state, i);
        }

        sub_bytes(state);
        shift_rows(state);
        add_round_key(state, Rounds);
        return state;
    }

    constexpr block decrypt(block_rvw cipher) /**/

private:
    static constexpr byte s_box[] = /*...*/;

    static constexpr byte inv_s_box[] = /*...*/;

    static constexpr byte r_con[] = /*...*/;

    static constexpr rnd_key_t key_expansion(block_rvw init) noexcept
    {
        rnd_key_t rk{};
        std::ranges::copy(init, rk[0].begin());

        for (auto i : std::views::iota(1ull, Rounds + 1))
        {
            block_rvw prv = rk[i - 1];
            block_vw cur = rk[i]; //seperating to make read-only sematic more explicit

            for (int j : iota_word)
            {
                cur[j] = prv[j] ^ s_box[prv[12 + (j + 1) % 4]];
            }

            cur[0] ^= r_con[i - 1];

            for (int j : std::views::iota(4, 16))
            {
                cur[j] = prv[j] ^ cur[j - 4];
            }
        }

        return rk;
    }

    static constexpr void sub_bytes(block_vw s) noexcept
    {
        for (byte& i : s)
        {
            i = s_box[i];
        }
    }

    static constexpr void inv_sub_bytes(block_vw s) noexcept
    {
        for (byte& i : s)
        {
            i = inv_s_box[i];
        }
    }

    static constexpr void shift_rows(block_vw s) noexcept
    {
        std::ranges::copy(block{
           s[0], s[5], s[10], s[15],
           s[4], s[9], s[14], s[3],
           s[8], s[13], s[2], s[7],
           s[12], s[1], s[6], s[11]
            }, s.begin());
    }

    static constexpr uc shift_rows_idx[] = {
        0,5,10,15,
        4,9,14,3,
        8,13,2,7,
        12,1,6,11
    };

    /**/

    static constexpr void mix_columns(block_vw s) noexcept
    {
        block res{};

        for (int i : std::views::iota(0, 16) | std::views::stride(4))
        {
            for (int x : iota_word)
            {
                for (int k : iota_word)
                {
                    res[i + x] ^= gmul(s[i + (x + k) % 4], k);
                }
            }
        }

        std::ranges::copy(res, s.begin());
    }

    static constexpr void inv_mix_columns(block_vw s) noexcept
    {
        block res{};

        for (int i : std::views::iota(0, 16) | std::views::stride(4))
        {
            for (int x : iota_word)
            {
                for (int k : iota_word)
                {
                    res[i + x] ^= gmul(s[i + (x + k) % 4], k + 4);
                }
            }
        }

        std::ranges::copy(res, s.begin());
    }

    static constexpr void bytes_xor(block_vw to, block_rvw other) noexcept
    {
        for (auto&& [x, y] : std::views::zip(to, other))
        {
            x ^= y;
        }
    }

    static constexpr block bytes_xor_ret(block_rvw x, block_rvw y) noexcept
    {
        block res{};
        for (int i : std::views::iota(0, 16))
        {
            res[i] = x[i] ^ y[i];
        }
        return res;
    }

    constexpr void add_round_key(block_vw block, size_t index)
    {
        bytes_xor(block, rnd_keys[index]);
    }

    static constexpr auto iota_word = std::views::iota(0, 4);
    static constexpr auto iota_byte = std::views::iota(0, 256) | std::views::transform([](int x) {return byte(x);});

    rnd_key_t rnd_keys;
};

解析

AES类通过size_t类型的模板参数提供了对不同轮数加/解密的支持（默认值为10轮），同时通过内联一个concept约束其轮数不小于1。

由于轮密钥存储等环节中利用了大量Rounds有关的参数，从编译器优化、运行效率、潜在应用场景等角度出发，笔者没有将轮数作为运行时参数。

encrypt等函数需要进行“遍历”时，笔者在其中大量应用了std::views::iota及其封装变形（iota_word/iota_byte）。
其相较传统for循环的优势有：

  • 调用语义、逻辑简洁统一（“一目了然”的iota_word）；
  • std::views::iota的循环是安全的（其类似不能被“打断”的迭代器，参考Python中range(x)的行为），从根源防止了循环体内临时修改变量等操作导致的bug；
  • 由于该循环确定（必定执行16次），因而编译器可以有更大的优化空间（const变量和各类编译器常量的应用同理）。

std::formatter相关

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
template<>
struct std::formatter<::byte> //F**king ADL...
{
    constexpr auto parse(std::format_parse_context& fpc)
    {
        return fpc.begin();
    }

    auto format(::byte b, std::format_context& fc) const
    {
        return std::format_to(fc.out(), "{:02x}", b.value);
    }
};


template<>
struct std::formatter<block_rvw>
{
    constexpr static auto hexify = [](::byte x) {return std::format("{:02x}", x.value);};

    constexpr auto parse(std::format_parse_context& fpc)
    {
        return fpc.begin();
    }

    auto format(block_rvw v, std::format_context& fc) const
    {
        return std::ranges::copy(v | std::views::transform(hexify) | std::views::join, fc.out()).out;
    }
};

目前（截至这篇Blog）本aes.h实现中没有提供自定义的窗口，仅使用format函数的部分“快速”复用来提供byte和block及类似类的格式化。

有趣的是ADL(Argument-Dependent Lookup)在byte的定义中“发威”了一番：由于全特化(Full Specialization)时使用了std::formatter声明之，此时填写其模板参数时会优先在namespace std（而非默认的全局空间）中查找byte，因而必须明确::byte方能正确特化之。
小趣事2.0：std::byte似乎在标准库中还没有std::formatter特化，连个unsigned char的forwarding都懒得干

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true