Git如何连接GitHub

第一步 配置git

1
2
3
4
5
6

git config --global user.name "Your Name" # 可以是任何名字
# 这里的Email可以是任何邮箱，但是只有在GitHub上配置过的邮箱（默认是登陆邮箱）
# 才能看到你的小绿块（活动记录）
# 同时GitHub提供匿名邮箱 [email protected]
# 可以避免邮箱
git config --global user.email "[email protected]"

可以看到git只配置了邮箱和名字，并没有密码之类的身份验证的东西。事实上，git并不做身份验证，只有git使用的SSH或HTTPS才可能需要身份验证。因为git完全可以在单机或局域网内运行，所以身份验证对于git来说并无必要。

不过GitHub需要知道你的身份，因为GitHub需要管理权限、付费等等必要因素，而git又是匿名的，所以需要使用一种身份验证方式来确认身份，如果你使用HTTPS进行clone操作的话，那么每次提交都会让你输入GitHub的用户名密码，所以可以使用SSH进行clone，这样我们可以用SSH来登录GitHub，通过下面的操作，GitHub会将某个SSH密钥对关联到你的账号，无需像HTTPS那样频繁输入用户名密码。

第二步 生成密钥对

注意：使用下面的命令时千万要注意输出中的Overwrite（覆盖）这个关键字，出现该关键字说明你已经有一个私钥了，就算无脑按回车（默认会跳过）也不要无脑按y继续。

1
2
3

# 这里的email并不一定要与上面的相同，同样也可以是任何邮箱
# 而且邮箱不会影响使用，随便编一个也是可以的，但是太多不好管理
ssh-keygen -C "[email protected]"

命令会询问你输入 passphrase，我们不管，直接回车就好。

默认情况下，ssh-keygen命令会在~/.ssh/目录下生成id_rsa和id_rsa.pub两个文件。

Windows下可以通过复制%UserProfile%\.ssh\到资源管理器访问文件夹，Linux下可以使用cd ~/.ssh访问。

也可以使用-f选项指定路径，如果指定那么则是path/to/name和path/to/name.pub两个文件。

第三步 将公钥添加到GitHub

前往上一步生成的目录，使用文本编辑器打开带有.pub后缀的文件，会看到一行文字，这就是要复制到GitHub上的SSH公钥。其类似下面这样

1

ssh-rsa AAAAC3...... [email protected]

复制该行内容到Github SSH and GPG keys 页面，点击 New SSH Key，Title随便输入一点什么，Key则为刚刚复制的那行文字。

第四步 配置SSH

如果在第二步生成密钥对时没有使用-f指定文件名，那么该步骤可以忽略，请直接到下一步。

有两种方法可以配置，使用其一即可。

• 第一种方法

  使用文本编辑器打开~/.ssh/config文件，在最后面添加如下行。

  1 2 3 4 5

  Host github.com HostName github.com User git IdentityFile path/to/your/private_key # 请将这里替换为你的私钥 IdentitiesOnly yes

  ~/.ssh/config文件为ssh使用的配置文件，在这里使用即可让连接到GitHub的命令均使用IdentityFile指定的私钥。

  这种方法是全局生效的，并且对第二种方法有隐性影响。

• 第二种方法

  在命令行中输入以下命令，注意路径不要有空格等特殊字符，不然引号转义很麻烦。

  1	git config --global core.sshCommand 'ssh -i path/to/your/private_key'

  这种方式也是全局生效的，不过如果使用了第一种方法配置后，这里的文件使用错误，则会默认使用第一种方法下的IdentityFile，而不会报错。

  如果去掉命令中的--global则可只对某个仓生效，这对使用多个GitHub账号的人而言会方便一些。

第五步 测试

输入以下命令

1

ssh -T [email protected]

如果出现下面的输出，那么就做对了。

1

Hi XXX! You've successfully authenticated, but GitHub does not provide shell access.

如果出现下面的输出，那么就是你的公钥没有配置对，需要重新从第二步开始检查。

1

[email protected]: Permission denied (publickey).

使用GPG签名提交

这里并非必选项，如果只需要连接到GitHub，这里可以不用看了。

在第一步我们发现我们可以随意填写名字和邮箱时，git的身份是很容易伪造的，在互联网下进行合作时，可以使用GPG对自己的提交进行签名，以避免其他人伪造自己的提交。对于初学GitHub的普通人而言，自然没人会伪造你，不过如果公司有要求，或者你意外出名了，就可以使用GPG的方式来签名你的提交。

GPG全程为GNU Privacy Guard，虽然直译为隐私保护，但目前它的主要用法是防止伪造身份。与实名制不同，这种方式下使用者身份只与一个私钥文件挂钩，而不与任何现实身份挂钩，只要私钥不泄露，身份就不会被伪造，同时也可以保证隐私。可以认为谁有这个私钥，谁就有这个身份。

这里的教程只教GPG的最基本用法，GPG的套路可以很复杂，但这里进行了尽可能的简化。

第一步 安装GPG

没什么好说的，apt、yum、brew 之类的命令install就行，Windows用户可以安装Gpg4win。不会可以去Google，这不是本文章的重点。

对于Windows用户，需要额外多执行一条命令以使得Git适配GPG，这是因为安装Git时，其自带的MinGW环境自带了一个MinGW版GPG，这会导致git优先使用自带的GPG，而非你安装的GPG，当然，你也可以通过调整PATH环境变量的方式直接使用git自带的GPG，应该也是一种可行的方案。Linux / Mac 用户不需要。

1
2
3

where.exe gpg
# 在获得了目录以后，需要将下面的字符串换成where输出的位置。
git config --global gpg.program "C:\Program Files (x86)\GnuPG\bin\gpg.exe"

第二步 生成密钥对

很遗憾，GPG并不能直接使用SSH的私钥，所以除了上面的SSH密钥，还需要额外管理一套GPG密钥。相比SSH密钥，GPG密钥的自定义项会比较多。

使用gpg --full-generate-key生成一个新密钥对，这会交互式地引导用户创建一个密钥对。

过程中会要求输入名字和邮箱，这里的邮箱必须是一个你能够收到邮件的邮箱，因为GitHub要使用该邮箱做认证。

中间可能需要你输入passphrase，和SSH私钥类似，我们也可以不输入直接点击OK（Windows，Linux下回车），这样可以创建一个无密码保护的密钥。虽然理论上无密码保护会导致黑客攻破设备时私钥被直接窃取，但以我的经验看，比起电脑被黑客攻击的概率，密码把未来的我自己防住的概率要高得多得多，所以除非有足够的准备，否则不建议大家输入密码，不然将来会后悔的。

剩下的去看GitHub去吧，没什么大坑了。

Telling Git about your signing key - GitHub Docs

Python中的排序方法

原生Python中有两种常见的排序方法，分别是 list.sort()与sorted()内置函数。

其中，list.sort()是列表的排序方法，是一个原地排序方法，使用尽可能少的额外空间，它只能在列表上使用。

而sorted()则会返回一个已经排好序的列表，其参数可以是任何可迭代对象，无论是列表、元组、字符串、range、字典、甚至使用函数生成的迭代器，只要其是一个可迭代对象，并且返回的对象可以比较，那就可以进行排序。其行为可以用以下代码模拟。

1
2
3
4

def sorted(iterable):
    tmp = list(iterable)
    tmp.sort()
    return tmp

所以当传入字典参数时，其返回的结果不会包括字典的value，而仅会包括字典的key。

排序的基本规则

排序算法

Python中的排序算法为TimSort，这种排序算法是一种稳定的排序算法，同时其保证最坏时间复杂度为$O(n log(n))$。而在数组已经有序时，其时间复杂度能低至$O(n)$​，即每个元素仅比较一次。

稳定意味着对于在比较中相等的值，在排序后依然保持原来的顺序不变。

排序会优先使用小于进行

Python在排序时，两个对象的比较会优先使用<进行比较，而如果<没有定义，则会尝试使用>进行比较，如果这两者都没有定义，那么就会抛出一个TypeError，表示不能对此进行排序。

排序的两个关键字参数

无论是list.sort()还是sorted()，其都接受两个关键字参数key和reverse。

key参数

key参数可以决定Python如何获取可比较的对象。当传入此参数时，Python比较时不会简单的进行 a<b这种方式，而是会进行key(a) < key(b)的比较，这可以让我们操作比较的细节。

例如，传入abs可以让Python按绝对值进行排序。

1
2

sorted([-1,-5,3,4])          # [-5, -1, 3, 4]
sorted([-1,-5,3,4], key=abs) # [-1, 3, 4, -5]

也可以通过匿名函数，让排序只对元组的某一个位置比较进行排序，而不是从头开始比较。

1
2
3

lst = [("Alice", 27), ("Bob", 26), ("Altman", 26)]
sorted(lst)                     # [('Alice', 27), ('Altman', 26), ('Bob', 26)]
sorted(lst, key=lambda x: x[1]) # [('Bob', 26), ('Altman', 26), ('Alice', 27)]

也可以巧妙的通过加符号而让一个升序，一个降序。

1
2

lst = [(1, 3), (5, 6), (1, 4)]
sorted(lst, key=lambda x: (x[0], -x[1]))  # [(1, 4), (1, 3), (5, 6)]

来自一个B站用户的想法：想让元组中第一个数字升序，第二个字符串降序。由于字符串不能使用负号反转比较结果，我们可以反转整数的比较结果，让第一个数字降序，第二个字符串升序，并且指示反转排序结果，可以看到这种取巧的方式也依然可行且为稳定排序。

1
2
3

lst = [(1, 'a', 'first'), (1, 'b'), (1, 'a', 'second'), (2, 'a')]
sorted(lst, key=lambda x: (-x[0], x[1]), reverse=True)
# [(1, 'b'), (1, 'a', 'first'), (1, 'a', 'second'), (2, 'a')]

其他使用方式

类似的，可以使用匿名函数对字典的某个键或者对象的某个属性进行排序，以让不可比较对象能够通过某种方式进行比较。

对于列表中被排序的每个元素，即使多次被比较，key函数也只会被调用一次。而显然，为了排序，key函数也至少会被调用一次。

Python标准库functools中有一个cmp_to_key函数，可以让大部分情况下自定义比较方法更简单，我们后文会提到。

注意事项

对于list.sort()而言，CPython中有一个实现细节：在排序过程中，会将列表的长度设为0，并将内容指针设为空。同时，在排序结束时，会检查列表是否被修改过。

