标签： Cryptography

手机 APP 应该选用哪个加密算法 - 兼吐槽 TEA

很多 APP 产品都有通信加密的需求，一部分出于市场的要求，比如苹果对于“ATS”的强制性规定，一部分出于自身安全的考虑，比如对账号和密码的保护。这些需求大部分都可以用简单的 HTTP -> HTTPS 升级来搞定，而且几乎不用付出什么成本（除加解密的计算开支外），例如使用我之前文章介绍到的 Let's Encrypt 免费证书。

但还有一类特殊的需求，HTTPS 解决不了，也就是防协议分析的需求。很多 APP 开发者应该知道，只要在手机里安装一个代理 CA 证书，就可以实现中间人攻击，通过代理软件抓到 HTTPS 包的明文内容。虽然这样的攻击很难在公开网络上进行，但对自己的手机进行抓包分析，作为 APP 和服务端通信的调试手段是被广泛使用的。

协议分析能做什么呢？可以猜想到一定的 APP 内部逻辑，可以对产品数据进行作弊攻击。举个例子：你的 APP 通过某个渠道进行推广，为了统计渠道安装、注册或者日活，你往往会在 APP 中埋一个点，当 APP 启动时，发送一些信息到服务器。如果这个协议被破解了，渠道商根本不需要真正进行推广，只需要构造一些假消息发送到你的服务器就行了。仅看数据你可能会以为这个渠道推广效果特别好，其实只是骗局而已。

这类情况下，就要求对敏感协议内容进行额外的数据保护。最常用的做法，就是对协议内容进行一次额外的加密，为了性能，往往选用对称加密算法。那么问题来了，手机 APP 开发时，应该选用哪个加密算法？

关于这个选型，国内互联网圈有个怪现状值得谈一下，那就是 TEA 算法。因为该算法在腾讯有着广泛的应用，因而被很多客户端开发人员推崇。典型推荐理由往往是：“TEA加密算法不但比较简单，而且有很强的抗差分分析能力，加密速度也比较快，还可以根据需求设置加密轮数来增加加密强度”。这是真的吗？算法安全性可以直接看维基百科上 TEA 算法的介绍，我的理解是不够安全。但其实大部分用户也不那么地在乎它的安全强度，那么性能呢？加密速度真的很快吗？

这就要从历史的角度去看了。作为曾经手撸过 “DES 差分密码攻击” 代码的程序员，表示 TEA 算法的确足够简单。在 QQ 诞生的那个年代，TEA 在计算上的确有着不小的优势。但 QQ 已经 18 岁了啊同学们，18 年来中国发生了多大的变化，世界发生了多大的变化啊！

2008 年，Intel 就发布了 x86 的 AES 指令集扩展，近几年的服务器 CPU 应该都支持，不相信你
grep aes /proc/cpuinfo 就能看到 ；2011 年 ARM 也在 ARMv8 架构下直接提供了 AES 和 SHA-1/SHA-256 指令 。这意味着什么？意味着服务端和客户端在硬件上直接支持 AES，意味着原来 N 条汇编指令只需要一条 AES 指令就完成了。其实也意味着，在绝大多数情况下 AES 才应该是你的首选。

口说无凭，咱们可以看一下测试数据，x86 服务器 CPU 测试可以直接看 Crypto++ 的 benchmark 。可以看到 AES/CTR (128-bit key) 与 TEA/CTR (128-bit key) 的加密速度比是：4499 MB/s 比 72 MB/s，62 倍的差异！这就是硬件实现的威力。

ARM 手机 CPU 加密算法的 Benchmark，我没有找到。但为了更有说服力，我自己实现了两个测试 APP，一个 Android 版，一个 iOS 版。写技术文章多不容易啊，写博客之前先写三个晚上代码，泪目！！！代码在 https://github.com/solrex/cipher-speed ，Android 版可以直接在 Release 里扫码安装。

