爸爸在你的名字里藏了你博士学位的研究方向，你解一下
图片：Christiaan Colen / CC BY-SA
如何将一个英文单词通过转码或者数学计算等手段隐藏在一个中文字里？
PhD/PKE/Java/听译
2017 年 01 月 01 日，也就是我将要步入 27 岁的这一年的第一天，正当我准备出门欢度元旦的时候，我年迈的父亲把我叫住。
于是，发生了如下令我惊讶的对话。
这段对话让我知道了我的身世，了解了我父母的过去，以及我父母相隔 27 年对我的嘱托。
父：儿子，很抱歉隐瞒了你那么多年。其实，我和你妈妈不是普通的工人，你的身上遗传了密码学家的血液…
我：老爸，你逗我玩呢…
父：我们早在你出生的时候，就知道你会攻读博士学位，并在 27 岁的那年毕业。
我：What The ……
父：你的名字“巍然”里面，已经隐藏了你的毕业时间，甚至你博士的攻读方向。正如我们所期待的，你去研究了公钥密码学。
我：（黑人问号…）
父：这里有一个信封，你出生那天我在邮局把这封信寄给了我自己，你看上面有邮戳。
我：然后呢？
父：我现在打开它。你看，里面有几行数字。现在，用你学的密码学知识，实现一个 RC4 算法。
我：我一个做公钥密码的，竟然要实现流加密算法… 行吧，实现完了，然后呢？
父：把你的名字用 UTF-8 编码。
我：好了，“巍然”这个字符串用 byte 数组表示是[-27, -73, -115, -25, -124, -74]。
父：现在，用信上的“1CAF19”作为密钥，调用 RC4 解密前两个 byte，也就是[-27, -73]。
我：这个容易，解密结果是[50, 55]。
父：再用 UTF-8 解码这个 byte 数组，就是你博士毕业的年龄。
我：我靠，这，这怎么可能？真的是 27。
父：现在，用信上的“4A320F71”作为密钥，调用 RC4 解密[-27, -73]，用“56AE6761”解密[-115, -25]，用“34CADC7A”解密[-124, -74]。
我：得到的是[-27, -123, -84, -23, -110, -91]。
父：再用 UTF-8 解码这个 byte 数组，就是你的博士研究方向。
我：竟然是“公钥”，老爸，我给你跪了…
上面就是搞笑一下啦~ 这个问题非常有意思！我一激动，花了 1 小时左右的时间写了实现的代码，构思了一下整个实现流程，应该是问题不大的。
实际上，这是密码学里面很著名的一个问题：潜信道信息传输问题。所谓潜信道，指的是通过一段哈希值、加密的密文、数字签名的结果隐蔽传递一段信息。
- 对于一般人，这段信息和正常的哈希值、密文、数字签名没有任何区别。哈希值依然可以实现完整性验证，密文依然可以正确解密得到明文，数字签名依然可以实现验证。
- 对于潜信道接收者，其可以从哈希值、密文、数字签名中得到隐蔽发送的信息。
对这方面感兴趣的知友们，可以看一看潜信道传输的开创者 Gustavus J. Simmons 于 1993 年在密码学顶级会议 EUROCRYPT 上发表的论文《Subliminal Communication is Easy Using the DSA》，就明白具体实现的思路了（Subliminal Communication is Easy Using the DSA）。这篇论文由于已经过了版权年限，因此可以公开下载和阅读。论文的阅读需要一点抽象代数的知识，不过难度并不是特别大，相信有一定基础的人都能读懂的。
最开始那段对话是如何做到的呢？其实思路很简单。密码学加密的目的是用密钥将一段明文信息加密成一段看起来像随机数的密文信息。我们反过来想：是否能找到一个密钥，使得明文的加密结果正好等于指定的密文呢？换句话说：
能否找到一个密钥，使得隐藏信息在密钥下的加密结果恰好等于正常传输信息？
答案当然是肯定的。我们遍历所有可能的密钥值，不断进行尝试，总可能找到密钥，使得隐藏信息的加密结果恰好等于名字本身。举个例子：
- “巍”这个字的 UTF-8 编码为[-027, -073, -115]
- “PhD”词语的 UTF-8 编码为[ 080, 104, 068]
- 目标：找一个密钥 key，使得[-027, -073, -115] = Encrypt(key, [080, 104, 068])
- 把 key 保存好，需要的时候让对方执行 Decrypt(key, [-027, -073, -115])，就可以解密得到[080, 104, 068]了。
这里有个问题，随着名字长度的增长，找这个密钥所花费的时间会指数级增大。如果名字长度为 k 比特，那么找到密钥预计要花费 2^k 次操作。
举个例子，“巍”这个字的 UTF-8 编码长度为 24bit，“PhD”词语的 UTF-8 编码长度同样为 24bit。找一个长度大于 24bit（比如 64bit）的密钥，使得[-027, -073, -115] = Encrypt(key, [080, 104, 068])，大概需要多长时间呢？具体时间我测了 3 次，最近一次测试结果如图所示：
差不多需要 1 分钟左右。
技术是死的，人是活的嘛，我们可以把隐蔽信息按 byte 拆分，依次寻找对应的密钥，然后再组合起来就好了呀！寻找 1byte=8bit 隐藏信息对应的密钥需要花费 2^8=512 次操作，若隐蔽信息一共有 k 比特，则一共需要花费 512k 次操作，只不过代价是密钥变长了…
举个例子，我们把“PhD”词语 UTF-8 编码里面的[80]藏到“巍”这个字 UTF-8 编码的[-27]中，把[104]藏到[-73]中，把[68]藏到[-115]中，即：
- 找密钥 key1，使得[-002] = Encrypt(key1, [080])
- 找密钥 key2，使得[-073] = Encrypt(key2, [104])
- 找密钥 key3，使得[-115] = Encrypt(key3, [068])
我用我电脑测试了一下，结果如下图：
约需要 160ms。但实际上因为 nanoTime()精度到不了那么高，所以这个时间是有很大误差的。
既然这个速度太快了，我们尝试把 2 个 byte 合成一组找密钥，看看时间。测试结果如下图：
约需要 218ms。需要强调的是，这个时间是比较准确的。因为理论上 3 个 byte 和 2 个 byte 找密钥的时间应该差 2^8=512 倍，而 60s 和 0.2s 差不多 300 倍，还是合理的。
这样一来，我们可以在任意名字里面隐藏任意信息了，只不过需要密钥的参与而已。
不过这还不满足父亲题主的要求。孩子还没出生我就想隐藏个信息，那孩子长大了，我怎么向他（她）证明我是当时隐藏的信息，而不是现在随便拿一台电脑算了个密钥呢？这就用到最开始故事中的方法了。这个方法其实挺常见的，在此引用 @岳峰 答案个人作者被侵权时，怎样证明该作品是自己的原创才具有法律效力？ - 岳峰的回答 - 知乎：
在国外，有的作家将自己的文稿通过邮局邮寄给自己，收到后不拆封，等到需要证明的时候拿出来，依靠信封上邮戳的时间和里面的文稿就可以证明是自己的原创作品。这个方法简单有效，虽然已经是互联网时代了，但仍然被很多人沿用。
实际上，这个方法映射的是密码学中的另一个领域：盲签名。这个概念比潜信道传输的概念提出时间更早。盲签名概念的提出甚至造就了第一个安全电子货币的诞生哦！在当时所引发的震动不亚于现在比特币的热潮。具体论文可以参考电子货币奠基人 David Chaum 于 1983 年在密码学顶级会议 CRYPTO 上发表的论文《Blind Signatures for Untraceable Payments》（Blind Signatures for Untraceable Payments）。这篇论文同样过了版权期限，可以公开下载和阅读。
能不能不借助密钥，直接在名字中隐藏有意义的信息呢？我感觉比较困难，因为名字的编码都是固定的，再怎么进行操作，操作方法都是固定的。而且，我们需要对操作方法保密，这总需要父亲题主自己保留一个秘密。我个人认为并没有使用密钥的方法来的方便。
@毛鳴 同学把握了真谛，在此引用他的评论作为实际没开始时那段故事的铁证：
列个时间表：
1990 年，你爸寄了好多封信（我才不信他能预测未来呢哼）
1992 年，Unicode 1.0.1 收录中文字，包括文中用到的 4 个字
1993 年，UTF-8 正式公开
1994 年，RC4 实现被意外公开（我知道谁是幕后黑手了……）
你的父母影响力很大啊…
嗯，“我父母”提前 3 年定义了 UTF-8 编码，提前 4 年就知道了 RC4 算法的具体执行流程，流着这样的密码学血液，就问怕不怕~
大家想试一试效果吗？我这里提供两个方法：
- 逐个 byte 依次隐藏，对应函数为 findShortMessageKey()；
- 2 个 byte 一组隐藏，对应函数为 findLongMessageKey()。
代码支持任意长度信息隐藏在任意长度字符串中，同时支持密钥长度的设定。源代码参考如下：
import org.bouncycastle.crypto.StreamCipher;
import org.bouncycastle.crypto.engines.RC4Engine;
import org.bouncycastle.crypto.params.KeyParameter;
import org.bouncycastle.util.encoders.Hex;
import java.security.SecureRandom;
import java.util.Arrays;
/**
* Created by Weiran Liu on 2017/1/18.
*
* Hide messages in a known string.
*/
class HideMessage {
private static int longKeySize = 4;
private static int shortKeySize = 2;
private final byte[] byteArrayName;
private final byte[] byteArrayHidden;
HideMessage(String nameString, String hiddenString) {
this.byteArrayName = nameString.getBytes();
this.byteArrayHidden = hiddenString.getBytes();
System.out.println(" Name in Bytes: " + Arrays.toString(byteArrayName));
System.out.println("Hidden in Bytes: " + Arrays.toString(byteArrayHidden));
}
static void setLongKeySize(int keySize) {
if (keySize <= 2) {
System.out.println("Invalid given long key size " + keySize + ", key size does not change");
}
HideMessage.longKeySize = keySize;
}
static void setShortKeySize(int keySize) {
if (keySize <= 1) {
System.out.println("Invalid given short key size " + keySize + ", key size does not change");
}
HideMessage.shortKeySize = keySize;
}
byte[][] findShortMessageKey() {
SecureRandom secureRandom = new SecureRandom();
byte[][] candidateKey = new byte[byteArrayHidden.length][shortKeySize];
byte[] result;
int nameLevel = 0;
for (int hiddenLabel = 0; hiddenLabel < byteArrayHidden.length; hiddenLabel++) {
do {
secureRandom.nextBytes(candidateKey[hiddenLabel]);
result = CTREncryption(candidateKey[hiddenLabel], new byte[] {byteArrayHidden[hiddenLabel]});
} while (result[0] != byteArrayName[nameLevel]);
System.out.println("Candidate Key " + hiddenLabel + " = "
+ Hex.toHexString(candidateKey[hiddenLabel]).toUpperCase());
nameLevel ++;
if (nameLevel == byteArrayName.length) {
nameLevel = 0;
}
}
return candidateKey;
}
String recoverShortMessage(byte[][] candidateKey) {
byte[] result = new byte[candidateKey.length];
int nameLevel = 0;
for (int hiddenLabel = 0; hiddenLabel < candidateKey.length; hiddenLabel++) {
byte[] tempResult = CTRDecryption(candidateKey[hiddenLabel], new byte[] {byteArrayName[nameLevel]});
System.arraycopy(tempResult, 0, result, hiddenLabel, tempResult.length);
nameLevel ++;
if (nameLevel == byteArrayName.length) {
nameLevel = 0;
}
}
return new String(result);
}
byte[][] findLongMessageKey() {
if (byteArrayHidden.length % 2 != 0) {
throw new RuntimeException("Hidden meesage byte array length must be an even number");
}
if (byteArrayName.length % 2 != 0) {
throw new RuntimeException("Name meesage byte array length must be an even number");
}
SecureRandom secureRandom = new SecureRandom();
byte[][] candidateKey = new byte[byteArrayHidden.length / 2][longKeySize];
byte[] result;
int nameLevel = 0;
for (int hiddenLabel = 0; hiddenLabel < byteArrayHidden.length; hiddenLabel += 2) {
do {
secureRandom.nextBytes(candidateKey[hiddenLabel / 2]);
result = CTREncryption(candidateKey[hiddenLabel / 2],
new byte[] {byteArrayHidden[hiddenLabel], byteArrayHidden[hiddenLabel + 1]});
} while (result[0] != byteArrayName[nameLevel] || result[1] != byteArrayName[nameLevel + 1]);
System.out.println("Candidate Key " + hiddenLabel / 2 + " = "
+ Hex.toHexString(candidateKey[hiddenLabel / 2]).toUpperCase());
nameLevel += 2;
if (nameLevel == byteArrayName.length) {
nameLevel = 0;
}
}
return candidateKey;
}
String recoverLongMessage(byte[][] candidateKey) {
if (byteArrayName.length % 2 != 0) {
throw new RuntimeException("Name meesage byte array length must be an even number");
}
byte[] result = new byte[candidateKey.length * 2];
int nameLevel = 0;
for (int hiddenLabel = 0; hiddenLabel < candidateKey.length; hiddenLabel++) {
byte[] tempResult = CTRDecryption(candidateKey[hiddenLabel],
new byte[] {byteArrayName[nameLevel], byteArrayName[nameLevel + 1]});
System.arraycopy(tempResult, 0, result, hiddenLabel * 2, tempResult.length);
nameLevel += 2;
if (nameLevel == byteArrayName.length) {
nameLevel = 0;
}
}
System.out.println("Hidden Message in bytes = " + Arrays.toString(result));
return new String(result);
}
static byte[] CTREncryption(byte[] key, byte[] plaintext) {
assert(key != null && plaintext != null);
KeyParameter keyParameter = new KeyParameter(key);
StreamCipher streamCipher = new RC4Engine();
streamCipher.init(true, keyParameter);
byte[] ciphertext = new byte[plaintext.length];
streamCipher.processBytes(plaintext, 0, plaintext.length, ciphertext, 0);
return ciphertext;
}
static byte[] CTRDecryption(byte[] key, byte[] ciphertext) {
assert(key != null && ciphertext != null);
KeyParameter keyParameter = new KeyParameter(key);
StreamCipher streamCipher = new RC4Engine();
streamCipher.init(false, keyParameter);
byte[] plaintext = new byte[ciphertext.length];
streamCipher.processBytes(ciphertext, 0, ciphertext.length, plaintext, 0);
return plaintext;
}
}
调用示例如下：
public static void main(String[] args) {
String name = "巍然";
String hide = "公钥";
HideMessage hideMessage = new HideMessage(name, hide);
HideMessage.setLongKeySize(4);
byte[][] candidateKey = hideMessage.findLongMessageKey();
System.out.println(hideMessage.recoverLongMessage(candidateKey));
HideMessage.setShortKeySize(2);
candidateKey = hideMessage.findShortMessageKey();
System.out.println(hideMessage.recoverShortMessage(candidateKey));
}
我在“知乎”这个名字里面隐藏了一段话，各密钥长度为 16byte，密钥依次为：
Key 00 = EDE20EAFE2A53F89960243E67835EB79
Key 01 = 90878DC31E9475BE760B025AEA340EC1
Key 02 = 877066098F00956408DC8331B0E434D8
Key 03 = 967C3E9C350D380C2D66C519DED5C09A
Key 04 = F1417629CF92283C694C8D81DC8DE37A
Key 05 = E2BC55790F4BE3F845BC391EACA43412
Key 06 = 77D86F5AC3B8C3001975941F6E0FEEAE
Key 07 = C5B5646B75350F3772ED4F6567FBC8A1
Key 08 = E9EB9D5CEA80C584AD3816D34C00614E
Key 09 = 83AFD62DAE14D042074B04054552E3F9
Key 10 = FA893C4E5F36282DE62797553A4ECABB
Key 11 = EDE3A2F37B56E94E3267459DBA1B2F62
Key 12 = 786BD904220E12F352AFDCAF7C52BCB1
Key 13 = 88DA076C83430B517193E2BC780C153D
Key 14 = 0162ABB0A41FDAF8B7663A3C89E97DEC
请知友们试一试，我隐藏了什么信息？
转载请注明：微图摘 » 爸爸在你的名字里藏了你博士学位的研究方向，你解一下
