前行的足迹
0%

一个看起来很简单的加密算法

发表于 分类于 ， 标签 ， ， ，

今天看到了一套加密解密算法，可以对任意数据流进行加密解密，实现很简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[C++]

unsigned char* encode( unsigned char *data, int length )
{
	for( int i = 0; i < length; i++ )
	{
		int a = data[ i ];
		a += ( i * i );
		data[ i ] = ( unsigned char )a;
	}
	return data;
}

unsigned char* decode( unsigned char *data, int length )
{
	for( int i = 0; i < length; i ++ )
	{
		int a = data[ i ];
		a -= ( i * i );
		data[ i ] = ( unsigned char )a;
	}
	return data;
}

这段代码看起来操作非常简单。

  • 源数据上加了一个数，然后强转成 unsigned char。

  • 解密时就是把加密数据减去之前加的那个数，然后再强转成 unsigned char。

恩，看起来他就是做了这点事儿。不过从字面上看，总感觉它加密之后没法正确的还原。
因为 a + ( i * i ) 之后很容易就超过1字节的上限（255），当强转回unsigned char时，超出上限的高位部分会被截断丢弃。
得出的这个结果无论怎么看都觉得不可能再还原成源数据。

##但神奇的是它真的能正常工作，而且不会出错！

###一点理解

  • 源数据取值范围为0~255，但实际上源数据和加密数据数据只要保持相同类型公式就成立，如源数据改为unsigned short那么
    加密数据只要相应的做unsigned short强制转换就可以保持公式的成立。

  • 后边参与加减计算的数实际上可以为任意自然数,这里是用平方数可能是为了使加密数据更加没有规律。

  • 这个算法神奇之处在于强转类型截断高位后公式仍然成立。对于其中的原理我是这样理解的：

    当计算出来的数值超过上限的时候，高位截断保留低位实际上是一种取模操作(模2^8)。

    这个操作就像向前拨动表盘指针，向前拨动N个小时，无论转多少圈都无所谓，但是最终停留在了模12后的数字上。

    而还原时就是将指针往回拨N个小时，同样在这过程中转了多少圈都无所谓，但它最终一定会停留在最初的数字上。

下面是我在思考这玩意儿时候补习的一些知识，留下来做个笔记：

  • 高位截断操作：

      258 = 0x102
  0x100被截断丢弃
  0x102 & 0xFF = 0x02 = 2
  C = 2

  • 无符号数与有符号数的关系：

    在限定的数据类型下，数字的二进制最高位为符号位，
    无符号数与有符号数的区别在于是否使用符号位来判断负数。

    有符号数用最高位表示符号（0正或1负），其余位表示数值大小，无符号数则所有位都用于表示数的大小。

    如：char类型，数据为1 byte(8 bit)，其取值范围为

      十六进制：
  0 ~ 0xFF
  二进制：
  0000 0000 ~ 1111 1111
  unsigned char:
  0 ~ 255
  signed char:
  -128 ~ 127

    由于有符号数的最高位作为了符号位，所以有符号数的正数范围变为了之前的一半，同时增加了一半的负数取值范围。

      当127 + 1 时
  0111 1111 变为 1000 0000
  此时作为无符号数则是128
  作为有符号数则是-128

  • 无符号数与有符号数二进制相同：

    由上边的127 + 1的例子可以看出，128和-128其二进制数是相同的，只有分别作为有符号数和无符号数产生了区别。

  • 整数补码的概念：

    引自百度百科

    在计算机系统中，数值一律用补码来表示和存储。其特性为：

    • 一个负整数（或原码）与其补数（或补码）相加，和为模。
    • 对一个正数的补码再求补码，等于该正数自身。
    • 补码的正零与负零表示方法相同。

    正整数补码是其二进制表示。

    负整数补码为将其对应正整数二进制表示所有位取反(包括符号位)后加1。

  • 模的概念：

    模是指一个计量系统的计数范围。如时钟，他的计量范围是011，模=12.表示n位的计算机计量范围是02^(n)-1, 模=2^(n)。

    模实质上是计量器产生“溢出”的量，它的值在计量器上表示不出来，计量器上只能表示出模的余数。任何有模的计量器，均可化减法为加法运算。

    如：假设当前时针指向10点，要调整时间到6点有两种方法：一种是倒拨4小时，即：10 - 4 = 6；另一种是顺拨8小时：10 + 8 = 12 + 6 = 6

    在以12模的系统中，加8和减4效果是一样的，因此凡是减4的运算，都可以用加8来代替。对模而言，8和4互为补数。即两者相加等于模的数均是补数。

    在计算机系统中 一个8位数所能表示的最大数为1111 1111，若再加1为 1 0000 0000，但因为只有8位，最高位1自然丢失，又回了0000 0000，
    所以8位二进制系统的模为2^8。在这样的系统中减法问题也可以化成加法问题，只需把减数用响应的补数表示就可以了。把补数用到计算机对数的处理上，就是补码。

  • 计算机整数减法：

    依据上述补码的的概念，计算机在进行减法操作时，将减数化为加上减数的补数。

    则 2 - 8 在计算时被化为 2 - 8补。

      8的二进制表示是 0000 1000
  对8进行求补：
  二进制各位取反为 1111 0111， 再加1 
  8补 = 1111 1000

    此时再与2进行相加：

      1111 1000 + 0000 0010 = 1111 1010

    1111 1010 表示为十进制有符号数为 -6；表示为十进制无符号数则是 250。两者二进制是相同的。

    此时源数据已被顺利还原。

  • 在限定位数内二进制循环规则:

    8位最大数为1111 1111，若再加1得 1 0000 0000，超出8位的最高位1丢失，数值又回了0000 0000；
    在限定位数内，数值总是在2^(n)的范围内循环。

下面是对于上面算法的Python版本实现，用于验证算法的正确性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
[python]

def encode( input, i ):
  input += ( i * i )
  input = input & 0xFF
  return input

def decode( input, i ):
  input -= ( i * i )
  input = input & 0xFF
  return input


if __name__ == '__main__':
  data = [ i for i in xrange( 255 ) ]
  data = data + data

  import random
  random.shuffle( data )

  error_count = 0
  print "input data:"
  print data
  print 10 * '='

  out = []
  for i in xrange( len(data) ):
    value_origin = data[ i ]
    value_encode = encode( value_origin, i )
    value_decode = decode( value_encode, i )
    is_same = value_origin == value_decode
    print "i: %s, origin: %s, encode: %s, decode: %s, same: %s" % ( i, value_origin, value_encode, value_decode, is_same )
    if not is_same:
      error_count += 1
    out.append( value_encode )


  print 10 * '='
  print "out data:"
  print out

  print 10 * '='
  print "error_count: %s" % error_count