《最新图像处理第7章精品课件》由会员分享，可在线阅读，更多相关《最新图像处理第7章精品课件（48页珍藏版）》请在金锄头文库上搜索。
1、图像处理第图像处理第7 7章章信息论基础B7.1 密码学的基础知识密码学的基础知识 人们希望把重要信息通过某种变换转换成秘密形式的信息。转换方法可以分为两大类：隐写术，隐蔽信息载体信号的存在，古代常用。编码术，将载荷信息的信号进行各种变换使它们不为非授权者所理解。 在利用现代通讯工具的条件下，隐写术受到很大限制，但编码术却以计算机为工具取得了很大的发展。 信息论基础B信息论基础B信息论基础B信息论基础B信息论基础B信息论基础B信息论基础BEBDBMCM保障保密性保障真实性MCMDAEADAEBDBEAMCCCM保密性真实性信息论基础B密码分类密码分类n根据加密明文数据时的加密单位的不同，分为分
2、组密码和序列密码两大类。n分组密码：设M为密码消息，将M分成等长的连续区组M1,M2,，分组的长度一般是几个字符，并且用同一密钥K为各区组加密，即 n序列密码：若将M分成连续的字符或位m1,m2,，并用密钥序列KK1K2的第i个元素给mi加密，即n常用分组密码。 信息论基础B熵概念熵概念n密码系统的安全问题与噪声信道问题进行类比。噪声相当于加密变换，接收的失真消息相当于密文，破译者则可类比于噪声信道中的计算者。 n随机变量的不确定性可以通过给予附加信息而减少。正如前面介绍过条件熵一定小于无条件熵。例如，令X是32位二进制整数并且所有值的出现概率都相等，则X的熵H(X)32比特。假设已经知道X是
3、偶数，那么熵就减少了一位，因为X的最低位肯定是零。 信息论基础B疑义度疑义度 n对于给定密文，密钥的疑义度可表示为n对于给定密文，明文的疑义度可表示为 信息论基础Bn破译者的任务是从截获的密文中提取有关明文的信息或从密文中提取有关密钥的信息 I(M；C)H(M)H(M/C) I(K；C)H(K)H(K/C)nH(M/C)和H(K/C)越大，破译者从密文能够提取出有关明文和密钥的信息就越小。n对于合法的接收者，在已知密钥和密文条件下提取明文信息：H(M/CK)0 I(M；CK)H(M)H(M/CK)H(M) 疑义度疑义度 信息论基础B 因为因为 H(K/C)H(M/KC) H(M/C)H(K/M
4、C)（M和和K交换）交换） H(M/C) （熵值（熵值H(K/MC)总是大于等于零）总是大于等于零）H(M/CK)0，上式得上式得 H(K/C) H(M/C)即即已已知知密密文文后后，密密钥钥的的疑疑义义度度总总是是大大于于等等于于明明文文的的疑疑义义度度。我我们们可可以以这这样样来来理理解解，由由于于可可能能存存在在多多种种密密钥钥把把一一个明文消息个明文消息M加密成相同的密文消息加密成相同的密文消息C，即满足，即满足 的的K值值不不止止一一个个。但但用用同同一一个个密密钥钥对对不不同同明明文文加加密密而而得得到相同的密文则较困难。到相同的密文则较困难。信息论基础B又因为又因为 H(K) H
5、(K/C) H(M/C)，则则 上上式式说说明明，保保密密系系统统的的密密钥钥量量越越少少，密密钥钥熵熵H(K)就就越越小小，其其密密文文中中含含有有的的关关于于明明文文的的信信息息量量I(M;C)就就越越大大。至至于于破破译译者者能能否否有有效效地地提提取取出出来来，则则是是另另外外的的问问题题了了。作作为为系系统统设设计计者者，自自然然要要选选择择有有足足够够多多的的密钥量才行。密钥量才行。 信息论基础B7.2 数据加密标准数据加密标准DES 1977年7月美国国家标准局公布了采纳IBM公司设计的方案作为非机密数据的正式数据加密标准（DESData Encryption Standard）
6、。DES密码是一种采用传统加密方法的区组密码，它的算法是对称的，既可用于加密又可用于解密。 信息论基础B7.2.1 换位和替代密码换位和替代密码 n换位密码：对数据中的字符或更小的单位（如位）重新组织，但并不改变它们本身。n替代密码：改变数据中的字符，但不改变它们之间的相对位置。 信息论基础BP盒015150014140013130012120输011110输010100入0990出0880数0770数0660据0551据0440033002201110输入第i位输出第j位151413121110987654321741210152111914638135换位盒(P盒)信息论基础BS盒n=32
7、n=82n=80001112213314415516677输入输出000001010011100101110111101010100111000110011001替代盒（S盒）信息论基础B0PsPsPsP0010000输0sss0输01入01出0sss1数01数00据0sss0据00010sss110P盒和S盒的结合使用信息论基础B7.2.2 DES密码算法密码算法 nDES密码就是在上述换位和替代密码的基础上密码就是在上述换位和替代密码的基础上发展的。发展的。n将输入明文序列分成区组，每组将输入明文序列分成区组，每组64比特。比特。 n64比特的密钥源循环移位产生比特的密钥源循环移位产生16
8、个子密钥个子密钥信息论基础B密钥表计算信息论基础B7.2.3 DES密码的安全性密码的安全性 DES的出现在密码学史上是一个创举。以前的任何设计者对于密码体制及其设计细节都是严加保密的。而DES算法则公开发表，任人测试、研究和分析，无须通过许可就可制作DES的芯片和以DES为基础的保密设备。DES的安全性完全依赖于所用的密钥。 信息论基础B弱密钥弱密钥nDES算法中每次迭代所用的子密钥都相同，即K1K2K16，如111，此时DESk(DESk(x)x，DESk1(DESk1(x)x即以k对x加密两次或解密两次都恢复出明文。其加密运算和解密运算没有区别。n而对一般密钥只满足DESk1(DESk(
9、x)DESk(DESk1(x)x信息论基础B半弱密钥半弱密钥n给定的密钥k，相应的16个子密钥只有两种图样，且每种都出现8次。如101010n半弱密钥的特点是成对地出现，且具有下述性质：若k1和k2为一对互逆的半弱密钥，x为明文组，则有DESk1(DESk2(x)DESk2(DESk1(x)x称k1和k2是互为对合的。信息论基础B问题问题nDES的密钥短了些 n选择长的密钥会使成本提高、运行速度降低。 n新算法很可能要采用128比特密钥。 n实现DES算法的产品有：q设计专用LSI器件或芯片；q用现成的微处理器实现；q只限于实现DES算法；q可运行各种工作模式。 信息论基础B7.2.4 DES
10、密码的改进密码的改进 尽管DES算法十分复杂，但它基本上还是采用64比特字符的单字母表替换密码。当同样的64比特明文块进入编码器后，得到的是同样的64比特的密文块。破译者可利用这个性质来破译DES。 改进方法：密码块链接、密码反馈方改进方法：密码块链接、密码反馈方式式信息论基础B密码块链接M1M2M3M4C1C2C3C4V#密钥DDDD解密箱加密箱密钥EEEEV#异或C1C2C3C4M1M2M3M4(a)(b)信息论基础B64位移位寄存器64位移位寄存器C2C3C4C5C6C7C8C9C2C3C4C5C6C7C8C9648密钥E加密箱C10密钥E加密箱C10选择最左字节选择最左字节8M10#C
11、10C10#M108(a)(b)密码反馈方式信息论基础B7.3 公开密钥加密法公开密钥加密法 n前面介绍的秘密密钥加密法，算法公开，密钥是保密的（对称密钥）。n如果要进行通信，必须在这之前把密钥通过非常可靠的方式分配给所有接收者，这在某些场合是很难做到的。n因而提出了公开密钥加密法PKC（Public Key Cryptography）信息论基础B密密 钥钥n使用两个不同密钥（非对称密钥体制）；n一个公开(公钥)，另一个为用户专用(私钥)；n通信双方无需事先交换密钥就可进行保密通信；n要从公钥或密文分析出明文或私钥，在计算上是不可能的。信息论基础B应应 用用n保密通信： 多个用户将信息传给某用
12、户，可用该用户的公钥加密，唯有该用户可用自己的私钥解读。n数字签名： 用自己的私钥加密信息，而以公钥作为解密密钥，用来确认发送者。信息论基础BPKC算法的关键算法的关键 加密函数加密函数yF(x)的单向性的单向性 n加密计算容易：对任意给定的x值，容易计算yF(x)的值；n破译难：已知F和y，不可能求出对应的x值；n用私钥容易解密：若知道F的某种特殊性质（窍门trapdoor ），就容易计算出x值。信息论基础B构造和使用构造和使用n使用者构造出单向函数F（公钥）和它的逆函数F1（私钥）。n破译者：已知F和密文不能推导出F1或明文；n接收者：用窍门信息（解密密钥Kd）简单地求解xF1Kd(y)。
13、 信息论基础B7.4.1 公开密钥密码体制公开密钥密码体制 保密通信保密通信 公开加密密钥秘密解密密钥B(e，n)B(d，n)A(e，n)A(d，n)B发到ABMfA(e，n)CAA接收BACfA(d，n)MA发到BAMfB(e，n)CBB接收ABCfB(d，n)M信息论基础B7.4.1 公开密钥密码体制公开密钥密码体制 数字签名数字签名 公开加密密钥秘密解密密钥B(e，n)B(d，n)A(e，n)A(d，n)B发到ABMfB(d，n)SfA(e，n)CAA收到BACfA(d，n)SfB(e，n)M信息论基础BRSA密码体制（密码体制（1） nRSA由来：RSA体制是根据PKC算法由美国麻省理
14、工学院（MIT）的研究小组提出的，该体制的名称是用了三位作者（Rivest，Shamir和Adleman）英文名字的第一个字母拼合而成。n理论基础：利用数论 正：要求得到两个大素数（如大到100位）的 乘积在计算机上很容易实现。 逆：但要分解两个大素数的乘积在计算上几乎 不可能实现。信息论基础Bn密钥设计：两个密钥：公钥（e，n） 私钥（d，n）n加密解密： 加密时：解密时： RSA密码体制（密码体制（2） 信息论基础Bn实现步骤：q选取两个很大的素数p和q，令模数 q求n的欧拉函数 并从2至(n)1中任选一个数作为加密指数e；q解同余方程 求得解密指数d；q(e，n)即为公开密钥，(d，n)
15、即为秘密密钥。 RSA密码体制（密码体制（3） 信息论基础B例题保密通信例题保密通信例7-1 在RSA方法中，令p3，q17，取e5，试计算解密密钥d并加密M2。解：npq51 (n)(p1)(q1)32 (5d) mod 321，可解得d13 加密 yxe mod n25 mod 5132 解密 yd mod n3213 mod 512x 若需发送的报文内容是用英文或其他文字表示的，则可先将文字转换成等效的数字，再进行加密运算。 信息论基础BRSA公开密钥体制用于数字签名公开密钥体制用于数字签名n发送者发送者A用自己的秘密解密密钥用自己的秘密解密密钥(dA，nA)计算签名；计算签名；n用接收
16、者用接收者B的公开加密密钥的公开加密密钥(eB，nB)再次加密：再次加密：n接收者接收者B用自己的秘密解密密钥用自己的秘密解密密钥(dB，nB)解密：解密：n查发送者查发送者A的公开密钥的公开密钥(dA，nA)计算，恢复出发送者计算，恢复出发送者的签名，认证密文的来源。的签名，认证密文的来源。(dA，nA)(eB，nB)(dB，nB)(eA，nA)MiSiSSiMi信息论基础B例题数字签名例题数字签名例7-2 用用户户A发发送送给给用用户户B一一份份密密文文，用用户户A用用首首字字母母B02来签署密文。用户来签署密文。用户A知道下列三个密钥：知道下列三个密钥： A B公开密钥公开密钥(e，n)
17、 (7，123) (13，51)秘密密钥秘密密钥(d，n) (23，123)A计算他的签名：计算他的签名：再次加密签名：再次加密签名：信息论基础B 接收者B必须恢复出02B认证他接收的密文。接收者也知道三个密钥： A B公开密钥(e，n) (7，123) (13，51)秘密密钥(d，n) (5，51)B用户用自己的秘密解密密钥一次解密： 再用A用户的公开密钥解密：B用户可以确认：该签名是由A发出用A公钥可解读； 该签名是发给自己的用了B的公钥。例题数字签名（续）例题数字签名（续）信息论基础B安全性和速度安全性和速度nn要大，破译512比特（154位） RSA算法体制与破译64比特的单密钥体制相当；n目前n512比特在短期内十分安全，但已有一定威胁，很快可能要采用768比特甚至1024比特；nRSA算法的硬件实现速度很慢，最快也只有DES的1/1000，512比特模下的VLSI硬件实现只达64kb/s；软件实现的RSA的速度只有DES的软件实现的1/100。n在速度上RSA无法与对称密钥体制相比，因而RSA体制多用于密钥交换和认证。