首先介绍一下目前的旗舰 CPU，骁龙 835 (MSM8998) 的表现，测试机型是小米 6：

# Speed Test of 10MB Data Enc/Decryption #
# AES: 
* [AES/CBC/PKCS5Padding] ENC: 1146.9 KB/ms
* [AES/CBC/PKCS5Padding] DEC: 692.4 KB/ms
* [AES/CBC/NoPadding] ENC: 1118.8 KB/ms
* [AES/CBC/NoPadding] DEC: 1343.5 KB/ms
* [AES/ECB/PKCS5Padding] ENC: 990.4 KB/ms
* [AES/ECB/PKCS5Padding] DEC: 703.2 KB/ms
* [AES/ECB/NoPadding] ENC: 973.4 KB/ms
* [AES/ECB/NoPadding] DEC: 988.9 KB/ms
* [AES/GCM/NOPADDING] ENC: 13.9 KB/ms
* [AES/GCM/NOPADDING] DEC: 14.7 KB/ms
# DES: 
* [DES/CBC/PKCS5Padding] ENC: 20.1 KB/ms
* [DES/CBC/PKCS5Padding] DEC: 20.7 KB/ms
* [DES/CBC/NoPadding] ENC: 21.3 KB/ms
* [DES/CBC/NoPadding] DEC: 21.6 KB/ms
* [DES/ECB/PKCS5Padding] ENC: 26.3 KB/ms
* [DES/ECB/PKCS5Padding] DEC: 26.2 KB/ms
* [DES/ECB/NoPadding] ENC: 25.9 KB/ms
* [DES/ECB/NoPadding] DEC: 26.8 KB/ms
# 3DES: 
* [DESede/CBC/PKCS5Padding] ENC: 23.6 KB/ms
* [DESede/CBC/PKCS5Padding] DEC: 23.2 KB/ms
* [DESede/CBC/NoPadding] ENC: 23.6 KB/ms
* [DESede/CBC/NoPadding] DEC: 23.5 KB/ms
* [DESede/ECB/PKCS5Padding] ENC: 8.5 KB/ms
* [DESede/ECB/PKCS5Padding] DEC: 8.5 KB/ms
* [DESede/ECB/NoPadding] ENC: 8.5 KB/ms
* [DESede/ECB/NoPadding] DEC: 8.6 KB/ms
# TEA: 
* [TEA] ENC: 16.0 KB/ms
* [TEA] DEC: 18.1 KB/ms

可以看到，TEA:AES=16:990，这是多少倍？我都懒得算了。然后是 2 年前的中低端 CPU，联发科 Helio P10 (MT6755)，测试机型是魅蓝 Note 3：

# Speed Test of 10MB Data Enc/Decryption #
# AES: 
* [AES/CBC/PKCS5Padding] ENC: 358.8 KB/ms
* [AES/CBC/PKCS5Padding] DEC: 267.9 KB/ms
* [AES/CBC/NoPadding] ENC: 438.8 KB/ms
* [AES/CBC/NoPadding] DEC: 515.0 KB/ms
* [AES/ECB/PKCS5Padding] ENC: 310.6 KB/ms
* [AES/ECB/PKCS5Padding] DEC: 222.1 KB/ms
* [AES/ECB/NoPadding] ENC: 312.4 KB/ms
* [AES/ECB/NoPadding] DEC: 319.5 KB/ms
* [AES/GCM/NOPADDING] ENC: 5.1 KB/ms
* [AES/GCM/NOPADDING] DEC: 5.7 KB/ms
# DES: 
* [DES/CBC/PKCS5Padding] ENC: 7.5 KB/ms
* [DES/CBC/PKCS5Padding] DEC: 7.7 KB/ms
* [DES/CBC/NoPadding] ENC: 7.7 KB/ms
* [DES/CBC/NoPadding] DEC: 7.8 KB/ms
* [DES/ECB/PKCS5Padding] ENC: 9.3 KB/ms
* [DES/ECB/PKCS5Padding] DEC: 9.2 KB/ms
* [DES/ECB/NoPadding] ENC: 9.3 KB/ms
* [DES/ECB/NoPadding] DEC: 9.5 KB/ms
# 3DES: 
* [DESede/CBC/PKCS5Padding] ENC: 12.5 KB/ms
* [DESede/CBC/PKCS5Padding] DEC: 12.3 KB/ms
* [DESede/CBC/NoPadding] ENC: 12.3 KB/ms
* [DESede/CBC/NoPadding] DEC: 12.5 KB/ms
* [DESede/ECB/PKCS5Padding] ENC: 3.1 KB/ms
* [DESede/ECB/PKCS5Padding] DEC: 3.1 KB/ms
* [DESede/ECB/NoPadding] ENC: 3.1 KB/ms
* [DESede/ECB/NoPadding] DEC: 3.1 KB/ms
# TEA: 
* [TEA] ENC: 6.2 KB/ms
* [TEA] DEC: 8.0 KB/ms

