练习题 - 编码(数理逻辑)

前言

算法拾遗继续。

题目

问题描述

DEX国刚刚截获了KCAJ国与AWAW国之间的S.Message 。D国S302情报机构情报员007 手里正拿着写有K国与A国之间Message的文件。“什么?!居然被加密了!!”007忍不住说道,“KCAJ,你会出路的!”
幸运的是K国与A国此次通讯时间远远超过了007所估计的30s,因此007又截获了大量的Message。通过对这些Message的研究,007发现了其中的秘密:

每一条S.Message原本由8个32-bit的正整数N1..N8组成,本来这8个整数可以由计算机直接破解得出相应的文字。但对于每条信息,K国与A国另外使用了不同的密钥M来再次加密。所谓“密钥”其实也是一个32-bit的整数,在传递讯息的时候,是将N1 Xor M、N2 Xor M、…、N8 Xor M、N9 Xor M这9个整数传给对方(其中N9为N1~N8这8个整数的和Mod 2^32)。
有了上面的发现,007马上意识到他可以破解出Message了!这实在是一个简单的工作,007决定让你——也就是他的助手来完成此工作。

输入(encode.in)

输入文件按顺序输入9个整数N1..N9。每个整数用16进制表示。

输出(encode.out)

输出仅一个数,即密钥M。同样用16进制表示。

样例

encode.in

3 4 4 7 7 b a 2 2e

encode.out

6

数据规模

40%的数据满足M<=500;
100%的数据满足M<2^32;

解答

由于本题涉及32位整数,因此本题的求解以二进制为核心。另外考虑二进制异或运算的特点,低位可以先确定然后再确定高位。

本题实际上采用二进制枚举算法,不过类似于决策树从低位开始枚举。

具体代码实现如下。

#include <math.h>
#include <stdio.h>

FILE *in, *out;
int a[11] = {0};
int b[11][33] = {0}, m[33] = {0};

void fdo2zhuan(int num, int x[]) {
  int i;
  for (i = 0; i < 32; i++) {
    x[i] = num % 2;
    num = num / 2;
  }
}

int fdo10zhuan(int x[]) {
  int i, tem = 0, quan = 1;
  for (i = 0; i < 32; i++) {
    tem += x[i] * quan;
    quan *= 2;
  }
  return (tem);
}

void fdosearch(int i, int jin) {
  if (i == 32) {
    fprintf(out, "%x\n", fdo10zhuan(m));

    fclose(in);
    fclose(out);
    exit(0);
  }

  int j, k, sum;
  for (j = 0; j <= 1; j++) {
    m[i] = j;
    sum = 0;
    for (k = 1; k <= 8; k++)
      sum += m[i] ^ b[k][i];
    sum += jin;
    if (sum % 2 == (m[i] ^ b[9][i]) % 2) {
      jin = sum / 2;
      fdosearch(i + 1, jin);
    }
  }
}

int main() {
  in = fopen("encode.in", "r");
  out = fopen("encode.out", "w");

  int i, j;
  for (i = 1; i <= 9; i++)
    fscanf(in, "%x", &a[i]);

  for (i = 1; i <= 9; i++)
    fdo2zhuan(a[i], b[i]);

  fdosearch(0, 0);

  fclose(in);
  fclose(out);

  return 0;
}

参考


* cached version, generated at 2018-12-04 06:23:42 UTC.

Subscribe by RSS