Yuan's blog

Linux虚拟网络设备-birdge

发表于 2021-07-30 更新于 2024-10-18 Disqus：
本文字数： 2k 阅读时长 ≈ 4 分钟

网络桥接

网桥是一种网络设备，它能够从多个通信网络创建一个单一的聚合网络，此功能被称为网络桥接。网络桥接不同于路由，路由允许多个独立网络互相通信，但各个网络仍然保持独立，而桥接是将多个独立网络连接成一个单一网络。

网桥工作于OSI模型的数据链路层，它基于以太网地址（而不是IP地址）转发数据包。交换机是一种常见的网络桥接设备，家用路由器内部一般也带有集成交换机。

Linux bridge

Linux bridge实现了802.1d标准的一个子集，Linux网桥比纯粹的硬件网桥更加强大，它不仅可以转发数据包，还可以进行过滤和流量调整等功能。

下面介绍一下Linux bridge的配置工具，然后利用树莓派上进行一个简单的桥接实验。

ip 和 bridge

iproute2程序包包含的 ip 和 bridge 命令可用于管理网桥。

基本命令

ip命令

创建bridge设备 br0
1
ip link add name br0 type bridge

将interface eth0添加到bridge br0

1	ip link set eth0 master br0

上面是以物理网卡 eth0 为例，但网桥中的设备不仅限于物理设备，tun/tap/veth/vlan/macvlan/macvtap/ipvlan/ipvtap 等各种虚拟设备均可添加到 bridge。

eth0 原本一端连接着外界物理网络，另一端连接着网络协议栈。一旦它接入了 br0，由外部传入 eth0 的数据包将被直接传递到 br0，而不再是网络协议栈。这样一来，为 eth0 配置IP就失去了意义，因为 eth0 另一端连接的只是一个虚拟网桥 br0，这是一个2层设备，它工作于数据链路层，仅基于MAC地址进行数据包转发，形象地说，也就是 eth0 现在只是相当于 br0 的一个 Port，把 br0 比作以太交换机，那么 eth0 就是 br0 的一个网口。

原本的网络结构：
eth0 连接着网络协议栈与外界网络

+-------------------------------------------------+
|                                                 |
|   +----------------------------------------+    |
|   |         Network Protocol Stack         |    |
|   +----------------------------------------+    |
|            ↑                     ↑              |
|............|.....................|..............|
|            |                     |              |
|            ↓                     ↓              |
|     +--------------+         +--------+         |
|     | 192.168.2.10 |         |        |         |
|     +--------------+         |   br0  |         |
|     |     eth0     |         |        |         |
|     +--------------+         +--------+         |
|            ↑                                    |
|            |                                    |
+------------|------------------------------------+
             ↓                                     
     Physical Network

之后的网络结构：
eth0 收到的外界数据包不再发给网络协议栈，而是虚拟2层设备 br0

+-------------------------------------------------+
|                                                 |
|   +----------------------------------------+    |
|   |         Network Protocol Stack         |    |
|   +----------------------------------------+    |
|            |                     ↑              |
|............|.....................|..............|
|            |                     |              |
|            ↓                     ↓              |
|     +--------------+         +---------+        |
|     | 192.168.2.10 |         |         |        |
|     +--------------+         |   br0   |        |
|     |     eth0     |<------->|         |        |
|     +--------------+         +---------+        |
|            ↑                                    |
|            |                                    |
+------------|------------------------------------+
             ↓                                     
     Physical Network

开启bridge br0
1
set link br0 up

bridge命令

bridge link：展示桥接到网桥的interface（相当于交换机的网口）
bridge fdb：展示网桥的转发表
bridge vlan：展示网桥的VLAN配置信息

由上面的分析，可以得知Linux虚拟网桥设备 bridge 可以将多个 interface 连接为一个网络，并且虚拟网桥设备有自己的MAC转发表，也可以在虚拟网桥中配置VLAN。

利用树莓派验证brdige的二层交换功能

实验设备

树莓派3b+：包含一个以太网卡 eth0，一个无线网卡 wlan0
PC：有一个以太网口
手机：可以连接WiFI

实验思路

在树莓派上创建一个 bridge，称为 br0
PC通过网线接入 eth0，WiFi设备接入基于 wlan0 构建的无线局域网
将 eth0 和 wlan0 添加到 br0，利用br0 将无线局域网和PC桥接在一起

这样一来，网络结构如下图所示（略去了Network Protocol Stack -> eth0 的单向连接）：

            +-------------------------------------------------+
            |   +----------------------------------------+    |
            |   |         Network Protocol Stack         |    |
            |   +----------------------------------------+    |
            |                        ↑                        |
            |........................|........................|
            |                        ↓                        |
            |       +----------------------------------+      |
            |       |               br0                |      |
            |       +----------------------------------+      |
            |            ↑                       ↑            |
            |            |                       |            |
            |            ↓                       ↓            |
            |     +--------------+       +--------------+     |
            |     |     eth0     |       |     wlan0    |<---------> WiFi_Device
            |     +--------------+       +--------------+     |
            |            ↑                  ↑        ↑        |
            +------------|------------------|--------|--------+
                         ↓                  ↓        ↓         
                        PC            WiFi_Device  WiFi_Device  
```                                    

根据其原理，只要合理地配置PC和无线设备的IP地址，它们理应可以借助虚拟网桥 `br0` 互相访问。

### 关键步骤

#### 树莓派配置AP

借助 `hostapd` 实现，大致步骤为：  

1. 安装 `hostapd`  
    ```shell
    sudo apt install hostapd

配置 hostapd，创建 /etc/hostapd/hostapd.conf

interface=wlan0
bridge=br0
hw_mode=g
channel=7
wmm_enabled=0
macaddr_acl=0
auth_algs=1
ignore_broadcast_ssid=0
wpa=2
wpa_key_mgmt=WPA-PSK
wpa_pairwise=TKIP
rsn_pairwise=CCMP
ssid=RaspberryPi
wpa_passphrase=password

关闭 dhcpcd，启用 hostapd

sudo disable dhcpcd
# References: /usr/share/doc/hostapd/README.Debian
sudo systemctl unmask hostapd
sudo systemctl enable hostapd

连接热点 RaspberryPi
配置好之后重启树莓派应该就能看到热点 RaspberryPi 了，由于树莓派没有开启dhcpd，WiFI设备需要配置使用Static IP，比如 192.168.31.100/24

桥接

创建虚拟网桥 br0
1
sudo ip link add name br0 type bridge

添加设备 eth0，wlan0 至 br0

1 2	sudo ip link set dev eth0 master br0 sudo ip link set dev wlan0 master br0

连接网络

由于树莓派没有开启dhcpd，需要为各个连接到WiFI的设备配置静态IP，当然经网线连接的PC也需要配置，各个设备的IP需要处于同一网段才能互相访问，比如 192.168.31.0/24

故障排除

PC和无线设备都配置好了却无法互相连接
关掉Windows防火墙再试试，稍等一会儿再试试
在Networking: bridge - Linux Foundation DokuWiki中有这样一句话：

The bridge will take a short amount of time when a device is added to learn the Ethernet addresses on the segment before starting to forward.
暂时没有2

测试结果

PC ping通了连接WiFI的手机，成功借助虚拟网桥连通了eth0和wlan0无线局域网。

树莓派配置信息

Script started on 2021-07-30 20:07:21+08:00 [TERM="linux" TTY="/dev/tty1" COLUMNS="240" LINES="67"]


pi@rasp:~/projects/bridge $ ip -d addr
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000
    link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00 promiscuity 0 minmtu 0 maxmtu 0 numtxqueues 1 numrxqueues 1 gso_max_size 65536 gso_max_segs 65535
    inet 127.0.0.1/8 scope host lo
       valid_lft forever preferred_lft forever
    inet6 ::1/128 scope host
       valid_lft forever preferred_lft forever
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc pfifo_fast master br0 state UP group default qlen 1000
    link/ether b8:27:eb:98:76:96 brd ff:ff:ff:ff:ff:ff promiscuity 1 minmtu 68 maxmtu 9000
    bridge_slave state forwarding priority 32 cost 4 hairpin off guard off root_block off fastleave off learning on flood on port_id 0x8002 port_no 0x2 designated_port 32770 designated_cost 0 designated_bridge 8000.b8:27:eb:98:76:96 designated_root 8000.b8:27:eb:98:76:96 hold_timer    0.00 message_age_timer    0.00 forward_delay_timer    0.00 topology_change_ack 0 config_pending 0 proxy_arp off proxy_arp_wifi off mcast_router 1 mcast_fast_leave off mcast_flood on neigh_suppress off group_fwd_mask 0 group_fwd_mask_str 0x0 vlan_tunnel off isolated off numtxqueues 1 numrxqueues 1 gso_max_size 8824 gso_max_segs 65535
3: wlan0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc pfifo_fast master br0 state UP group default qlen 1000
    link/ether b8:27:eb:cd:23:c3 brd ff:ff:ff:ff:ff:ff promiscuity 1 minmtu 68 maxmtu 1500
    bridge_slave state forwarding priority 32 cost 100 hairpin off guard off root_block off fastleave off learning on flood on port_id 0x8001 port_no 0x1 designated_port 32769 designated_cost 0 designated_bridge 8000.b8:27:eb:98:76:96 designated_root 8000.b8:27:eb:98:76:96 hold_timer    0.00 message_age_timer    0.00 forward_delay_timer    0.00 topology_change_ack 0 config_pending 0 proxy_arp off proxy_arp_wifi off mcast_router 1 mcast_fast_leave off mcast_flood on neigh_suppress off group_fwd_mask 0 group_fwd_mask_str 0x0 vlan_tunnel off isolated off numtxqueues 1 numrxqueues 1 gso_max_size 65536 gso_max_segs 65535
5: br0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default qlen 1000
    link/ether b8:27:eb:98:76:96 brd ff:ff:ff:ff:ff:ff promiscuity 0 minmtu 68 maxmtu 65535
    bridge forward_delay 1500 hello_time 200 max_age 2000 ageing_time 30000 stp_state 0 priority 32768 vlan_filtering 0 bridge_id 8000.b8:27:eb:98:76:96 designated_root 8000.b8:27:eb:98:76:96 root_port 0 root_path_cost 0 topology_change 0 topology_change_detected 0 hello_timer    0.00 tcn_timer    0.00 topology_change_timer    0.00 gc_timer  220.78 group_fwd_mask 0 group_address 01:80:c2:00:00:00 mcast_snooping 1 mcast_router 1 mcast_query_use_ifaddr 0 mcast_querier 0 mcast_hash_elasticity 16 mcast_hash_max 4096 mcast_last_member_count 2 mcast_startup_query_count 2 mcast_last_member_interval 100 mcast_membership_interval 26000 mcast_querier_interval 25500 mcast_query_interval 12500 mcast_query_response_interval 1000 mcast_startup_query_interval 3125 mcast_stats_enabled 0 mcast_igmp_version 2 mcast_mld_version 1 nf_call_iptables 0 nf_call_ip6tables 0 nf_call_arptables 0 numtxqueues 1 numrxqueues 1 gso_max_size 8824 gso_max_segs 65535
    inet6 fe80::ba27:ebff:fecd:23c3/64 scope link
       valid_lft forever preferred_lft forever


