（信号与信息处理专业论文）像素缩小的可视秘密共享方案研究.pdf

摘要 摘要 在数据保护与信息安全的领域中，秘密共享是一项十分重要的技术。它在 信息与数据的传输和电子系统的安全中起着关键的作用。而可视秘密共享作为 秘密共享技术中的一种，它具有安全、算法简单等突出的特点，改善了其他传 统加密技术体制中出现的权力过度集中、抗干扰性弱等不足之处。可视秘密共 享技术被人们广泛地应用于银行体制管理、身份认证、军事等领域。目前已经 有许多种可视秘密共享方案，但仍然存在重建图像对比度低、以及分存图像像 素扩张等问题。 本文提出了一种像素缩小的( 2 n ，2 n ) 秘密共享方案，该方案对一幅秘密图像 进行置乱处理，根据实际需求将置乱后的图像分割成若干个像素块，对各个像 素块实行编码运算，从而得到2 ，2 幅尺寸为原密图1 2 n 大小的分存图像，将这些 分存图像分发给参与者保管。由于分存图像尺寸更小，减少了参与者的负担， 同时也有效地减少了系统的存储容量和传输带宽。在重建图像时，只有当这些 分存图像共同存在时才能够恢复出原始密图信息，且重建图像拥有理想对比度。 任何少于2 托幅分存图像都不能够获得关于秘密图像的任何信息。本文通过与其 它方案的对比，从方案的适用图像类型、像素扩展倍数、重构图像质量以及安 全性等角度阐释了该方案的性能特点。仿真结果表明，本文提出的基于置乱的 像素缩小的秘密共享方案是有效和可行的。 关键词：信息安全；可视秘密共享；像素缩小；理想对比度 ab s t r a c t a b s t r a c t s e c r e ts h a r i n gi sa ni m p o r t a n tt e c h n o l o g yi nt h ef i e l do fd a t ae n c r y p t i o na n d i n f o r m a t i o ns e c u r i t y i tp l a y sac r u c i a lr o l ei nt h es a f ek e e p i n g ，t r a n s f e ra n dl e g i t i m a t e u s eo fi n f o r m a t i o na n dd a t a a so n eo ft h es e c r e ts h a r i n gt e c h n o l o g i e s ，v i s u a ls e c r e t s h a r i n gh a ss o m ep r o m i n e n tf e a t u r e ss u c ha sm o r es e c u r i t y , s i m p l e ri m p l e m e n t a t i o n ， e t c a n ds u r p a s s e so t h e rt r a d i t i o n a le n c r y p t i o ns y s t e m sw h i c hg e n e r a l l yh a v et h e d r a w b a c k ss u c ha st h ee x c e s s i v er i g h tc o n c e n t r a t i o n ，w e a ka n t i - ja m m i n g ，e t c t h e v i s u a ls e c r e ts h a r i n gh a sb e e nw i d e l ya p p l i e dt ob a n k i n g s y s t e mm a n a g e m e n t ，i d e n t i t y a u t h e n t i c a t i o n ，m i l i t a r ya n do t h e rf i e l d s a l t h o u g ht h e r ea r em a n yk i n d so fv i s u a l s e c r e t s h a r i n gs c h e m e s ，t h e r e s t i l le x i s ts o m ep r o b l e m ss u c ha sl o wc o n t r a s tf o r r e c o n s t r u c t e di m a g e s ，p i x e le x p a n s i o nf o rs h a r ei m a g e s ，e t c i nt hi sd i s s e r t a t i o n ，ip r o p o s eap i x e lc o n t r a c t i b l e ( 2 n ，2 n ) v i s u a ls e c r e ts h a r i n g s c h e m e i nt h i ss c h e m e ，as e c r e ti m a g ei ss c r a m b l e da n dt h e nt h es c r a m b l e di m a g ei s d i v i d e di n t os e v e r a lb l o c k sa c c o r d i n gt ot h ea c t u a ld e m a n d e a c hb l o c ki se n c o d e d i n t o2 ns h a r ei m a g e sw h o s es i z ei s1 2 no ft h eo r i g i n a li m a g e t h e s es h a r ei m a g e sa r e d i s t r i b u t e i dt ot h ep a r t i c i p a n t st ok e e p t h es m a l l e rs i z eo fs h a r ei m a g e sr e d u c e st h e s t o r a g eb u r d e no np a r t i c i p a n t sa n dd e c r e a s e st h es y s t e m ss t o r a g ea n dt r a n s m i s s i o n b a n d w i d t hr e q u i r e m e n t s w h e nd e c o d i n g ，o n l yb ya l lt h ea v a i l a b l es h a r ei m a g e sc a n w eg e ts e c r e tr e c o n s t r u c t i o nw h i c hh a si d e a lc o n t r a s t a n yl e s st h a n2 ns h a r ei m a g e s c a nn o tr e v e a la n yi n f o r m a t i o na b o u tt h es e c r e ti m a g e b yc o m p a r i s o nw i t ho t h e r s e c r e ts h a r i n gs c h e m e s ，w ea n a l y z et h ep e r f o r m a n c eo ft h i sm e t h o di nd i f f e r e n t a s p e c t s ，s u c ha si m a g ef o r m a t ，p i x e le x p a n s i o n ，s e c r e ti m a g er e c o n s t r u c t e dq u a l i t y , a l g o r i t h m ss e c u r i t y , e t c t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e ds c h e m ei s e f f 宅c t i v e ：a n dr e l i a b le k e yw o r d s ：i n f o r m a t i o ns e c u r i t y ；v i s u a ls e c r e ts h a r i n g ；p i x e lc o n t r a c t i o n ；i d e a l c o n t r a s t 1 i 第1 章绪论 第1 章绪论 1 1 课题背景和研究意义 在数字化的今天，信息的传递在人们的生活中变得越来越重要，与此同时， 信息安全也引起了研究人员和工程技术人员的重视，其研究成果在很多领域得 到了广泛的应用，如网上银行、网上交易、电子政务、电子商务、军事图像、 秘密视频会议等。信息安全渐渐地深入到人们生活的各个方面，因此也越来越 受到社会的广泛关注。 在人们的日常生活中，图像和语音是人们传递和交流信息的主要媒介，其 中视觉信息占6 0 ，听觉信息占2 0 。由此可见，通过图像来传递信息的这一 方式在日常生活中占据着重要位置。因而，数字图像作为交流和传递消息的一 种媒介和手段，在人们的感知生活中扮演者不可替代的角色。数字图像常常被 用于网络和媒体的信息传递，例如数码照片以及秘密文件的传输等。然而大部 分的信息传输通道都是脆弱的，例如通过网络来传输军事图像、商业图像等较 为重要机密的图像是十分危险的，窃取者很容易在图像传递过程中监视因特网 而获取这些秘密图像。为了提高图像传递的安全性，人们对所要传递的图像信 息采用加密技术。图像的加密技术 1 是发送者为了使得图像原始信息安全传递 到接收方，从而对数字图像进行灰度变换、位置置乱等图像加密技术，隐藏原 始图像中所包含的有价值的信息，而接收者则能够通过事先约定的密钥及算法 正确地解密图像。 随着信息化的迅猛发展，加密技术也日益更新，同时也带来了密钥( k e y ) 的保存与管理问题，这使得密钥的安全管理成为加密技术的核心问题，并直接 影响到通信的安全【2 。因此，人们为了保护密钥，使密钥不受到损坏或是被人窃 取，采取将密钥分割成多份的方法，这样就增加了秘密的可靠性，秘密共享便 应运而生。所谓秘密共享一1 ( s e c r e ts h a r i n g ) ，是指把秘密依靠某种算法分割许多 份( 每份称为子秘密，或影子) ，再将这些份额分发给多个人保管，只有足够多 的份额数才能恢复出原有的秘密。最早提出这一概念的是s h 锄i r 【4 】和b l a k l e y 5 l ， 其主要思想是将一个秘密p 分成多个子秘密s 并分别交予, 个参与者保管，只 有当任意f ( 0 f o 那么r 称为实现访问结构r 上的非完善秘密共享方案【35 1 。 用熵的概念来对上述定义中的条件1 和条件2 来进行描述，则可以表示为： ( 1 ) 对于v a f ，均有h 岱ia ) = 0 。 ( 2 ) 对于v a 萑f xa p ，均有h 14 ) = h ( s ) 。 2 1 4 秘密共享的信息率 信息率是用来衡量一个秘密共享方案效率高低的指标，它是指方案中参与 者所掌握的予秘密的位长与共享秘密的位长的比例【3 6 1 ，即 参与者提供的子秘密总位长 r ，= ( 2 2 ) 共享秘密位长 从设计者的角度来讲，对于某一个固定的秘密，参与者所获得的子秘密与 秘密相关的信息越少越对方案的安全性有利。而对于参与者，其保管的子秘密 的规模越小越有利于存储及安全。因此，在秘密共享方案中，子秘密的规模越 7 第2 章秘密共享的基本原理与技术 小越好。换言之，信息率越大，方案的安全性越高。一般情况下，信息率r 。 1 。 当r 。= 1 时，是最理想的情况，将此种方案称为理想( i d e a l ) 的秘密共享方案。 定义2 1 2 【3 7 1 设p 为参与者集合，r 为p 上的访问结构，s 为共享秘密。p 为 秘密空间的概率分布，t 为r 上的秘密共享方案的空间，q 为s 上所有非凡概率 分布的空! 司，则 “) f 的信息率定义为： p ( r ，只) = 尚。 ( 2 ) r 的平均信息率定义为：占( f ，只 ) 2 南。 ( 3 ) 最优信息率定义为： p 。( 1 1 ) _ s u p 瑚器。 ( 3 ：) 最优信息率定义为： 二+ ( r ) = s u p t ，q 芝南。 一个秘密共享方案中的信息率和平均信息率主要取决于秘密空间的概率分 布和秘密份额的分配规则。p + ( r ) 与占+ ( r ) 只是一个仅与访问结构相关的参数，它 们、ie lf 上所有秘密共享方案的信息率以及平均信息率的最大值，因而称为最 优信息率和最优平均信息率。容易证明，对于任意的访问结构i ，均有： p ( r ，只) 茎p ( r ，只)，p + ( r ) s p ( r ) o p ( r ，只) ! p ( r ) s 1，o 占仃，尸) s p + ( r ) 1 1 2 2 门限秘密共享方案 门限方案( t h r e s h o l ds c h e m e ) 在很多普遍的秘密共享方案中是关键的构成模 块，它包含了两个重要的参数：门限值f ，予秘密数目甩，且满足f 墨船。( f ，甩) 门限方案是这样- * 0 方法【3 8 1 ：秘密消息m 在行个参与者组成的集体中共享，每 位参与者都持有相应数目的子秘密份额。由任意f 个或t 个以上的参与者组成的 子集都能够恢复出消息m 但是小于f 个参与者组成的子集则不能恢复出消息m 。 下面介绍两种经典的门限秘密共享方案。 2 2 1s h a m i r 的门限秘密共享方案 1 9 7 1 年，s h a m i r 第一次了提出基于拉格朗日( l a g r a n g e ) 插值法的( 六，2 ) 8 第2 章秘密共享的基本原理与技术 门限方案。 构造此方案时，首先选定一个素数p ( p 需要满足比所有可能的消息以及参 与者的个数船都大) 。用一个模p 数来表示消息m ，并在行个人中秘密共享消息 m 。然后，随机选取卜1 个模p 数，分别为0 1 ，a ：，a t 一，。构造多项式： s ( x ) = m + a l x + a 2 x 2 十+ a t 一1 x 卜1 ( m o d p ) ( 2 3 ) 该多项式满足s ( o ) 兰m ( m o dp ) 。 最后，在秘密分发时，选定不同的整数，x ：，x , ( m o d p ) ，给每一个参与者 一个数对( 一，乃) ，其中y ，三s ( x , ) ( m o d p ) 。在多项式中，素数p 的值是己知的，s ( x ) 的值则是保密的。 重构消息m 时，需要任意t 个参与者共同聚集并出示他们的数据对，假设 得到的f 个数据对为：( 五，y 。) ，( x ：，咒) ，( 一，y t ) ，通过l a g r a n g e 插值公式，便能 重构出秘密消息m ： y ( _ c ) = zy k 兀善( m o dp ) k = l i = l ，i * k - x k 一 j 令x = 0 ， m = y ( o ) = 坛兀鲁( m o d p ) k = l j = 1 ， 一 ， ( 2 4 ) ( 2 5 ) 从s h a m i r 的方案中可知，对于任何少于f 个参与者的集合都不能够恢复出 秘密m ，并且不能够获取与秘密相关的任何信息。对于大于等于f 个参与者则能 够计算出秘密，因此，s h a m i r 门限方案是完善的秘密共享方案。此外，每个子 秘密的尺寸不会超过秘密消息的尺寸，秘密分发者也可以通过选择不同的参数， 在不改变秘密的情况下而改变子秘密。同时也能够实现分级方案，主要是通过 适量地增加方案中新的参与者，根据每个参与者的重要性而分发给参与者相应 数量的子秘密来实现。 2 2 2b l a k l e y 的门限秘密共享方案 同样是在1 9 7 9 年，b l a k l e y 提出了基于投影集合理论的( 六挖) 门限秘密共 享方案。在该方案中，秘密消息被看作是f 维空间中的一个点，而每个子秘密则 看作是包含这个点的( 卜1 ) 维的超平面，通过在f 维空间用卜l 维的超平面，可 以对任意的f 和刀来创建一个( 咒) 门限方案。在恢复秘密时，任意的f 个这样 q 第2 章秘密共享的基本原理与技术 的超平面的交点正好能够确定这个秘密消息。 例如，设计者要安排3 个参与者共同参与时能够重构出秘密，而少于3 个 则无法计算出秘密。选择一个素数p ，随机选择y 。，m o dp ，令为秘密消息。 这样可以构造三维空间内的一个点q = ( x 0y o ，z 。) 。分发者分发给每一个参与者 一个通过q 点的平面方程： z = 似+ b y + c( 2 6 ) 其中，a ，b 为随机选取的模p 数，c = z o o x o b y o ( m o dp ) 。 利用三个平面必相交于一点可以计算出秘密消息q 。由于两个平面相交于 一条直线，因此少于三个的参与者无法计算出秘密。 与s h a m i r 方案相比较， b l a k l e y 提出的这个矢量体制是不完善的，加密编 码算法的效率也比s h a m i r 方案低。然而，在b l a k l e y 方案中任意的，个这样的超 平面份额：不仅能够确定唯一一点，而且他们之间是毫无关联的，但是对于s h a m i r 方案，足够数量的子秘密份额不仅能够确定出多项式同时也可以计算出其他的 份额值。 2 2 3t h i e n 和l i n 的秘密共享方案 t h i e n 和l i n e 3 9 】在s h a m i r 方案的基础上，提出了一种利用l a g r a n g e 插值多项 式对图像进行秘密共享的( r ， ) 门限方案。但在该方案中无需产生随机系数， 而是将图像的各个像素当作r - 1 阶多项式的系数。 假设共享的密图为s ，生成的船幅子秘密图像为s ，s ，一，s 。，取素数p = 2 5 1 。 由于灰度图像的像素值为0 2 5 5 ，因此在秘密分发阶段首先要将密图中2 5 1 2 5 5 的像素值都转化为2 5 0 ，这样使得密图中所有的像素值都在0 2 5 0 的范围内。然 后再选取一个密钥k e y 生成一个置乱序列来打乱密图s 中原有的像素位置，得 到置乱后的图像s t 。再对图像s 进行分割，得到多个包含，个像素的加密编码单 元，依次选取这些加密编码单元，按照式( 2 7 ) 对编码单元中的各个像素进行 计算，得到，2 幅子秘密图像的像素值。 q ，( x ) = ( p o + p l x + + p ，一l x r - 1 ) m o d 2 5 1 ( 2 7 ) 其中，风，p l ，只一，为第，个编码单元的r 个像素。计算g j ( 1 ) ，q ( 2 ) ，q ，( ，2 ) 的值， 并分别作；为刀幅子秘密图像的像素。直到所有的加密编码单元都编码结束为止， 这样就生成了n 幅子秘密。 1 0 第2 章秘密共享的基本原理与技术 在秘密重构阶段，选取r 幅子秘密图像，并从这r 幅图像中分别提取出相对 应的且未经过编码的像素q j ( ) ，q ，( 之) ，g 以) 。利用式( 2 7 ) 和这r 个数据对 ( i l ，q 恕) ) ，( i 2 ，q ，( f 2 ) ) ，( r ，q 舷) ) 求解出该式中的系数p o ，p 1 ，一，b _ 1 0 这r 个系数就是置 乱图像s 中相对应的像素。不断地重复上述过程，直到，幅子秘密图像中的所有 像素都处理完毕，这样便会得到了簧乱图像s 。最后运用逆置乱密钥对s 进行 逆置乱，从而得到重建图像。 在该方案中，由于在秘密分发阶段对密图中大于2 5 0 的像素值进行了处理， 因而该方案所恢复出的密图有相应的质量损失。此外，该方案对图像进行了置 乱处理，这也适当地增加了方案的算法复杂性。 2 3 基于矩阵乘法的秘密共享 2 3 1k a r n i n 的矩阵乘法秘密共享方案 k a m i n 4 0 】等人首次提出了基于矩阵乘法的图像秘密共享的方案，设共享的秘 密为s ，秘密分发过程为： 1 ) 令s = u a 。，其中u 是，z 维的行向量，a 。是为r t x m 维的矩阵，即秘密s 为 m 维行向量。选取，2 个n x m 的矩阵a ，a ：，a 。，满足 a ，a ：，a 。) 中任意f 个a ，组成的矩阵为满秩阵。 2 ) 将秘密s 分割，分割后的子秘密为s 。= u a ；，浮1 ，2 ，z ，子秘密的大小与 于原秘密s 的大小相同。 秘密重构过程为： 1 ) 任意f 个子秘密组成的矩阵为： 【u a x ，u 龟，驰 _ u a 1 ，a 】 ( 2 8 ) 其中任意，个a ，组成的矩阵为满秩阵，由此可以计算出其逆矩阵 a 一，a ， - l ， 这样便构成了f 阶的线性方程组，未知数为向量u ，从而求解出u 。 2 ) 得到向量u 后，秘密s = u a 。，这样便重构出了原秘密。 在k a m i n 的方案中，秘密共享的分发者在分发阶段不仅需要传输子秘密， 同时还需要额外传输a 。，这样无疑增加了方案的复杂程度。此外，子秘密与原 秘密同样大小，不利于存储或者是数据量较大的方案。 第2 章秘密共享的基本原理与技术 2 3 2l ib a i 的投影矩阵秘密共享方案 针对k a m i n 方案的不足之处，l ib a i 1 提出了基于投影矩阵的( 屯甩) 门限方 案，该方案利用投影矩阵的不变性，使得子秘密比原秘密小。下面先介绍投影 矩阵的定义及不变性理论。 假设个矩阵a 删，且秩为f ，小f 0 。则a 的投影矩阵s 定义为： s ：a ( a a 、。1a 可简记为s - p r o j ( a ) ，式中a 表示矩阵a 的转置。 构造f 个线性无关的f 1 维向量x ，( 1 i f ) ，计算向量v ，= a x ，。从而得到矩 阵b 。，= i v 。，v ：，v ，】，那么矩阵a 的投影和矩阵b 的投影是相等的，即 s = p r o j ( a 。) = p r o j ( b ) 。对于投影矩阵s ，它具有以下的性质： ( 1 ：) s 是对称矩阵。 ( 2 ：) s 是一个幂等矩阵，即s 2 = s 。 ( 3 ：)s a = a 。 ( 4 ：) t r ( s ) = r a n k ( s ) = t ，其中t r ( s ) = s f 。 l i1 3 a i 的方案便是在投影矩阵性质的基础上提出来的，假设s 。，为秘密矩 阵，秘密分发过程为： ( 1 ：) 构造一个矩阵a m 使得矩阵a 的秩为k 。 ( 2 ) 计算投影矩阵s = ( a ( a f a ) 叫a ) m o d p ，同时计算残差矩阵 r = l s sl m o d p ，并且公开矩阵r 。 ( 3 ) 任意选取力个七维向量x ，( f - 1 ，2 ，船) ，满足其中任意尼个向量都线性 无关。 ( 4 ) 计算子秘密v ，= ( a x ，) r o o dp ，江1 ，2 ，刀，将子秘密分发给n 个参与 者。 秘密重构过程为： ( 1 ) 任意选取k 个子秘密，假设选取的子秘密为v ，( 汪1 ，2 ，忌) ，构造矩阵 g = v 1 ，v 2 ，v 七】，计算投影矩阵s = ( g ( g g ) 。g m o dp 。 ( 2 ) 验证矩阵迹t r ( s ) = k ，恢复秘密矩阵s = ( s + r ) m o dp 。 在nb a i 的投影矩阵方案中，子秘密的大小是原秘密大小的1 m 。但是在 1 2 第2 章秘密共享的基本原理与技术 秘密重构阶段，如果矩阵r 遭到恶意篡改或丢失，那么秘密将无法恢复。这使 得该方案存在一定的局限性。 2 4 可验证的秘密共享 通常在秘密共享方案中，都是假定参与者以及子秘密的持有者是可靠的， 并且子秘密是安全的。然而，在现实中有时难以满足这两种情况，一是参与者 有可能存在欺诈现象，提供虚假的子秘密，从而使得原秘密无法恢复。二是秘 密分发者也会存在欺诈现象，分发给参与者虚假的秘密份额。而可验证秘密共 享则是解决这些问题，它的主要思想是在一个一般的秘密共享方案上增添一个 分发者和参与者互相认证彼此提供的秘密份额是否有效的验证算法。 根据验证算法是否需要分发者与参与者之间或参与者与参与者之间进行交 互可以将可验证秘密共享方案分为非交互式与交互式。早期提出的方案大都是 交互式的，运算效率较低。随后出现了非交互式方案，这种方案不需要可信机 构的参与，提高了运算效率，引起了研究人员的广泛重视，非交互式的可验证 秘密共享方案目前广泛地应用于多方安全计算，分布式密钥生成等领域。下面 介绍两个经典的非交互式可验证秘密共享方案。 2 4 1f e l d m a n 可验证秘密共享方案 f e l d m a l l 【4 2 1 于1 9 8 7 年首次提出了非交互式的( f ，胛) 可验证秘密共享方案，该 方案是在s h a m i r 的门限秘密共享方案的基础上增添一个公开验证函数，子秘密 的接受者能够通过这个函数来验证子秘密是否有效，从而防止分发者的欺骗行 为。 假设秘密为s ，门限值为，选取参数p ，q ，g ，满足p 为一个大素数，g 为 p 的大素因子，g z ：且为g 阶元。分发者在z p 中任选随机多项式： 厂( x ) = a o + a t x + + a t x 卜1m o dq ， 其中a 0 ，a 1 ，一，a t l 是在z ，上任选的随机数，a o = s 。 计算秘密份额s ，= f ( x 。) 并发送给参与者，同时广播验证消息： c j = g 。m o dp ， 其中，= o ，1 ，f 一1 。参与者可以通过式( 2 9 ) 来验证所得到的秘密份额是否正 第2 章秘密共享的基本原理与技术 确。 t - 1 9 1 - - 1 - i c ；m o dp ( f _ 1 ，2 ，聆) ( 2 9 ) j = o 若不满足等式，则参与者可以对秘密分发者给予举报，分发者必须做出相 应的回应：，同时分发正确的子秘密。若对分发者的举报数超过了一定数目，则 可以取消分发者的资格。 秘密：重构时，每个参与者都可以通过式( 2 9 ) 来验证彼此提供的子秘密是 否有效，通过合法验证后，然后再利用拉格朗日插值公式来恢复秘密。 可以证明，该方案是安全的。尽管与秘密相关的信息g o , m o d p 是公开的， 然而任意少于f 个子秘密都无法恢复出原始秘密消息，除了从g 嘞m o d p 获取的信 息外，无法获取任何关于秘密的其他信息。 2 4 2p e d e r s e n 可验证秘密共享方案 非交互式的可验证秘密共享的另一个典型方案是由p e d e r s e n t 4 3 】提出的，与 f e l d m a n 的方案相比较，该方案给出了对秘密的一种更安全的信息论可验证共享 机制。 假设秘密依然为s ，门限值为，。选取参数p ，q ，g ，满足p 为一个大素数，g 为 p 一1 的大素因子，g z ；且为g 阶元。h 是由g 生成的循环群中的元素，且l o g 。h 未 知。秘密分发步骤如下： ( 1 ：) 构造两个f 次随机多项式： f ( x ) = 口o + q x + + a t x 。，f ( x ) = b o + 反x + + 眈x 。 其中，a o = s ，q ，a t 和，2 5 1 ，岛是- f fz , 上随机选取的数。计算= f ( i ) m o dq ， s ，= f ( d m o dq ，作为秘密份额分发给参与者。同时公布验证消息： y k = g 吼h m o dp ( 尼= 0 ，1 ，f ) ( 2 1 0 ) 这是不同于f e l d m a n 的可验证方案的根本地方，在这里，有关秘密的信息 仅为y 。= = g o o h m o dp ，因此对于任意的s 乙，都存在唯一的b z q ，使得 y o = g h 6m o d p 。因此虬没有泄露任何关于s 的信息，秘密值是无条件安全的， 称为一种无条件安全的承诺。 ( 2 ) 参与者可通过式( 2 1 1 ) 来验证秘密份额的正确性： 1 4 第2 章秘密共享的基本原理与技术 g 谢r ：r 1 ( ) j m o dp k = o ( 2 1 1 ) 通过验证算法，参与者便能通过检验自己所持有的子秘密的真假来判断分 发者是否有欺骗行为。 秘密重构时，由式( 2 1 1 ) 来检验各参与者提供的秘密份额，然后通过拉格 朗日插值法恢复出秘密j ，假设通过验证的t + 1 个碎片为溉，屯，s i t + l ，那么秘 密a 。= s 可以如下恢复： r + 1 s = 凡 m o d p ( 2 1 2 ) = i p e d e r s e n 的方案具有无条件安全的优点，而对于f e l d m a n 的方案，尽管无法 从泄露的信息g 嘞m o d p 中完全恢复出秘密，但这个信息可能会被攻击者所利用， 攻击者可以随机地选取一些数来控制g r o o d p 的值，从而使得秘密具有其所需 要的性质。 2 5 本章小结 本章首先介绍了秘密共享的基本概念，包括秘密共享的定义、访问结构、“完 善”的概念以及信息率。随后介绍了秘密共享中的三大经典方案，即门限方案、 矩阵乘法方案和可验证秘密共享方案。针对这三种方案，本章给出了相应的阐 述以及分析。 第3 章可视秘密共享的研究 第3 章可视秘密共享的研究 3 1 可视密码学的基本原理 3 1 1 图像的基本知识 人们通过感觉器官来从外界获取信息，而视觉信息的信息量大，传播的速 度快，作用距离远等等，因而图像在人们的生活中扮演着十分重要的角色。尤 其是在安全通信以及数据保护方面，图像处理更是不可缺少的一项基本技术。 在s h a m i r 和b l a c k l e y 方案的基础上，越来越多的秘密共享方案倾向于对图像进 行处理。尤其是在可视秘密共享方案中，便常常是对一幅或多幅图像进行秘密 共享。 就图像自身而言，大致分为模拟图像和数字图像两类。将一幅图像表示为 一个二维函数f ( x ，y ) ，其中x ，y 是空间的坐标，而对应空间坐标点( x ，y ) 上的幅 值厂称作该图像的强度、亮度或灰度。对于模拟图像，计算机是无法直接处理 的，因为， 莫拟图像的空间坐标和明暗程度的变化具有连续性。而对于数字图像【4 4 l ， 则可以用计算机直接处理，因为数字图像中的z ，y 和幅值厂是有限离散的值。因 此，图像秘密共享中的图像是指数字图像。构成数字图像的具有特定位置和幅 值的有限的元素，称作画面元素、图像元素或像素。数字图像处理有诸多优点， 例如：处理精度高、有灵活的变通能力、处理的内容丰富、能够进行复杂的非 线性运算处理等。 数字图像也常常用矩阵来表示，矩阵的每一个元素对应了图像的一个像素， 当保存一幅图像时，不仅要保存图像的位图数据矩阵，还要保存每个像素的颜 色。假设图像s 用一个矩阵m 表示。定义一幅图像有彩色数c 和w h 个像素阢， 其中1 1 时， 说明图像的解析度损失了，并且不利于子秘密的存储，因此在v s s 方案中希望 17 第3 章可视秘密共享的研究 m 的值越小越好。 在秘密重构阶段，任意授权集合中的子集进行叠加，就能够恢复出在一定 程度上能：够辨识的密图。密图中的每一个像素在经过重构以后由m 个黑和白的 子像素表：示，其灰度值取决于这m 个子像素构成的向量v 的海明重量( h a m m i n g w e i g h t ) h ( v ) 。 定义3 1 2 令d 为门限值，且满足1 d m 。当h ( v ) d 时，该灰度级别在 视觉上可辨识为黑色；当h ( v ) d a m 时，该灰度级别在视觉上可辨识为白色。 其中，a = f 一”。l m ，代表结果图像在对比度上的损失情况。和刀。分别为密 图中黑色像素和白色像素所产生的子像素的数目。因此在v s s 方案中希望口的 值越大越好。 总之，由以上的秘密分发与秘密重构两个阶段可以看出，一般的( 屯门) v s s 方案是这样一种方案：构造两个m 的布尔矩阵c 。，c 。当所加密的像素为白色 时，从c 。中随机选取一个矩阵；当所加密的像素为黑色时，从c ，中随机选取一 个矩阵。所选取的矩阵确定了分存图像中m 个子像素的灰度级。并且该方案满 足以下条件： ( 1 ) 对于v m c 。，矩阵m 中的任意胛行中的r 行进行或操作得到的结果 向量v 蒲足h ( v ) d 一口，z ； ( 2 ) 对于v m c ，矩阵m 中的任意挖行中的r 行进行或操作得到的结果 向量v 满足h ( v ) d ； ( 3 ) 对于任意的 ，i 2 ，i q c 1 ，2 ，” ( g ，) ，选取c 。和c 。中的每个矩阵的 ，之，行，构成两个矩阵簇d 。和d 。那么d 。和d 1 以相同的频率包含相同的矩 阵。 条件( 1 ) 和条件( 2 ) 被称为“对比性”条件，即任意k 幅分存图像所重构出的密 图能够通过人眼识别出。而条件( 3 ) 被称为“安全性”条件，即任何少于k 个分存 图像都无法得到关于密图的任何信息。 对于一般的( 屯尼) v v s 方案，当参数m = 2 肛1 ，口= 1 2 扣1 时，此方案为最 优方案。对于更为一般的( 屯门) v v s 方案，则需满足m = l o g 2 0 ( k l o g k ) ，口= 1 2 q ( 。 3 1 3 传统的s h a m i r 和n a o r 可视密码方案 1 9 9 4 年，s h a m i r , n a o r 在欧洲密码学会上第一次提出了可视密码研究方案， 该方案主要是对黑白图像进行加密编码运算，在编码后将分存图像( s h a r ei m a g e ) 18 第3 章可视秘密兆享的研究 打印到透明胶片上分发给用户，在重构时无需通过电脑计算，仅通过透明胶片 的叠加便能识别出加密图像。 以s h a m i r , n a o r 的( 2 ，2 ) v c s 方案为例来进行说明，如表3 1 所示。生成 的两幅分存图像为s ，和s ，表中的每一行都表示一种加密规则，概率则是该行 被选中的机率，可以看到，每行被选中的概率为o 5 。秘密图像的像素为白色或 黑色时，分存图像中与之对应的像素均为一黑一白，这样在每个分存图像中， 黑白像素出现的概率相同。加密编码后生成的图像都是由随机出现的黑白像素 点组成的，任何人无法读出其中的信息，这样图像共享后的安全性便有了保证。 表3 1s h a m i r , n a o r 的( 2 ，2 ) v c s 方案 加密像素 s ls 2s 1 + s 2 口 口口口 口 口口 口 口l 口一口i 密图重构时将两个分存图像叠加，即进行或运算s ，+ s ，那么密图中为白色 的像素，叠加后为一黑一白，密图中为黑色的像素，叠加后全为黑。这样重构 出的图像和原图比较，密图中的白色区域在重构图像中显示的是灰色，而密图 中的黑色区域在重构图像中仍显示为黑色，灰色与黑色的对比使得通过人眼能 够识别出密图信息。从表中可以明显看出，由于密图中的一个像素被共享后变 成了两个像素，使得重构的图像大小扩大了两倍，即长宽比例由之前的1 ：1 变成 了1 ：2 。结果如图3 1 所示，图( a ) 为秘密图像；( b ) 、( c ) 为两幅分存图像；( d ) 为重 构图像。 1 9 第3 章可视秘密共享的研究 ( c ) ( d ) 图3 1s h a m i r , n a o r 的( 2 ，2 ) v c s 方案结果图：( a ) 秘密图像；( b ) 分存图像s 1 ；( c ) 分存 图像s 2 ：( d ) 重构图像 用两个布尔矩阵c 。，c 。来构造该方案，c 。为白色像素的加密矩阵集合，c ，为 m o 2 1oi m l 2 fo1 c o 一删删) c l 一心删 加密矩阵c 。和c 。假设要构造( 2 ，3 ) v c s 方案，则可以令基阵m 。和m 。为： m 。= i 三三 ，m ：= 釜三詈 。 2 0 第3 章可视秘密共享的研究 后生成的分存图像存在像素扩张问题。( 3 ) 重构后的图像对比度低。 3 2 概率可视秘密共享 3 2 1 概率可视秘密共享的基本理论 为了解决秘密共享方案中分存图像的像素扩张问题，y a n g t 2 引，h o u t 2 0 】和i t o t 2 4 】 等人都针对二值图像提出了概率可视秘密共享方案( p r o b v s s ) 。在p o b v s s 方 案中，密图的每一个像素的恢复都是以一定的概率进行的，如果在重构图像中 的某一个区域白色像素点越多，那么这个区域看起来就越白。反之，如果某一 区域黑色像素点越多，那么就认为这个区域看起来越黑。例如，如果用一幅有 8 0 为黑色像素的图像b 来代表具有相同大小的全黑图像b ，用一块有3 0 为白 色像素的图像w 来代表具有相同大小的全白图像w ，通过人眼的视觉系统，可 以看到虽然图像b f 看起来没有图像b 黑，而图像w 看起来没有图像w 白，但 是依然可以区别b 和w 之间存在的差异，这就是通过控制在图像中黑色像素和 白色像素出现概率的p r o b v s s 方案。 定义3 2 1 ( 免船) p r o b v s s ：p r o b v s s 方案通过两个矩阵集合c 。，c ，来构造。 当所加密的像素为白色时，从c 。中随机选取一个矩阵；当所加密的像素为黑色 时，从c ，中随机选取一个矩阵。其中c 。，c ，分别包含了聆。个和玎，个n 1 矩阵， 用m ，和b ，表示，m ，( f _ 1 ，, 五) cc o ，b ，( f - 1 ，行，) cc l ，并且满足以下条件： ( 1 ) 对于v m icc 。( 或v b 。cc ，) ，矩阵m ，( 或b ，) 中的任意k 列向量 的或运算结果的汉明重量为h ( v ) ，所有这些汉明重量组成一个集合五( 或y ) ； ( 2 ) 用r 和鼻分别表示“0 ”( 即白色像素点) 在集合五和7 中出现的概率， 则满足p 0 岛，置舅h 一口。其中，口0 ，为相对差。0 l ，为一个固定 的门限值。 ( 3 ) 对于任意的 ，i 2 ， c 1 ，2 ，胛 ( g 只，对比度口= o 5 ，因此能够通过人眼辨识出原秘密图像。而对于每一 个分存图像，像素点是“0 ”( 白色) 的概率和像素点是“1 ”( 黑色) 的概率均为 0 5 ，因而无法从分存图像中获取任何有关密图的信息。这样就满足了“对照度” 条件和“安全性”条件。 在秘密重构时，只要将生成的两幅图像的相对应的像素进行或运算便能得 到重构图像。如图3 3 所示，图( a ) 为待加密的l e n a 图像，( b ) 、( c ) 为分存图像， ( d ) 为重建图像。 第3 章可视秘密共享的研究 c 。= 量 ，i ，c。=筝，兰1，釜，毛，。 2 5 第3 章可视秘密共享的研究 图像。当这些网点分布的越密集，人眼看到的图像就会越暗，而当这些网点分 布的越稀疏，人眼看到的图像就会越亮。根据视觉系统的这一特点，人们用网 点的大小或者疏密程度来表现出画面阶调，也称为色调值。目前使用较广的半 色调技术有：抖动法、误差扩散法、蓝噪声法等。 表3 2h o u 的( 2 ，2 ) 可视密码方案 加密序列选中概率 分存图像s 1分存图像s 2s l + s 2 0 5 一 一 匝 o 5 口口口 o 5 即口l - i 0 5 口l 0 2 5 口 一1 口 0 2 5 阻口 一 0 2 5 口口 0 2 5町 口 町 0 2 5 口口 一 阻口1 【1 0 2 5 0 2 5口 一 口口口 0 2 5 通过半色调技术，可以运用白点与黑点的变化模拟出灰度图像的效果。基 于这一点，h o u 运用半色调技术将一幅灰度图像转化为二值图像，然后对其进行 加密。该加密方法主要是通过构造基本矩阵对多个像素点同时进行加密。以( 2 ，2 ) 方案为例来阐述该方案的基本思想。假设待共享图像为s ，分存图像为s i 和s 2 ， 依次选取s 中的两个连续的像素作为加密序列，如表3 2 所示，当加密序列都为 白( 黑) 色时，对应于表中的全为白( 黑) 色像素的加密规则，随机选取其中 的一行并分别分配给两幅分存图像作为其对应位置的像素，由于生成的分存图 像的像素都是一黑一白，这样在分存图像中黑白点出现的概率相同，因此无法 从图中识别出有关密图的任何信息。此外，可以从表中的叠加结果看到，密图 中两个为白色的像素重构后的结果是一黑一白，而两个为黑色的像素重构后的 结果均为黑色，这样重构后的白点与黑点之间有对比上的差异，因而人眼能够 2 6 第3 章可视秘密共享的研究 识别出来。当加密序列为一黑一白时，对应于表3 2 中所示的加密规则，全为白 色和全为黑色像素的加密规则各占一半，生成的分存图像依然为一黑一白。然 而，倘若加密时随机选取全为白色像素或全为黑色像素的加密规则，会使得重 构图像看起来较为混乱。因此对于连续两点为一黑一白的像素，h o u 采用如下的 加密规则： i f( 聊r o o d2 ) 1t h e n 从两个为黑色像素的加密规则中随机选取一行 e l s e 从两个为白色像素的加密规则中随机选取一行 其中，m 为已加过密的一黑一白的加密序列的个数。这样会使得每两个一黑一白 的加密序列中的一对运用的是全为白色像素的加密规则，另外一对则运用的是 全为黑色像素的加密规则，并且所重构的图像在视觉上看起来也