冗余码是一种所用符号数或信号码元数比表示信息所必需的数目多的代码,应用了冗余加密技术,即利用了
纠错码的
编码原理,在加密的文件中加入了大量的冗余信息,从而达到加密的目的。大多数研究人员研究的冗余加密技术是
公钥密码系统。常用的冗余编码有
汉明码、
循环码、
BCH码、
代数几何码等,内容非常丰富,涉及的领域广泛。国内外很多学者利用冗余码的特点和理论构造了各种各样的
公钥密码体制、
数字签名方案、
秘密共享方案、
认证码等,使相关的研究得到了迅速的发展。
主要内容
冗余码是一种利用了
纠错码的编码原理,在加密的文件中加入了大量的冗余信息,得到的一种所用符号数或信号码元数比表示信息所必需的数目多的代码。大多数研究人员研究的冗余
加密技术是
公钥密码系统的。
冗余码加密不论是在
纠错编码研究领域还是在加密领域都是一个新的值得研究的课题,使得
纠错码和
密码学相结合的研究紧密的结合。在对明文进行冗余加密方面的研究,还有许多值的探索的东西,同时也可以促进加密方法实现多元化,不仅仅限于广为应用的几种加密方法。
分类
循环校验码
循环校验码(CRC码),是
数据通信领域中最常用的一种
差错校验码,其特征是信息字段和校验字段的长度可以任意选定。
在数据存储和
数据通讯领域,为了保证数据的正确,就不得不采用检错的手段。在诸多检错手段中,CRC是最著名的一种,其特点是:检错能力极强,开销小,易于用
编码器及检测电路实现。从其检错能力来看,它所不能发现的错误的几率仅为0.0047%以下。从性能上和开销上考虑,均远远优于
奇偶校验及算术和校验等方式。因而,在
数据存储和数据通讯领域,CRC无处不在:著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC-CCITT,WinRAR、NERO、ARJ、LHA等压缩工具软件采用的是CRC32,
磁盘驱动器的读写采用了CRC16,通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。CRC的本质是模-2除法的余数,采用的除数不同,CRC的类型也就不一样。通常,CRC的除数用生成多项式来表示。
根据应用环境与习惯的不同,CRC又可分为以下几种标准:
1)CRC-12码;
2)CRC-16码;
3)CRC-CCITT码;
4)CRC-32码。
CRC-12码通常用来传送6-bit字符串。
CRC-16及CRC-CCITT码则是用来传送8-bit字符串,其中CRC-16为美国采用,而CRC-CCITT为欧洲国家所采用。CRC-32码大都被采用在一种称为Point-to-Point的
同步传输中。
海明码
海明码是由1950年由汉明首先提出的,由于
海明码可以纠一位错的
线性分组码,而且它的编码结构和原理较为简单,因此在数据传输和计算机存储系统中广泛应用。但是同时,海明码的最小码距为3,可以纠正一位错误,但对于两位错不能检测,因此即使发生一位错误的几率比较高,但在有较高要求的应用中,
海明码一般不被使用。
海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位,增加r位冗余位,构成一个n=k+r位的码字,然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式:2>=n+1 或 2 >=k+r+1
海明码的
编码效率为:R=k/(k+r),式中k为信息位位数,r为增加冗余位位数。
海明码的校验矩阵中冗余信息较多,同时在7位的海明码中只存在着4位的信息位,只占其中的4/7,而且7位的海明码只能纠正4位信息位中的一位错误。所以,这里我们试验汉明码对连续多位差错纠正的实现。如果不想再加大码的距离,同时又可以纠正连续多位差错,提高破解密文的复杂性,可根据校验矩阵得出的汉明码重新进行组织排列。以16比特的汉明码为例作说明,首先把11个字节的数据信息
比特的16个字节汉明码后再按高低字节分成两组。我们将把每列的8个数据
编码每字节8个汉明码的第1位分别取出,组成第1个字节。然后,再把这8个字节汉明码的第2位取出,组成第2个字节。依此类推,将这组8个字节汉明码处理完毕,得到新的8个字节
编码,两组一共16字节。我们可以看到这们排序后,每个字节包括原来8个汉明码的其中1位。这样,如果我们对其中的一组编码进行人为的纠错,使某一编码字节连续8位都发生改变,实际是分别使原来8个汉明码的其中1位发生了改变。只要在纠错前把受干扰的
编码恢复为原来正常的排列顺序,就可通过计算
校验码完成差错的定位及纠错。
BCH码
BCH码是1959年由Hocquenghon,1960年由Bose和Ray-Chaud-hui分别独立得到的纠多个随机错误的
循环码。
BCH码是迄今为止发现的一类性能优良的线性纠错码,它的纠错能力强,并且构造方便,编译码简单,有快速的译码方法。特别是它具有严格的
代数结构,因此它在编码理论与实际中起着重要的作用,也是迄今为止研究的最为详尽,分析的最为透彻,取得的成果最为丰富的码类,并且可以用它构造某些密码体制和认证码。
BCH码是循环码种的一种,是纠正多个随机错误的
线性分组码,是建立在
有限域基础之上的,有着严格的代数结构。不仅在理论上有重要意义,而且再实践中,也是被广泛应用的。
容错计算中的应用
计算机采用
二进制数。在计算机内部,表现为元器件的高低
电位信号,分别用1和0表示。数据沿着数据通路,从源部件传送到目的部件时,若源部件发送了某一信息(例如低电平0),而目的部件接收的信息与之不同(高电平1),则出现了错误。在此情况下,计算机继续工作只会得出错误的结果。导致信息出错的原因很多,主要有
元器件的质量问题、电路故障和噪声干扰等引起的错误。人们尽可能严格测试、筛选装机的
元器件,提高系统装配工艺与质量,改善系统的抗干扰能力;但所有这一切都不可能完全避免故障,都难以使系统的
平均故障间隔时间达到满意的水平。因此,
信息编码的
容错技术是至关重要的。
信息编码的
容错计算技术的基本思想是
信息冗余(Message Redundancy),即在
信息编码上附加一段冗余编码,使信息具有发现本身错误的能力,甚至能指出错误的所在位置,然后借助逻辑线路自动纠正。利用冗余码实现对数据信息的校验,目的就是提高计算机的可靠性,尽可能提高系统的
平均故障间隔时间。
展望
现有的冗余码加密只适用于密文中冗余信息所占比例较少的情况,不适合对文字较多的报价单进行加密,这一点还需要进一步改进。
正常破解时,每块密文信息块都要找到其中的冗余信息,都需要进行纠错,接受方必须知道每块信息块中冗余信息的位置,而且这些位置可能是不同的,计算量加大,因此耗费的破解时间较多。因此,可以设计一个计算每块信息中冗与位信息的程序,改进该算法,也是未来发展的方向。