pi@rasp:~/projects/bridge $ bridge -d link
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 master br0 state forwarding priority 32 cost 4
    hairpin off guard off root_block off fastleave off learning on flood on mcast_flood on neigh_suppress off vlan_tunnel off isolated off
3: wlan0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 master br0 state forwarding priority 32 cost 100
    hairpin off guard off root_block off fastleave off learning on flood on mcast_flood on neigh_suppress off vlan_tunnel off isolated off
5: br0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 master br0


pi@rasp:~/projects/bridge $ bridge fdb
f4:30:b9:ad:56:eb dev eth0 master br0
b8:27:eb:98:76:96 dev eth0 master br0 permanent
01:00:5e:00:00:01 dev eth0 self permanent
33:33:00:00:00:01 dev eth0 self permanent
e0:cc:f8:ce:27:a9 dev wlan0 master br0
b8:27:eb:cd:23:c3 dev wlan0 master br0 permanent
01:00:5e:00:00:01 dev wlan0 self permanent
33:33:00:00:00:01 dev wlan0 self permanent
33:33:00:00:00:01 dev br0 self permanent
01:00:5e:00:00:6a dev br0 self permanent
33:33:00:00:00:6a dev br0 self permanent
01:00:5e:00:00:01 dev br0 self permanent
33:33:ff:cd:23:c3 dev br0 self permanent
33:33:00:00:00:fb dev br0 self permanent
pi@rasp:~/projects/bridge $ bridge -d fdb
f4:30:b9:ad:56:eb dev eth0 master br0
b8:27:eb:98:76:96 dev eth0 master br0 permanent
01:00:5e:00:00:01 dev eth0 self permanent
33:33:00:00:00:01 dev eth0 self permanent
e0:cc:f8:ce:27:a9 dev wlan0 master br0
b8:27:eb:cd:23:c3 dev wlan0 master br0 permanent
01:00:5e:00:00:01 dev wlan0 self permanent
33:33:00:00:00:01 dev wlan0 self permanent
33:33:00:00:00:01 dev br0 self permanent
01:00:5e:00:00:6a dev br0 self permanent
33:33:00:00:00:6a dev br0 self permanent
01:00:5e:00:00:01 dev br0 self permanent
33:33:ff:cd:23:c3 dev br0 self permanent
33:33:00:00:00:fb dev br0 self permanent


pi@rasp:~/projects/bridge $ bridge -d vlan
port    vlan ids
eth0
wlan0
br0
pi@rasp:~/projects/bridge $ exit

Script done on 2021-07-30 20:08:17+08:00 [COMMAND_EXIT_CODE="0"]

设备IP配置

PC：192.168.100.100
手机：192.168.100.102

tcpdump部分抓包结果

抓包命令：sudo tcpdump -i br0

可以看到两台设备之间的 ICMP echo request 和 ICMP echo reply，至于为什么没有互相询问ARP的消息，大概是因为在我截取消息的时候他们已经知道了对方的MAC。

19:56:53.340646 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28
19:56:53.577869 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 279, length 64
19:56:53.578378 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 279, length 64
19:56:54.105795 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28
19:56:54.580512 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 280, length 64
19:56:54.580882 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 280, length 64
19:56:54.875747 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28
19:56:55.582730 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 281, length 64
19:56:55.583236 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 281, length 64
19:56:55.629983 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28
19:56:56.584221 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 282, length 64
19:56:56.584775 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 282, length 64
19:56:57.079863 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28
19:56:57.585969 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 283, length 64
19:56:57.586473 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 283, length 64
19:56:57.851101 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28
19:56:58.587740 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 284, length 64
19:56:58.588376 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 284, length 64
19:56:58.606484 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28
19:56:59.589851 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 285, length 64
19:56:59.590206 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 285, length 64
19:56:59.639003 IP 192.168.17.102.62171 > 239.255.255.250.1900: UDP, length 174
19:57:00.591333 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 286, length 64
19:57:00.592043 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 286, length 64
19:57:00.642907 IP 192.168.17.102.62171 > 239.255.255.250.1900: UDP, length 174
19:57:01.593566 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 287, length 64
19:57:01.593930 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 287, length 64
19:57:01.645152 IP 192.168.17.102.62171 > 239.255.255.250.1900: UDP, length 174
19:57:01.729974 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28
19:57:02.491623 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28
19:57:02.582445 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 288, length 64
19:57:02.582814 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 288, length 64
19:57:02.646148 IP 192.168.17.102.62171 > 239.255.255.250.1900: UDP, length 174
19:57:03.258025 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28
19:57:03.595961 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 289, length 64
19:57:03.596639 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 289, length 64
19:57:04.121192 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28
19:57:04.599132 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 290, length 64
19:57:04.599516 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 290, length 64
19:57:04.881646 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28
19:57:05.592449 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 291, length 64
19:57:05.593202 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 291, length 64
19:57:05.630129 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28
19:57:06.601837 IP 192.168.17.100 > 192.168.17.102: ICMP echo request, id 2945, seq 292, length 64
19:57:06.602326 IP 192.168.17.102 > 192.168.17.100: ICMP echo reply, id 2945, seq 292, length 64
19:57:06.735715 ARP, Request who-has 192.168.17.1 tell 192.168.17.100, length 28

参考资料

Win10禁用Ctrl+Space中英文切换快捷键

发表于 2021-07-29 更新于 2024-10-18 分类于 Tutorial Disqus：
本文字数： 623 阅读时长 ≈ 1 分钟

解决方案

十几年的老BUG了，Win7时代的修改注册表的方法也失效了。
Win7时代的方案在这里：CTRL-Space always toggles Chinese IME (Windows 7)

需要注意的是：

HKEY_CURRENT_USER/Control Panel/Input Method/Hot Keys 保存的是当前用户的快捷键配置
HKEY_USERS\.DEFAULT\Control Panel\Input Method\Hot Keys 保存的是系统默认的快捷键配置

当年的方案修改的是用户快捷键配置，现已失效，现在需要修改系统默认的快捷键配置。

操作步骤

打开注册表编辑器
打开 HKEY_USERS\.DEFAULT\Control Panel\Input Method\Hot Keys
需要修改两项，00000070 是繁体中文快捷键配置，00000010 是简体中文快捷键配置
分别打开上面所说的两项，修改下面两项数据
- Key Modifiers 代表 Alt/Ctrl/Shift等修饰键，默认配置是 Ctrl (02c00000)，把它的第一个字节由 02 改为 00
- Virtual Key 代表与修饰键配合使用的辅助键，默认配置为 Space (20000000)，把它的第一个字节由 20 改为 FF
然后重启系统即可，也许注销再登录就行
我是只改系统默认配置然后重启，Ctrl+Space就无效了，如果只改系统默认配置无效的话，可以再把用户配置也按相同方法改掉，再不行的话就等微软修复BUG吧~~~

VMWare-UbuntuServer2004网络配置记录

发表于 2021-07-24 更新于 2024-10-18 分类于 Tutorial Disqus：
本文字数： 2.9k 阅读时长 ≈ 5 分钟

达成的目标

在Ubuntu Server 20.04 虚拟机当中添加了两块虚拟网卡。一块VMWare虚拟网卡以桥接模式使用电脑的网线接口直接与树莓派通信，可拥有独立于物理网卡的Mac地址和IP地址，同时在树莓派上测试了Macvlan虚拟网卡，Macvlan虚拟网卡有多种工作模式，其中桥接模式可使虚拟网络接口借助物理接口与外界直接通信。另一块VMWare虚拟网卡配置为NAT模式，借助主机网络访问互联网。

主机配置

桥接网络配置

VMWare默认的桥接网络会自动选择用于桥接的实体网卡，如果需要指定通过网线接口而非无线网卡桥接，就需要专门进行配置。在虚拟网络编辑器当中为默认桥接网络指定网卡即可。

NAT网络配置

NAT网卡无需特别配置，默认的配置已经开启了DHCP，但是需要注意的是网关可能不是 192.168.227.1（以我的IP为例说明），我原本在虚拟机中配置了静态地址，结果无法访问互联网，也无法ping通 192.168.227.1，后来改成了 DHCP 模式，发现虚拟机自动配置的网关是 192.168.227.2，而Windows中可以看到 VMware Virtual Ethernet Adapter for VMnet8 的IP是 192.168.227.1，值得关注的还有 IPv4 WINS 服务器: 192.168.227.2，通过查看虚拟机上自动经DHCP配置好的信息，发现虚拟机的网关和DNS服务器恰好都是 192.168.227.2，因此如果想要配置静态IP，需要注意网关和DNS服务器的配置。我所采用的方法是在开启DHCP Client的同时再额外配置一个自定义的IP地址，这样既可以在局域网通过自定义IP地址访问虚拟机，也可以使虚拟机自动配置网关和DNS服务器。

虚拟机ping不通主机是因为Windows防护墙，关掉就能ping通了，不过即使能ping通，也无法将 192.168.227.1 配置为网关来访问互联网，原因上面说了。

VMware Virtual Ethernet Adapter for VMnet8 网络属性

虚拟机当中由DHCP Client配置的 DNS 以及网关

补充说明

后来发现VMWare网络编辑器里面是能看到网关信息的，确实是 192.168.227.2，如果想要手动配置，就按这个信息配置。

虚拟机配置

Ubuntu Server 20.04 的网络配置方法

Ubuntu Server 20.04 使用 netplan 进行网络管理（总是旧的还不熟悉就换了，，）,还默认启用 systemd-resolve 进行域名解析，所以网络配置文件不再是 /etc/network/interfaces，DNS配置文件也不再是 /etc/resolv.conf。

