欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一道搜狗机试题的解答

程序员文章站 2022-06-30 12:55:01
...

在网上看到搜狗这道机试题,觉得好深奥。一时技痒,尝试做了下,运行结果比较有意思-“搜狗输入法支持各种炫酷的皮肤,彰显个性的你!!!”。运算涉及到异或、与、(无符号)移位、还有强制转型,难度并不算大。

题目如下:

 

/**
 * 搜狗机试题,根据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"));
	}
}