杂谈-密码学当中的移位运算

本篇重新回归到随便聊聊的时刻了，才不是因为我没得写了，本篇瞎聊的内容呢就是密码学当中的移位运算的一些知识，如果读者之前学过体系结构或者对于位运算比较熟悉的话，那么这篇文章就可以不用浪费时间去看了，省下来的时间可以多陪陪家人，或者喝杯咖啡休息一下。

如果还有耐心看到这里，可能读者对于移位运算相关的知识不是很了解，希望读者不要嫌我后面的啰嗦哈，接下来我们一起来看一下移位运算是怎么个玩的。

内存当中的数据是如何存储的？

在介绍移位运算之前，我们要首先的来看一下内存当中是如何存储数据的。我们知道计算机当中数据的单位是bit, 但是呢，对于内存来说，对于一个bit是没有办法直接处理的，在计算机当中最小的存储单位实际上是字节，也就是8bit。

其实内存的一个字节，可以看做是一个套房，这个套房呢，他有点特殊，每个套房固定的有8个小屋子，每个小屋子呢，只能够住下一个bit。整个内存呢，就是有许多个这种套房构成的一个大的高楼。如果是真的一个字节看做一个套房的话，内存来说就是一个拥有贼多套房的一个房东了，这内存完全可以通过收租实现财务自由了。

那么，对于一个字节来说，我们可以通过这个字节表示一个数字，那么，这个字节可以表示多少数字呢？

通过乘法原理，我们很容易的得到，一个字节最多可以表示256个数字。这里简单说一下怎么算的吧，我们看上图，我们知道一个字节有8bit，对于每一个bit我们都有0或者1两个选择，首先来看第一个bit，我们可以表示0或者1两个数字，我们接下来再来看下一个bit，同样的有两种选择，结合之前的两种选择，那么我们就有2 × 2 = 4 中选择了，以此类推，我们就可以得到对于一个字节8bit 一共就有2^8 = 256 种选择了。

这里说的数字，我们都没有考虑到这个数字的符号，那么我们所说的负数是怎么表示的呢？

对于密码学来说，实际上字节的正负对于加密实际上是没有影响的，考虑到读者可能会用到Java这种没有无符号整数的语言，所以这里简单的聊一聊负数是怎么表示的（实际上，对于正负内存当中的bit来说实际上是没什么区别的）。

原码、反码和补码

在介绍负数如何表示之前，先来普及一下计算机当中的一些基础知识，这里下面的例子当中，我们先看一个字节可以存储的数据。

原码

一个整数，按照绝对值大小转换成为二进制表示，我们称之为原码。

举一个小栗子，我们计算5的原码，5的绝对值还是5，因此5的原码为0b00000101

反码

将二进制数按位取反，所得的新的二进制数字称之为原二进制数字的反码。

取反操作是指: 原来为1，得0；原来为0，得1。

还是用我们上面提到过的5作为例子，5的反码为0b11111010 ，这里反码是个相对的概念，a是b的反码，反过来b也是a的反码。

补码

反码加一我们称之为补码。

还是来看我们上面这个5的例子，首先我们得到反码0b11111010然后对反码加一得到0b11111011这实际上就是-5在内存当中的表示了。

通过上面来看，我们可以用0b11111011表示-5也可以用这个数字来表示一个正数251，所以说，正负实际上在内存当中的存在其实没有区别，只不过是我们怎么理解这个内存当中表示的bit。

如何将有符号数字转换为无符号数字

我们知道，在Java当中实际上是不存在无符号数字的，而对于Python当中的字节范围是0-255那么这两种语言，我们需要怎么做转换呢，我们只需要用与运算来做转换，还是用-5作为例子，转换成正数的话就是-5 & 0xFF这样就可以了。

好了，这里介绍完了怎么把一个负数转换成为一个正数，后面我们讨论的范围都考虑无符号数了，因为本身在密码学当中，我们一般不关心字节表示的是正数还是负数，实际上这存在的就是一些数据，和真实的数字实际上并没有什么关联。

移位运算

在密码学当中，我们会经常的用到左移或者右移的运算。下面我们就来聊一聊左移和右移的相关知识。还是用上面当中的房子做例子，我们知道一个字节可以看成有8个小屋子的一个小房子，bit的值存1，那么表示这个房子里面已经住了人了，那么移位运算可以怎么看呢？假设住这个房子的人都是有一些特殊的喜好，就是他们想要出去，不能够直接走，而是只能够占用他前面一个格子或者后面一个格子，要是他前面没有格子的话，那么他就可以出去了。

这里，如果想要去玩位运算相关的东西，建议用C/C++去玩，因为类似于Python，Java实际上在位运算的实现上还是有一些语言本身的东西在里面，举个例子，Python对于负数的右移其实是不考虑符号的，对绝对值进行右移运算，最后添加上原来的符号，然后Java来说，本身没有无符号数这个概念，当然Java当中也有无符号右移的这个运算符，这些都是需要注意的，而对于C语言来说，本身的变量，实际上就是在内存当中实打实的表示出来的，没有什么外层的对象包装(只考虑基本类型）因此呢，对于移位运算，实际上就是直接操作的内存当中的bit，因此呢，在搞安全分析跨语言还原算法的时候，特别的要注意不同语言之间位运算的一些差别，还有就是溢出的差别，否则搞出来的可能就是错的。

我们来看几个具体的例子，来实际看一下不同语言的差异。

• C

#include <cstdio>
int main() {
    for (int i = 0; i < 8; ++i) {
        printf("5 << %d = %hhu\n", i, (unsigned char) (5 << i));
    }
    return 0;
}
// output
5 << 0 = 5
5 << 1 = 10
5 << 2 = 20
5 << 3 = 40
5 << 4 = 80
5 << 5 = 160
5 << 6 = 64
5 << 7 = 128

• Python

if __name__ == '__main__':
    for i in range(0, 8):
        print(f"5 << {i} = {5 << i}")
# output
5 << 0 = 5
5 << 1 = 10
5 << 2 = 20
5 << 3 = 40
5 << 4 = 80
5 << 5 = 160
5 << 6 = 320
5 << 7 = 640

上面是因为Python当中实际上是没有溢出这个概念的，如果需要处理掉溢出的情况，只需要& 0xFF就好了，这里与的内容取决于具体的数字长度。

编码实现

对于Python的右移运算，实际上是没有的，我们需要自己简单实现一下。

import ctypes
MAX_INT = 0x7F
def int_overflow(val: int) -> int:
    if not -MAX_INT - 1 <= val <= MAX_INT:
        val = (val + (MAX_INT + 1)) % (2 * (MAX_INT + 1)) - MAX_INT - 1
    return val
def unsigned_right_shift(n: int, i: int) -> int:
    if n < 0:
        n = ctypes.c_uint8(n).value
    if i < 0:
        return -int_overflow(n << abs(i))
    return int_overflow(n >> i)

这里需要注意一下，具体看自己需要对哪种类型做无符号右移的运算，要针对MAX_INT对应进行修改。

总结

对于移位运算来说，这块还是稍微有点点坑的，特别是在不同语言直接照着实现的时候，一定要注意这个语言下位运算的差异，否则可能观察了好久，都没有发现自己错在哪，最终实际上是因为位运算的不同导致的结果不同。