然后是 3 年前的旗舰 CPU，Apple A8，测试机型是 iPhone6。别问我为啥不用今年的苹果旗舰 CPU...

# Speed Test of 10MB Data Enc/Decryption #
# AES
* [AES/CBC/PKC7Padding] ENC: 76.0 KB/ms
* [AES/CBC/PKC7Padding] DEC: 111.3 KB/ms
* [AES/CBC/NoPadding] ENC: 138.2 KB/ms
* [AES/CBC/NoPadding] DEC: 450.7 KB/ms
* [AES/ECB/PKC7Padding] ENC: 305.6 KB/ms
* [AES/ECB/PKC7Padding] DEC: 735.9 KB/ms
* [AES/ECB/NoPadding] ENC: 330.0 KB/ms
* [AES/ECB/NoPadding] DEC: 673.6 KB/ms
# DES
* [DES/CBC/PKC7Padding] ENC: 23.1 KB/ms
* [DES/CBC/PKC7Padding] DEC: 24.5 KB/ms
* [DES/CBCPadding] ENC: 23.1 KB/ms
* [DES/CBCPadding] DEC: 22.8 KB/ms
* [DES/ECB/PKC7Padding] ENC: 19.4 KB/ms
* [DES/ECB/PKC7Padding] DEC: 20.8 KB/ms
* [DES/ECBPadding] ENC: 22.2 KB/ms
* [DES/ECBPadding] DEC: 22.2 KB/ms
# 3DES
* [3DES/CBC/PKC7Padding] ENC: 9.7 KB/ms
* [3DES/CBC/PKC7Padding] DEC: 9.8 KB/ms
* [3DES/CBC/NoPadding] ENC: 9.8 KB/ms
* [3DES/CBC/NoPadding] DEC: 9.8 KB/ms
* [3DES/ECB/PKC7Padding] ENC: 9.4 KB/ms
* [3DES/ECB/PKC7Padding] DEC: 9.1 KB/ms
* [3DES/ECB/NoPadding] ENC: 9.2 KB/ms
* [3DES/ECB/NoPadding] DEC: 9.4 KB/ms
# TEA
* [TEA] ENC: 10.9 KB/ms
* [TEA] DEC: 11.1 KB/ms

关于 Apple A8 的测试多说两句。我上面的 AES 性能，离 GeekBench 发布的 A8 AES Single Core 还有不少差距，不知道是不是测试方法差异导致。但总的来说，不影响结论，那就是 TEA 跟 AES 差距巨大。

