最新图像处理第7章精品课件.ppt
信息论基础B7.1 密码学的基础知识密码学的基础知识 人们希望把重要信息通过某种变换转换成秘密形式的信息。转换方法可以分为两大类：隐写术，隐蔽信息载体信号的存在，古代常用。编码术，将载荷信息的信号进行各种变换使它们不为非授权者所理解。 在利用现代通讯工具的条件下，隐写术受到很大限制，但编码术却以计算机为工具取得了很大的发展。 信息论基础B信息论基础B信息论基础B信息论基础B信息论基础B信息论基础B信息论基础BEB DB M C M保障保密性保障真实性 M C MDA EADA EBDB EA M C C C M保密性真实性信息论基础B密码分类密码分类n根据加密明文数据时的加密单位的不同，分为分组密码和序列密码两大类。n分组密码：设M为密码消息，将M分成等长的连续区组M1,M2,，分组的长度一般是几个字符，并且用同一密钥K为各区组加密，即 n序列密码：若将M分成连续的字符或位m1,m2,，并用密钥序列KK1K2的第i个元素给mi加密，即n常用分组密码。 )()()( 21MEMEMECkkkCEMEm Emkkk()()()1212信息论基础B熵概念熵概念n密码系统的安全问题与噪声信道问题进行类比。噪声相当于加密变换，接收的失真消息相当于密文，破译者则可类比于噪声信道中的计算者。 n随机变量的不确定性可以通过给予附加信息而减少。正如前面介绍过条件熵一定小于无条件熵。例如，令X是32位二进制整数并且所有值的出现概率都相等，则X的熵H(X)32比特。假设已经知道X是偶数，那么熵就减少了一位，因为X的最低位肯定是零。 信息论基础B疑义度疑义度 n对于给定密文，密钥的疑义度可表示为n对于给定密文，明文的疑义度可表示为 jijijijckpckpcpCKH)/(log)/()()/(2jijijijcmpcmpcpCMH)/(log)/()()/(2信息论基础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/MC)（M和和K交换）交换） H(M/C) （熵值（熵值H(K/MC)总是大于等于零）总是大于等于零）H(M/CK)0，上式得上式得 H(K/C) H(M/C)即已知密文后，即已知密文后，密钥的疑义度总是大于等于明文的疑义密钥的疑义度总是大于等于明文的疑义度度。我们可以这样来理解，由于可能存在多种密钥把一。我们可以这样来理解，由于可能存在多种密钥把一个明文消息个明文消息M加密成相同的密文消息加密成相同的密文消息C，即满足，即满足的的K值不止一个。但用同一个密钥对不同明文加密而得值不止一个。但用同一个密钥对不同明文加密而得到相同的密文则较困难。到相同的密文则较困难。)(MECK信息论基础B又因为又因为 H(K) H(K/C) H(M/C)，则则 上上式说明，式说明，保密系统的密钥量越少，保密系统的密钥量越少，密钥熵密钥熵H(K)就越小，其密文中含有的关于就越小，其密文中含有的关于明文的信息量明文的信息量I(M;C)就越大就越大。至于破译者。至于破译者能否有效地提取出来，则是另外的问题了。能否有效地提取出来，则是另外的问题了。作为系统设计者，自然要选择有足够多的作为系统设计者，自然要选择有足够多的密钥量才行。密钥量才行。 )()()/()();(KHMHCMHMHCMI信息论基础B7.2 数据加密标准数据加密标准DES 1977年7月美国国家标准局公布了采纳IBM公司设计的方案作为非机密数据的正式数据加密标准（DESData Encryption Standard）。DES密码是一种采用传统加密方法的区组密码，它的算法是对称的，既可用于加密又可用于解密。 信息论基础B7.2.1 换位和替代密码换位和替代密码 n换位密码：对数据中的字符或更小的单位（如位）重新组织，但并不改变它们本身。n替代密码：改变数据中的字符，但不改变它们之间的相对位置。 信息论基础B P盒 0 15 15 0 0 14 14 0 0 13 13 0 0 12 12 0输 0 11 11 0 输 0 10 10 0入 0 9 9 0 出 0 8 8 0数 0 7 7 0 数 0 6 6 0据 0 5 5 1 据 0 4 4 0 0 3 3 0 0 2 2 0 1 1 1 0输入第i位输出第j位151413121110987654321741210152111914638135换位盒(P盒) 信息论基础BS盒n=3 2n=8 2n=8 0 00 1 1 1 2 21 3 3 1 4 41 5 5 1 6 6 7 7输入输出000001010011100101110111101010100111000110011001替代盒（S盒） 信息论基础B 0 P s P s P s P 0 0 1 0 0 0 0输 0 s s s 0 输 0 1入 0 1 出 0 s s s 1数 0 1 数 0 0据 0 s s s 0 据 0 0 0 1 0 s s s 1 1 0 P盒和S盒的结合使用 信息论基础B7.2.2 DES密码算法密码算法 nDES密码就是在上述换位和替代密码的基础上密码就是在上述换位和替代密码的基础上发展的。发展的。n将输入明文序列分成区组，每组将输入明文序列分成区组，每组64比特。比特。 n64比特的密钥源循环移位产生比特的密钥源循环移位产生16个子密钥个子密钥Kk kk1264信息论基础B 64 64 64 16 次 64 48 64 输入 初始置换 IP 密码运算 逆置换 输出 子密钥 密钥源 64 32 32 L0 R0 K1 f L1R0 R1L0 f(R0，K1) K2 f L2R1 R2L1 f(R1，K2) Kn f L15R14 R15L14 f(R14，K15) K16 f L16R15 R16L15 f(R15，K16) 64 图 7-7 密码运算 Ri-1(32) 密钥(64) E 密钥表 48比特 Ki(48) S1 S2 S3 S8 P 32比特 图7-8 密码计算函数f(R，K) 密钥 64 置换选择 1 28 28 C0 D0 左移 左移 C1 D1 48 置换选择 2 K1 左移 左移 Cn Dn 48 置换选择 2 Kn 左移 左移 C16 D16 48 置换选择 2 K16 密钥表计算信息论基础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(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密码的改进密码的改进 尽管DES算法十分复杂，但它基本上还是采用64比特字符的单字母表替换密码。当同样的64比特明文块进入编码器后，得到的是同样的64比特的密文块。破译者可利用这个性质来破译DES。 改进方法：密码块链接、密码反馈方改进方法：密码块链接、密码反馈方式式信息论基础B密码块链接 M1 M2 M3 M4 C1 C2 C3 C4 V # # # # 密钥 D D D D 解密箱 加密箱密钥 E E E E V # # # # 异或 C1 C2 C3 C4 M1 M2 M3 M4 (a) (b)信息论基础B 64位移位寄存器 64位移位寄存器 C2 C3 C4 C5 C6 C7 C8 C9 C2 C3 C4 C5 C6 C7 C8 C9 64 8 密钥 E 加密箱 C10 密钥 E 加密箱 C10 选择最左字节 选择最左字节 8 M10 # C10 C10 # M10 8 (a) (b)密码反馈方式信息论基础B7.3 公开密钥加密法公开密钥加密法 n前面介绍的秘密密钥加密法，算法公开，密钥是保密的（对称密钥）。n如果要进行通信，必须在这之前把密钥通过非常可靠的方式分配给所有接收者，这在某些场合是很难做到的。n因而提出了公开密钥加密法PKC（Public Key Cryptography）信息论基础B密密 钥钥n使用两个不同密钥（非对称密钥体制）；n一个公开(公钥)，另一个为用户专用(私钥)；n通信双方无需事先交换密钥就可进行保密通信；n要从公钥或密文分析出明文或私钥，在计算上是不可能的。信息论基础B应应 用用n保密通信： 多个用户将信息传给某用户，可用该用户的公钥加密，唯有该用户可用自己的私钥解读。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)。 信息论基础B7.4.1 公开密钥密码体制公开密钥密码体制 保密通信保密通信 公开加密密钥 秘密解密密钥 B(e，n) B(d，n) A(e，n) A(d，n)B发到A B M fA(e，n) C A A接收B A C fA(d，n) M A发到B A M fB(e，n) C BB接收A B C fB(d，n) M信息论基础B7.4.1 公开密钥密码体制公开密钥密码体制 数字签名数字签名 公开加密密钥 秘密解密密钥 B(e，n) B(d，n) A(e，n) A(d，n)B发到A B M fB(d，n) S fA(e，n) C AA收到B A C fA(d，n) S fB(e，n) M 信息论基础BRSA密码体制（密码体制（1） nRSA由来：RSA体制是根据PKC算法由美国麻省理工学院（MIT）的研究小组提出的，该体制的名称是用了三位作者（Rivest，Shamir和Adleman）英文名字的第一个字母拼合而成。n理论基础：利用数论 正：要求得到两个大素数（如大到100位）的 乘积在计算机上很容易实现。 逆：但要分解两个大素数的乘积在计算上几乎 不可能实现。信息论基础Bn密钥设计：两个密钥：公钥（e，n） 私钥（d，n）n加密解密： 加密时：解密时： RSA密码体制（密码体制（2） )(modnxye)(modnyxd信息论基础Bn实现步骤：q选取两个很大的素数p和q，令模数 q求n的欧拉函数 并从2至(n)1中任选一个数作为加密指数e；q解同余方程 求得解密指数d；q(e，n)即为公开密钥，(d，n)即为秘密密钥。 RSA密码体制（密码体制（3） qpn) 1() 1()(qpn1)()(mod(nde信息论基础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用接收者用接收者B的公开加密密钥的公开加密密钥(eB，nB)再次加密：再次加密：n接收者接收者B用自己的秘密解密密钥用自己的秘密解密密钥(dB，nB)解密：解密：n查发送者查发送者A的公开密钥的公开密钥(dA，nA)计算，恢复出发送者计算，恢复出发送者的签名，认证密文的来源。的签名，认证密文的来源。 (dA，nA) (eB，nB) (dB，nB) (eA，nA) Mi Si S Si Mi 信息论基础B例题数字签名例题数字签名例7-2 用户用户A发送给用户发送给用户B一份密文，用户一份密文，用户A用首字母用首字母B02来签署密文。用户来签署密文。用户A知道下列三个密钥：知道下列三个密钥： A B公开密钥公开密钥(e，n) (7，123) (13，51)秘密密钥秘密密钥(d，n) (23，123)A计算他的签名：计算他的签名：再次加密签名：再次加密签名：8)123(mod8388608)123(mod)02(mod23AdiinMSA26)51(mod885497558138)51(mod8mod13BeinSSB信息论基础B 接收者B必须恢复出02B认证他接收的密文。接收者也知道三个密钥： A B公开密钥(e，n) (7，123) (13，51)秘密密钥(d，n) (5，51)B用户用自己的秘密解密密钥一次解密：再用A用户的公开密钥解密：B用户可以确认：该签名是由A发出用A公钥可解读； 该签名是发给自己的用了B的公钥。例题数字签名（续）例题数字签名（续）8)51(mod11881376)51(mod26mod5BdinSSB2)123(mod2097153)123(mod8mod7AeiinSMA信息论基础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体制多用于密钥交换和认证。