如果排序时通过key函数访问原始的列表，打印该列表可以发现该列表的内容为空。如果此时在key函数中修改了列表，则可能会出现ValueError: list modified during sort，即使修改进行了list.clear()操作仍然会导致该问题。除非并未实际修改（如my_list.extend([])）,该行为可能会因为版本不同而不同，我们需要知道的只是如果排序中需要访问列表，我们需要访问列表的复制。

当然，不进行原地排序的sorted()不会受到该特性的影响。

reverse参数

reverse参数比较简单，就是反向排序，默认的排序方案是小的排在前面，通过指定reverse=True，可以让大的排在前面。和先进行排序，再进行反转不同的是，这种排序方式仍然是稳定的。

富比较

__cmp__与富比较方法

使用C语言的朋友们一定知道，在C中的各类比较并非通过任何运算符重载，而通常是通过一个cmp函数进行比较。我们以strcmp(char* str1, char* str2) 为例，其可能返回0、-1或1，分别代表str1 == str2，str1<str2, str1>str2。这种比较方式的优点是仅需要实现一个比较函数，就可以完成排序、寻找最大值等多种需要比较的场合，C++也于C++20引入了<=>（三向比较运算符）支持这种方式。

事实上，在Python2时代，Python也使用这种方式来重载所有比较运算符，然而这有一个很难注意到的问题：这里的比较结果只能为0、大于0或小于0，也就是说一个值和另一个值比较，不是大于或小于，就是等于，但是也有一些时候我们的数据不是全序的，会需要既不大于，也不小于，也不等于的比较，此时__cmp__方法就无能为力了。

上述情况中最常见的属于浮点数NaN，我们来看代码。

1
2
3
4
5
6
7

nan = float('nan')
print("nan == nan", nan == nan)  # False
print("nan > nan", nan > nan)  # False
print("nan < nan", nan < nan)  # False
print("nan >= nan", nan >= nan)  # False
print("nan <= nan", nan <= nan)  # False
print("nan != nan", nan != nan)  # True

类似的，还有SQL中的NULL比较等，也都不是cmp函数可以覆盖的范围。

所以在Python3中，Python不再使用__cmp__运算符，而是将其分为了6个富比较运算符。

• __eq__ 重载==运算符，a == b相当于a.__eq__(b)
• __ne__ 重载!=运算符，a != b相当于a.__ne__(b)
• __lt__ 重载<运算符，a < b相当于a.__lt__(b)
• __gt__ 重载>运算符，a > b相当于a.__gt__(b)
• __le__ 重载<=运算符，a <= b相当于a.__le__(b)
• __ge__ 重载>=运算符，a >= b相当于a.__ge__(b)

所以在Python中，我们也不是不可能可能见到a == b and a != b为真的情况，不过应该没人会写这种代码。我们也可能见到 a==b的返回值并非bool值的情况，而这种情况常常发生在numpy中。

标准库中的cmp_to_key

默认情况下，这个函数由C语言实现以提高速度，不过标准库中仍然提供了纯Python实现的fallback，该实现和C语言实现具有同样的行为，并且这个实现很简单，我们直接看实现源码。

（是的，C语言实现中也使用了对象和0的Rich Compare，而并非仅接受数字的比较，所以你可以在cmp函数中返回任何可以和0相比较的对象。）

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

def cmp_to_key(mycmp):
    """Convert a cmp= function into a key= function"""
    class K(object):
        __slots__ = ['obj']
        def __init__(self, obj):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        __hash__ = None
    return K

不知道该说啥，着实是简单了点，让我们看一个实际案例：让字符串升序排在前面，让数字降序排在后面。

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

from functools import cmp_to_key


def cmp(a, b):  # 字符串升序排前面，数字降序排后面
    # True 和 False几乎在任何情况下均可以当作 1 和 0 看待
    if isinstance(a, str) and isinstance(b, str):
        return (a > b) - (a < b) # True - False = 1, False - True = -1
    elif isinstance(a, int) and isinstance(b, int):
        return (a < b) - (a > b)
    else:  # 类型不同时，字符串要排前面就需要比其他类型小，所以返回-1
        if isinstance(a, str):
            return -1
        else:
            return 1


def main():
    lst = [3, 2, 1, 'a', 'b', 'c']
    lst.sort(key=cmp_to_key(cmp))
    print(lst)


if __name__ == '__main__':
    main()

静态链接符号重名导致的Abort

本质上来说，这就是编译时连接器ld没有发现符号名冲突，进而导致运行时链接器ld-linux-$(arch).so将同一个对象初始化了两遍，并且在该对象上调用了两遍析构函数，进而导致析构时引发double free。

需要注意的是，只有 *nux 系统中才有这种问题，Windows 系统中并不存在该问题，因为 Windows 切实处理好了所有被静态链接的库，会在内存中加载相同的副本。

由于涉及到链接器的细节，所以我将仔细区分编译式链接器和运行式链接器。

在编译 glog、gtest 时，你是否遇到过无端出现 Aborted的情况？根据退出消息，你的进程出现了 double free。然而，即使你把代码审查了个遍，仍然没有发现究竟在哪里发生了 double free。这时就需要考虑一下代码之外的问题，比如这可能是链接器导致的。

在编译时，你的主程序编译时链接了一个动态库。而你的主程序和动态库都编译时链接了一个静态库，而这个静态库又是由C++编写的，且拥有非static的、析构函数中需要调用free(void *)的变量，此时就有不小的发生 double free 以及内存泄漏的风险。而对于static变量，则只有内存泄露的问题，不过通常这种程度的泄露不会有任何问题。

为什么没有在编译时发现

在编译时链接器进行链接时，如果是 .o 文件，那么当符号发生冲突时，编译时链接器将会报告链接错误。然而，如果是.a 或 .so 文件，编译时链接器会忽略第一个符号以后的其他符号。

原因

C/C++均使用符号作为启动时期定位全局变量内存地址的方式，在程序执行运行时动态链接时，运行时链接器会将变量名与地址空间相关联，同时会执行对应动态链接库的初始化函数，并且在程序结束时会执行库的卸载回调函数。

对于 c 语言库而言，如果不对函数使用特殊标记__attribute__((constructor)) / __attribute__((destructor))，那么就没有额外的初始化函数及拆卸回调要执行。但是对于 c++ 而言，在加载动态库以及程序退出时，均会执行全局变量的构造及析构函数，并且每一个动态库都会执行一次。然而，由于编译时链接器仅链接了第一个符号，两次构造也均会在同一个内存地址上进行构造和析构，发生两次构造，只会导致内存泄露。然而，发生两次析构则会导致 double free。

以std::string为例，如果在cpp文件中写了全局变量std::string g_abort_str = "0123456789abcdef"，运行时动态链接器会为每个so中的该符号执行一次构造函数，然而，对于导出符号而言，即使同名符号处于两个不同的动态链接库中，最终仍然会映射到内存当中的同一地址，该地址会被初始化两次，显然，第一次初始化的使用的内存发生了内存泄露。而当程序退出，运行时链接器执行清理时，同样会对该地址执行两次析构函数，第一次析构函数当然可以正常释放内存，而第二次析构函数执行时，由于该内存已经在第一次析构函数当中释放，再次尝试释放该内存则会导致 double free。注意字符串长度如果小于16个字节，则会因为SSO优化而不会有该问题。

如何避免

下面我列举几种可能的规避方式。正确使用以下的任何一种方法都可以规避该问题。

1. 在编译选项中加入-Wl,--exclude-libs,<your_static_lib>

   -Wl为gcc 传给静态链接器ld的选项。gcc -Wl,aa,bbb,cde在gcc传给ld时，会变为ld aaa bbb cde这种形式。

   需要注意的是这里的lib名是需要lib前缀的。

   通常情况下，一个动态库链接静态库后，这个动态库也会继承静态库当中的导出符号（即非static符号），而使用该链接选项，则可以让动态库在链接静态库后将静态库中的导出符号改为非导出符号，相当链接时为静态库中的所有函数、变量均加上了 static。这样所有静态库符号都保存在本地，同样也不会被主程序或其他动态链接库劫持符号。

2. 在编译选项中加入-Wl,-Bsymbolic。（不推荐）

   这会使共享库中的全局符号优先绑定到本地(locally)，不会被主程序或其他共享库劫持。然而，这也会导致共享库出现一些其他的行为差异。

3. 使用dlopen

   使用dlopen打开动态库，例如dlopen("libconflict.so", RTLD_LOCAL | RTLD_LAZY);，RTLD_LAZY同样也会保证该 so 中的符号不被劫持。

哈希算法是什么？

哈希算法是一类将数据映射到固定长度输出的算法。它满足两个最基本的性质。

1. 输出长度是有限的
2. 同样的数据输入产生同样的输出。

这里的输出长度有限就像是的成语一样，无论故事长短，最终都会简化为四个字的成语。类似的，哈希函数也会生成固定长度的输出，比如 md5总是会产生128比特，也就是32个16进制字符的输出。而SHA-1算法则总是会生成160比特的数据。

常见哈希算法的分类

哈希算法根据用途不同，在多种不同的特征都有差异。其中我们经常看到的 md5、SHA-1 算法都属于加密哈希函数。

加密哈希

加密哈希(Cryptographic hash)在满足上述哈希算法的要求的情况下，又额外满足三个条件。

抗原像攻击、抗次原像攻击、抗碰撞性。

1. 抗原像攻击

   给定一个哈希值 $y$，很难找到一个消息$x$，使得 $h(x)=y$。

   例如，我给定一个文件的SHA-1值0880c6327abd62fdc94aa09d7ba1cd994ed90d12，除了暴力穷举以外，没有其他更有效的方法找到一个与其SHA-1相同的文件。

2. 抗次原像攻击

   给定一个消息$x_1$，很难找到另一个消息$x_2$使得 $h(x_1) = h(x_2)$

   例如，123456的SHA-1为7c4a8d09ca3762af61e59520943dc26494f8941b，同样除了暴力穷举外，很难再找到另一个文件使得输出也为这个值。

3. 抗碰撞性

   很难找到两个不同的输入 $x_1$和 $x_2$，使得 $h(x_1) = h(x_2)$

   例如，对于你电脑里的任意两个不同的文件，它们的 SHA-256 值都互不相同。

需要注意的是，对于任何哈希函数而言，碰撞都是必然的。根据我们小学就学过的鸽笼原理，十只鸽子放入九个鸽笼，那么必然有一个鸽笼有着一只以上的鸽子。像上面例子中提到的 SHA-1 算法，其输出长度只有160比特，而对于所有大小为 1KB 的文件而言，平均其每个哈希值就对应了$2^{8032}$个文件。这么多的文件，不可能找不到原像、第二原相，所以这里说的仅仅是没有比暴力穷举更快的方式找到两个消息，使它们的哈希值相同。