看到这里，可能大部分人心里已经做出选择了。即使还没做出选择的读者，我想你也可以考虑看看我的代码实现是否存在问题。不过最后还是回答一下开头提出的问题吧：

  • 如果你使用平台语言来实现对称加密，也就是 Android 上用 Java，iOS 上用 OC 或者 Swift，AES 是不二选择。这样能充分利用硬件提供的能力，安全性+性能肯定是最优，不要再想其他选项了。
  • 如果你使用 Native 语言来实现对称加密，在 Android 上使用 JNI 调用 C 编译的代码，的确不少人认为原生指令更难逆向。可能要在 ARM 架构上做个取舍，是取悦 v8 用户，还是取悦 v7 以下的用户，这可能影响到选型。不过我认为 AES 依然是一个好的选项，起码在服务器端，你肯定会节省成本。

Math in CS: 数论和公钥密码学

1940年，英国数学家哈代在他的一本小书《一个数学家的辩白》(A Mathematician's Apology)中说：“如果有用的知识是这样的知识（我们暂时同意这样说）：它大概会在现在或相对不远的未来，为人类在物质上的享受方面作出贡献，因而，它是否在单纯的智力上满足人们乃是无关紧要的，那么，大量更高级的数学就是无用的。现代几何和代数、数论、集合论和函数论、相对论、量子力学——没有一种比其它的更经得住这种检验，也没有真正的数学家的生涯可以在这个基础上被证明是有价值的。”但是我们会看到，哈代这个断定在当时“不远的未来”几乎被一一证明是错误的，数论就是其中一个。

在 1970 年代以前，人们所知道的密码学都是对称密码学，就是在加密和解密过程中需要使用同一个密钥。在那个时代，一些密码算法已经能保证足够的安全性，比如数据加密标准 DES。但是人类的需求是很难完全得到满足的，他们为每次密钥交换的复杂度而苦恼，比如在战时如果密码本被敌方获得，就必须重新向无线电收发员分发密码本，这个工作量和代价是相当大的；还有一个需求就是数字签名，能不能用加密实现对数字文件的签名，像手写的签名一样，确保该文件出自谁人之手？

上述问题，就是 Whitfield Diffie 和 Martin Hellman 1976 年在他们那篇划时代的论文《密码学的新方向》(New Directions in Cryptography)中提出的，他们也给出了其中一个问题的解决办法，那就是 Deffie-Hellman 密钥交换算法（后来被改为 Deffie-Hellman-Merkle 密钥交换算法，里面还有一段小故事。）。但是 DH 没做完的功课，仅仅在一年后就被 RSA 解决了，那就是 Ron Rivest, Adi Shamir, 和 Leonard Adleman 的 "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems"。RSA 的加密和解密使用的是不同的密钥，即公钥和私钥，你可以将你的公钥扔到世界上任何一个位置，我用你的公钥加密一段信息，除了你用自己的私钥解密，没有别的人能从中得到原始消息。就相当于你把打开了的箱子扔的满世界都是，但箱子一旦锁上，就只有你能再打开。

RSA 算法自其诞生之日起就成为被广泛接受且被实现的通用公钥算法，但是 RSA 算法还带来一个另外的意义，那就是：数论知识从未像现在这样被广泛地使用着。RSA 程序的普及率要远远大于 Windows，因为每台 Windows 上都装配着 RSA 算法程序，但 RSA 并不仅仅装配 Windows。每当你登录邮箱、网上银行、聊天软件、安全终端，你都在使用着数论带来的好处。而且相比之前密码学的字母替换和置换，混淆和扩散，DH 和 RSA 使用的东西更有资格说自己是数学。

大概也是由于其基于数学的简洁性，RSA 和 DH 算法描述要比 DES, AES 简练许多，我在这篇小文中都能写完。

RSA

RSA 用到了数论中的三个基本定理：费马小定理、欧拉定理和中国剩余定理（几乎处处都在），和一个古典难题：大整数分解问题。如果你是数学系的学生，对这些概念一定不会陌生。

费马小定理：若 p 是素数，a 是正整数且不能被 p 整除，则： ap-1 = 1(mod p)。或者另一种形式：ap=a(mod p)，这种形式不要求 a 与 p 互素。

欧拉定理：对任意互素的 a 和 n，有 aΦ(n) = 1(mod n)。其中，Φ(n)是欧拉函数，即小于 n 且与 n 互素的正整数的个数。

大整数分解问题：将两个整数乘起来是简单的，但是将一个整数分解为几个整数的乘积是困难的，尤其是当这个数比较大的时候。迄今为止没有有效的算法来解决这个问题，甚至我们连这个问题的计算复杂度量级是多少都不知道。

那么 RSA 算法是什么样的呢？

密钥的产生：
1. 选择两个素数 p 和 q.
2. 计算 n = p*q.
3. 计算 Φ(n) = (p-1)(q-1) （这是欧拉函数的性质）
4. 选择 e<Φ(n) 并使得其与 Φ(n) 互素。
5. 确定 d<Φ(n) 并使得 d*e = 1(mod Φ(n))。
6. 这时候，私钥就是{d, n}，公钥就是{e, n}。
加密算法：
假设 M 是明文（M<n），那么密文就是 C = Memod n。（为什么明文是数字？在计算机科学里任何数据最终表示都是数字。）
解密算法：
假设 C 是密文，那么明文就是 M = Cd mod n。

我们来证明一下算法是否正确，由于 Cd = Me*d = Mk*Φ(n)+1 (mod n)。

如果 M 和 n 是互素的，显然直接由欧拉定理我们就能得到：
Cd = Mk*Φ(n)*M1 = M (mod n) = M
说明算法是正确的；
如果 M 和 n 不互素，由于 n 是两个素数 p 和 q 的乘积且 M<n，那么 M 要么是 p 的倍数，要么是 q 的倍数，由 e*d = 1(mod Φ(n)) = 1(mod (p-1)(q-1)) 我们可得：
e*d = 1(mod (p-1)) 且 e*d = 1(mod (q-1))
则 e*d 可以写成： e*d = k*(p-1)+1, e*d = h*(p-1)+1
由费马小定理，我们有：Me*d = Mk*(p-1)+1 = M(mod p) 和 Me*d = Mh*(q-1)+1 = M(mod q)。
由于 p 和 q 均为素数，且 p, q 均整除 Me*d-M，所以我们有：
Cd = Me*d = M (mod p*q) = M (mod n) = M

从上面我们可以看到 RSA 算法实现了加密和解密使用不同密钥，而且证明了这个算法的正确性。但 RSA 算法要想实用，光有正确性还不够，最重要的一点是安全性，即从公钥{e, n}无法推导出私钥{d, n}。在 RSA 算法中我们可以看到，关键要知道 Φ(n)，知道了 Φ(n)，使用欧几里德算法就能求出 e 的逆元，就得到了用户的私钥{d, n}。要求出 Φ(n)，就必须知道 p,q，但 p,q 是不公开的，仅仅知道 p,q 的乘积 n 去求 p,q，根据大整数分解古典难题，当 n 比较大时其分解在计算上是不可行的。这就保证了 RSA 算法的安全性。

而且 RSA 算法是可逆的，所以它就有能力同时实现加密和签名的功能。由于公钥是公开的，每个人都可以用你的公钥加密一段信息发给我，而私钥是保密的，所以只有你能看到别人用你的公钥加密的消息；而也因为可逆性，如果你用私钥解密一段明文（实际是加密），所有人都可以用你的公钥加密它来得到明文（实际是解密），因为私钥只有你一个人知道，这个消息只有可能是你发出的，就相当于你对这段明文做了一个签名。

DH 密钥交换算法

DH 密钥交换算法较 RSA 算法更为简单，它也是基于数论中的一个古典难题：离散对数问题。

离散对数问题：若 p 是素数，p 已知，考虑方程 y = gx mod p，给定 g,x 求 y 是简单的，但给定 y,g 求 x，即求 x = logg,py mod p，在计算上是不可行的。

DH 密钥交换算法的描述如下：
已知公开的素数 p 和 p 的本原根 α
1. 用户 A 选择秘密的 Xa<p，计算 Ya = αXa mod p，将其发送给 B。
2. 用户 B 选择秘密的 Xb<p，计算 Yb = αXb mod p，将其发送给 A。
3. A 和 B 分别计算 Ka = (Yb)Xa mod p 和 Kb = (Ya)Xb mod p，就同时得到了共享的密钥 K=Ka=Kb，然后就可以用 K 进行加密传输了。

DH 密钥交换算法的优点在于：双方在通信前不需要知道任何共享的密钥，而是通过公开的 p 和 α 协商出一个密钥来进行加密通信。

先看一下算法的正确性，Ka = Kb 是否成立：
Ka = (Yb)Xa = (αXb)Xa = αXa*Xb (mod p)
Kb = (Ya)Xb = (αXa)Xb = αXa*Xb (mod p)
Bingo! Ka 和 Kb 是相同的。

再来看一下算法的安全性，就是能否从公开的信息推导出 K 来：
由于密钥是 K = αXa*Xb，那么攻击者必须知道 Xa 和 Xb 才能得到共享的密钥 K，而公开的信息只有 Ya 和 Yb，由离散对数问题，从 Ya,Yb 求出 Xa,Xb 在计算上是不可行的，就保证了算法的安全性。

从上面两个算法我们可以看出，数论在公钥密码学中的重要地位，恐怕哈代当时怎么也想不到三十多年后人人都在使用他所认为在实际生活中毫无用处的数论吧！

密码学：对3轮DES进行的差分密码攻击

我发现自己做事情老是有虎头蛇尾的习惯，就像文章标题的这篇实验报告一样，本来我的题目是 Differential Cryptanalytic Attacks of Reduced Round DES，后来发现写对更多轮的 DES 攻击代码太困难。其实密码分析很简单，都是别人做过的东西，拿来抄抄就是了，但是实际写起来代码才发现完全不是那么回事。文章中一句话带过的东西可能需要你编码好长时间再加调试，而且还很难找到正确代码做比较，所以写到后来实在泄气，就只写好了一个3轮的攻击，再加上我时间本来就不多，只好作罢。等以后有闲功夫了我再恢复原来那标题吧 :)

