（计算机应用技术专业论文）基于二次背包加密的数字水印技术.pdf

南京理工夫学硕士学能论文蕊予二次背包加密鞠数字水印技术 摘要 数字承印技术耩予目前国际上新兴的研究领域。它按照定方法夜被保护的数字 载髂申褒久一鎏秘密信患，亲运爨保护鼗字母骛菸舨投戳及谶稼- | 蒌藜盗激蠖投行为翡藩 的。 本文通过研究公钥密码学中的二次背包体制，给出了种基于二次背包加密的数 字承印算法。二次游镪热密算法具专安全矬麓、窑曩绽程蜜瑰、热薅密遮度诀等爨点， 傻弼二次瑟包算法燎密水露信慰将绘整个水邵系统带来穰好的安全挂。承印图德在僚 输或遭受攻击时出现的误码问题，将会对水印祭统的稳能性产生一定的影响，所以又 引入b c h 纠错编码技术，对承印密文序列塞施纠错编码，使之具备容错能力。本文 懿最后，透过餐鼹瓿疆曲数学缡程互其，摸羧垂乏算法著缭密鬻燕酌玻毒溺试缝暴。 实验证明，本文算法啦予饿耀了二次鹜融加密技术，聚统安全性褥到了保证。使 用b e h 码对水印密文序列进行纠错编码尉，该算法可以经受常见的攻击。可见，本 算法爨备了一是静安全性与稳穗往。 必键谣：数字水印，二次鬻毯细密，离散余弦变抉，b c h 码。 南京邈工大学硕士学位论文基予：次背包加密盼数字水裔 技术 a b s t r a c t c u r r e n t l y ，d i g i t a lw a t e r m a r k i n gi sa n a d v a n c e d t e c h n o l o g y i nt h e i n t e r n a t i o n a lc r y p t o g r a mr e s e a r c ha r e a 。i tp r o t e c t st h ec o p y r i g h t so fd i g i t a l p r o d u c t i o n sb ye m b e d d i n g s o m eu n d i s c o v e r e di n f o m a t i o ni n t ot h ed i g i t a l c a r r i e r t tp r o v i d e sag o o ds o l u t i o nt oc o p y r i g h tp r o t e c t i o na n dp i r a t ec o p y t r a c i n g ， i nt h isp a p e r ，w ep r o p o s ean e wd i g i t a lw a t e r m a r k i n ga l g o r i t h mb a s e do n q u a d r a t i ck n a p s a c kp r o b l e m ，w h i c hb e l o n g st op u b l i c k e yc r y p t o s y s t e m t h e q u a d r a t i ck n a p s a c kp r o b e mu s e sam a t r i xa sp u b l i ck e yt oe n c r y p tw a t e r m a r k i n f o r m a t i o n i ti sh a r dt oa c q u i r ep r i v a t e - k e yb yc a l c u l a t i n gf r o mp u b l i c k e y ， a n dt h es p e e do fe n c r y p t i o ni sf a s t 。w eu s eq u a d r a t i ck n a p s a c kp r o b l e mt o e n c r y p tt h ew a t e r m a r ki n f o r m a t i o na n dd c r ( b i s c r e t e c o s i n et r a n s f o r m ) t o c o m p l e t et h ep r o c e s so fw a t e r m a r ke m b e d d i n g t na d d i t i o n ，f o rt h es a k eo f s y s t e mr o b u s t n e s s ，t h ee r r o r c o r r e c t i n g c o d ei sa d d e dt oi m p r o v et h e e r r o - - t o l e r a t e da b i l i t yo fe n c r y p t e di n f o r m a t i o n t h er e s u l t so ft h ee x p e r i m e n t sp r o v et h a tt h ea l g o r i t h mi sr o b u s tt os o m e c o m m o n l yu s e di h a g ep r o c e s s i n gm e t h o d s k e y w o r d s ：d i g it a lw a t e r m a r k i n g ，q u a d r a t i ck n a p s a c kp r o b l e m ，d c t ，b c hc o d e i i 声臻 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在率 攀位论文中，除了加以标注和致谢的部分外，不包含其他入已经发袭戴 公布逶熬疆究成粟，也不包禽鼗搀获得程俺教育飘籀静学位或学瓣褥谴 用过的材糕。与我一嬲z 作的囝攀慰本学位论文做出的爨献均巍论文 审作了翳魂鳃遂臻。 磷巍生签名：盘：查， 辨每胃、零匿 学位论文使用授权声明 毒裘瑗工大学有数保存零学象论文麴电子帮纸震文档，焉以落瓣或 上网公布本学位论文的部分或全部内容，可以向肖关部门或规构送交井 授权其绦存、借阋或上两公带本学位论文豹部分或全部内容。对于保密 论文，接攥密馥有关娥定_ 程程序处磷。 磷巍皇签名；壹啦 如b 年知嚣 8 嚣 南京理工大学硕士学位论文摹于二次背包加密的数字水印技术 1 绪论 1 1 公钥密码学理论及发展 密码学的历史源远流长，从古至今，对于信息保密的要求就得到了广泛的关注。 古代对于信息的保密有着两种方法，一种是以机密信息的隐藏为目的，我们称之为隐 写术；另一种是将机密信息加以变化，使之无法被截获者所理解，即密码术”1 。 古老的密码术，与其说是科学，不如说是一门艺术。可它在实际中的作用是非常 巨大的。战争中，信息保密的重要性关乎一场战争最后的结局。政治外交中，信息的 保密也攸关国家的利益。一直以来，密码学都是人们的研究热点，可以说密码学是一 门既古老又年轻的科学。 在科技飞速发展的今天，各种各样的信息存在着被保护的需要，如：个人资料、 银行记录等涉及隐私的信息。同时随着互联网的发展，对于数字产品版权的保护也显 得日益重要。密码学从传统的军事与外交领域开始走向公开，在不同的领域中，结合 了计算机科学、微电子学、信息与通信学等学科，逐步发展成一门在各行各业中有着 重大作用的交叉学科。密码学的商用价值和社会价值也得到了充分的肯定。 密码学的发展历史大致可划分为三个阶段”： 第一阶段为密码学诞生到1 9 4 9 年。这段时期的密码技术可以说是一种艺术，而不 是- - 1 7 科学，密码学专家常常是凭借着直觉、经验和信念来进行密码设计和分析，而 不是推理证明，没有形成系统的理论架构。这一段漫长的时期，往往可以视为科学密 码学的萌芽时期。 第二阶段从1 9 4 9 年到1 9 7 5 年。1 9 4 9 年s h a n n o n 发表了“保密系统的信息理论” 一文，此文为私钥密码系统建立了理论基础，从此密码学成为一门科学，但密码学直 到今天仍具有艺术性，是具有艺术性的一门科学。1 9 6 7 年k a h n 出版了一本专著破 译者，该书没有新的技术思想，只记述了一段值得注意的完整经历，包括政府仍然 认为是秘密的一些事情。它的意义在于它不仅记述了1 9 6 7 年之前密码学发展的历史， 而且使许多不知道密码学的人了解了密码学。7 0 年代初期，m m 发表了f e i s t e l 和他 的同事们在这个学科方面的几篇技术报告。可以说这段时期密码学理论的研究工作进 展不大，公开的密码学文献很少。这段时期是传统的科学密码学的发展时期。 第三阶段为1 9 7 5 年至今。1 9 7 6 年d i t i i e 和h e l l m a n 在“密码学的新方向”一文中 提出了公钥密码体制的新概念，导致了密码学上的一场革命。之前传统的密码学是通 过通信双方相互秘密约定一个私钥来实现对称的加解密的，这种通信方式很快在现实 中露出了弊端，随着计算机软硬件的发展和基于网络的并行计算能力的破解技术的日 益成熟，单靠增加密钥长度的方法来增强系统的安全性已非上上策了d 瓶e 和 1 南京理工大学硕士学位论文 基于二次背包加密的数字水印技术 h e l l m a n 首次证明了在发送端和接受端无密钥传输的保密通信是可能的，从而开创了 公钥密码学的新纪元。 在过去4 0 0 0 多年的时间里，几乎所有密码编码系统都是建立在替代和置换等机 制的基础上。公钥密码学则与以前的所有方法都截然不同：一方面它基于数学函数， 另一方面它用到两个不同的密钥而不是常规对称加密的一个密钥。在公钥密码学里， 仅知道加密算法和加密密钥是无法通过计算得到解密密钥的。公钥密码学的算法模型 如下图1 1 i ： 图i 1 1 公钥密码系统模型 到了1 9 7 8 年，麻省理工大学的r i v e s t ，s h a m i r ，a d l e m a n 三人基于大整数分解的 困难性提出了世界上第一个公钥密码体制- r s a 体制，从此r s a 方案作为唯一被 广泛接受并实现的通用公开密钥加密方式而广受推岽。 在这之后，公钥密码学研究领域呈现百花齐放的姿态，大量的公钥密码算法层出 不穷。如：较为经典的m e r k e h e l l m a n 背包算法、m c e l i e e e 算法、e 1 g a m a l 算法、椭 圆曲线密码算法等。同时还衍生出了许多新概念和新的应用，例如：公钥密码体制用 于数字签名，概率加密体制，门限方案等。同时，一些已提出的公钥密码体制也遭到 破译，在被破译之后又做出了相应的改进，这样就形成了较为系统的公钥密码体系”。 公钥密码学中的背包加密体制一直以其加解密迅速、安全性高而引人瞩目。最早 的背包体制是m h 背包加密算法，属于一次背包体制，由m e r k l e 和h e l l m a n 于1 9 7 8 年提出。我国的何敬民与卢开澄也于1 9 8 8 年提出了一种基于孙子定理的背包体制。 同年，c h o r 和r i v e s t 利用有限域上算术性质也设计了一个新的背包体制。但不幸的 是，大部分一次背包体制均被破译了，如s h a m i r 就于1 9 8 2 年成功破译著名的m h 背 包体制。 尽管如此，背包加密体制依然吸引着研究人员的兴趣。在一次背包体制的基础上， 提出的二次背包体制，引入了变量之间的关系信息，具有更强的安全性。来学嘉曾于 1 9 8 6 年设计了一种基于矩阵覆盖的背包体制。曹珍富等人改进了来学嘉的背包体制， 2 南京理工大学硕士学位论文基于二次背包加密的数字水印技术 设计了m c 概率背包体制，并在1 9 8 9 年又提出了一种新的m c 线性分拆背包体制。 之后，又有学者提出了一些新的二次背包算法。算法的每次的改进创新，都使得现有 背包体制变得更加的稳定和成熟【1 羽。 1 2 数字水印技术简介 上文我们介绍了密码学的发展历程，提到了古代隐藏信息的两种方法，一种是隐 写术，另一为密码术。随着历史的推移，两者也在不断的变化、更新与发展。它们的 发展可以看作两条线。古代的密码术发展至今，成为了现代密码学；古代的隐写术， 发展到今天，也诞生出诸如伪装式信息安全、信息隐藏学、数字水印等新技术” 从1 9 9 3 年开始，公开发表的有关信息隐藏和数字水印的文章日渐增多。v a n s c h y n d e l 于i c i p 9 4 会议上发表了题为“ad i g i t a lw a t e r m a r k i n g 的文章。这篇文章被 认为是一篇具有历史价值的文章，因为这是第一篇在主要会议上发表的有关数字水印 的文章，并提出了一些数字水印相关的重要概念。1 9 9 6 年第一届信息隐藏学术研讨 会在英国剑桥举行，标志着信息隐藏作为一个新的学科而诞生。此外，一些信息安全、 密码学和信息处理领域的国际会议也都有信息隐藏技术的专题和文章。i e e e 会报、 s p i e 等著名杂志也都出版了有关信息隐藏技术的专题。国内在信息隐藏方面的研究 起步稍晚，但已引起了信息安全领域研究人员的普遍关注，自1 9 9 9 年开始每年都召 开一届研讨会，并于2 0 0 0 年召开了第一届数字水印技术研讨会。各类科技期刊学报 上面有关信息隐藏和数字水印的文章也从2 0 0 0 年开始迅速增多”。 信息隐藏和数字水印技术的实际应用，随着互联网的发展而不断更新。在数字作 品版权保护的手段上，以前人们使用磁带之类的载体来记录信息，版权保护的手段无 非就是对原始拷贝进行妥善保管等一些人性化工作。盗版拷贝之后，因为其物理特性， 质量肯定是来不及原始拷贝的。到了数字时代，数字拷贝的质量完全不失原版质量， 同时网络技术的发展，大容量磁盘，c d r o m 的普及，这些都为数字拷贝盗版提供了 非常完善的制作、传播环境。这样对数字信息传播的安全性以及数字产品的版权保护 就显得十分重要。各国政府、企业组织、学术界对此情况相当关注，因此数字产品的 版权保护及数字信息的网络传播安全问题业已成为当今的研究热点。 数字作品很容易被不失真的复制与传播，且易于修改等特点，对数字作品的版权 保护也提出了一些技术上的难题，包括”： ( 1 ) 如何鉴别当前数字作品的作者。 ( 如何确定数字作品作者的版权声明。 ( 3 ) 如何公证一个数字作品的签名和版权声明。 ( 4 ) 在采用登记制的情况下，怎样确认登记的有效性。 数字水印利用了信息隐藏原理，利用数字作品存在的信息冗余度，将版权信息隐 3 南京理工大学硕士学位论文基于二次背包加密的数字水印技术 藏到数字作品之中，可以给出作品的作者、所有者、发行者以及授权使用者等相关版 权信息，以达到版权保护、盗版跟踪、拷贝防护等目的，为数字产品的版权保护及数 字信息的网络传播安全问题提供了很好的解决方案。总体来说，数字水印主要有以下 特征嘲： ( 1 ) 数字产品中嵌入的信息不易被轻易去除。 ( 2 ) 它需要在数字产品中一次性的嵌入大量的数据，过程比数字签名要来的简便。 ( 3 ) 它可以为解密后的数据提供进一步的保护，比相应的传统加密要来的安全。 在网络信息化普及和电子商务迅猛发展的今天，数字水印技术的研究有着重要的 意义。数字水印技术对于保护各种各样的数字多媒体作品起着重要的作用。我们结合 数字水印原理的一些特性，可以配合密码学、认证技术、数字签名等技术来一起使用， 这样一个数字水印系统在实际应用中才能经得起考验，抵抗各种攻击，构成完整的数 字作品版权保护的解决方案。 1 3 本文的研究内容介绍 对于一个给定的水印信息，按内容的性质可分为有意义水印和无意义水印，无论 其类型是有意义的( 文本、图像或其他) 还是无意义的( 随机序列) ，在进行水印的 嵌入时，绝大多数算法首先是对它进行二值化转换，转化成0 和1 或一1 和l 的序列， 当然，转化的形式是多种多样的。其中最简单的就是把水印信息在计算机中的存储形 式不加变化的使用，这种方式虽然方便，但是对水印信息的保密性很差。因为只要攻 击者在水印载体中提取出了水印信息，那么接下来对其进行的篡改伪装攻击就变得很 简单”“。基于此，对水印信息的预处理就显得非常重要，采用一个好的预处理方法， 对水印系统的安全性将是一个很大的提升。 本文选取公钥密码学中经典的n p c 问题背包体制进行研究，考虑到其中的 二次背包加密算法具有安全性高、易于编程实现且加解密速度快等特点，故可以使用 它来对水印信息进行加密处理，使之转换为看似杂乱无章的二值序列。且只有版权所 有者拥有私钥，攻击者即使获得了水印数据，也困于背包体制密码系统的复杂性而难 以破解，使得水印系统具有很好的安全性。并在水印信息处理的过程中，引入纠错编 码技术，对含有水印信息的数字产品在经过传输或遭到攻击之后产生的误码问题给予 纠正，保证了系统的稳健性。 本文的研究内容在于使数字水印技术和二次背包加密相结合，并辅之以数字纠错 编码技术，设计了一个基于二次背包加密的数字水印方案。并通过m a t l a b 模拟实验， 测试此水印系统具有一定的安全性和稳健性。 4 南京理工大学硕士学位论文基于二次背包加密的数字水印技来 1 4 本文的结构安排 本论文共分六章： 第一章：绪论，介绍了本论文的课题背景、公钥密码学理论及数字水印技术的发 展现状、本论文的研究工作概述及论文的组织结构。 第二章：二次背包加密相关知识的详细介绍，本文从概念和定义讲起，介绍一次 背包加密以及二次背包加密算法的大致分类，主要介绍三种常见的二次背包体制。 第三章：对计算机纠错编码技术进行理论介绍，从浅入深，重点介绍本文所需使 用的b c h 纠错编码技术。 第四章：数字水印技术的介绍，包括其产生的需求背景，及相关的概念和定义， 大致分类，详细介绍本文所采用的离散余弦变换域嵌入方法。 第五章：基于二次背包加密的数字水印研究，这是本文的重点所在，是上述二次 背包加密算法和数字水印技术的结合，详细叙述水印方案的建立步骤和技术细节。 第六章：给出本算法的测试数据，证明本算法的安全性与稳健性。 南京理工大学硕士学位论文基于二次背包加密的数字水印技术 2 二次背包算法相关知识 2 1 算法与问题的分类 在计算机科学理论中，算法有着如此的分类：一般来说，一个算法是具有时间复 杂性和空间复杂性的，其分别对应了此算法对时间与空间的需求量。我们可以根据算 法的时间( 或者空间) 复杂性将算法分为两类，即多项式时间算法( 又名有效算法) 和指数时间算法。其大意为： 多项式时间算法：是指算法的所需的执行时间是o ( n7 ) ，其中t 是常数。可用多 项式来对时间进行界定的算法。 指数时间算法：是指计算时间用指数函数来界定的算法。 同时算法又可以分为确定性算法和非确定性算法，不过确定性算法可以视为非确 定性算法的特例，因为根据定义，确定性算法有着一组明确的操作顺序，而非确定性 算法每执行一步可选择性的执行下一步，所以它又被称为概率算法。可以把非确定算 法的执行所选择的顺序视为多种确定性的算法步骤。 对于一个要求给出解答的一般提问称为一个问题，问题根据其使用的确定性算 法、非确定性算法以及时间复杂度之类的又可分为p 问题、p 问题、p c 问题等。 其中： 户问题：是指使用确定性算法，在多项式时间内可以解决的问题。 n p 问题：是指使用非确定性算法，在多项式时间内也可以解决的问题。 n p c 问题：是指p 困难问题，即如果对于一个给定问题4 ，对于p 中的每个 问题q ，均有g 多项式时间内规约到q 。n p c 问题又称 】= p 完全问题”。 本文所要应用的二次背包加密算法属于背包问题，它就是一个n p c 问题。 2 2 一次背包加密算法介绍 最初的背包算法是一次背包体制，是由m e r k l e 和h e l l m a n 于1 9 7 8 年提出来的， 其加解密速度迅速，在当时亦引起了研究人员很大的关注。其问题可形象地描述为： 一个旅行者携带背包去登山，已知他所能随身携带的背包重限度为b ，现有1 种物品 可供选择装入背包。第f 种物品重量为口，其重要性价值指标为c 。，旅行者应如何选 择携带各种物品，以使总价值最大”。抽象为数学描述就是：设口= ( q9o * $ ) 是长为 n 的背包向量，其中q ( i = l ，n ) 均是正整数，则已知a 与正整数f ，求 ( 毛，毛) o ，1 ) 4 使得： q 毛+ + 毛= c 6 南京理工大学硕士学位论文基于二次背包加密的数字水印技术 满足上式条件的问题就是背包问题( k n a p s a c k 问题) 阁。 为了使问题求解简单化，我们做超递增向量口= ( q ，) ，所谓超递增向量就是 对于v q 口，巳 窆q ( ，：2 ，3 ，胛) 。若口是超递增向量，则相应的背包问题称为 简单背包问题，时间复杂性为d ( 栉) ，根据如下解法，可迅速得解。 解法虾= 躲： 证明：若c a n ，且矗= o ， n - i 二口，a 。 c ，与q 毛+ + q 矗= c 矛盾。 i t lj t l 类似地，对于，= n - i ，n - 2 ，21 ，我们有= l ，c 一q 2 乃 + i o ，c 一哆t q l - j 十i 一般来说，背包体制加密的算法思想就是，通过生成超递增向量彳，利用某些方 法把它变化为另一个不再超递增的向量b ，口做为公钥用来加密明文，a 做为密钥用 来解密。而向量口到向量4 的算法不可逆。 例如，一次背包加密体制中著名的m h 背包体制的算法思想是：生成超递增向量 a = ( a a ，吼) ，w _ 1 和m ，满足0 w 1 口，1 嘞，w 瓦，聊 a i r + p 嘞，w ) = l a l = l j 耐 l 。j 生成公钥： = w a l t 0 0 ： o0 0 o ： 4 ” q i a 1 2 a 2 1 口2 2 口ma h 2 口l n 口2 ： 口_ l2 r 2 1 饧 ： l2 1 1 ，1 2 r 2 1 ： l2 公钥：。 密钥：m 取口瓴l ，瓦) 。 明文：( 而，矗) o ，1 ) ” 加密过程：c = 6 j f + b o f ( i ，_ ，) 。 解密过程：求w 模m 的逆w 一，做运算( w - 1 c ) 。= c l ；再计算( c ，) ，= ；最后就化为了 解一个简单背包问题蟊。毛。+ 轧工。= 气。 9 ；k 暑 ；k 鼍 南京理工大学硕士学位论文基于二次背包加密的数字水印技术 c = 6 i ，+ 屯f ( ，力 = w 窆t = l 瓦一+ d 喜吼+ 吾乃，( f ，纠+ 文喜气+ 蔷f ( f ，) j - i# j，l i l， 所以可以得出： 铲( w 1 妒喜确+ pn 卜+ 酗砘叫 c 0 = ( c 1 ) 。= 瓦t 至此，便可解出明文“，矗) o ，1 ) ” 2 4 2m c 线性分拆背包体制 m c 线性分拆背包体制，兵主要思想是将原先由一维超递增向量所构成的主对角 阵或对角线具有超递增性的矩阵分拆成几个矩阵的线形组合，然后再把这些矩阵做一 些变换处理，从而转变为另一个矩阵。于是将前面对角线有超递增性的矩阵和其他一 些变换参数、线形组合系数做为私钥供解密之用。而后生成的那个矩阵作为公钥用做 加密f 1 7 1 如：曹珍富就提出过这样一种m c 线性分拆背包体制鲫，将超递增向量( 口1 ，4 。) a l 0 作一个对角阵彳= i 1 ，然后将4 分拆为m 个任意矩阵4 ( f = 1 ，所) ，再生 【0a n j 成m 个任意矩阵c o = 1 ，肌) ，取p 口，做线性运算得：e = 4 + p c j 。 公钥：最； 密钥：a ib ，o = 1 ，m ) ； 明文：工= ( 五，x n ) ； 加密过程：弘= x b , x 7 ( 1 = l ，m ) ； 解密过程：计算萎以只2 x l 善6 l “+ p e ) j ，= 础7 + p 善6 j e ， 因为p q q 五，且善? = o = l ，n ) ， 所以p x a x 7 ， 解简单背包问题口。x l + + x n = ( 6 。y 。) 可得明文。 i o 南京理工大学硕士学位论文基于二次背包加密的数字水印技术 2 4 3 一般二次背包体制 关于一般二次背包体制，其原理是利用两个一次背包向量的乘积来代替原来的一 次背包向量。对生成的矩阵要进行一些处理使之变换成一个新的矩阵，这样做增加了 破译的难度【m 。其中比较有代表性的如：m c 分段解密体制和m c 二次性代数体制。 m c 分段解密体制主要原理为：由于一般的m c 问题可以视为两个背包向量的乘 积，即对于明文x = 0 。x 2 ) 0 ，1 p ，n 茎埘，则有： 一尘陉幽丝二篙a l b t 罢a , b 2 主a l b 引, l r 1 当m 栉时，可利用上述代数式设计出m c 分段解密体制，即先解出五，x 。，再解 出。，x n 。具体的算法如下： 生成超递增向量“，) 手口p 。，玩) ，然后将( 6 卅+ ，吒) 随机扩充至 b = ( 6 l ，b 。，b m + ，瓦) 。分解b 为非负整数向量6 1 和6 2 ，b = b l + b ：，做代数式： f ( x ) = q t + a ( 。) ( c x ) + p ，p ：( 吣，) ( c 2 t x 。) ， t = ll - li # l f 。lj l 其中，( c ，c 。) 与( c ：，c ：，) 为正整数向量，且有 p 。 a j ，p ： ( b l ，) ( ) 。 j ；lt = ll l l 对代数式，( z ) 进行整理得二次性，即为： 4 = 彳+ p l6 1 1 q 1 + a ，2 6 2 l c 2 1 a 2 , 7 1 + p l b l 2 e 1 1 + p i 见6 2 2 吒i a k c l l + p i p 2 屯。c 2 l 胂”，啦 a l a 2 + 见6 1 i c l 2 + p l p 2 6 2 l c 2 2 + p l b t 2 c 1 2 + p l p 2 k c 2 2 p l b l 。c 1 2 + a 岛b 锄 a6 l l c l 用+ p i p 2 6 2 1 c 抽 p l b l 2 q m + p l j k 6 2 2 c h i a k + a 见b a 是一个m 胛阶的矩阵，同时，我们是把彳作为公钥公开，用以加密明文。当 然也可以对a 进行一些处理，然后公开。 整个加密体制可描述为： 公钥：a 密钥：瓴，a 。) ，0 。，6 l 。) ，( 6 ：。，b ：。) ，0 ，l c 。) ，( c ：，乞。) ，p t i 劬： 明文：工= 0 1 x 2 ) 0 ，1 ”，r x l + 靠0 。 南京理工大学硕士学位论文基于二次背包加密的数字水印技术 加密过程：d = “，弘e 2 。 一算曙k 一卜吐 幺：芝 可以解出而，x 。 酣算旧l p 2j = 鲺，( d 。) = 以 有 d 4 = ( 6 1 ，t ) ( c 。t ) “”1 ，把上面求得的而代入可得： m ” d 3 = ( 6 2 f ) ( c ：，一) t - i；l h d 5 = + 以= 也 ，1 。解简单背包问题，再得。，x 。 7 解密过程结束，得到明文x = g 。x 2 ) o ，1 ) ”。 2 5 本章小结 本章主要介绍了背包体制的相关概念、分类和典型的算法，着重介绍的二次背包 加密算法属于n p c 问题，其加密的安全性有着充分的数学理论保证。本章介绍二次 背包加密的目的在于，为其应用于数字水印领域提供相应的理论基础。 1 2 砖 t 。一。一 = = 西 ，、1【 南京理工大学硕士学位论文基于二次背包加密的数字水印技术 3 纠错码知识介绍 3 1 编码纠错技术概述 在现实生活中，人与人之间对话，当察觉到对方语言中存在错误的时候，我们还 是能够了解其所要表达的大致意思。比如一个中国人和美国人交流时，中国人基本上 可以听懂对方不流利的汉语。那是因为人类语言中的每一句、每一字之间存在着相关 性和冗余度，我们就是利用这些语言的相关性和冗余度来发现并纠正交流中的错误 的。 在计算机原理以及数字通信系统中，用二进制数来表示我们所使用的信息，数字 信号存在两种模式，即1 和0 。任何的数字形式( 数字图像、音频、视频等) 都可以 化作二进制，这就为我们传输这些数字信息带来了方便。同时和传统的模拟信号相比， 二进制数字信号具有抗噪声、抗干扰强等特性，也为系统带来了可靠性。 但是，当噪声和干扰强度增加的时候，将对数字信号产生一定的影响，存在着错 误地把0 当成1 ，1 当成0 的情况。由于这些二进制数字信息仅包含了信息位，码与 码之间不存在相关性和冗余度，没有任何规律可循，当错误产生的时候，纠错工作无 法展开。比如：二进制六位数据0 1 0 1 0 0 经过传输或者遭受攻击而变成了0 1 0 1 1 0 ，有 位产生了错误，则整个数据就变成了别的信息，不再代表原来的意思。所以这个6 位二进制码本身是没有抗干扰能力的。因此，只用6 位的二进制序列来表示6 4 个不 同的符号，想在接收端发现或者纠正传输中的错误是不可能的。为解决这一问题，可 以运用编码纠错技术，对所要发送的数据用7 位或8 位，甚至更长的二进制序列来表 示。不同于原来的6 位表示法，这些多余出来的码元本身不含有信息，但是和数据位 之间存在一定的关系。接收端利用这种关系，使用数据译码器来发现和纠正可能存在 的错误。通过编码纠错技术，可以纠正大部分的错误，并尽可能的保证数据的正确性 与可读性。 编码纠错技术以编码理论为基础，是随着信息化社会的发展及半导体技术的普及 而大力发展起来的一种编码技术，其主要目的是为了提高数字系统的可靠性。即便在 有的情况下，完成不了纠错工作，也可以凭着代码相关性，参考前后关系等因素估计 信息，进行一定的错误修正( 补正) t 作。 3 2 纠错码的工作原理 3 2 1 纠错码的编码原理 编码纠错技术的主要技术思想嗍是：在数据传输、信息记录系统中，对要传输和 1 3 南京理工大学硕士学位论文基于二次背包加密的数字水印技术 记录长度为k 位的信息，添加m 位的错误校验位或纠错位，然后构成( t + 州= 阼) 位 的代码字再进行传输和记录工作。 这里存在着一些基本概念，如上所述的_ j 位的信息称之为报文，编码器把信源的 信息位划分成每个k 比特的信息后再处理。( 针m = 甩) 位的代码字，刀称为码长。信 息比特数和码长的比率称之为代码率r = k n 。如果信道输入了发送字 w = ( ，x 2 ，x n ) ，就输出一比特的接收字y = ，y 2 ，y n ) 。 如简单的单一奇偶校验码，信息位为3 位，从( 000 ) 到( 1l1 ) 表示了8 种报文。采 用单一奇偶校验码，在信息位的最后在加上一位冗余位，如果报文中1 的个数是偶数， 则在第四位上附加o ；如果报文中1 的个数是奇数，则在第四位上附加l 。此时的纠 错码码长为4 ，信息位数为3 ，故称之为( 4 ，3 ) 码。可以计算，此( 4 ，3 ) 单一奇偶校验 码的编码率r 为0 7 5 。具体编码如表3 2 1 所示： 表3 2 1 ( 4 3 ) 单一奇偶校验码 i 报文i 。 代码字w 一。，报寒t ，。 代码字妒薹 0o00 0 00lo ol0 0 1 00 1 0 0 ll1o l 10lo 0 l0o l0 1ll0l1o0 0 1i0 1l0 11l 1lll 当错误发生时，如发送的代码字w 1 = ( 000 ) 或w 2 ；( 11 1 ) ，而接收字y = ( o10 ) 一 如果发送字是w 1 = ( o0 0 ) ，则表明第2 位被错误的接收，第1 和第3 位是正确的，设 出错率是p ，发生这种情况的概率是：p ( y 1w 1 产( i - p ) 2 p 。 如果发送字是w 2 - - ( i11 ) ，则表明第2 位被正确的接收，第l 和第3 位是错误接 收的，设出错率是p ，发生这种情况的概率是：p ( yw 2 声( 1 一p ) p 2 。 假设此信道出错率较高，p = 1 0 。2 达之多，则出错概率p ( y lw 1 ) 要比p ( y l 心) 来 的高。 在上例中，w 1 和y 存在着1 处不同，和，存在着2 处不同，为此我们引入一 个概念叫做汉明距离，表示在两个比特串”，1 ，对应位置比特不同的位置数，用d ( u ，v ) 表示。则以上两者的汉明距离为d ( m ，y 户l ；d ( d d 2 ，产2 。可以得知距离越小，概 率就越大。 3 2 2 纠错码的纠错原理 介绍了上述的基本知识之后，我们再来看纠错码是怎样实现纠错功能的闭。设w l 为( 0o000 ) ，以m 为圆心，纠错位数r 为半径做一个圆。假设t = 1 ，则此圆内包含 了5 个元素，分别为口，b ，c ，d , y 。 1 4 南京理工大学硕十学位论文摹于二次背包加密的数字水印技术 ooooo oo ool oo olo ooloo olooo lo ooo 图3 2 1 纠错码的纠错半径 如图3 2 1 ，发送字w 1 为( 00000 ) ，在传输中受到一定的攻击之后，发生了失真， 有一位出现变化，至接收字y = ( 10 0 0 0oy 和w 】的汉明距离d ( m ，护1 ，在w 1 的 纠错半径之内( 处于圆中) 。且只有这个圆包含了j ，周围别的圆不包含y ，则按最接 近y 的代码字w l 翻译，于是y 转化为( 00 00 0 ) ，完成了纠错功能。 进一步讲，纠错系统中，存在着许多个这样的纠错圆，每个圆都各尽其职，但有 时候会产生冲突。比如上述的y 若是处于两个圆的共同范围内，分别是以( 0 0000 ) 为圆心，半径为1 的圆和以( 10 0 01 ) 为圆心，半径为l 的圆。那究竟y 该被纠正 为w 1 还是鸺呢? 这就有了冲突，为避免这种情况的发生，我们定义一个最小距离 d ，如图3 2 2 所示： 图3 2 2 最小距离的定义图 按上图所说当以各代码字为中心，半径为t 的小球，最小距离j 。2 f + 1 ，就可 保证不会有共同部分出现。 由于y 和w 1 的距离是小于t 的，故按照译码规则，最接近y 的代码字是w 1 ，就把 y 翻译成最接近于接收方的代码字w 1 ，完成了纠错。上例我们假定t 等于1 ，其实t 可以是一个大于0 的常数，可以用这种代码纠正任意的，重错误，所以称为t 重纠错 码。当t 为1 时，称之为单一纠错码s e c ( s i n g l ee r r o rc o r r e c t i o n ) ：当t 为2 时，称之 为双重纠错码d e c ( d o u b l ee r r o rc o r r e c t i o n ) 。 3 3 纠错码的分类 纠错码的种类繁多，按照对信源输出的数字信息序列处理方式的不同，分为分组 码与卷积码两大类。卷积码中信息数列与代码数列的对应是逐次的，没有相当于块代 码代码字的定界符。本文限于篇幅，将只做分组码的介绍。 塑塞里三查兰堡主兰壁丝苎墨王三坚翌垒塑窒竺墼兰查竺垫查 纠错编码大致可以分为以下几种，如下图3 3 1 ： 圈3 3 1 纠错编码的分类图 分组码是把信息序列以每七个码元分组，通过编码器把每组的七个信息元按一定 规律产生埘个多余码元( 称为监督码) ，输出为行= k + m 长的一个码字。因此，每一 码组的m 个监督元仅与本组的信息元有关，而与别组无关1 。 循环码属于分组码，其中的b c h 码和r s 码( r e e d - s o l o m o n 码) 比较有代表性，均 在应用方面有着重要作用。按照本文所需，这里将根据纠错编码的分类图，按线性码、 循环码、循环汉明码、双重纠错b c h 码、b c h 码的顺序来进行循序渐进的介绍，重 点放在本文所需的b c h 码上。因为在第5 章构建一个基于二次背包加密的水印系统 时，为保证加密算法的稳健性，需设计出一个与之相应的b c h 纠错编码方案。 3 3 1 纠错码的基本概念 对于下文所涉及的一些有关纠错码的基本概念“，本节将做一个系统的介绍。 g f ( 2 m ) 称为g f ( 2 ) 扩大域，g f 在代数中称为伽罗瓦域( g a l o i sf i e l d ) ，即有限域。 在伽罗瓦域g f ( 2 ) 中有两个元0 和1 ，可以在他们之间进行加、减、乘、除四则运算， 它们满足r o o d 2 计算规则。对此，g f ( 2 m ) q 6 有2 ”个元，即0 , 1 ，口，口2 ，口。令q = 2 ” 为伽罗瓦域的位数，把o t 初次等于l 的那种元，称为原始元。 对于有限域g f ( 2 m ) 上的多项式p ，若能被多项式，一1 整除，且栉2 ”一1 ，则 称p 为原始多项式。3 4 次以下的原始多项式已被整理成一张表，如表3 1 3 1 所示， 以供第5 章设计b c h 码时查表使用。图表说明：如l o 次的原始多项式，查表可得： 1 030 ，代表了j p ( z ) = x ”+ x + l 。 口的g f ( 2 ) l ? 的最小多项式是这样定义的：对于给出g f ( 2 m ) 的任意元口，是具有 以盯为根的g f ( 2 ) _ h 的次数最小的多项式。如果求口的共轭根b ，口2 ，口4 ，口2 ” ，则 口的最小多项式为m ( 功= 一口) 口2 ) o 一口2 ”) 。 1 6 南京理工大学硕士学位论文基于二次背包加密的数字水印技术 表3 3 13 4 次以下的原始多项式表 f ”“ “ 1 + 一o 。一 鏊謦多嘎襄姆 零琢 m ，：冬蒌越羡摹殛。穗靠辆多项式非零项，i ll01 21 27430 2 32 35 o 22l01 31 3 43l02 42 44 310 33101 41 4 1 21 1lo2 5 2 53o 44 l 01 51 5lo2 6 2 687 l o 55 201 61 6 53 2o2 72 787lo 6 6l o1 7 1 7 30 2 82 880 77lo1 81 8 7o2 92 920 88 65lo1 91 9 65103 03 0 1 61 51o 99 402 02 0303 13 130 1 0 l o 3o 2 12 12o3 2 3 2 2 82 71o l ll l 202 22 2lo3 33 3 1 30 3 4 线性编码 线性编码的编码思想是，将信息f 用编码器( 数学表示为g 0 ) 函数) 生成发送 字w = i g ，要求对于奇偶校验矩阵日，满足h w 7 = 0 ，完成编码的过程，并将其传送 至信道。发送字w 经过信道传输或处理之后变成了接收字y ，在解码器端，通过计算 伴随式s = 王7 ，来进行错误的检测纠正。 在纠错时，s = 7 作为伴随式，用来检测纠错。发送字w 经过传输，附加上了 错误类型e 之后就转化为接收字y 。 f v = w + p 7 j = 缈7j s = 缈7 = l - l ( w + e ) 7 = h e 7 。 【h w r = 0 可以看出伴随式s 只有错误类型p 决定，不影响发送字y 。当s = 0 时表示没有错 误产生，当s 0 时，则根据s 的值来判断出错的位置。现举一例： 0 0 011l 1 l 设有奇偶校验矩阵日= l0 1l0 01 1 l ，发送字w 为( 0 1l 1 l00 ) ，在传 【1 0l010 1 j 输中产生了错误e = ( 0010000 ) ，即接收字变为y = w + e = ( 01o1100 ) 。通过计 f o 算伴随式s = 母7 ，i 4 s = 1 1l 。j 作为二进制，可以得知是3 ，于是得出y 的第3 【l j 比特存在错误。因此判断e = ( 0010 0 00 ) ，用e 纠正y ，正确译出发送字w - - - - y e - - 南京理工大学硕士学位论文基于二次背包加密的数字水印技术 ( 01 1 1100 ) 3 5 循环汉明码 3 5 1 循环汉明码的编码 循环码是线性分组代码中最重要的一种，它的结构完全建立在伽罗瓦域( 有限域) 的基础上，是用循环置换了任意代码字的代码，即对于一个( 疗，助线性分组码，若将 其任意一个码字( c 。，c 1 ，) 的码元向右或向左循环移一位，所得，c 。c ：c 。) 或 ( c 。，q c 。c 。) 仍然是码字。目前的差错控制系统中所使用的线性分组码几乎都是循 环码或循环码的子类。 按照循环码定义，( z ) = c a - i x “十+ c l 工+ 岛，码字( c 。1 ，c 1 ，气) 的码元向左循 环移一位得( c m ，c l c o c ) ，故彤( 工) = 已一2 x “+ + c o x + c ，即( 工) = x w o ( 砷 m o d ( x ”+ 1 ) 。依次类推，循环码循环移2 位、3 位、n - l 位，可得： 降2 ( 工) = x 彤( x ) = x 2 w 0 ( x ) m o d ( x ”+ 1 ) ； q = 工( 力= x w 0 0 m o d ( x “+ 1 ) ； 阡：一l ( x ) = x w 2 ( 石) = x n - i r v o ( x ) m o d ( x “+ 1 ) ； 式中，m o d