常见的加密哈希有 md5、SHA 家族，同时也有bcrypt 、blake、国密sm3等不太常见的哈希算法。不过MD5、SHA1目前都已经被证明为不安全的哈希函数，它们都不满足特定场景下上述的抗第二原像攻击的性质，目前已经逐渐被更新、输出更长的加密哈希取代。不过在假设没有被攻击的情况下（大多数情况下都可以做这种假设），这些哈希函数仍然可以用来校验文件的完整性。

非加密哈希

很多哈希函数并没有显著的特点，他们的目的仅仅是为了更均匀地输出哈希值。这些没有显著特点的，且不符合加密哈希要求的，统称为非加密哈希。

大部分编程语言中的哈希函数都是非加密哈希，这些哈希函数主要用于为 map 数据结构提供基础能力，所以快速是他们的主要目的。不过为了防止hash DoS 攻击，一些编程语言（比如 Rust），也采用了加密哈希，以降低一点速度为代价，避免哈希表因恶意攻击而进入最坏情况，导致拒绝服务攻击。

滚动哈希

哈希函数理论上可以接受无限长的输入，虽然常用的一些哈希函数可以接受的输入有限，但这些限制也远远超过了目前文件的最大大小。但是滚动哈希的输入是有限长度的。它有一个窗口，每当新数据进入这个窗口时，滚动哈希就会“遗忘”掉老数据，并产生一个新哈希值。例如为12345678计算窗口大小为4的滚动哈希，则会先计算1234的哈希值，然后计算2345、3456直到5678。

显然，普通的哈希函数也可以做到这一点，例如下面的代码。

1
2
3
4

import hashlib
data = b"1234567890abcdefghijklmnopqrstuvwxyz"
for i in range(len(data) - 8):
    print(data[i:i+8], hashlib.sha1(data[i:i+8]).hexdigest())

然而，普通的哈希函数，窗口每滑动一次，就需要将窗口内的全部数据重新计算。设窗口的大小为 $w$ 数据的大小为 $m$，显然无论如何，其时间复杂度都为$O(mk)$，而滚动哈希的设计，会让窗口向前滑动时，仅需要计算新输入的那部分数据，将时间复杂度缩小为了 $O(w+m)$。滚动哈希通常被用于进行字符串搜索，使用它可以在 $O(n)$ 时间内完成大量字符串的预过滤，提升后续的查找效率。

媒体哈希

大部分哈希函数的设计原则是相似的输入产生完全不同的输出，以尽可能达到让输出均匀分布、减少冲突的目的。但还有一些哈希函数是为搜索优化的哈希函数，相似的输入会产生相似或者相同的输出。而通过对比哈希值的相似性，我们可以间接得知输入的相似性。

例如，图片领域有直方图哈希、aHash、pHash、dHash，而音频领域也有音频指纹等。我们平常使用的以图搜图、听歌识曲等功能，就用到了这些技术。

GeoHash

GeoHash是对地理位置进行哈希。不过这种哈希函数与其说是哈希，更像是对地理位置按块进行编码。在划分好块后，每一个块都唯一对应一个哈希，而每一个哈希也唯一对应一个块。这些哈希值通常共享前缀越长，则地理上的位置就越接近，不过反之则不然，即使地理上的位置非常接近，也有可能拥有完全不同的前缀。使用这种哈希，可以让搜索特定的地理位置变得更加快速和准确。

z

最近先写一个简单的，之后再写复杂的。

在初学C语言时，我们往往被告知C语言的编译过程是预处理、编译和链接，那么这些过程都是什么呢？

下面以Linux下常用的gcc编译器举例说明我们平时见到的这些过程都是什么。

gcc原名GNU C Compiler，后改名 GNU Compiler Collection，下面的介绍也能让你明白为什么gcc换了名字。

预处理

我们先写一个入门C语言程序hello.c。这里puts的功能与printf类似，但是其只能输出纯字符串，不能像printf那样输出其他变量，使用puts代替printf是因为printf相关的优化较多且无法关闭，实际操作和理论一致性较差。

1
2
3
4
5
6
7
8

#include <stdio.h>

#define OK 0

int main() {
    puts("Hello, World!\n");
    return OK;
}

在C语言中，一些以#开头的行，被称为预处理指令，它们通常没有任何缩进，可以出现在文件中的任意一行，一些指令会被预处理器处理，最后生成新的.i的文本文件，这些.i文件会实际上参与下一步 - 编译。

预处理指令主要有以下功能

• 处理包含指令。上面代码中相当于将 stdio.h内的所有内容粘贴到到#include所在的行并删除该行，当然如果stdio.h中也有#include指令那么它也会被处理，直到没有该指令。
• 处理宏。例如将上面代码中的OK替换为0
• 处理条件编译指令#if、#ifdef等
• 更改编译器的行为（如字节对齐）

需要注意的是，预处理器并不会处理所有的预处理指令。有一些虽然定义上是预处理指令，但实际上会在编译阶段起作用，比如#pragma指令通常在编译期生效，在.i文件中你仍然可以看到这些指令。

汇编

通常C编译器并不直接从C代码生成机器指令，而是会有一个生成汇编代码的步骤，再通过汇编器将汇编代码编译为机器代码。这种方式方便了程序员使用内联汇编。由于C编译器生成的汇编代码有缩进格式，所以往往能见到使用多行内联汇编时会在\n后加\t（不加也一样）。该阶段生成的代码人类仍然可读。查看改代码可以发现头文件的大部分内容都已经消失，只剩下实际使用的puts这一个函数的名称了。

编译

汇编器会将刚才生成的汇编代码转换为机器可执行的代码。它会生成.o文件，此时该文件人类已经不可读，但其仍然和汇编文件基本对应，可以使用objdump工具查看其内容。

链接

链接是生成可执行程序的最后一步，它被用于处理符号引用。我们平时使用的printf、puts均会在此处被处理。链接分为动态链接和静态链接，通常我们使用的都是动态链接方式。

动态链接需要分别在两个阶段进行：编译时与运行时（这里说的编译是指源代码到生成可执行文件的整个流程，通常编译指的都是这个流程）。编译时的链接用于指定某个符号在哪个动态库中，而运行时链接则为真正在内存中装载函数和变量。

原子计数、缓存争用与性能问题

操作系统会在什么时候进行线程切换

想必熟背八股的朋友们都知道，操作系统进行线程切换时无非是两种情况：线程时间片用尽和线程主动让出执行权。

线程主动让出执行权时包括等待锁、等待IO操作或者是单纯的sleep，这里我们主要讨论的不是这个问题。

而操作系统是如何知道线程的时间片用尽的呢？实际上，操作系统是根据时钟中断来确认时间片是否用尽的。时钟中断的触发频率通常为100-1000Hz，这在Linux系统中由编译时决定，可以使用zcat /proc/config.gz | grep CONFIG_HZ来查看时钟中断的频率。

比如我的WSL，获取到的结果为

1
2
3
4
5
6
7

qy@localhost ~/test_c$ zcat /proc/config.gz |grep CONFIG_HZ
# CONFIG_HZ_PERIODIC is not set
CONFIG_HZ_100=y
# CONFIG_HZ_250 is not set
# CONFIG_HZ_300 is not set
# CONFIG_HZ_1000 is not set
CONFIG_HZ=100

这代表我的电脑的时钟中断频率为100Hz，也即每秒钟会有100次时钟中断。操作系统会每秒会进行100次的时钟处理，这其中包括更新系统时间、检查线程时间片是否用尽，如果用尽则调度线程、更新一些系统计数（如load average）等等操作。

CPU会在什么时候处理中断

中断分为硬中断(Hardware interrupt)和软中断(Software interrupt)，顾名思义，硬中断是由计算机的外围硬件引发的中断，而软中断则是由软件自身引发的中断。而时钟中断则属于一种硬中断。

硬中断

由于硬中断并非由CPU内部产生，其到达的时机不固定，CPU不能同时处理指令和中断，所以CPU会将硬中断暂存，每当执行一条指令前，CPU会检查中断寄存器，如果发现有中断则会执行中断处理程序。

这里我们可以看到CPU的指令执行本身是原子的，一条指令过程中并不会被硬中断打断，也就意味着不会被操作系统调度。

软中断

软中断即为程序通过指令触发的中断，除了通过int指令手动调用中断外，其他指令也可能会引起软中断，比如内存访问引起的缺页中断，除法指令引起的除0中断等，这些中断都在指令执行中发生，而具体如何处理取决于操作系统和程序设计。

多核下的竞争冒险

我们来看一段在x86上的C代码，如无特殊说明，这些代码都采用gcc -O2编译。

多核读写同一个变量

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

#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
// TOTAL 这个数字在我的i7-7700HQ上大部分时间能跑完示例，如果你的CPU性能太好可以酌情加一些
#define TOTAL (100000000)
__attribute__((aligned(4))) static uint32_t counter = 0;

void *add_addl(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 一条汇编指令，没有锁，也没有原子计数
        asm("addl $0x1, %0":"+m"(counter));
        asm(""); // 空指令
    }
    return NULL;
}

int main() {
    pthread_t t1;
    pthread_t t2;
    pthread_create(&t1, NULL, add_addl, NULL);
    pthread_create(&t2, NULL, add_addl, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("end thread t1 and t2\n");
    printf("counter = %u\n", counter);
    return 0;
}

在执行的最后，其会有什么结果呢？刚刚我们知道，CPU在执行单条指令时不会被操作系统中断，那么结果会是counter = 200000000吗？不幸的是，在大多数CPU下，其结果不会是这个数字，和所有常见的竞争冒险类似，它的结果也是比200000000小的。但如果addl指令是不会被操作系统中断的，那么还有什么会是导致竞争冒险的原因呢？

显然，是多核CPU的导致了这个问题。我们知道，多核CPU是不共享L1、L2缓存的，这样就会导致虽然每个核心上计数器都是原子的，但是由于缓存的不一致，导致最终加起来的总数不一致。不过在单核CPU下，或者是使用某些方式将线程限制在仅在一个核心中运行时，则不会有这种问题。

那么，是因为使用了过期的缓存行吗？将上面的的代码略作修改，修改为下面的代码。

多核读写同一缓存行的不同变量

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

#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
// TOTAL 这个数字在我的i7-7700HQ上大部分时间能跑完示例，如果你的CPU性能太好可以酌情加一些
#define TOTAL (100000000)
// aligned(64)保证其必然在同一个缓存行内，虽然不写大概率也会在同一个缓存行内
__attribute__((aligned(64))) static uint32_t counter[2] = {0};

void *add_addl_1(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 和上面一样，但是这是在同一个缓存行内的两个counter
        asm("addl $0x1, %0":"+m"(counter[0]));
        asm("");
    }
    return NULL;
}