网络配置文件是 /etc/netplan/*，我就直接修改了安装时生成的文件 /etc/netplan/00-installer-config.yaml，修改完毕之后需要执行 sudo netplan try 命令检测配置并按Enter应用配置。

DNS配置文件我没有仔细查，看systemd-resolve文档即可，不过/etc/resolv.conf的开头是这样的，最好不要乱改。顺便说一下，查看DNS服务器的命令是 resolvectl status。

1	# This file is managed by man:systemd-resolved(8). Do not edit.

我的配置文件

# This is the network config written by 'subiquity'
network:
  ethernets:
    ens33:
      addresses: [192.168.10.11/24]
      #gateway4: 192.168.10.1
      #nameservers:
      #  addresses: [192.168.10.1]
      dhcp4: no
    ens38:
      addresses: [192.168.227.5/24]
      dhcp4: yes
  version: 2

其中 ens33 是桥接网卡，配置文件中仅为其配置了静态IP地址，并关闭了dhcpv4，其余的网关、DNS等配置被注释掉是因为如果保留的话，netplan 将为根据设定的网关添加默认路由，而且该默认路由的优先级比 ens38 的默认路由要高，导致各种外网请求走没有互联网连接的 ens33。这里只为 ens33 配置IP，不配置网关，就可以避免 netplan 添加相应的默认路由。
ens38 本来采取的是纯静态配置，结果无法访问互联网，原因在上面讨论了，这里采用了较为稳妥的 DHCP + 静态IP 的方法，既能通过固定IP便捷访问，又能借助DHCP自动配置网关和DNS。

树莓派配置MacVLAN虚拟接口

之前使用路由器多拨时接触过MacVLAN，感觉十分神奇，居然可以通过一个实体网络接口拓展出众多虚拟接口，并且每个都可以拥有自己的Mac地址和IP，而多拨原理就是每个虚拟接口都拨号，然后带宽叠加。

最近了解到相关虚拟技术是由Linux内核提供支持的，从最初的TUN/TAP，发展到后来的MacVLAN和MacVTap，原本我是打算创建一个MacVTap虚拟接口的，结果好像报错说不支持该类型，就用了MacVLAN，并顺利为虚拟接口配置了IP，经测试可以连通。

配置工具就是一系列 ip 命令，在此不再赘述。下图当中的 macvlan0@eth0 即为基于 eth0 的虚拟网络接口，需要注意的一点是，在使用 ip 命令配置的过程中，使用 macvlan0 引用虚拟网卡，不需要带也不能带 @eth0

为什么网络接口、交换机可以虚拟化？

以前没有仔细考虑过这件事情，感觉很神奇，在这里简单地说一下现在的想法。

先来回顾一下交换机工作原理：

交换机工作于OSI参考模型中的第二层（数据链路层），交换机的工作依赖于对MAC地址的识别（所有的网络设备都有一个唯一的MAC地址，通常是由厂商直接烧录进网卡中）。
当交换机从其某个端口收到一个数据包时，先读取包头中的源MAC地址（即发送该数据包的设备网卡的MAC地址），将该MAC地址和端口对应起来添加到交换机内存里的地址表中；然后再读取包头中的目的MAC地址，对照内存里的地址表看该MAC地址与哪个端口对应，如果地址表中有该MAC地址的对应端口，则将该数据包直接复制到对应的端口上，如果没有找到，则将该数据帧作为一个广播帧发送到所有的端口，对应的MAC地址设备会自动接受该帧数据，同时，交换机将接受该帧数据的端口与这个目的MAC地址对应起来放入内存中的地址表中。

简单地说交换机的作用就是转发MAC帧，物理交换机可以用于在一些物理接口之间转发MAC帧。

那么网络接口如何实现虚拟化呢？在没有虚拟接口的情况下，一个网卡对应一个MAC地址，交换机按照转发表，把对应的MAC帧发送到特定的物理端口。只要在此基础上，允许一个物理网卡对应多个MAC地址，那么每个MAC地址都可以配置一个虚拟接口，物理网卡所属机器在拿到MAC帧之后，再根据具体内容分发到虚拟接口即可。而一个物理网卡对应多个MAC地址其实只要允许交换机转发表中一个接口对应多个表项即可。

上面说的是数据链路层的虚拟化，只要实现了数据链路层的虚拟化，那么每个虚拟接口都可以独立地实现局域网通信了，它们是物理端口还是虚拟端口对于上层协议栈来说其实是透明的。

如果接口是用软件虚拟的，那么自然地，就可以同样利用软件在这些虚拟接口间转发MAC帧，这些软件就相当于虚拟交换机了？

Win10配置过程记录

发表于 2021-07-10 更新于 2024-10-18 分类于 Tutorial Disqus：
本文字数： 2.1k 阅读时长 ≈ 4 分钟

简介

由于原来的系统出了一些问题，今日重装了Windows10系统，下面简要记录一下各种基本设定以及开发环境的配置过程，供今后参考。

系统安装

如何让Win10在系统盘重建ESP分区？

系统安装基本没什么好说的，只是需要注意如果有多块磁盘，并且其中一个磁盘存在ESP分区（Fat32），则在重装Win10时，即使选择安装到另一块未分区的磁盘，似乎Win10安装器也不会在另一块磁盘重建ESP分区，而会使用已有的ESP分区，如果想要Win10安装器在操作系统所在磁盘重建ESP分区，可以把另一块磁盘的ESP分区删掉。

对于无洁癖用户大可不必这样操作，不过给Win10预留一个未分区磁盘，还是比分好一个NTFS分区给它用要好的，这样Win10安装器似乎会建立好几个分区，也许多余的分区是用于系统恢复的。

UEFI启动项管理软件

*nix系统建议直接使用 efibootmgr，至少Arch系、Debian系的系统都自带这个工具。
Windows系统可以用 EasyUEFI，不过试用版过期后就没法用了，即使重装、删除注册表项，也难以重新试用，可以用pj版。

指定用户名

如果按照Win10默认的引导进行配置，它会诱导用户登录微软账户，并自动把微软账户名的前缀（邮箱前缀）作为系统用户名，作为一个经常使用终端的CSer，是无法容忍奇奇怪怪的用户名的。

如果想要自定义用户名，需要先以本地账户登录，自己起一个用户名，之后再切换到微软账户登录即可。

初始配置

卸载自带应用

卸载一系列自带的无用软件。

Onedrive同步

登录Onedrive并开启个人文件夹同步，打开文档文件夹的同步功能，这样应该可以实现微信和QQ聊天记录的同步，写此文时尚未安装QQ和微信，所以不是特别确定。

WSL2配置

本次重装彻底删掉了Ubuntu系统，打算迁移到WSL2，毕竟双系统切换太麻烦了。

WSL2安装

按照官方教程配置即可，主要步骤大概如下：

开启两项可选功能： Linux子系统和虚拟化平台
下载安装最新的 WSL2 Linux内核升级包
设置wsl默认版本为wsl2
安装所需发行版

如何从主机访问WSL2？

由于wsl2的ip地址是动态配置的，而自动端口映射功能也并不稳定，为了便捷地从win10访问wsl2，一种可靠的方案是动态获取wsl2的ip地址并在win10的hosts文件中为其设置域名。

go-wsl2-host 项目实现了这个功能，参照项目说明进行配置,使用时可能会遇到一些问题：

服务启动失败：检查用户名和密码，用户名基本就是个人文件夹的名字，密码为微软账户密码
账号密码正确仍无法登录：开始->Windows管理工具->本地安全策略->本地策略->用户权限分配->作为服务登录->添加用户或组，把相应用户添加进去
服务启动成功，但hosts文件却没变：可以使用 wsl2host debug 命令查看程序输出，如果程序提示无法写入hosts，检查hosts文件是否为只读，把只读属性取消即可。hosts路径为 C:\Windows\System32\drivers\etc\hosts

自动启动WSL2，以及其中的一些服务

WSL2不支持systemd，也就无法通过systemctl配置自启服务，可以在 /etc/init.wsl 中写入一些启动服务的命令，并在Windows中配置开机执行 wsl -u root /etc/init.wsl。可以利用Win10的 任务计划程序 配置执行上述命令。

我导出的任务计划程序配置（wsl2-init.xml）如下:

<?xml version="1.0" encoding="UTF-16"?>
<Task version="1.2" xmlns="http://schemas.microsoft.com/windows/2004/02/mit/task">
  <RegistrationInfo>
    <Date>2021-07-01T20:23:06.8672886</Date>
    <Author>OMEN\lpyhe</Author>
    <Description>Windows开机时自动运行WSL2并且运行 /etc/init.wsl</Description>
    <URI>\Custom\WSL-INIT</URI>
  </RegistrationInfo>
  <Triggers>
    <BootTrigger>
      <Enabled>true</Enabled>
    </BootTrigger>
  </Triggers>
  <Principals>
    <Principal id="Author">
      <UserId>S-1-5-21-226882884-566579671-1051654333-1001</UserId>
      <LogonType>Password</LogonType>
      <RunLevel>LeastPrivilege</RunLevel>
    </Principal>
  </Principals>
  <Settings>
    <MultipleInstancesPolicy>IgnoreNew</MultipleInstancesPolicy>
    <DisallowStartIfOnBatteries>true</DisallowStartIfOnBatteries>
    <StopIfGoingOnBatteries>true</StopIfGoingOnBatteries>
    <AllowHardTerminate>true</AllowHardTerminate>
    <StartWhenAvailable>false</StartWhenAvailable>
    <RunOnlyIfNetworkAvailable>false</RunOnlyIfNetworkAvailable>
    <IdleSettings>
      <StopOnIdleEnd>true</StopOnIdleEnd>
      <RestartOnIdle>false</RestartOnIdle>
    </IdleSettings>
    <AllowStartOnDemand>true</AllowStartOnDemand>
    <Enabled>true</Enabled>
    <Hidden>false</Hidden>
    <RunOnlyIfIdle>false</RunOnlyIfIdle>
    <WakeToRun>false</WakeToRun>
    <ExecutionTimeLimit>PT72H</ExecutionTimeLimit>
    <Priority>7</Priority>
  </Settings>
  <Actions Context="Author">
    <Exec>
      <Command>wsl</Command>
      <Arguments>-u root /etc/init.wsl</Arguments>
    </Exec>
  </Actions>
</Task>

Windows Terminal 中 wsl自动进入 `~`

在windows terminal中配置wsl的启动目录为 //wsl$/Ubuntu-20.04/home/用户名/，可能需要根据实际情况修改wsl名称和用户名。

Win10 实用软件

WinSW: 设置守护服务

Win10配置守护服务不像Debian、Arch的systemd那样方便，可以借助第三方程序实现，比如 WinSW。

下面是一个将frpc配置为服务的配置示例：

<service>
  
  <!-- ID of the service. It should be unique across the Windows system-->
  <id>frpc</id>
  <!-- Display name of the service -->
  <name>frpc</name>
  <!-- Service description -->
  <description>frpc</description>
  
  <!-- Path to the executable, which should be started -->
  <executable>C:\Programs\Frpc\frpc.exe</executable>
  
  <arguments>-c C:\Programs\Frpc\frpc.ini</arguments>

  <onfailure action="restart" />

</service>

AutohotKey: 配置快捷键

可用于配置快捷键，下面的脚本将 Ctrl + Alt + T 配置为启动Windows Terminal的快捷键。将写好的ahk脚本放到 C:\Users\用户名\AppData\Roaming\Microsoft\Windows\Start Menu\Programs\Startup 中即可开机自启。

1
2
3

^!t::
Run, wt.exe
return

WSL2子系统环境配置

使用python3作为默认python

推荐使用 update-alternatives 进行配置，这样便于管理。为python3添加alternatives的命令为：

1	sudo update-alternatives --install /usr/bin/python python /usr/bin/python3 30

vim配置

首先安装 vim-plug，然后准备好vim配置文件 ~/.config/nvim/init.vim，接下来启动 vim 等待各种插件安装完成，其中Coc插件需要高版本的node，官方源版本过低，参考下一条进行node的安装。

我的Vim配置文件：

 " setting
" setting - basic
set nocompatible
set encoding=utf8
set showcmd
set hls
set relativenumber
set number
syntax on
" setting - tab & indent
set tabstop=4
set softtabstop=0
set shiftwidth=4
set expandtab
set autoindent
set smartindent

" keymap
let mapleader=","
nmap <Leader>t :NERDTreeToggle<CR>
nmap <Leader>w :w<CR>
nmap <Leader>q :q<CR>
" nmap <Leader>, 10<C-w><
" nmap <Leader>. 10<C-w>>
nmap <Leader>- 5<C-w>-
nmap <Leader>= 5<C-w>+
" nmap <Leader>i :bn<CR>
" nmap <Leader>o :bN<CR>

inoremap <C-L> <Del>

" tnoremap <A-h> <C-\><C-N><C-w>h
" tnoremap <A-j> <C-\><C-N><C-w>j
" tnoremap <A-k> <C-\><C-N><C-w>k
" tnoremap <A-l> <C-\><C-N><C-w>l
" inoremap <A-h> <C-\><C-N><C-w>h
" inoremap <A-j> <C-\><C-N><C-w>j
" inoremap <A-k> <C-\><C-N><C-w>k
" inoremap <A-l> <C-\><C-N><C-w>l
" nnoremap <A-h> <C-w>h
" nnoremap <A-j> <C-w>j
" nnoremap <A-k> <C-w>k
" nnoremap <A-l> <C-w>l

" use h,i,j,k move cursor in insert mode
inoremap <A-h> <C-o>h
inoremap <A-j> <C-o>j
inoremap <A-k> <C-o>k
inoremap <A-l> <C-o>l

" use h,i,j,k switch window in normal mode
nnoremap <A-h> <C-w>h
nnoremap <A-j> <C-w>j
nnoremap <A-k> <C-w>k
nnoremap <A-l> <C-w>l

" 在使用CTRL-U 和 CTRL-H时开启新的undo
" 防止意外删除字符却不可undo
inoremap <C-H> <C-G>u<C-H>
inoremap <C-U> <C-G>u<C-U>

tnoremap <Esc> <C-\><C-N>

tnoremap <A-n> <C-\><C-N>gt
tnoremap <A-p> <C-\><C-N>gT
inoremap <A-n> <C-\><C-N>gt
inoremap <A-p> <C-\><C-N>gT
nnoremap <A-n> gt 
nnoremap <A-p> gT

augroup terminal
    autocmd!
    autocmd TermOpen * setlocal nonumber
    autocmd TermOpen * setlocal norelativenumber
    autocmd TermOpen * setlocal signcolumn=no
augroup end

" for cpp
function! CompileAndRun() 
    write
    execute printf("!g++ -std=c++11 -Wall %s -o %s && %s", expand("%:p"), expand("%:p:r"), expand("%:p:r"))
endfunction
autocmd filetype cpp command! CompileAndRun call CompileAndRun()
autocmd filetype cpp nnoremap <Leader>r :CompileAndRun<CR>

" vim-plug
call plug#begin(stdpath('data') . '/plugged')

" Make sure you are using single quotes
Plug 'neoclide/coc.nvim', {'branch': 'release'}
Plug 'vim-airline/vim-airline'
Plug 'vim-airline/vim-airline-themes'
Plug 'Yggdroot/LeaderF'
Plug 'wakatime/vim-wakatime'

" On-demand loading
Plug 'scrooloose/nerdtree', { 'on':  'NERDTreeToggle' }

" Always load the vim-devicons as th very last one
Plug 'ryanoasis/vim-devicons'
call plug#end()

let g:airline_powerline_fonts = 1
let g:airline_theme='bubblegum'

" >>> FOR COC >>>
" TextEdit might fail if hidden is not set
set hidden

" Some servers have issue with backup files, see #649
set nobackup
set nowritebackup

" Give more space for display messages
set cmdheight=2

" Having longer updatetime (default is 4000 ms = 4 s) leads to noticeable"
" delays and poor user experience
set updatetime=300

" Don't pass messages to |ins-completion-menu|
set shortmess+=c

" Always show the signcolumn, otherwise it would shift the text each time
" diagnostics appear/become resolved.
if has("patch-8.1.1564")
  " Recently vim can merge signcolumn and number column into one
  set signcolumn=number
else
  set signcolumn=yes
endif

" Use tab for trigger completion with characters ahead and navigate.
" NOTE: Use command ':verbose imap <tab>' to make sure tab is not mapped by
" other plugin before putting this into your config.
inoremap <silent><expr> <TAB>
      \ pumvisible() ? "\<C-n>" :
      \ <SID>check_back_space() ? "\<TAB>" :
      \ coc#refresh()
inoremap <expr><S-TAB> pumvisible() ? "\<C-p>" : "\<C-h>"

function! s:check_back_space() abort
  let col = col('.') - 1
  return !col || getline('.')[col - 1]  =~# '\s'
endfunction

" Use <c-space> to trigger completion.
if has('nvim')
  inoremap <silent><expr> <c-space> coc#refresh()
else
  inoremap <silent><expr> <c-@> coc#refresh()
endif

" Use [g and ]g to navigate diagnostics
" use :CocDiagnostics to get all diagnostics of current buffer in location list
nmap <silent> [g <Plug>(coc-diagnostic-prev)
nmap <silent> ]g <Plug>(coc-diagnostic-next)

" GoTo code navigation.
nmap <silent> gd <Plug>(coc-definition)
nmap <silent> gy <Plug>(coc-type-definition)
nmap <silent> gi <Plug>(coc-implementation)
nmap <silent> gr <Plug>(coc-references)

" Use K to show documentation in preview window.
nnoremap <silent> K :call <SID>show_documentation()<CR>

function! s:show_documentation()
  if (index(['vim','help'], &filetype) >= 0)
    execute 'h '.expand('<cword>')
  else
    call CocActionAsync('doHover')
  endif
endfunction

" Highlight the symbol and its references when holding the cursor.
autocmd CursorHold * silent call CocActionAsync('highlight')

" Symbol renaming.
nmap <leader>rn <Plug>(coc-rename)

" Formatting selected code.
" xmap <leader>f  <Plug>(coc-format)
" nmap <leader>f  <Plug>(coc-format)

augroup mygroup
  autocmd!
  " Setup formatexpr specified filetype(s).
  autocmd FileType typescript,json setl formatexpr=CocAction('formatSelected')
  " Update signature help on jump placeholder.
  autocmd User CocJumpPlaceholder call CocActionAsync('showSignatureHelp')
augroup end

" Applying codeAction to the selected region.
" Example: `<leader>aap` for current paragraph
xmap <leader>a  <Plug>(coc-codeaction-selected)
nmap <leader>a  <Plug>(coc-codeaction-selected)

" Remap keys for applying codeAction to the current buffer.
nmap <leader>ac  <Plug>(coc-codeaction)
" Apply AutoFix to problem on the current line.
nmap <leader>qf  <Plug>(coc-fix-current)

" Map function and class text objects
" NOTE: Requires 'textDocument.documentSymbol' support from the language server.
xmap if <Plug>(coc-funcobj-i)
omap if <Plug>(coc-funcobj-i)
xmap af <Plug>(coc-funcobj-a)
omap af <Plug>(coc-funcobj-a)
xmap ic <Plug>(coc-classobj-i)
omap ic <Plug>(coc-classobj-i)
xmap ac <Plug>(coc-classobj-a)
omap ac <Plug>(coc-classobj-a)

" Remap <C-f> and <C-b> for scroll float windows/popups.
" Note coc#float#scroll works on neovim >= 0.4.0 or vim >= 8.2.0750
nnoremap <nowait><expr> <C-f> coc#float#has_scroll() ? coc#float#scroll(1) : "\<C-f>"
nnoremap <nowait><expr> <C-b> coc#float#has_scroll() ? coc#float#scroll(0) : "\<C-b>"
inoremap <nowait><expr> <C-f> coc#float#has_scroll() ? "\<c-r>=coc#float#scroll(1)\<cr>" : "\<Right>"
inoremap <nowait><expr> <C-b> coc#float#has_scroll() ? "\<c-r>=coc#float#scroll(0)\<cr>" : "\<Left>"

" NeoVim-only mapping for visual mode scroll
" Useful on signatureHelp after jump placeholder of snippet expansion
if has('nvim')
  vnoremap <nowait><expr> <C-f> coc#float#has_scroll() ? coc#float#nvim_scroll(1, 1) : "\<C-f>"
  vnoremap <nowait><expr> <C-b> coc#float#has_scroll() ? coc#float#nvim_scroll(0, 1) : "\<C-b>"
endif

" Use CTRL-S for selections ranges.
" Requires 'textDocument/selectionRange' support of language server.
nmap <silent> <C-s> <Plug>(coc-range-select)
xmap <silent> <C-s> <Plug>(coc-range-select)

" Add `:Format` command to format current buffer.
command! -nargs=0 Format :call CocAction('format')

" Add `:Fold` command to fold current buffer.
command! -nargs=? Fold :call CocAction('fold', <f-args>)

" Add `:OR` command for organize imports of the current buffer.
command! -nargs=0 OR :call CocAction('runCommand', 'editor.action.organizeImport')

" >>> config for coc >>>
let g:coc_global_extensions = ['coc-tsserver', 'coc-html', 'coc-css', 'coc-json',
	\ 'coc-python', 'coc-xml', 'coc-yaml', 'coc-markdownlint', 'coc-highlight',
    \ 'coc-clangd', 'coc-pairs', 'coc-git', 'coc-go', 'coc-rust-analyzer']
inoremap <silent><expr> <cr> pumvisible() ? coc#_select_confirm() : "\<C-g>u\<CR>"
" <<< config for coc <<<

node安装

官方源中版本过低，很多软件都要求更高版本的node，建议使用nodesource维护的软件源安装，具体参考项目主页。写此文时，安装长期维护版node的具体命令为：

1
2
3

# Using Ubuntu
curl -fsSL https://deb.nodesource.com/setup_lts.x | sudo -E bash -
sudo apt-get install -y nodejs

利用快速幂模运算加速RSA加密解密过程

发表于 2021-07-03 更新于 2024-10-18 Disqus：
本文字数： 829 阅读时长 ≈ 2 分钟

简介

之前实现RSA加密算法时，计算幂成了程序的瓶颈，前段时间了解了快速幂以及快速幂模运算，这种算法可以用于加速RSA加密解密过程中的幂模计算过程。

快速幂

基本原理

用精确的数学符号表示的话，有下面两种写法：

$$ a ^ b = {\begin{cases}(a ^ {\frac b 2}) ^ 2, &if\ b\ is\ even\\a \cdot (a ^ {\frac {b-1} 2}) ^ 2, &if\ b\ is\ odd\end{cases}}$$

或

$$ a ^ b = {\begin{cases}(a ^ {\lfloor {\frac b 2} \rfloor}) ^ 2, &if\ b\ is\ even\\a \cdot (a ^ {\lfloor {\frac b 2} \rfloor}) ^ 2, &if\ b\ is\ odd\end{cases}}$$

上述公式显然成立，故计算幂可用上述递推式进行。

而在编程语言中，整除一般就相当于向下取整，故上述递推式可以表示成下面的伪代码：

func pow(a, b):
  if b is 0:
    return 1
  if b is even:
    return pow(a, b/2) ^ 2
  if b is odd:
    return pow(a, b/2) ^ 2 * a

时间复杂度

对于 $a^b$，用原始的求幂算法，需要计算 $b$ 次乘法，用上述递推式大约需要运算 $log\ b$ 次

代码实现

下面的代码实现了朴素求幂算法和快速幂算法，并对比了他们的运算时间。

import time


def calc_time(func):
    def inner_func(*args, **kwargs):
        start_time = time.time()
        func(*args, **kwargs)
        end_time = time.time()
        print(f"Time used: {end_time - start_time}")
    return inner_func


@calc_time
def prime_pow(base, power):
    res = 1
    for _ in range(power):
        res *= base
    # print(f'The last five digits of the result {base} ^ {power}: {str(res)[-5:]}')


def quick_pow(base, power):
    if power == 0:
        return 1
    res = quick_pow(base, power // 2)
    if power % 2 == 0:
        return res * res
    else:
        return res * res * base


@calc_time
def quick_pow_wrapper(base, power):
    res = quick_pow(base, power)
    # print(f'The last five digits of the result of {base} ^ {power}: {str(res)[-5:]}')


prime_pow(2, 1000000) # Time used: 15.331219911575317
quick_pow_wrapper(2, 1000000) # Time used: 0.003216981887817383
quick_pow_wrapper(13789, 722341) # Time used: 0.003216981887817383
prime_pow(13789, 722341) # long long long long no result

快速幂模

基本原理

求模运算有这样一条性质: $(a * b) \% m = (a \% m * b \% m) \% m$

利用这一性质，结合快速幂递推式可得：

$$ a ^ b \% m = {\begin{cases}(a ^ {\lfloor {\frac b 2} \rfloor} \% m) ^ 2 \%m, &if\ b\ is\ even\\(a \%m \cdot (a ^ {\lfloor {\frac b 2} \rfloor} \%m) ^ 2) \%m, &if\ b\ is\ odd\end{cases}}$$

表示成伪代码如下所示：

func pow_mod(a, b, m):
  if b is 0:
    return 1
  if b is even:
    return pow_mod(a, b/2, m) ^ 2 % m
  if b is odd:
    return (a % m * pow_mod(a, b/2, m) ^ 2) % m

代码实现

def pow_mod(a, b, m):
    if b == 0:
        return 1
    res = pow_mod(a, b // 2, m)
    if b % 2 == 0:
        return res * res % m
    else:
        return res * res * (a % m) % m

print(pow_mod(2147483647, 200, 1337))

加速RSA加密解密过程

RSA加密和解密需要计算大数幂的模，用原始计算方法难以进行，可以用快速幂模运算加速运算过程。

下面的代码是对 2021-05-23-RSA加密算法原理 中RSA密钥生成、加密、解密的DEMO的改进。

具体代码如下:

from typing import Tuple


class RSAKey:
    class RSAParams:
        def __init__(self, p, q, N, phiN, e, d) -> None:
            self.p = p
            self.q = q
            self.N = N
            self.phiN = phiN
            self.e = e
            self.d = d

        def __str__(self) -> str:
            return f"""{{
  p: {self.p}\n
  q: {self.q}\n
  N: {self.N}\n
  phiN: {self.phiN}\n
  e: {self.e}\n
  d: {self.d}
}}"""

    def __init__(self) -> None:
        self.params = self.__generateRSAParams()

    def getPublicKey(self) -> Tuple[int, int]:
        """get public key

        Returns:
            Tuple[int, int]: (N, e)
        """
        return (self.params.N, self.params.e)

    def getPrivateKey(self) -> Tuple[int, int]:
        """get private key

        Returns:
            Tuple[int, int]: (N, d)
        """
        return (self.params.N, self.params.d)

    def __generateRSAParams(self) -> RSAParams:
        """Generate parameters for RSA

        Returns:
            RSAParams: instance of RSAParams
        """
        # 产生两个大素数
        from Crypto.Util import number
        p: int = number.getPrime(476)
        q: int = number.getPrime(476)

        # p 与 q 不能相等
        while q == p:
            q: int = number.getPrime(10)

        # N = p x q
        N: int = p * q

        # phi(N)
        phiN: int = (p - 1) * (q - 1)

        # 取公钥参数 e，e 应小于 phi(N) 且与 phi(N) 互质
        # 一种简单的思路是找到一个质数 e，只要 phi(N) 不是它的倍数即可
        e: int = number.getPrime(16)
        while phiN % e == 0:
            e: int = number.getPrime(16)

        # 使用扩展欧几里得算法求解 e 的模逆元 d
        _, d, _ = self.__exgcd(e, phiN)

        # 如果计算得到的 d 是负数，则加上 phi(N) 将其转为正数，仍然与 phi(N) 保持同余关系
        if d < 0:
            d = d + phiN

        return self.RSAParams(p, q, N, phiN, e, d)

    def __exgcd(self, a, b):
        """扩展欧几里得算法

        Args:
            a (int): a
            b (int): b

        Returns:
            int: (gcd, x, y)
        """
        ri: int = a
        rj: int = b
        si: int = 1
        sj: int = 0
        ti: int = 0
        tj: int = 1

        while rj != 0:
            qi = ri // rj

            rtemp = rj
            rj = ri - qi * rj
            ri = rtemp

            stemp = sj
            sj = si - qi * sj
            si = stemp

            ttemp = tj
            tj = ti - qi * tj
            ti = ttemp

        return ri, si, ti


def pow_mod(a: int, b: int, m: int) -> int:
    """fast power module

    Args:
        a : a ^ b % m
        b : a ^ b % m
        m : a ^ b % m

    Returns:
        int: a ^ b % m
    """
    if b == 0:
        return 1
    res = pow_mod(a, b // 2, m)
    if b % 2 == 0:
        return res * res % m
    else:
        return res * res * (a % m) % m


def encrypt(m, publicKey) -> int:
    """encrypt message using public key

    Args:
        m (int): origin message m
        publicKey (Tuple[int, int]): (N, e)

    Returns:
        int: encrypted message c
    """
    N, e = publicKey
    c = pow_mod(m, e, N)
    return c


def decrypt(c, privateKey) -> int:
    """decrypt message using private key

    Args:
        c (int): encrypted message c
        privateKey (Tuple[int, int]): (N, d)

    Returns:
        int: origin message m
    """
    N, d = privateKey
    # m = c ** d % N
    m = pow_mod(c, d, N)
    return m


def main():
    rsakey = RSAKey()
    publicKey = rsakey.getPublicKey()
    privateKey = rsakey.getPrivateKey()

    print(f"publicKey: {publicKey}")
    print(f"privateKey: {privateKey}")

    message = 123456789
    encryptedMessage = encrypt(message, publicKey)
    decryptedMessage = decrypt(encryptedMessage, privateKey)

    print(f"origin message: {message}")
    print(f"encrypted message: {encryptedMessage}")
    print(f"decrypted message: {decryptedMessage}")


if __name__ == '__main__':
    main()

RSA加密算法原理

发表于 2021-05-23 更新于 2024-10-18 Disqus：
本文字数： 5.3k 阅读时长 ≈ 10 分钟

简介

RSA加密算法是一种非对称加密算法。

所需数学知识

想要完整地理解RSA加密算法，需要了解不少数论知识，下面介绍几点核心内容。

同余

同余是数论中的一种等价关系。两个整数 $a$、$b$，若它们除以正整数 $m$ 所得的余数相等，则称 $a$、$b$ 对于模 $m$ 同余，表示为：
$$a \equiv b \quad (mod \quad m)$$

同余式有多种性质：

整除性
$$a\equiv b{\pmod {m}}\Rightarrow c\cdot m=a-b,c\in \mathbb {Z}$$
传递性
$$ \left.{\begin{matrix}a\equiv b{\pmod {m}}\\b\equiv c{\pmod {m}}\end{matrix}}\right\} \Rightarrow a\equiv c{\pmod {m}}$$
保持基本运算
$$\left.{\begin{matrix}a\equiv b{\pmod {m}}\\c\equiv d{\pmod {m}}\end{matrix}}\right\}\Rightarrow \left\{{\begin{matrix}a\pm c\equiv b\pm d{\pmod {m}}\\ac\equiv bd{\pmod {m}}\end{matrix}}\right.$$
当 $c=d$ 时，则为等量加法、减法：$a\pm c\equiv b\pm c{\pmod {m}}$

此性质更可进一步引申成：
$$ a\equiv b{\pmod {m}}\Rightarrow {\begin{cases}an\equiv bn{\pmod {m}},\forall n\in \mathbb {Z} \\a^{n}\equiv b^{n}{\pmod {m}},\forall n\in \mathbb {N} ^{0}\end{cases}}$$
更多性质见同余 - 维基百科

欧拉定理

在数论中，欧拉定理)是一个关于同余的性质。

若 $n$, $a$ 为正整数，且 $n$, $a$ 互质，即 $gcd(n,a)=1$，则
$$a^{\varphi(n)}\equiv1 \quad (mod \quad n)$$
其中 $\varphi(n)$ 为欧拉函数。

欧拉函数

在数论中，对正整数 $n$，欧拉函数 $\varphi (n)$ 是小于或等于 $n$ 的正整数中与 $n$ 互质的数的数目。
特别地：

若 $n$ 为质数，则 $\varphi(n) = n - 1$
若 $n$ 可以表示为两个互质的整数之积，比如 $n=pq$，则 $\varphi(n)=\varphi(p)\varphi(q)$
若 $n$ 可以表示为两个质数之积，比如 $n=pq$，则 $\varphi(n)=\varphi(p)\varphi(q) = (p-1)(q-1)$

扩展欧几里得算法

扩展欧几里得算法是欧几里得算法的扩展。已知整数 $a$、$b$，扩展欧几里得算法在求得 $gcd(a,b)$ 的同时，能找到整数 $x$、$y$，使它们满足裴蜀等式：
$$ax+by=gcd(a,b)$$

扩展欧几里得算法可用于求解裴蜀等式：
$$ax+by=m$$

当且仅当 $m$ 是 $a$ 与 $b$ 的最大公约数的倍数时，该方程有解，且有解时必有无数组解。

模反元素

模反元素也称为模倒数，或者模逆元。

一整数 $a$ 对同余 $n$ 之模逆元是指满足以下公式的整数 $b$
$$a^{-1}\equiv b{\pmod {n}}$$

也可以写成以下的式子
$$ab\equiv 1{\pmod {n}}$$

或者
$$ab{\pmod n}=1$$

由定义可得：
$$ab = 1 + kn \Rightarrow ab - kn = 1$$

要求解 $b$，就需要求不定方程 $ax + ny = 1$ 的解，根据裴蜀定理，当且仅当 $1$ 是 $gcd(a, n)$ 的整数倍时，即 $a$ 与 $n$ 互质时，上述方程有解。用扩展欧几里得算法求得的 $x$ 即为模反元素 $b$。

生成密钥

假设Alice想要通过一个不可靠的媒体接收Bob的一条私人信息。她可以用以下的方式来产生一个公钥和一个私钥：

任意选取两个大质数 $p$、$q$，保证 $p \neq q$ ，计算 $N=pq$
根据欧拉函数，计算 $$\begin{equation}\begin{split} \varphi(N)&=\varphi(pq)\\\\ &=\varphi(p)\varphi(q)\\\\ &=(p-1)(q-1)\end{split}\end{equation}$$
选择一个小于 $\varphi(N)$ 的整数 $e$，使 $e$ 与 $\varphi(N)$ 互质，并求得 $e$ 关于 $\varphi(N)$ 的模逆元，称为 $d$。
由模逆元的定义可得： $ed \equiv 1 {\pmod {\varphi(N)}}$
则有 $ed + h\varphi(N) = 1$
已知 $e$ 与 $\varphi(N)$ 互质，根据裴蜀定理知该不定方程有解，利用扩展欧几里得算法即可求得 $e$ 的模逆元 $d$
销毁 $p$、$q$、$\varphi(N)$

Alice将她的公钥 $(N,e)$ 传给Bob，而将她的私钥 $(N,d)$ 藏起来。

加密与解密

加密

假设Bob想给Alice送一个消息，他知道Alice产生的 $N$ 和 $e$。他使用起先与Alice约好的格式将消息转换为一个小于 $N$ 的非负整数 $m$，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为 $m$。用下面这个公式他可以将 $m$ 加密为 $c$：
$$ c\equiv m^e {\pmod N}$$

计算 $c$ 并不复杂。Bob算出 $c$ 后就可以将它传递给Alice。

解密

Alice得到Bob的消息 $c$ 后就可以利用她的密钥 $N$ 和 $d$ 来解码。她可以用以下这个公式来将 $c$ 转换为 $m$：
$$m \equiv c^d {\pmod N}$$

得到 $m$ 后，她可以将原来的信息重新复原。

解密原理

根据加密公式可得：

$$\begin{equation}\begin{split} &c \equiv m^e {\pmod N} \Rightarrow\\\\ &(c)^d \equiv (m^e)^d {\pmod N} \Rightarrow\\\\ &c^d \equiv m^{ed} {\pmod N}\\\\ \end{split}\end{equation}$$

只要能证明下面的式子，就说明解密公式是正确的：

$$\begin{equation} c^d \equiv m^{ed} \equiv m {\pmod N} \end{equation}$$

证明：
根据密钥推导过程，可知 $ed = 1 + h\varphi(N) $，则
$$m^{ed} = m^{1+h\varphi(N)} = (m^{\varphi(N)})^h m$$

若明文 $m$ 与 $N$ 互质，根据欧拉定理可得：

$$\begin{equation}\begin{split} &m^{\varphi(N)} \equiv 1 {\pmod N} \Rightarrow\\\\ &(m^{\varphi(N)})^h \equiv (1)^h {\pmod N} \Rightarrow\\\\ &(m^{\varphi(N)})^hm \equiv (1)^hm {\pmod N} \Rightarrow\\\\ &m^{ed} \equiv m {\pmod N} \Rightarrow\\\\ &c^{d} \equiv m {\pmod N}\\\\ \end{split}\end{equation}$$

若明文 $m$ 与 $N$ 不互质，由于 $N=pq$，且$p$、$q$均为质数，而 $0 < m < N$，故 $m=kp$ 或 $m=kq$，下面以 $m=kp$ 为例展开证明：

如果 $m=kp$，则 $m$ 不会是 $q$ 的倍数，否则 $m$ 就会大于等于 $N$，违反了前提条件，而 $q$ 又是质数，故 $m$ 与 $q$ 互质，根据欧拉定理可得：
$$\begin{equation}\begin{split} &m^{\varphi(q)} \equiv 1 {\pmod q} \Rightarrow\\\\ &(m^{\varphi(q)})^{\varphi(p)} \equiv (1)^{\varphi(p)} {\pmod q} \Rightarrow\\\\ &m^{\varphi(q)\varphi(p)} \equiv 1 {\pmod q} \Rightarrow\\\\ &m^{\varphi(N)} \equiv 1 {\pmod q} \Rightarrow\\\\ &m^{h\varphi(N)} \equiv 1 {\pmod q} \Rightarrow\\\\ &m^{1+h\varphi(N)} \equiv m {\pmod q} \Rightarrow\\\\ &(kp)^{1+h\varphi(N)} \equiv kp {\pmod q} \Rightarrow\\\\ \end{split}\end{equation}$$

由上式可得：

$$\begin{equation}\begin{split} &kp(kp)^{h\varphi(N)} = kp + tq\\\\ \end{split}\end{equation}$$

由于$p$ 与 $q$ 互质，要使该式成立，须有 $t=t’p$，代入上式可得：

$$\begin{equation}\begin{split} &(kp)^{1+h\varphi(N)} = kp + t‘qp \Rightarrow\\\\ &(kp)^{1+h\varphi(N)} = kp + t‘N \Rightarrow\\\\ &m^{1+h\varphi(N)} = m + t‘N \Rightarrow\\\\ &m^{1+h\varphi(N)} \equiv m {\pmod N} \Rightarrow \end{split}\end{equation}$$

结合 $m^{ed} = m^{1+h\varphi(N)} = (m^{\varphi(N)})^h m$ 可得：

$$\begin{equation}\begin{split} &c^d \equiv m^{ed} \equiv m^{1+h\varphi(N)} \equiv m {\pmod N} \end{split}\end{equation}$$

签名与验证

见RSA加密算法 - 维基百科。

基本原理与加密、解密基本一致，只是用私钥加密，用公钥解密。

算法安全性

假设偷听者Eve获得了Alice的公钥 $n$ 和 $e$ 以及Bob的加密消息 $c$，但她无法直接获得Alice的密钥 $d$。要获得 $d$，最简单的方法是将 $n$ 分解为 $p$ 和 $q$，这样她可以得到同余方程 $ed\equiv 1{\pmod{(p-1)(q-1)}}$并解出 $d$，然后代入解密公式
$$c^{d}\equiv m\ (\mathrm {mod} \ n)$$

导出m（破密）。但至今为止还没有人找到一个多项式时间的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在（见因数分解）。

至今为止也没有人能够证明对 $n$ 进行因数分解是唯一的从 $c$ 导出 $n$ 的方法，直到今天也还没有找到比它更简单的方法。（至少没有公开的方法。）

因此今天一般认为只要 $n$ 足够大，那么黑客就没有办法了。

假如 $n$ 的长度小于或等于256位，那么用一台个人电脑在几个小时内就可以分解它的因子了。1999年，数百台电脑合作分解了一个512位长的 $n$。一个由Shamir 和Tromer在2003年从理论上构建的硬件TWIRL，使人们开始质疑1024位长的 $n$ 的安全性，目前推荐 $n$ 的长度至少为2048位。

1994年彼得·秀尔（Peter Shor）证明一台量子计算机可以在多项式时间内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀尔的算法可以淘汰RSA和相关的派生算法。（即依赖于分解大整数困难性的加密算法）

假如有人能够找到一种有效的分解大整数的算法的话，或者假如量子计算机可行的话，那么在解密和制造更长的钥匙之间就会展开一场竞争。但从原理上来说RSA在这种情况下是不可靠的。

DEMO

下面的代码根据上述原理实现了一个简单版本的RSA密钥生成、加密、解密的DEMO。

本以为应该不难实现，结果发现大质数的生成本身就是问题，除此之外还有其它的一些问题。关键问题以及大致思路：

质数的生成，经过查阅资料，得知大致方法是随机选取大整数，并通过一些方法判断它是不是质数，然而暴力的方法复杂度极高，目前有几种比较有效的质数判定方法，在此不再赘述，可自行查阅相关资料。下列程序当中使用了 Crypto 模块的素数生成功能。
公钥参数 $e$ 的生成， $e$ 需要与 $\varphi(N)$ 互质，一种简单的思路是选取一个质数 $e$，只要 $\phi(N)$ 不是它的整数倍即可。

具体代码如下:

from typing import Tuple


class RSAKey:
  class RSAParams:
    def __init__(self, p, q, N, phiN, e, d) -> None:
        self.p = p
        self.q = q
        self.N = N
        self.phiN = phiN
        self.e = e
        self.d = d

    def __str__(self) -> str:
        return f"""{{
  p: {self.p}\n
  q: {self.q}\n
  N: {self.N}\n
  phiN: {self.phiN}\n
  e: {self.e}\n
  d: {self.d}
}}"""

  def __init__(self) -> None:
    self.params = self.__generateRSAParams()

  def getPublicKey(self) -> Tuple[int, int]:
    """get public key
    Returns:
        Tuple[int, int]: (N, e)
    """
    return (self.params.N, self.params.e)

  def getPrivateKey(self) -> Tuple[int, int]:
    """get private key
    Returns:
        Tuple[int, int]: (N, d)
    """
    return (self.params.N, self.params.d)

  def __generateRSAParams(self) -> RSAParams:
    """Generate parameters for RSA
    Returns:
        RSAParams: instance of RSAParams
    """
    # 产生两个大素数
    from Crypto.Util import number
    p : int = number.getPrime(10)
    q : int = number.getPrime(10)

    # p 与 q 不能相等
    while q == p:
      q : int = number.getPrime(10)

    # N = p x q
    N : int = p * q

    # phi(N)
    phiN : int = (p - 1) * (q - 1)

    # 取公钥参数 e，e 应小于 phi(N) 且与 phi(N) 互质
    # 一种简单的思路是找到一个质数 e，只要 phi(N) 不是它的倍数即可
    e : int = number.getPrime(16)
    while phiN % e == 0:
      e : int = number.getPrime(16)

    # 使用扩展欧几里得算法求解 e 的模逆元 d
    _, d, _ = self.__exgcd(e, phiN)

    # 如果计算得到的 d 是负数，则加上 phi(N) 将其转为正数，仍然与 phi(N) 保持同余关系 
    if d < 0:
      d = d + phiN

    return self.RSAParams(p, q, N, phiN, e, d)

  def __exgcd(self, a, b):
    """扩展欧几里得算法
    Args:
        a (int): a
        b (int): b
    Returns:
        int: (gcd, x, y)
    """
    ri :int = a
    rj :int = b
    si :int = 1
    sj :int = 0
    ti :int = 0
    tj :int = 1

    while rj != 0:
      qi = ri // rj

      rtemp = rj
      rj = ri - qi * rj
      ri = rtemp

      stemp = sj
      sj = si - qi * sj
      si = stemp

      ttemp = tj
      tj = ti - qi * tj
      ti = ttemp
    
    return ri, si, ti


def encrypt(m, publicKey) -> int:
  """encrypt message using public key
  Args:
      m (int): origin message m
      publicKey (Tuple[int, int]): (N, e)
  Returns:
      int: encrypted message c
  """
  N, e = publicKey
  c = m ** e % N
  return c


def decrypt(c, privateKey) -> int:
  """decrypt message using private key
  Args:
      c (int): encrypted message c
      privateKey (Tuple[int, int]): (N, d)
  Returns:
      int: origin message m
  """
  N, d = privateKey
  m = c ** d % N
  return m


def main():
  rsakey = RSAKey()
  publicKey = rsakey.getPublicKey()
  privateKey = rsakey.getPrivateKey()

  print(f"publicKey: {publicKey}")
  print(f"privateKey: {privateKey}")

  message = 12345
  encryptedMessage = encrypt(message, publicKey)
  decryptedMessage = decrypt(encryptedMessage, privateKey)

  print(f"origin message: {message}")
  print(f"encrypted message: {encryptedMessage}")
  print(f"decrypted message: {decryptedMessage}")


if __name__ == '__main__':
  main()

参考资料

扩展欧几里得算法 - 维基百科
 同余 - 维基百科
 欧拉定理 - 维基百科)
欧拉函数 - 维基百科
 模反元素 - 维基百科
 RSA加密算法 - 维基百科
 阮一峰：RSA算法原理（一）
阮一峰：RSA算法原理（二）
阮一峰：数字签名是什么？
RSA算法的数学原理与证明

扩展欧几里得算法

发表于 2021-05-22 更新于 2024-10-18 Disqus：
本文字数： 2.2k 阅读时长 ≈ 4 分钟

简介

上一篇文章简单介绍了欧几里得算法，即辗转相除法，它可以用于求解任意两个自然数 $a$ 和 $b$ 的最大公约数。而扩展欧几里得算法在求得 $gcd(a.b)$ 的同时，也能找到整数 $x$ 和 $y$ ,使它们满足裴蜀等式：
$$ax+by=gcd(a,b)$$

裴蜀定理

定义

在数论中，裴蜀定理是一个关于最大公约数的定理。

对任意两个整数 $a$、$b$，设 $g=gcd(a,b)$ 是它们的最大公约数。那么关于未知数 $x$ 和 $y$ 的线性裴蜀等式：
$$ax+by=m$$
有整数解 $(x, y)$ 当且仅当 $m$ 是 $g$ 的整数倍。

裴蜀等式有解时必然有无穷多个解，每组解 $(x,y)$ 都称为裴蜀数。

证明

参考裴蜀定理 - 维基百科

维基百科中证明步骤的大概思路是这样的：
(1) 给出集合 $A = {ax+by|(x,y)\in\mathbb{Z}^2}$
(2) 通过$A\cap\mathbb{N}^*\neq\emptyset$，$\mathbb{N}$良序等讨论，指出$A$中必然存在最小正元素$d_0=ax_0+by_0$

基本逻辑是这样的， $A\cap\mathbb{N}^*$ 中包含了$A$中所有的正元素，且$A\cap\mathbb{N}^*$是良序集合自然数集合$\mathbb{N}$的非空子集，故其中存在最小元素。也就是说集合$A$中存在最小正元素，记为$d_0$。

(3) 假设$p=ax+by$为$A$中任何一个正整数，试图计算$p$对$d_0$的带模除法，记为$p=qd_0+r$，因为$d_0$是$A$中最小正整数，故另一正整数$p$必然满足$p \geq d_0$，故$q > 0$，$0\leq r < d_0$
(4) 可得$r=p-qd_0=ax+by-q(ax_0+by_0)=a(x-qx_0)+b(y-qy_0)$，根据其形式可判断$r\in A$，结合上一条的结论$0\leq r < d_0$，且$d_0$是$A$中的最小正元素，可推断$r=0$，则可知$A$中任意正整数$p$都满足$p=qd_0$，即$A$中任意正整数$p$都是$d_0$的整数倍，记为$d_0|p$，并且显然$a \in A,b \in A$，故$d_0|a$，$d_0|b$，于是可知$d_0$是$a$和$b$的公约数

只能判断是公约数，结合后面的证明才得出最大公约数的结论，并且，上面的论述没有仔细考虑$a$，$b$为负值的情况，裴蜀定理 - 维基百科的证明也许适用于负数

(5) 设$a$与$b$的任意公约数为$d$，则$a$与$b$可表示为$a=kd$，$b=ld$，那么$d_0=ax_0+by_0=kdx_0+ldy_0=(kx_0+ly_0)d$，可知$d|d_0$，也就是说$d_0$是任何$a$和$b$的公约数$d$的倍数，最大公约数也不例外，且由上一点可知$d_0$是$a$和$b$的公约数，由此可推断$d_0$本身就是$a$与$b$的最大公约数
(6) 关于解的数量无限的讨论，详见裴蜀定理 - 维基百科
(7) 总之，从上面的讨论可以得出如下结论：在集合$A = {ax+by|(x,y)\in\mathbb{Z}^2}$当中，最小正元素$d_0=gcd(a,b)$，且$A$中任意正元素都是$d_0$的倍数
(8) 因此如果$ax+by=m$有整数解，显然$m \in A$，根据上面的讨论可知 $gcd(a,b)|m$，即$m$是$gcd(a,b)$的整数倍

算法步骤

相比欧几里得算法，扩展欧几里得算法在计算余数($q_i$)和商($r_i$)的基础上又增加了两列数据：$s_i$和$t_i$，最终得到的$s_i$和$t_i$满足裴蜀等式：
$$as_i+bt_i=r_i=gcd(a,b)$$

具体算法步骤如下:

序号	余数$r_i$	$s_i$	$t_i$
$0$	$a$	$1$	$0$
$1$	$b$	$0$	$1$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$i+1$	$r{i+1}=r{i-1}-q_ir_i$	$s{i+1}=s{i-1}-q_is_i$	$t{i+1}=t{i-1}-q_it_i$

终止条件与欧几里得算法相同，当$r_{i+1}=0$时终止，此时：
$$as_i+bt_i=r_i=gcd(a,b)$$

证明

上一篇文章证明了欧几里得算法的正确性，在此基础上说明扩展欧几里得算法的正确性。

当$i=0$时，$r_0=a,s_0=1,t_i=0$，显然满足$as_i+bt_i=r_i$
当$i=1$时，$r_1=b,s_0=0,t_i=1$，显然满足$as_i+bt_i=r_i$
由下列递推式可推及所有$i>1$时的情况：
$$\begin{equation}\begin{split} r_{i+1}&=r_{i-1}-q_ir_i\\\\ &=(as_{i-1}+bt_{i-1})-q_i(as_i+bt_i)\\\\ &=a(s_{i-1}-q_is_i)-b(t_{i-1}-q_it_i)\\\\ &=as_{i+1}+bt_{i+1} \end{split}\end{equation}$$

因此当$r_{i+1}=0$，算法终止时：
$$as_i+bt_i=r_i=gcd(a,b)$$

参考资料

扩展欧几里得算法 - 维基百科
 辗转相除法 - 维基百科
 裴蜀定理 - 维基百科
 丢番图方程 - 维基百科
 二元关系 - 维基百科
 偏序关系 - 维基百科
 全序关系 - 维基百科
 良序关系 - 维基百科

辗转相除法

发表于 2021-05-21 更新于 2024-10-18 Disqus：
本文字数： 1.5k 阅读时长 ≈ 3 分钟

简介

辗转相除法，又称欧几里得算法，用于系统性地求两个自然数的最大公约数。

核心思想

对于任意两个正整数 $a$ 和 $b$ ，求 $a$ 和 $b$ 的最大公约数 $gcd(a, b)$，等价于求解 $gcd(b, a \% b)$，相关资料一般会限定 $a \geq b$，但其实即使 $a < b$ 也无妨，在这种情况下，第一步计算相当于交换 $a$ 和 $b$ 的位置。

证明该算法所需知识

下文的论证会用到三种相关的数学方法，分别是数学归纳法、递归和无穷递降。

归纳

数学归纳法经常用来证明某个定理对所有自然数成立：首先证明定理对一个特定的数n0成立（通常是1）；然后证明如果定理对自然数n成立的话，那么它对自然数n + 1成立。这样，便可证明定理对所有大于n0的自然数也成立。

递归

递归是将相关的数组成一个数列$(a1, a2, a3…)$，当中除初始项外，其中每一项都用前一项或前几项表示。如斐波那契数列就是递归的，每一项$Fn$都等于$F{n−1} + F_{n−2}（n\geq2）$。辗转相除法中的一些等式也是递归的。

无穷递降

最后，无穷递降是用方程的一个自然数解导出比它小的自然数解。但是，这种转化不能永远进行下去，因为只有有限个小于原来的自然数解的自然数。所以，要么方程无解，不然在有限步内必然能得出最小的自然数解。在下文会用到此法来证明辗转相除法一定会在有限步内结束。

算法步骤

下面以非负整数为例说明如何算法步骤，每一次计算的输入都是前两次计算的非负余数 $r{k-1}$和$r{k-2}$，记$a=r{-2}$，$b=r{-1}$，按如下步骤递归计算

$a = p0b + r_0$
$b = p_0r_0 + r_1$
$r_0 = p_0r_1 + r_2$
$r_1 = p_0r_2 + r_3$
…
$r{k-2} = p0r{k-1} + r_k$

按照该算法进行计算，$r_k$必然会逐渐减小，并且由于$[0,r_0]$之间数字有限，该算法必然能够在第$N$步终止。

此时$rN$为0，$r{N-1}$即为$gcd(a,b)$

证明上述算法的正确性

辗转相除法的正确性可以分成两步来证明。在第一步，我们会证明算法的最终结果$r{N-1}$同时整除$a$和$b$。因为它是一个公约数，所以必然小于或者等于最大公约数$g$。在第二步，我们证明$g$能整除$r{N-1}$。所以g一定小于或等于$r{N-1}$。两个不等式只在$r{N-1}=g$时同时成立。具体证明如下：

(1) $r_{N-1}$能整除$a$和$b$

在算法终止时，余数$rN=0$。则有：$r{N-2} = p0r{N-1}$
说明$r{N-1}$能整除$r{N-2}$，又根据$r{N-3} = p_0r{N-2} + r{N-1}$
可推断$r{N-1}$能整除$r{N-3}$，以此类推，最终可推断：
**$r{N-1}$能整除$a$和$b$，说明 $r{N-1}$是$a$和$b$的一个公约数**，且由于$g$是最大公约数，应有$r{N-1} \leq g$

(2) $g$能整除$r_{N-1}$

根据定义，$g$是$a$和$b$的最大公约数，则$g$能整除$a$和$b$，$a$和$b$可表示为$a=mg$，$b=ng$
由$r0=a-p_0b=mg-p_0ng=(m-p_0n)g$，可知$g|r_0$，即$g$能整除$r_0$,
由$r_1=b-p_0r_0$，$g|r_0$，$g|b$，可得$g|r_1$,
依此类推，最终可得$g|r{N-1}$，则$g \leq r_{N-1}$

综合(1)(2)，可知$g=r_{N-1}$

算法优化

漫画算法：辗转相除法是什么鬼？ - 知乎

参考资料

辗转相除法 - 维基百科

RSA加密算法阅读笔记

发表于 2021-05-20 更新于 2024-10-18 Disqus：
本文字数： 1.2k 阅读时长 ≈ 2 分钟

背景

最近读到了阮一峰介绍的的RSA算法原理，本文作为对这篇文章的简单批注。

一、非对称加密算法

对称加密算法的加密与解密过程采用相同的密钥，在这种情况下，往往需要传输密钥，一旦密钥被拦截，就会暴露所传递的信息。

非对称加密算法包含一对密钥，称为公钥和私钥，私钥由密钥所有者保存，不必公开，公钥可以公开。非对称加密算法既可以用于加密也可用于签名。

当用于加密时，消息发送者使用接收者的公钥对消息进行加密，然后将密文传输给接收者，接收者使用对应的私钥对密文进行解密即可得到原始消息。由于经公钥加密的密文只能由对应的私钥进行解密，只要不暴露私钥，就可以安全地传输消息。而非对称加密算法都采用了十分安全的算法保证攻击者难以通过公钥推算私钥，因此可以安全地公开公钥。

当用于签名时，私钥持有者使用自己的私钥对消息的摘要进行签名，然后将消息和摘要的签名一并发送给接收者，接收者可以利用对应的公钥对签名进行解密，并将解密结果与消息摘要进行比对，以确定消息是否被篡改。

二、互质关系

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。

关于互质关系，不难得到以下结论：

　　1. 任意两个质数构成互质关系，比如13和61。

　　2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。

　　3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。

　　4. 1和任意一个自然数是都是互质关系，比如1和99。

　　5. p是大于1的整数，则p和p-1构成互质关系，比如57和56。

　　6. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

上述结论中1-4均显而易见，下面对第5点进行证明：

假设p和p-1存在公因子k，k为正整数，则：
(1) p = mk，m为正整数
(2) p-1 = nk，n为正整数
由(1)(2)可得：(3) (m-n)k = 1
由于m，n均为正整数，则m-n也为整数，记为a=m-n
则 ak=1，由于a和k均为整数，且k>0，可得a=k=1
上述结论说明，p与p-1的公因子k只能为1，即p与p-1互质

下面对第6点进行证明：

假设p和p-1存在公因子k，k为正整数，则：
(1) p = mk，m为正整数
(2) p-2 = nk，n为正整数
由(1)(2)可得：(3) (m-n)k = 2
由于m，n均为正整数，则m-n也为整数，且k>0
则可得两组解：
解(1): m-n=1,k=2
解(2): m-n=2,k=1
由于p为奇数，则因子k不能为偶数，第一组解不成立
故只能使用第二组解，可得p和p-2的公因子k为1，p和p-2互质

不写了

需要学的东西还很多，有一些阮一峰未介绍的转换细节，参考RSA算法的数学原理与证明吧，写不动了，太菜了，总是RSA算法很NB，需要用到大量数论知识

参考资料

阮一峰：RSA算法原理（一）
阮一峰：RSA算法原理（二）
阮一峰：数字签名是什么？
RSA算法的数学原理与证明

Nvidia双显卡笔记本双屏配置

发表于 2021-01-16 更新于 2024-10-18 Disqus：
本文字数： 1.2k 阅读时长 ≈ 2 分钟

说明

对于Ubuntu 20.10已经可以开箱即用，不过对于Debian10，Arch等系统还是需要专门进行配置才行。

方案一使用开源驱动nouveau

此方案在此时最新的Arch上可行（我的是1050Ti），如果不想折腾直接安装nouveau软件包即可。
但是在我的Debian10上并不能直接使用，在此系统上如果没有在内核启动参数添加nouveau.modeset=0的话会直接卡到无法操作，所以PASS。

方案二使用Nvidia官方驱动，采用Nvidia单显卡渲染

步骤如下。

安装nvidia驱动

这一步根据系统不同安装不同的软件包即可，一般情况下，安装nvidia软件包的时候会自动blasklist nouveau，如果是上古版本可能需要手动blasklist。

xorg.conf配置

可以在xorg.conf中进行具体配置，也可以在xorg.conf.d中添加一个nvidia配置用于自动配置，第二种方式不需要xorg.conf文件。

方法一直接配置xorg.conf文件

为Nvidia显卡配置驱动nvidia，为Intel核显配置驱动modesetting，具体工作原理参见debian和nvidia文档。


Section "ServerLayout"
    Identifier     "Layout0"
    Screen      0  "nvidia"
    Inactive       "intel"
EndSection

Section "Device"
    Identifier     "nvidia"
    Driver         "nvidia"
    # By default, the NVIDIA X driver will bail out if there 
    # are no displays available. In order to ensure that the 
    # X server can start with no heads connected directly to 
    # the dGPU, you must add 
    # 'Option "AllowEmptyInitialConfiguration"' to the 
    # "Screen" section of xorg.conf.
    Option         "AllowEmptyInitialConfiguration"
    VendorName     "NVIDIA Corporation"
EndSection

Section "Device"
    Identifier     "intel"
    # By default, your xorg.conf will be set up such that only
    # the NVIDIA driver will be loaded. In order to ensure 
    # that the iGPU’s heads are available for configuration, 
    # the 'modesetting' driver must be specified.
    Driver         "modesetting"
    VendorName     "Intel Graphics"
EndSection

Section "Screen"
    Identifier     "nvidia"
    Device         "nvidia"
EndSection

Section "Screen"
    Identifier     "intel"
    Device         "intel"
EndSection

其实有一个官方工具nvidia-xconfig可以自动生成配置，但是它生成的配置只会在外接显示器上显示，所以需要自己配置双屏，不过可以借助此工具生成一个配置框架再修改。

方法二添加文件`/etc/X11/xorg.conf.d/10-nvidia-drm-outputclass.conf`指导系统进行自动配置

这个方法来自Arch的文档，和方法一的核心配置大致相同，只是方法一是直接指定了Device，Screen，ServerLayout等，这里只是添加OutputClass，指导X Server自动配置。

添加文件/etc/X11/xorg.conf.d/10-nvidia-drm-outputclass.conf，内容如下：

Section "OutputClass"
	Identifier  "intel"
	MatchDriver "i915"
	Driver      "modesetting"
EndSection

Section "OutputClass"
	Identifier  "nvidia"
	MatchDriver "nvidia-drm"
	Driver      "nvidia"
	Option      "AllowEmptyInitialConfiguration"
	Option      "PrimaryGPU"   "yes"
	ModulePath  "/usr/lib/nvidia/xorg"
	ModulePath  "/usr/lib/xorg/modules"
EndSection

使用`xrandr`配置双屏

配置完上面的之后可能需要重启X服务，最简单的方法大概就是直接重启机器了。

配置内容如下:

xrandr --setprovideroutputsource modesetting NVIDIA-0
xrandr --auto
# 如果显示DPI不正常的话添加下面的DPI配置
# xrandr --dpi 96

其中最关键的是第一条命令。可以把这几条命令写入 ~/.xinitrc 或者 ~/xsession，根据自己的具体情况吧，也可能需要配置你的Display Manager（如果有的话）。

核心步骤已经说的差不多了，到这里为止应该已经可以在xrandr中看到内置显示器和外置显示器都处于connected状态了，已经可以根据自己的需要进行输出了。

顺便附上自己的 .xinitrc，这来自一台没有使用Display Manager的Arch系统，在 .xinitrc 的最后启动了i3桌面管理器。

#!/bin/sh

#######################################################
#            original /etc/X11/xinit/xinitrc          #
#######################################################

userresources=$HOME/.Xresources
usermodmap=$HOME/.Xmodmap
sysresources=/etc/X11/xinit/.Xresources
sysmodmap=/etc/X11/xinit/.Xmodmap

# merge in defaults and keymaps
if [ -f $sysresources ]; then
    xrdb -merge $sysresources
fi

if [ -f $sysmodmap ]; then
    xmodmap $sysmodmap
fi

if [ -f "$userresources" ]; then
    xrdb -merge "$userresources"
fi

if [ -f "$usermodmap" ]; then
    xmodmap "$usermodmap"
fi

# start some nice programs
if [ -d /etc/X11/xinit/xinitrc.d ] ; then
 for f in /etc/X11/xinit/xinitrc.d/?*.sh ; do
  [ -x "$f" ] && . "$f"
 done
 unset f
fi


#######################################################
#                     lpy's xinitrc                   #
#######################################################

# Dual Display
# The X server must be told to configure iGPU displays using PRIME. 
# This can be done using the ‘xrandr’ command line tool, 
# via ‘xrandr –setprovideroutputsource modesetting NVIDIA-0’. 
# If this fails, you can verify the available graphics devices 
# using ‘xrandr –listproviders’.
xrandr --setprovideroutputsource modesetting NVIDIA-0
# Once PRIME is configured as described above, the iGPU’s heads may 
# be configured as if they were the dGPU’s with any RandR-aware tool, 
# be it ‘xrandr’ or a distro-provided graphical tool. The easiest way 
# to get something to display is ‘xrandr –auto’, but more complicated 
# configuration is possible as well.
xrandr --auto
# If your display dpi is not correct add the following line
# xrandr --dpi 96


# Disable DPMS turning off the screen
xset -dpms
xset s off

# Disable bell
xset -b

# Enable zapping (C-A-<Bksp> kills X)
setxkbmap -option terminate:ctrl_alt_bksp

# Enforce correct locales from the beginning:
# LC_ALL is unset since it overwrites everything
# LANG=de_DE.UTF-8 is used, except for:
# LC_MESSAGES=C never translates program output
# LC_TIME=en_DK leads to yyyy-mm-dd hh:mm date/time output
unset LC_ALL
export LANG=zh_CN.UTF-8
export LC_MESSAGES=C
export LC_TIME=en_US.UTF-8

# Use XToolkit in java applications
export AWT_TOOLKIT=XToolkit

# Set background color
xsetroot -solid "#333333"

# Enable core dumps in case something goes wrong
ulimit -c unlimited

# input method
export GTK_IM_MODULE=ibus
export QT_IM_MODULE=ibus
export XMODIFIERS=@im=ibus

# i3-sensible-terminal
export TERMINAL=termite

# Start i3 and log to ~/.i3/logfile
mkdir -p ~/.i3/log
echo "Starting at $(date)" >> ~/.i3/log/"$(date +%Y%m%d)".log
exec /usr/bin/i3 -V -d all >> ~/.i3/log/"$(date +%Y%m%d)".log

参考资料

Debian Wiki - NVIDIA Optimus
Nvidia Forums - Prime and Prime synchronization
Arch Wiki - NVIDIA Optimus

网络桥接

Linux bridge

ip 和 bridge

基本命令

ip命令

bridge命令

利用树莓派验证brdige的二层交换功能

实验设备

实验思路

桥接

连接网络

故障排除

测试结果

树莓派配置信息

设备IP配置

tcpdump部分抓包结果

参考资料

解决方案

操作步骤

达成的目标

主机配置

桥接网络配置

NAT网络配置

VMware Virtual Ethernet Adapter for VMnet8 网络属性

虚拟机当中由DHCP Client配置的 DNS 以及网关

补充说明

虚拟机配置

Ubuntu Server 20.04 的网络配置方法

我的配置文件

树莓派配置MacVLAN虚拟接口

为什么网络接口、交换机可以虚拟化？

参考资料&相关链接

简介

系统安装

如何让Win10在系统盘重建ESP分区？

UEFI启动项管理软件

指定用户名

初始配置

卸载自带应用

Onedrive同步

WSL2配置

WSL2安装

如何从主机访问WSL2？

自动启动WSL2，以及其中的一些服务

Windows Terminal 中 wsl自动进入 ~

Win10 实用软件

WinSW: 设置守护服务

AutohotKey: 配置快捷键

WSL2子系统环境配置

使用python3作为默认python

vim配置

node安装

简介

快速幂

基本原理

时间复杂度

代码实现

快速幂模

基本原理

代码实现

加速RSA加密解密过程

简介

所需数学知识

同余

欧拉定理

欧拉函数

扩展欧几里得算法

模反元素

生成密钥

加密与解密

加密

解密

解密原理

签名与验证

算法安全性

DEMO

参考资料

简介

裴蜀定理

定义

Windows Terminal 中 wsl自动进入 `~`

方案一使用开源驱动nouveau

方案二使用Nvidia官方驱动，采用Nvidia单显卡渲染

方法一直接配置xorg.conf文件

方法二添加文件`/etc/X11/xorg.conf.d/10-nvidia-drm-outputclass.conf`指导系统进行自动配置

使用`xrandr`配置双屏