一道搜狗机试题的解答
在网上看到搜狗这道机试题,觉得好深奥。一时技痒,尝试做了下,运行结果比较有意思-“搜狗输入法支持各种炫酷的皮肤,彰显个性的你!!!”。运算涉及到异或、与、(无符号)移位、还有强制转型,难度并不算大。
题目如下:
/** * 搜狗机试题,根据encode方法写出decode方法 * */ public class TestDecode { public static void encode(byte[] in, byte[] out, int password) { int len = in.length; int seed = password ^ 0x8c357ca5; for (int i = 0; i < len; ++i) { byte a = (byte) ((in[i] ^ seed) >>> 5); byte b = (byte) (((((int) in[i]) << 16) ^ seed) >>> (16 - 3)); a &= 0x7; b &= 0xf8; out[i] = (byte) (a | b); seed = (seed * 3687989 ^ seed ^ in[i]); } } public static void decode(byte[] in, byte[] out, int password) { int len = in.length; int seed = password ^ 0x8c357ca5; for (int i = 0; i < len; ++i) { //填写代码 } } public static void main(String[] args) throws Exception { int password = 0xe87dd9d3; byte[] buf1 = { 29, -16, 96, 43, -85, 25, -96, 83, 13, 66, -109, 49, -111, 0, 60, -101, 99, -86, -38, 86, -35, 48, 23, 83, -102, 25, 73, -116, -101, -88, -5, 14, -14, -112, 87, -87, 2, 108, -58, 40, 56, 12, 108, 77, 83, 38, 20, -114, }; byte[] buf2 = new byte[buf1.length]; decode(buf1, buf2, password); System.out.println(new String(buf2, "GBK")); } }
首先,分析加密方法。seed每次加密都有变化,解密的时候,也需要计算。计算代码为:seed = (seed * 3687989 ^ seed ^ out[i]);。 循环体内,12-17行是由明文生成密文的方法。
12行,byte a = (byte) ((in[i] ^ seed) >>> 5);将明文与种子异或右移5位取证,得到的byte的3-1位是明文8-6位的与种子8-6位的异或结果。13行,byte b = (byte) (((((int) in[i]) << 16) ^ seed) >>> (16 - 3));将明文左移至24-17位与种子24-17位异或然后右移13位,得到的byte的8-4位是是原明文的5-1位与种子24-17位异或的结果。14行,
a &= 0x7;//与00000111与运算,取低三位。15行,b &= 0xf8;// 与11111000与运算取高五位。16行,out[i] = (byte) (a | b);使用a的低三位与b的高5位合成密文。很明显,经过简单的运算,明文的8-6位生成了密文的3-1位,明文的5-1位生成了密文的8-4位。
然后,根据加密方法,逐步求解。int seedForLow3 = seed;int seedForHigh5 = seed >>> 16;byte low3 = (byte) (in[i] << 5); byte hight5 = (byte) (in[i] >>> 3);//将高地位与其种子对齐。out[i] = (byte) (((low3 ^ seedForLow3) & 0xe0) | ((hight5 ^ seedForHigh5) & 0x1f));将高低位分别与种子异或后拼合为原明文。seed = (seed * 3687989 ^ seed ^ out[i]);计算新种子
完整的代码如下:/**
* 搜狗机试题,根据encode方法写出decode方法 * * @author SunShadow * */ public class TestDecode { public static void encode(byte[] in, byte[] out, int password) { int len = in.length; int seed = password ^ 0x8c357ca5; for (int i = 0; i < len; ++i) { // 与种子异或后右移5位,即高3位与876位异或 高三位至3-1 byte a = (byte) ((in[i] ^ seed) >>> 5); // 与种子的24-17异或后取低五位 低五位至8-4 byte b = (byte) (((((int) in[i]) << 16) ^ seed) >>> (16 - 3)); a &= 0x7;// 取低三位 00000111 b &= 0xf8;// 取高五位11111000 out[i] = (byte) (a | b); seed = (seed * 3687989 ^ seed ^ in[i]); } } public static void decode(byte[] in, byte[] out, int password) { int len = in.length; int seed = password ^ 0x8c357ca5; for (int i = 0; i < len; ++i) { int seedForLow3 = seed; int seedForHigh5 = seed >>> 16; byte low3 = (byte) (in[i] << 5); // 现在在8-6位 byte hight5 = (byte) (in[i] >>> 3);// 现在在5-1位 out[i] = (byte) (((low3 ^ seedForLow3) & 0xe0) | ((hight5 ^ seedForHigh5) & 0x1f)); seed = (seed * 3687989 ^ seed ^ out[i]);// 计算种子 } } public static void main(String[] args) throws Exception { int password = 0xe87dd9d3; byte[] buf1 = { 29, -16, 96, 43, -85, 25, -96, 83, 13, 66, -109, 49, -111, 0, 60, -101, 99, -86, -38, 86, -35, 48, 23, 83, -102, 25, 73, -116, -101, -88, -5, 14, -14, -112, 87, -87, 2, 108, -58, 40, 56, 12, 108, 77, 83, 38, 20, -114, }; byte[] buf2 = new byte[buf1.length]; decode(buf1, buf2, password); System.out.println(new String(buf2, "GBK")); } }
上一篇: *里犯人的对话
下一篇: 使用python批量转换文件编码方式