void *add_addl_2(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 同一个缓存行内的另一个计数器
        asm("addl $0x1, %0":"+m"(counter[1]));
        asm("");
    }
    return NULL;
}

int main() {
    pthread_t t1;
    pthread_t t2;
    pthread_create(&t1, NULL, add_addl_1, NULL);
    pthread_create(&t2, NULL, add_addl_2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("end thread t1 and t2\n");
    printf("counter[0] = %u\n", counter[0]);
    printf("counter[1] = %u\n", counter[1]);
    return 0;
}

运行这段代码，我们会惊讶的发现，其运行结果为两者都是100000000，这可以证明CPU并非是使用了过期的缓存行数据。这里我们就要清楚缓存刷新原理与CPU指令执行的局限性。

即使CPU的单个指令看似是原子的，但是CPU实际上仍然不能直接操作主存，addl指令在实现内部仍然是读内存-增加-写回内存三步走，这也就可以解释为什么单指令多核多线程的不一致了。

缓存争用与总线锁

MESI 协议

如今CPU的缓存刷新方式是使用MESI协议，MESI 协议是 4 个状态单词的开头字母缩写，用于标记缓存行的四种不同状态，其含义分别为：

• Modified，已修改：数据已被该核心修改，但还未写回主存（共享区域）。
• Exclusive，独占：其他核心的缓存中没有该数据，CPU可以随意对该缓存行进行读写。
• Shared，共享：其他核心的缓存行中也有该数据，但所有核心均未对该缓存行的数据进行修改。
• Invalid，已失效：其他核心写入了该数据，这个缓存行的内容已经被修改过了。

现在让我们来看看MESI协议下，上面两种情况是CPU是如何工作的呢？

假设我们的counter的起始地址总是 0x1000，这样可以简化我们的部分讨论，并且和实际情况相差不大。

• 多核读写同一个变量

  由于CPU0和CPU1都需要使用0x1000的数据，我们几乎可以断定在0x1000所在的缓存行中几乎不可能有Exclusive状态的时间。

  1. CPU1等待0x1000缓存行为Shared，读取，寄存器中为0

  2. CPU2等待0x1000缓存行为Shared，读取，寄存器中为0

     注意到此时CPU1和CPU2同时读取了同一个变量，目前其内部的寄存器值也相同

  3. CPU1为该寄存器+1，CPU2也为该寄存器+1

  4. CPU1将增加后的数值1写回0x1000，此时CPU1的缓存行为Modified，CPU2的缓存行为Invalid，内存中值为1

  5. CPU2等待缓存行刷新为Shared，并将增加后的数值1写回0x1000，此时CPU2的缓存行为Modified，CPU1的缓存行为Invalid，内存值仍然为1

  由此可见即使CPU只会写Shared的缓存行，仍然会出现竞争冒险问题，因为多核CPU的读写通常是不会被串行化的，这也就导致了在指令执行过程中数据变为旧数据的情况。

• 多核读写同一缓存行内的不同变量

  1. CPU1等待0x1000缓存行为Shared，读取，寄存器中为0

  2. CPU2等待0x1004缓存行为Shared，读取，寄存器中为0

     注意到此时CPU1和CPU2同时读取了不同的变量，但它们都在同一个缓存行

  3. CPU1为该寄存器+1，CPU2也为该寄存器+1

  4. CPU1将增加后的数值1写回0x1000，此时CPU1的缓存行为Modified，CPU2的缓存行为Invalid，内存中值为1

  5. CPU2等待缓存行刷新为Shared，并将增加后的数值1写回0x1004，此时CPU2的缓存行为Modified，CPU1的缓存行为Invalid，内存值为1，其不会使用老值。

MOESI/MESIF 协议

可以看到，MESI协议下，每当数据脏时，都需要重新写回主存才能够让其他核心获得新数据，然而可以想到的是，CPU内部核心之间传递缓存行的速率会高于CPU与主存之间的通信效率。这也就诞生了MOESI和MESIF两个协议。

与MESI协议类似，但它们各增加了一个状态，增加的状态是对MESI协议的补充。协议的字母顺序仅仅是为了方便发音，其顺序并无含义。

• Owned，拥有：MESI协议下，当数据写入缓存时，其他核心的该缓存都会变为Invalid，这样就导致所有使用该数据的核心一个需要写回主存，而剩下的则需要从主存拿回数据。Owned可以保持其他核心的Shared状态，但Owned的核心可以写入该缓存，并在写入后在CPU内部广播该写入，其他核心无需从主存中再次获取，加快了缓存更新的速度。 AMD、ARM主要使用该技术。
• Forward，转发：与Owned类似，也是可以让缓存之间通信，而不通过主存的方式。但是F状态的是干净的缓存，该缓存由CPU内的L3缓存提供。这样当多个核心读取同一个内存地址时可以不用频繁访问主存。Intel主要使用该技术。

这里的优化对接下来的原理几乎没什么影响。

缓存争用带来的性能问题

上面的例子可以看到，CPU会频繁的争用同一个内存地址，这样在读取和写入时都会引起CPU等待缓存刷新，而这种等待会导致CPU无法执行其他任务，因为指令还未完成，操作系统也无法有效利用这些等待时间，是实打实的多占用了CPU时间。然而这种问题也是可以轻易规避的。显然，只要我们的变量不在同一缓存行，那么问题就迎刃而解。现代CPU的缓存大小通常为64字节，所以只要让变量间隔64字节，那么两个变量就不会映射在同一个缓存行，通常也不会被组相联映射在同一个缓存行里。

让我们先来实际测试一下CPU缓存征用带来的性能下降。我们对 多核读写同一缓存行的不同变量 这里的代码再稍作修改，改为下面的代码。

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

#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
// TOTAL 这个数字在我的i7-7700HQ上大部分时间能跑完示例，如果你的CPU性能太好可以酌情加一些
#define TOTAL (100000000)
// aligned(64)保证其必然在同一个缓存行内，虽然不写大概率也会在同一个缓存行内，64/4=16，所以我们申请17个int32，分别增加第一个和最后一个
__attribute__((aligned(64))) static uint32_t counter[17] = {0};

void *add_addl_1(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 和上面一样，但是这是在同一个缓存行内的两个counter
        asm("addl $0x1, %0":"+m"(counter[0]));
        asm("");
    }
    return NULL;
}

void *add_addl_2(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 同一个缓存行内的另一个计数器
        asm("addl $0x1, %0":"+m"(counter[16]));
        asm("");
    }
    return NULL;
}