鉴于自己在做作业时找代码样例对比的难处，像上次的大作业一样，我把我对 3 轮 DES 差分攻击的实验报告又放到了我的个人网站共享空间里，可以从 https://github.com/solrex/solrex/blob/master/dc_des/dc_des_lr.pdf 下载。这篇文章主要内容是对 3 轮 DES 差分攻击特征的分析和实现，文章里面有全部 DES 加密解密和 3 轮攻击的源代码。本来我觉得我的实验报告够挫的了，因为都是别人已经做出来的东西。后来我发现在 2003 年 8 月份的《计算机工程》杂志上登过这样一篇文章《数据加密标准DES分析及其攻击研究》，基本信息量为0，连引用文献都没有写到 Eli Biham 和 Adi Shamir 经典文章，我庆幸我好歹还附上了代码...希望能对某些对密码学有点兴趣的人有所帮助。

顺便说几句废话，看到 Eric师兄在博客里说 PageRank，我查看了一下我 WordPress 博客的 PageRank，嘿嘿，居然有到 2 ？我怀疑自己是不是看花了眼，在 Win 下的 Firefox Google 工具栏，IE Google 工具栏，Linux 下的 Firefox Google 工具栏查看了三遍，都是显示 2(希望 Google Toolbar 没有耍我)。哈哈，我的博客网站居然也有 PageRank 了！大家以后多到 这里 踩我吧，另外链接我博客时候最好也用这个链接，别用 Space 或者 Blogspot 的博客链接(那个网站是人家的...) :).