保形加密(FPE)

2024-10-10

数学基础

保形加密解决的问题

  • 保持原始数据格式
    • AES('123456') 是一堆乱码，而 FPE('123456') 会返回一个类似 '908245' 的打乱后的字符串。
  • 保持原始数据的长度
    • AES('123456') 的输出长度必须是 16 字节的倍数，而 FPE('123456') 的输出长度和输入长度一样。

我们公司对应的场景是短链生成算法，通过数据库主键生成短链，而且要求短链长度固定。类似这样：FPE('00001') = 'a3b4c'，其中 00001 是数据库主键，a3b4c 是加密后的短链码。

其他了解到的应用场景：

  • 用户信息加密（例如公司之间营销信息共享，同时也能保证用户信息不会泄漏）

加密流程

最基本的加密公式就是 ciphertext = Encrypt(plaintext), 下表中用一个仅包含 2 次循环的简单保形加密来解释：

encrypt_formula
encrypt_formula

其中：

  • plaintext = A + B
    • 其中 A B 各占一半长度，不一定要相等长度。
  • W 即 padding，为了满足 AES block-size = 16bytes 的限制。
  • Rev() 翻转字节的函数
  • AES() 用来 AES128 加密的函数
  • mod 即取模。
    • 例如 11 % 7 = 4
    • -11 % 7 = 3
      • 因为 (-7 * 2) = -14
      • (-11) - (-14) = 3
  • U 即 A 半部分的最大表示空间。
    • 比如对于 16 进制的 plaintext='3d4'
    • A = '3d'
    • U = len(A) ** 16
    • U = 256
  • V 即 B 半部分的最大表示空间。
    • 比如对于 16 进制的 plaintext='3d4'
    • B = '4'
    • U = len(B) ** 16
    • U = 16

上述流程中是如何保形的？

利用一些取模运算的特性，如下面的代码片段所示：

# 将要被加密的原始数据 X
x = 45735432     

# 混淆用的密钥（对应 FPE 实现中的 tweak）
y = 45739654332543

# 模空间，模空间必须能够包含 X，否则造成数据丢失，那就没法解密了。
m = 99999999

print('取模特性测试，x, y, m = ', x, y, m)
c = (x+y) %m
result = (c - y) % m
print(c, result, x == result)

print('\n当 X 超出模空间的范围时，解密会失败：')
m = 99999
c = (x+y) %m
result = (c - y) % m
print(c, result, x == result)

Output:

取模特性测试，x, y, m =  45735432 45739654332543 99999999
got cipher:  525372
decrypt cipher:  45735432 True

当 X 超出模空间的范围时，解密会失败：
got cipher:  69549
decrypt cipher:  35889 False

原理就是每次循环，都通过 AES + tweak + 另外一半未加密数据 生成一个"16字节的随机数"，然后和需要被加密的数字取模，得到本次循环加密后的结果。

多次循环后，就可以得到一个毫无规律的结果。

在解密时，反着按照上面流程来一次就行。

其中，上面 Sb0 = AES(Rev(W + B0)) 是生成随机数的主要公式，并且可以被任意的加密算法替代。

参考资料

目录