int main() {
    pthread_t t1;
    pthread_t t2;
    pthread_create(&t1, NULL, add_addl_1, NULL);
    pthread_create(&t2, NULL, add_addl_2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("end thread t1 and t2\n");
    printf("counter[0]  = %u\n", counter[0]);
    printf("counter[16] = %u\n", counter[16]);
    return 0;
}

我们让两个线程分别使用两个缓存行，这样就可以尽量保证在每个CPU核心中，它们对缓存行都是独占状态，让我们来看看两个程序运行时间的差异。

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

# 无缓存行争用版本
end thread t1 and t2
counter[0]  = 100000000
counter[16] = 100000000

real    0m0.181s
user    0m0.336s
sys     0m0.000s

# ============================================
#有缓存行争用版本
end thread t1 and t2
counter[0] = 100000000
counter[1] = 100000000

real    0m0.290s
user    0m0.551s
sys     0m0.010s

我们可以看到缓存行争用在极端情况下带来了60%的额外性能消耗。

总线锁

一些熟悉X86汇编的朋友们可能注意到，我在所有的操作里都没有使用lock这一个X86指令前缀，前面我说的是X86无锁的情况下，如果带上了lock前缀，那么就可以保证是原子操作。然而同样的操作，由于需要提供额外的顺序保障，会有更多的性能消耗。

锁与原子操作

互斥器 (mutex)

CAS原子操作

FAA原子操作

LL/SC原子操作

强弱内存模型架构

更高效的多线程

由此可见，多线程中想要效率更高，除了减少锁的使用，还应该尽量避免将写入较多的多线程的数据放入同一个缓存行中。对于高负载线程，应尽量每个线程绑定一个CPU核心执行，这样可以避免线程颠簸，对于多核CPU而言可能还好，但对于服务器上的多个CPU而言，线程颠簸的代价相对就大得多，因为这意味着要完全从内存中转移线程常用的数据，CPU中的缓存将彻底失效。

本文以Linux系统为例，简析栈究竟是什么东西。其中的部分思想也可以用于其他操作系统。

栈是什么

函数运行的栈是计算机内存中的一种数据结构，用于管理函数调用和执行过程中的局部变量、参数、返回地址以及执行上下文。

但无论在什么情况下，栈都是一块内存。或许是一块物理内存，或许是通过mmap映射出来的虚拟内存，又或者是操作系统通过某种方式保留的内存。具体是什么需要依据操作系统和架构而定。

栈的内存分配原理

向上增长还是向下增长

有些教程和书中提到栈是向下增长的，堆是向上增长的，很多人不求甚解，就此记了下来，并且会根据猜测（说难听点就是臆想）去理解编译器怎么编译与程序怎么执行。实际上，栈的增长方向取决于CPU架构，而且仅仅是CPU架构中的一个小设定：加速栈存取的指令push会将SP增加还是减少。如果push减少SP，那么就是向下增长。

我们常用的x86架构的CPU，其push会减少rsp寄存器的值，所以其向下增长。而ARM架构的CPU，其并不自动维护栈，所以程序员完全可以选择编译向上增长的操作系统，而做到栈向上增长。类似的，IA64、MIPS架构则是默认向上增长。

为什么通常是向下增长

通过上面的解释，我们知道，栈增长方向并非什么金科玉律，其只是依赖于CPU架构而进行选择罢了。

而为什么我们最广泛使用的X86 CPU会使用向下增长的栈，这个我并没有查到具体的资料。 大体的说，这和早期的CPU与内存的设计有关，有人说是因为CPU要让程序知道有多少空间可以使用，也有人说是为了让程序总能以正数的偏移量访问其栈内部的数据。它并不是一个多么好或者多么坏的设计，向上增长或者向下增长不会对程序的易用性和安全性产生巨大的影响。而这么多年过去了，如此设计原因恐怕也只有其设计者才能知道了。

栈生长方向与栈帧布局

当然还是有人会把栈是向下生长的这种话作为金科玉律，这也是我写这篇文章的主要诱因。有些人不经过实测光凭想象就认为数组也是向下生长的，栈变量也是向下生长的。事实上，在函数内部，数组和栈变量如何布局与栈的生长方向完全没有关系，而是和编译器的实现有关系。是栈帧布局（stack frame layout）相关的内容了。但编译器的栈帧布局并不是我们主要讲的对象，所以这里我们只是做简单的说明。

对于数组而言，它并不是像CPU申请“我要一块栈空间”*n次，而是在函数编译时编译器就已经计算出来这个函数运行需要多少栈空间（这也是为什么C99前数组只能是定长的），并且在运行时提前为其分配对应的栈空间，也即将栈指针下移。

但无论栈是向下增长还是向上增长，数组的第N加一位的地址一定比数组的第N位地址要高。也就是说&arr[n+1] > &arr[n]恒为真，因为实际上arr[n]就是*(arr + n)的语法糖。而对于栈变量的布局，虽然大体上代码从前往后执行，编译器会从上往下排布栈变量，但是这也只是用于没有优化的阶段。如果开启了优化，栈变量连存在与否都不一定，更不要说内存的排布了。相信各位在使用gdb查看O2优化的程序的时候经常会看见<optimized out>，这就说明这个变量被优化没了。而对一些小的函数，其可能根本就没有使用到栈，而是仅仅在寄存器上就把所有的功能都完成并返回了，同样也没有栈变量与栈地址一说。

相关寄存器

X86-64

rsp寄存器

stack pointer. 栈指针寄存器。这个寄存器标识了函数的栈顶在哪里，栈地址中高于这个寄存器的地址空间都是受保护的区域，中断处理程序不会对该区域进行修改。而当你使用push/pop/call/ret/enter/leave等指令时，它们会自动调整该寄存器的值。

特别的，在Linux系统中，其下方的128字节区域内依然是受保护的区域，这被称为red zone。这种处理主要是为了方便优化，使得一些比较小的叶函数（不调用其他函数的函数）不需要使用额外的指令去调整rsp的大小，而可以直接使用那128字节的保留区域。不过Windows没有这种保证，rsp下的栈空间是不稳定的。

rbp寄存器

base pointer. 用于保存栈底指针，但是在任何非零的优化等级且无VLA（可变长数组）的函数内，该寄存器都将被视为通用寄存器使用，并不保存栈底指针。因为一个不含VLA的函数，其所需要的空间大小是固定的。仅需要根据栈顶指针的值和固定大小的偏移量，即可算出栈底指针的值。这样可以节省一次访存操作以及几个指令的开销，同时对正常运行的程序不会造成任何影响，所以即使是最低等级的优化也会将该寄存器用于通用寄存器。

如果在函数中使用了VLA，则依然会保存栈底指针，因为此时函数需要的空间大小不确定。此时需要将原rbp压栈，并将当前的rsp赋值给rbp，然后根据VLA的长度调整rsp的大小。函数返回时将rbp赋值给rsp，然后从栈中取出原rbp，这通常使用leave指令实现。

ARM64

Arm架构的CPU设计上相对来说就好多了，不再有那么多难记住的名字，取而代之的是所有的通用寄存器，都以Xn/Wn来命名。这让我们一眼就能看出哪些是通用寄存器，我们可以修改。

SP寄存器

类似于x86的rsp寄存器，同样有red zone保证。Apple产品会保证该区域不会被中断修改。

Linux 不知道。

我才不会去在ARM上玩Windows……

FP寄存器(X29)

Frame Pointer. 类似于x86的rbp寄存器，同样可用作通用寄存器。

LR寄存器(X30)

存储函数返回地址的寄存器，相较于X86 CPU，这是对叶子函数调用的进一步优化。它甚至不需要访问内存保存PC(rip)了，而是直接将PC转移到LR寄存器，能节省一些内存访问的开销。

为什么栈内存不设计为固定大小

猜测是因为需要支持在程序运行过程中动态调整栈的最大大小，所以没有将其在启动时就设定为固定大小。

但是除了主线程外，其他线程的栈为固定大小。

不同操作系统也有不同的做法，似乎Windows也会自动扩展，但总的来说，这不应该是一个可以假设的前提。

栈安全

与栈相关的漏洞

栈相关的漏洞较为基础，其有一些共同的特点：不正确的内存访问。这其中包括不正确的使用scanf, (f)gets,str(mem)cpy等函数，错误使用数组指针等。不过随着编译器的保护越来越多，静态代码检查越来越完善，很多可能产生漏洞的代码都会产生编译警告，而在生产环境下通常会使用-Wall选项将警告全部转换为错误强迫程序员修改该问题代码。

在计算机设计早期，内存页还不能设置执行权限的时候，栈内代码也可以执行。通过精心编排写入栈中的内容，可以做到任意代码执行，后来有了单独的执行权限，这种风险也就得以消除。

来自gcc的栈保护功能

然而，并非所有的风险都能被静态编译保护消除，仍然有许多风险不能在静态检查时被暴露。为此，gcc设计了栈保护器功能。该功能默认会在gcc认为可能产生漏洞的地方添加一层保护，无论优化级别如何，该选项始终会打开，可以通过-fno-stack-protector选项关闭检查。也可以通过-fstack-protector-all来对所有函数启用该检查，但需要注意的是该检查会堆运行时性能有一定影响，如果不是特别注重安全的情况下仅需默认栈保护即可。

使用Canary进行栈保护

gcc栈保护的原理是选取一个canary值，在函数运行时将其压入栈中，当函数即将返回时，对比栈中的canary的值与之前选取的canary值。如果不同则说明栈被破坏，将会调用__stack_chk_fail终止程序。

Canary的选取

在X86-64架构Linux系统下，gcc11.4版本会选取%fs:40作为canary的值。在Linux下，fs寄存器被glibc用于存储指向TLS(Thread Local Storage)的指针，而其再偏移40字节后则是一段随机值。每个程序每次启动时都不一样，而由于溢出攻击的原理，攻击者往往不能得知该值的内容，所以能够有效检测里用缓冲区漏洞的攻击。

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

/* from glibc    sysdeps/x86_64/nptl/tls.h   2023/09/10*/
typedef struct
{
  void *tcb;     /* 0-8 bits */	/* Pointer to the TCB.  Not necessarily the
			   thread descriptor used by libpthread.  */
  dtv_t *dtv;     /* 8-16 bits */
  void *self;     /* 16-24 bits */		/* Pointer to the thread descriptor.  */
  int multiple_threads;/* 24-28 bits */
  int gscope_flag;     /* 28-32 bits */
  uintptr_t sysinfo;   /* 32-40 bits */
  uintptr_t stack_guard;/* 40-48 bits <==> %fs:40 <==> %fs:0x28 */
  uintptr_t pointer_guard;
  unsigned long int unused_vgetcpu_cache[2];
  /* Bit 0: X86_FEATURE_1_IBT.
     Bit 1: X86_FEATURE_1_SHSTK.
   */
  unsigned int feature_1;
  int __glibc_unused1;
  /* Reservation of some values for the TM ABI.  */
  void *__private_tm[4];
  /* GCC split stack support.  */
  void *__private_ss;
  /* The lowest address of shadow stack,  */
  unsigned long long int ssp_base;
  /* Must be kept even if it is no longer used by glibc since programs,
     like AddressSanitizer, depend on the size of tcbhead_t.  */
  __128bits __glibc_unused2[8][4] __attribute__ ((aligned (32)));

  void *__padding[8];
} tcbhead_t;

不过这个值也并非所有位都是随机的，这和最常发生的栈溢出的原因有关：通常是不正确/不安全的字符串函数使用与意外/精心配置的错误字符串导致的。

除了写越界的任意代码执行很危险外，读越界导致栈中的敏感信息泄露同样很危险。所以另一种canary的思路是使用固定的字节组合00 0D 0A FF (NUL CR LF EOF) (\0 \r \n \0xff)作为Canary，虽然如今并没有看到其实际使用，但仍然为现在的栈保护提供了思路。使用它们作为canary时，虽然不能防止精心构造的写越界攻击，但是可以防止大多数的字符串函数读越界，字符串操作函数将会在遇到其中之一时停止。而glibc也利用了这一点，其stack_guard并非完全随机，在glibc的实现中，其低位总是0。这样可以缓解攻击者利用不正确的字符串处理函数获取canary后，再构造能特定于栈溢出攻击的串。

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

/* sysdeps/generic/dl-osinfo.h#L22-L48 */
static inline uintptr_t __attribute__ ((always_inline))
_dl_setup_stack_chk_guard (void *dl_random)
{
  union
  {
    uintptr_t num;
    unsigned char bytes[sizeof (uintptr_t)];
  } ret = { 0 };

  if (dl_random == NULL)
    {
      ret.bytes[sizeof (ret) - 1] = 255;
      ret.bytes[sizeof (ret) - 2] = '\n';
    }
  else
    {
      memcpy (ret.bytes, dl_random, sizeof (ret));
// 区分大小端的宏，其目的就是让低位为 00 防止被str类函数读出内容
#if BYTE_ORDER == LITTLE_ENDIAN
      ret.num &= ~(uintptr_t) 0xff;
#elif BYTE_ORDER == BIG_ENDIAN
      ret.num &= ~((uintptr_t) 0xff << (8 * (sizeof (ret) - 1)));
#else
# error "BYTE_ORDER unknown"
#endif
    }
  return ret.num;
}

不同系统、架构的区别

然而上面提到的canary仅面向X86-64 CPU。在arm架构上，这种保护有着不同的实现方式。其值被静态编译进二进制文件当中，而非从TLS中读取。 Windows上的msvc同样也支持类似原理的栈保护功能。

操作系统中针对栈的保护

操作系统中也有针对栈溢出相应的保护。与编译器相比，操作系统提供的保护是对整个栈空间的保护。虽然实现原理上各不相同，但本质都是不允许栈顶的一部分空间可读写，以此在栈溢出时让程序直接停止工作，而不是出现内存数据泄露或任意代码执行的风险。

栈保护页／栈保护空洞

以Linux内核的实现为例。在栈向下生长时内核总是额外要求1MB的空间，虽然额外的空间不会被映射，但是当检查时如果没有这1MB空间的空余，那么则会直接返回-ENOMEM，程序segmentation fault。

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

// mm/mmap.c  @expand_downwards
/* Enforce stack_guard_gap */
int expand_downwards(struct vm_area_struct *vma, unsigned long address) {
    // ...
    prev = mas_prev(&mas, 0);
    /* Check that both stack segments have the same anon_vma? */
    if (prev) {
        if (!(prev->vm_flags & VM_GROWSDOWN) &&
            vma_is_accessible(prev) &&
            (address - prev->vm_end < stack_guard_gap))
            return -ENOMEM;
    }

    if (prev)
        mas_next_range(&mas, vma->vm_start);
    // ...
}
/* enforced gap between the expanding stack and other mappings. */
// 4KB page size，256*page_size = 1MB
unsigned long stack_guard_gap = 256UL<<PAGE_SHIFT; // #define PAGE_SHIFT 12 

Windows则是以不可读、不可写、不可执行的页面放在栈顶来保护栈溢出的情况。

地址随机化

现在操作系统使用地址随机化来缓解和地址有关的攻击。在没有地址随机化之前，函数的栈、堆、系统调用等映射均是固定的。其他的库的映射也相对较为固定。有潜在的被利用风险。 Linux内核早在2.6版本就通过引入地址随机化的方式来缓解这一攻击风险。简单地说就是让这些固定位置的映射的地址都有一定随机程度的起始位置偏移，使得攻击者更难预测需要利用的数据的位置。这缓解了一系列任意代码执行漏洞及内存敏感信息泄露漏洞等风险。

为什么生产中不应该打印函数指针

让外界知道运行时的函数指针是一个非常危险的行为。如果打印了某个函数指针，则代表该动态链接库、或者该程序内的其他指针都有可能被计算出来。尤其是对于一些公共库的函数，更应该注意。因为攻击者不一定能获取到内部的二进制文件，但公共的二进制文件，比如glibc，是很容易获取到的。一旦该库中的函数指针被打印，那么就很容易计算出该库中的其他函数指针的位置，地址随机化就没有缓解攻击的功能了，此时配合缓冲区溢出漏洞，可以构造出return to glibc攻击，而由于glibc中含有非常多可以用于攻击的实用函数，故该行为非常危险。

Redis为什么不能在Windows上工作

因为Redis虽然使用ANSI C编写，兼容所有编译器版本，但是其调用了只有*nix系统才存在的fork系统调用，而Windows上没有这个调用。

为什么Redis需要fork

Redis作为非常快速的内存数据库，也需要持久化保存数据到硬盘的能力。如果单纯凭借自己实现，就会产生很多竞争或者数据一致性、或者是保存时不得不暂停写入（甚至读取）的问题。而使用fork系统调用，就可以充分利用fork的COW（写时复制）技术来加速。

本文旨在记录Linux下C/C++常见的内存错误。

SIGSEGV

段错误，最常见的内存错误，是由于使用错误的方式访问内存导致的，常见的错误方式有下面几种。

1. 解引用空指针，这是最可能发生的段错误，在有core dump文件时也很容易定位，看到fault addr时0时即可基本确认该问题是引起的。

   然而需要注意的是，解引用空指针并非绝对不可行的，之所以空指针指向空而不是虚拟内存的起始位置，是因为大部分情况下系统并未提供虚拟地址0附近内存区间的映射，如果一定要映射，在有root权限的情况下是可以通过mmap实现对空指针的映射的。

   1 2 3 4

   int main() { int *p = NULL; *p = 23456; // segmetation fault }

2. 解引用值为未被映射的地址的的指针。通常是未初始化的指针变量造成的野指针导致的。

3. 尝试修改不具有写权限的内存。

   1 2 3 4

   int main() { char *str = "This is a static string"; str[0] = 't'; // segmetation fault }

4. 未开启栈保护时，发生栈溢出的情况。此时函数return时会由于栈中存储的caller地址错误而大概率产生segment fault.

SIGABRT

程序终止，这个信号通常是由程序自身发出，编程人员也可以通过手动调用abort()函数来为本进程产生这个信号，这个信号结束的程序通常是在运行时检测到的错误。常见的错误原因有下面几种。

1. double free，即free已经free过的指针，glibc检测到堆内存中的double free会直接调用abort()终止进程。

   1 2 3 4 5 6 7

   #include<malloc.h> int main() { void *ptr = malloc(100); free(ptr); free(ptr); // Aborted }

2. stack smashing，栈损坏，当开启了gcc的栈保护功能时，gcc在每次函数退出时都会尝试检查栈中的数据是否被修改，如果被修改则会终止程序，避免栈溢出造成更大的问题。

   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

   #include <stdio.h> #include <string.h> #include <assert.h> void print_hex(void* data, size_t len) { char* buf = (char*)data; for (int i = 0; i < len; i++) { printf("%02X ", (unsigned char)buf[i]); if (i % 16 == 15) { printf("\n"); } } } int read() { char buf[10] = {0}; printf("buf = %p\n", buf); print_hex(buf, 80); printf("\n"); strncpy(buf, "0123456789A", 11); print_hex(buf, 40); // aborted，因为libc检测到了栈损坏。 return 0; } int main() { int res = read(); printf("res = %d\n", res); // 不会被打印，已经aborted了 }

3. 堆内存结构损坏。当malloc使用的元数据被修改后，其检查到无法进行正常内存管理时会释放内存。

4. assert失败，断言失败也会产生该问题。

   1 2 3

   int main() { asset(0 == 1);// false, aborted }

SIGBUS

在x86 CPU上这种信号并不常见，但可能会在ARM CPU上出现。

1. 非对齐的原子内存访问，例如ldaxr，stlxr两个指令，在未对齐（寄存器为x时为8字节对齐，w为4字节对齐）的情况下会产生该信号，其和系统是否允许对齐无关。

   1 2 3 4

   :main ldaxr x0, =0x12345677 # 这里会产生sigbus，因为有非对齐的原子内存访问 ldaxr x0, =0x12345678 # 这里会产生段错误，因为对齐了，但是虚拟内存里没有这个页，当然如果事先做了map就没问题。

2. 非对其的指令访问。ARM指令集为等长的，均为4字节，当使用b类指令跳转到一个没有四字节对齐的地址也会产生该信号，通常这在C面向对象编程时错误的修改函数指针有关。不过在X86上可能会表现为Illegal Instruction，因为X86架构并非等长指令，即使不对齐也可以执行指令，但大概率这个指令是没见过的指令。

   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

   #include<stdio.h> #include<stdint.h> void function() { printf("做点什么"); return; } uint64_t counter[8] = {0}; void(*func_ptr)() = NULL; int init() { // 不相关代码... func_ptr = function; // 不相关代码... return 0; } int somthing_counter_add() { // 这里其实是对counter中某个元素的自增操作，但是由于编译器内存布局具有一定 func_ptr++; } int main() { init(); somthing_counter_add(); func_ptr();// sigbus }

什么是RSA

简单地说，RSA就是一种非对称加密算法，它组成了今天计算机网络安全的基石。每个人的浏览、消息、支付等背后，都有RSA的身影。虽然其有很多竞争者，但直到如今，RSA依然是主流的非对称加密方式。比如B站的证书就是基于RSA的。

本文旨在让已经对非对称加密有一定了解的朋友了解RSA所使用的算法。如果你不了解非对称加密，本文并不能作为非对称加密的科普，可以去网上搜索看看其他的非对称加密相关的介绍。

RSA中使用到了许多定理与一些为被证明的假设，本文仅使用这些定理与假设，不深究其具体细节与证明。

函数与运算符号

部分函数虽然小学就学过了，但我们可能对它们的名字比较陌生，先看看这些函数的名字。

1. $gcd(m, n) $：计算m与n的最大公因数。
2. $lcm(m, n) $：计算m与n的最小公倍数。
3. $m \mod n$ 或 $m % n$：计算m除n的余数，也称作m模n，前者在数学中出现，后者在计算机程序中出现。
4. $a ≡ b (\mod c)$： a除c的余数等于b除c的余数，也被称作a与b模c同余。其中恒等号可换为等号。

如何生成一个RSA密钥？

1. 生成两个质数 p 和 q。

   p和q应该是随机的，并且差距应该足够大。

2. 计算 $N=pq$

3. 计算 $λ(N)$，$λ(N) = lcm(λ(p),λ(q)) = lcm(φ(p),φ(q)) = lcm(p-1, q-1)$

4. 选择一个数e，使得e与λ(n)互质。这里e是公钥指数。

5. 根据e与λ(n)，计算私钥指数d，满足 $ed \equiv 1\mod N$。

经历过这些步骤，我们得到了RSA加解密所需要的全部信息，将(N, d)作为私钥保存，而(N, e)作为公钥发布，而其中的p、q、λ(n) 均无需保留，可以抛弃。不过在大多数的RSA实现中，p和q都被保留在私钥文件中。

算法演示

我们使用一个较小的数来演示生成RSA密钥的方式。按照上面提到的方法生成一个演示密钥。

1. 选择p=257，q=379.
2. N = 257 * 379 = 97403.
3. λ(N) = lcm(256, 378) = 48384.
4. 选择e = 5.
5. 计算得到d = 9677.

可以验证，(5*9677) mod 48384 = 1.

其实这里我想选e=3，发现3居然是48384的因子，遂选择5作为公钥指数。

组装公钥E为(N = 97403, e = 5)，而私钥D为(N = 97403, d = 9677)。

公钥加密

当Bob持有Alice的公钥E时，如果它想给Alice发送一个秘密消息msg，需要先将m转换为一个不大于N的数字m，加密方法为计算 $c = m^e \mod N$，此时c就是密文，可以通过不安全的信道传送给Alice。

假设Bob要发送“hi”，那么可以将“hi”两个字母中的ASCII编码，计算可得“hi” = 104*256+105*1 = 26729，接下来算$26729^5 \mod 97403 = 46004$，此时49388即可发送给Alice。

私钥解密

当Alice接收到Bob的密文c时，Alice可以使用他的私钥解密。解密方法为计算$m = c^d \mod N$。

计算得到 $46004^{9677} \mod 97403 = 26729$，按照拼接ASCII的反向算法就可以得到消息msg为“hi”了。

解决消息过长

上面的例子中，Bob给Alice发送的消息仅有两个ascii字符，如果有三个，那计算得到的结果会超出N，虽然依然可以算，但是解密后的消息就不是原消息M了。比如Bob发送了消息“ack”，编码后为“ack” = 97*256**2+99*256+107 = 6382443. 继续计算密文得到c=6473，而解密后得到m为51248，和原消息不同。

解决方案非常简单：将消息分段，使每段可以满足m<N，再将分段一起发送或保存即可。

而实际应用中，非对称加密常被用于传递对称加密的密钥。RSA密钥中的N往往有2048bits或者更高的值，使用它来传递一个通常只有256bits的对称密钥是无需分段的。

密钥长度

密钥长度就是平时所谓的密钥的位数，比如256位AES就是说AES的密钥长度是256位。而RSA的密钥长度指的就是N的长度，即N有多少比特，或者说是N在二进制下的位数。

比如上文演示用的密钥N为97403，二进制为“10111110001111011”，即该密钥的位数为17位。目前被认为较为安全的是2048位及以上的密钥长度。

安全性

实践中保证RSA的安全性，需要很多细节工作。这里我们只讨论理想条件下，增加密钥长度是如何增加安全性的。从上面算法演示的过程中，我们知道，如果分解了N=p*q，那么相当于破解者也可以从第一步开始算得私钥指数d，此时该密钥对也就被破解了。目前，最行之有效的分解大数的方式是 Pollard rho算法，对于一个合数M，若其因子包括$m_1,m_2,…,m_k$，那么其期望的时间复杂度为$O(\sqrt{min(m_1,m_2,…,m_k)}$，而在实际的分解中，其时间复杂度往往能达到$O(\sqrt[4]{min(m_1,m_2,…,m_k)}$. 对于大数N=p*q 而言，其期望的时间复杂度为$O(\sqrt[2]{min(p,q)}) \leqslant O(\sqrt[4]{N})$。对于2048bits的RSA密钥来说，其消耗时间依然高达$t\cdot 2^{512}$，底线在$t\cdot 2^{256}$上，t为一个常数，所以目前在传统计算领域是安全的。

要注意的是，p与q不能过于接近，否则可以先计算$n = \sqrt{N}$，然后从n开始做减法计算因子。这种分解方法叫做费马因式分解。从上面的时间复杂度分析上我们可以知道，只要保证$|p-q|>\sqrt[4]{N}$即可让费马因式分解的期望时间长于Pollard rho算法。

量子安全性

秀尔算法（Shor’s algorithm）和量子计算机的出现似乎打破了RSA的安全神话。这项技术为因数分解提供了指数级加速，足以在多项式时间内分解N，然而其需要量子计算机有与RSA密钥位数相当的量子比特，而量子比特的增加是非常困难的。目前已知的具有最多量子比特的量子计算机为IBM Eagle（2021年），其拥有127个量子比特。

目前公开的对RSA的最佳量子破解也来自IBM，他们使用量子计算机成功分解了15=5×3.

不能被证明的安全性

事实上，RSA安全性的核心，也就是因数分解的困难性，并没有被证明。该问题是一个NP问题，可以在多项式时间内验证p*q=N，但不能在多项式时间内算出N的两个因子p和q.

P=NP这个问题至今没有答案，但RSA等非对称加密手段都是建立在P!=NP的基础之上的，由于没有人能拿出一个行之有效的破解方式，所以大家相信破解RSA是不可能的. 值得一提的是，一个调查显示，知道NP问题的人中，多数人相信P!=NP.

当然，即使哪天证明了P=NP，如果只有证明而拿不出有效的算法的话，我们或许依然可以焦虑地使用RSA等非对称加密手段.

工程实现

RSA生成的5个步骤中，第2，3，4步都很简单，然而第1步和第5步则需要特殊的算法实现。

本文会提供切实可行的实现方式，要求如下。

Windows 10及以上操作系统，Python >= 3.7，Python无需安装第三方库。

选择Python是因为其原生提供无限长度的整数运算，无需额外关注具体的大整数运算实现，同时具有较好的可读性。

对不了解Python的朋友，我在下方简单的介绍一下下文中使用的功能。

• a ** b： 计算a的b次方，等于$a^b$.
• pow(a, b, m)： 计算a的b次方模m，等于$a^b \mod m$.
• public_key = N, e： 将N和e”打包“进变量public_key中。
• N, e = public_key： 将N和e从变量”public_key“中解包出来。
• for var in range(n)：循环n次，var会从0赋值到n-1，不关心var的值时可以使用 _代替。
• random.randint(m, n)： 生成从m到n的整数，包括m和n.

Miller-Rabin 算法

演示中使用了两个小质数257和379，这两个数即使是使用纸笔的人类也能验证其并非合数。然而在实际应用中，我们面对的是$10^{308}$这种数量级的质数，仅凭试除法肯定是是不能判断其是否为质数的。此时就需要一个多项式时间的算法来判断该数是否为质数，也就是米勒-拉宾素性检验算法(Miller-Rabin primality test)。

米勒拉宾算法是一种概率性的检验算法，其并不能绝对判断某数是否为质数。但是在合理选择迭代次数的情况下，其错误率是可接受的。下面给出Miller-Rabin算法的Python实现。

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

def miller_rabin(n, k):
    # n必须为一个奇数
    if n % 2 == 0:
        return "composite"
    s = 0
    m = n - 1
    if m % 2 == 0:
        s += 1
        m //= 2
    d = (n - 1) // (2 ** s)
    # 找到 s > 0, d > 0 且 d 为奇数, 使得 2 ** s * d = n - 1
    # 由于 n 为奇数，所以 s 至少为 1，同时当 s 足够大时总能找到一个奇数 d 满足上面等式
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)  # 快速幂取余，相当于 (a ** d) % n
        # 定理1. 如果 n 是一个质数，对任意整数 x，当且仅当 x = 1或x = -1时，(x ** 2) % n = 1
        # 定理2. 如果 n 是一个质数，对任意整数 a，总有 a ** ((2 ** s) * d) = 1  (mod n)

        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == 1:
                return "composite"
            if x == n - 1:
                break
        if x != n - 1:
            return "composite"
    return "probably prime"

Miller-Rabin 算法给出了一个时间复杂度为$O(k\cdot \log^3n)$的算法，它能有效的检查一个数是否为质数，其中k为循环次数，log来自于快速幂取余的时间复杂度。而其将一个合数误报为质数的概率为$4^{-k}$，因此很容易将在线性时间内以足够高的准确度预测n是否为一个质数。OpenSSL中，k默认为20.

质数分布与大质数生成

一个显而易见的事实是，除了2和3，质数n必然满足 $n = 6k + 1$或$n = 6k-1$，其中k为正整数。

当生成一个n bits的质数时，实际上是在$[2^{n-1}, 2^n)$中找一个整数，验证是否为质数。

由于质数分布规律较为复杂，其生成时间具有较大的不确定性。不过，根据质数定理，对于一个自然数N，其前面的质数大约有 $\frac{N}{\ln N}$个。

那么，如果生成1024bits的质数，我们可以算得在$2^{1023}-2^{1024}$质数的密度如下。
$$
\frac{\frac{2^n}{\ln {(2^n)}}-\frac{2^{n-1}}{\ln (2^{n-1})}}{2^n-2^{n-1}} = \frac{2-\ln 2}{n\ln2} = 1.841 \times 10^{-3} = 543.12^{-1}
$$
可以看到，平均而言，每543.12个数中有一个质数。这个数字不是很大，所以即使暴力搜索也能比较快的搜索到。下面是具体的实现代码。

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

def gen_prime(n):
    # n为要生成质数的位数
    num = random.randint(2 ** (n - 1), (2 ** n) - 1)
    num = ((num // 6) * 6) + 1  # 6n+1 模式
    # 这里设置为5，速度会快很多，安全性上应该设置为较大的值，比如15以上
    while miller_rabin(num, 5) != "probably prime":
        # 如果不是质数，那就再生成一个
        num += 4  # 6n + 5 模式
        if miller_rabin(num, 5) == "probably prime":
            break
        num += 2  # 6(n+1) + 1 模式
    return num

测试CPU为i7-7700HQ，生成1024bits的质数，测试20次，平均消耗31.14秒。实际平均约10000个奇数遇到一个质数。和上面的计算相差较大，暂未知原因。

扩展欧几里得算法

第五步中，要求计算 de = 1 (mod λ(N)). 即计算e模λ(n)的乘法逆元。

变形这个算式，可以得到 $de = kλ(N) + 1$，其中d, e, k 均为正整数，e为已知数。

当然，可以从k=1开始，一个个计算符合的d，不过有更快的算法，也就是标题提到的扩展欧几里得算法。

扩展欧几里得算法，顾名思义，其由欧几里得算法扩展而来，而欧几里得算法就是辗转相除法。
$$
gcd(a, b) = gcd(b, a \mod b)
$$
而扩展欧几里得算法，则可以求解裴蜀等式（或贝祖等式）
$$
ax+by = gcd(a,b)
$$
求解裴蜀等式就是当 a, b 已知时，求解一对可以使等式成立的x, y.

我们将求解乘法逆元的算式代入，得到下面的式子。
$$
de-λ(N)\cdot k = 1
$$
接下来就可以使用扩展欧几里得算法求解d了。

1
2
3
4
5
6

def ex_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x, y = ex_gcd(b % a, a)
        return gcd, y - (b // a) * x, x

简单地说，ex_gcd返回的第二个值就是要求的私钥指数d.

自己生成一个密钥对

上文中给出了生成一个密钥对所需的全部算法。接下来我们可以自己生成一个可以使用的密钥对了。

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

def fmt_big_int(name, num):
    max_len = 30
    name += " = "
    indent = len(name)
    num = str(num)
    if len(num) <= max_len:
        return f"{name}{num}"
    num_l = []
    for idx in range(0, len(num), max_len):
        num_l.append(num[idx:idx + max_len])
    return name + " \\\n{}".format(' ' * indent).join(num_l)


def generate_key_pair():
    bits = 1024
    p = gen_prime(bits)
    q = gen_prime(bits)
    N = p * q
    lambda_N = math.lcm(p - 1, q - 1)
    e = 65537  # 通常e会选择65537，这几乎不会和lambda_N有公因数
    gcd_e = math.gcd(e, lambda_N)
    if gcd_e != 1:
        print(f"真不巧e和λ(n)有公因数{gcd_e}")
        return
    _, d, _ = ex_gcd(e, lambda_N)
    if d < 0:  # 可能算出负数来，算出来了就加上，避免私钥指数为负数。
        d += lambda_N

    print(fmt_big_int("N", N))
    print(fmt_big_int("p", p))
    print(fmt_big_int("q", q))
    print(fmt_big_int("e", e))
    print(fmt_big_int("d", d))

下面是我生成的密钥对。

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

N = 227442712852228682420414779319 \
    562687651643739341662796692929 \
    163922400267934787590621116694 \
    891760619327203004901144906832 \
    800095526049668470542778999323 \
    651897322671119077281968001372 \
    446392959926682893287212273771 \
    241722129942437331580897662308 \
    578666249068303886306662169412 \
    193217352311366461532975812852 \
    124193228404641158708725065274 \
    708644109118939811612576529812 \
    846988041909580026981490541567 \
    445743128463667379869830312310 \
    386152013370124058632684548068 \
    516907871220638110433917758192 \
    056516147025352893608425414982 \
    659378237947057838512573683719 \
    656010305302908753593858876575 \
    962355149895528849120178912224 \
    35170357514424413
p = 145051038077958860693796012628 \
    625876634665931949940050370449 \
    387104965384223153152471552741 \
    833745166885914511061893077670 \
    464028682608703752485689595048 \
    619321249150617970591218334362 \
    527527974241212468108567074763 \
    798879903619803151999405468786 \
    884736416473525334019578812862 \
    866293752484163777592143766285 \
    811404063
q = 156801851173231690833526980220 \
    070443094216022723233530479768 \
    612945390163310468787991953168 \
    708616715527769639602060536294 \
    556776062794179272183786104176 \
    586288917546573301530873029141 \
    344273752018571280068748133198 \
    532396742562461156175632492260 \
    503161905280147990066527029768 \
    573516310751136244023374550179 \
    197384451
e = 65537
d = 190701085970214780948194029687 \
    199134633227390280671539409439 \
    821132122232067634742277345047 \
    596048736317344478986189673473 \
    951588402832434845298468132701 \
    140909072444237503954165458831 \
    132479258250625219130145024089 \
    136405862952788979818580748948 \
    783095204026783321674032778570 \
    883886865579895128877382561243 \
    636791701404807498474376829463 \
    986075399201337437286982733483 \
    883375774171899112093369852188 \
    022751835849225142095728136344 \
    556634868177611264216881972938 \
    769052035843741360883732498917 \
    623652545912814027557437888976 \
    645651446879691031770018258055 \
    933872022471957950567451266956 \
    588963326221579878715175692341 \
    743003401618123

在实践中，不要使用文章里的方式生成密钥，这只是作为演示使用。虽然文章完整的复现了RSA的生成算法，但是很多地方并没有考虑。比如没有检查p和q是否过分相近，Miller-Rabin检查次数过少，没有使用安全的随机数生成器等等，它虽然是一个可用的RSA密钥对，但是并不具有足够的安全性。

尝试使用自制的密钥对进行加解密

现在我们已经具备生成一个RSA密钥对的能力了，可以尝试使用生成的密钥对进行数据的加解密。

注意：这种加解密方式是不安全的 ，不要在实践中使用这种方式。

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

def big_int_to_bytes(num):
    out = []
    while num > 0:
        out.append(num % 256)
        num //= 256
    return bytes(out)


def bytes_to_big_int(content: bytes):
    s = 0
    for i, byte in enumerate(content):
        s += byte * (256 ** i)
    return s


def encrypt(public_key, msg: bytes):
    N, e = public_key
    msg = bytes_to_big_int(msg)
    if msg > N:
        raise ValueError("msg过长，无法编码")
    cipher_text = pow(msg, e, N)
    return big_int_to_bytes(cipher_text)


def decrypt(private_key, cipher_text: bytes):
    N, d = private_key
    cipher_text = bytes_to_big_int(cipher_text)
    if cipher_text > N:
        raise ValueError("密文过长，无法解密，可能不是密文。")
    plain_text = pow(cipher_text, d, N)
    return big_int_to_bytes(plain_text)


def test_rsa():
    N = 227442...4413 # 真实数字在上面，这里太长就不放了
    e = 65537
    d = 1907...123
    msg = b"Hello, I'm Bob."
    print("msg = ", msg)
    cipher_text = encrypt((N, e), msg)
    print("cipher_text = ", cipher_text)
    decrypted_text = decrypt((N, d), cipher_text)
    print("decrypted_text = ", decrypted_text)

加密与解密的结果

1
2
3
4

msg =  b"Hello, I'm Bob."
cipher_text =  b'\x0f\x9b\t...@\xc5\xadc\x97\x9a' 
# 加密的密文比较长，就不全写了，可以自己复制测试
decrypted_text =  b"Hello, I'm Bob."

RSA特性

从上面的算法讲解，可以发现RSA有很多特性。

公钥与私钥的对称性

上文中，我们并没有对公钥指数e做出什么特殊要求，仅仅是看似随机的选取了65537这个数，它并没有成为公钥指数的必然性。而在加密和解密章节中，这种对称性则更加明显，除了变量名和报错信息有区别，它们完全是一样的。

任何与λ(n)互质的数都可以作为公钥e。而解密密钥d则是使用扩展欧几里得算法得到的。回到求解私钥的要求中。
$$
ed ≡ 1 (\mod λ(N))
$$
可以看到公钥与私钥时对称的，当把选取的数字作为私钥指数时，那么计算得到的就是公钥指数了。事实上，RSA三人组最初的论文中，选取的数字就是作为私钥指数，而计算得到的则为公钥指数。

但是，将选取的数字作为公钥具有一定的好处。选择一个很小的数字作为公钥指数，私钥指数就会非常大，这为破解增加了难度。

交换公私钥的安全问题

假如以d作为公钥指数，那么私钥指数e就只有65537了，此时如果知道d和N，就可以对e进行暴力破解。下面是对交换公私钥后成功的暴力破解。

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

def crack_unsafe_private_key(public_key, cipher_text):
    # 假设 Alice 加密的是以ASCII编码的明文
    N, e = public_key
    cipher_text = bytes_to_big_int(cipher_text)
    for d in range(3, 100000):
        probably_plain_text = pow(cipher_text, d, N)
        probably_plain_text = big_int_to_bytes(probably_plain_text)
        if probably_plain_text.isascii():
            print("破解出明文可能是: ", probably_plain_text, "d = ", d)
            return


def test_crack():
    # 对当前的公钥选择策略而言，交换公私钥后，其不能保证安全
    N = 227442...4413
    e = 65537  # e仅作为展示，此处假设它是隐藏的私钥指数
    d = 190...123 #让算出来的d作为公钥，此时不仅加密速度变慢，而且会不安全
    # 这里反向利用，将计算出来的d作为公钥指数，而e作为私钥指数
    cipher_text = encrypt((N, d), b"Hello, I'm Alice.")
    crack_unsafe_private_key((N, d), cipher_text)

运行结果如下

1

破解出明文可能是:  b"Hello, I'm Alice."  d =  65537

可以看到，2048bits的密钥很容易就被破解了。所以虽然公私钥具有对称性，但是并不能真的将随便一个数作为私钥指数。使用私钥加密，公钥解密并不能保证秘密消息的安全性。

数字签名

然而私钥加密依然有其用武之地。只有使用私钥加密的信息，其他人才可以使用公钥解密。利用这个特性，Alice可以将其要公布的明文信息与该信息被私钥加密的密文一起公布，这样任何持有Alice公钥的人都可以验证消息来自Alice。Alice的动作叫做签名(Sign)，而验证者Bob的动作叫做验正(Verify)。

1
2
3
4
5
6
7
8
9
10
11

def sign_and_verify():
    N = 2274427...413
    e = 65537
    d = 190...123
    msg = b"Hello, I'm Alice"
    cipher_text = encrypt((N, d), msg)
    print("msg = ", msg, "cipher_text = ", cipher_text[:10] + b"...")
    # 验证签名
    decrypted = decrypt((N, e), cipher_text)
    print("decrypted = ", decrypted)
    print("is decrypted == msg :", decrypted == msg)

函数输出如下。

1
2
3

msg =  b"Hello, I'm Alice" cipher_text =  b'\xd0@;2\x995X\x7f\x1e\x94...'
decrypted =  b"Hello, I'm Alice"
is decrypted == msg : True

而如果有人篡改了明文或者篡改了密文，那么解密后的密文与明文会不同，也就验证消息没有来自Alice。

在实际应用中，文件通常很大，通常总会超过密钥能加密的最长长度。而分段虽然可以，但是需要下载两个内容完全一样的文件，消耗一倍的流量。所以实践中，会先对文件求一个加密哈希（如SHA-256），然后对哈希值做加密，这样签名的体积就会小很多。验证者只要解密出哈希后，再对原文件做哈希，比对两个哈希值是否相等即可

明文填充

可以看到，如果我们把RSA明文转换为正整数加密，那么1显然是无法被加密的。为了避免这种情况以及增加安全性，出现了明文填充 (Padding)。Padding 的目的为尽可能提高安全性，以及提供验证消息是否被正确解密的方法。选择一个好的Padding可以增强RSA的安全性。

比如在交换公私钥的安全问题提到的暴力破解中，其实只要解码出任意一个字符是非ASCII字符即可跳过，这提高了破解速度，而一个好的Padding，必须要解码全部消息才能够验证消息是否被正确解密。

不过Padding不在本文的讨论范围内。

实践中使用RSA

这篇文章主要介绍RSA的实现及其算法，不会对如何使用RSA工具做赘述。但本文可以提供一些工具的简单介绍。

下面这些工具很多不止提供基于RSA的非对称加密，也有基于其他算法的非对称加密。

OpenSSL

这是世界上最主流的非对称加密软件，内置在许多操作系统中，Chrome浏览器完成HTTPS使用的也是OpenSSL的一个分支版本BoringSSL。

下面的命令可以在Windows上使用(PowerShell)，应该也适用于Linux及Mac。

1
2
3
4
5
6

# 生成一个1024bits的质数
openssl prime -generate -bits 1024
# 生成一个2048bits(3.1.10 默认)的RSA密钥
openssl genrsa 2048
# 生成一个2048bits rsa密钥，并以人类可理解的方式打印
openssl genrsa 2048 | openssl rsa -text

可以看到第三个命令打印了了 exponent1 和 exponent2，以及coefficient三个本文没有介绍过的值。

这三个值是从私钥计算而来，目的是加快私钥解密速度，并不对RSA算法起实际作用，删去它们不会对算法的正确执行造成任何影响，只是会慢一些。

PGP

PGP原本是一个使用非对称加密的商业应用程序，但随着时间进展，其已经变成了一套标准，被称作OpenPGP，有很多符合该标准的开源软件。

Windows平台有Gpg4win，这是一套软件，可以提供邮件、文件的加密与验证。

Android有OpenKeyChain，也可以较为简单的使用。

在线版本

也有一些网页提供了网页版RSA加解密，比如这个网站就提供了RSA生成与加解密的功能。