《编码引论复习---密码及信道编码》由会员分享，可在线阅读，更多相关《编码引论复习---密码及信道编码（13页珍藏版）》请在金锄头文库上搜索。
1、编码引论复习编码引论复习-密码及信道编码密码及信道编码密码基本方法及对称密码信息加密传输系统模型明文 m 加密秘钥 k1 密文 s 信道编码 x 公开信道 y Alice(源）发出 x: s = f(m,k1) x = c(s)安全的要求：-无条件安全，一次一密-计算上安全。破译密码的代价超过密文信息的价值。破译密码的时间超过密文信息的有效生命期密码攻击：密码分析、穷举攻击根据 Eve 知道信息的多少，攻击分类（均假设 Eve 已知加密算法）-维密文攻击-已知明文攻击-选择性明文攻击-选择性密文攻击经典加密机制之一：代换逐字符代换加密密文字符集等于明文字符集密文字符与明文字符的对应关系由秘钥决
2、定凯撒秘法算法：E(m) = m+k mod n密钥：k移位代换密码信源冗余度的影响（定性理解）这里有计算结论：信源压缩是安全通信的重要手段凯撒密码攻击代换可实现的额最大密钥量。单表代换密码。用一个一一映射表，实现逐符号的明文到密文的代换。当符号集大小为 n 时，共有 n!个不同的一一映射表密钥量 n!代换法的不足代换不改变符号集的概率分布代换法不足的克服：。解决思路：-变长代换、类似于信源压缩。 。-多符号定长代换，可以压缩，也可以不压缩。压缩：符号集，或分组长度的压缩。不压缩的考虑是明文组合太多目的：-符号的概率分布更均匀-符号组（组长不等于代换组长）的概率分布更均匀代换的扩展：二元符号的
3、代换：取反，或不取反。多表代换，时变代换：-每个符号的代换表不同，由密钥决定代换表随时间变化的图案-例：二元符号与扰码的疑或-流密码。多符号代换-n 个二元符号构成 2n 元符号-密钥量：(2n)!多符号代换举例：Hill 密码：-明文中 m 个连续符号，代换成密文中 m 个符号-字母符号代换成对应的 0-25 整数值-密钥为 m 行 m 列的 mod26 可逆矩阵 k例：m = 3, C = (c1,c2,c3), P = (p1,p2,p3)加密：C=KPmod26解密：P=K-1 *C mod 26优点：隐藏了单字母的概率特性，此例还隐藏了双字母的概率特性，当然，三字母的概率特性还存在缺
4、点：由于是线性运算，若 Eve 获得足够的密文、明文对，则易破解设英文字母 A,B,C,Z 分别编码为 0，1，2，25。已知采用 m=2 的 Hill 密码，密钥是 Z26 上的一个 2 阶可逆方阵。假设明文FRIDAY 对应的密文为 PQCFKU。求这个密钥 K多表代换举例：。用一个密钥，周期性的用它的字母做密钥。自动生成不重复的密钥词Vigenere 密钥自动生成器密钥前面用一个词，后面用明文的延时版本仍然有一定的概率信息，因为是明文加密明文，如 e 加密 e 的概率明显的高。经典加密机制之二：置换、将一串符号的顺序打乱（按收发约定的规律）、置换的密钥量：L！置换的不足。单纯置换的不足-
5、没有改变字符的统计分布规律-属于线性操作，难以对付选择性明文攻击-令明文中除一个符号外，其它均为 A，依次试验，很快就可以分析出置换表。解决思路：扩散（密码设计的另一个重要要求）-明文的一个符号的变化应能导致密文中大量符号的变化-多符号代换中的 HILL 密码，就是一种扩散置换与代换相结合：常见的对称加密机制数据加密标准 DES 简介高级加密标准 AES 思路简介Feistel 密码结构加密和解密可以共用一套结构，以及一套相同的密钥数据加密标准 DES 简介。多轮迭代。每轮中有置换和代换。每次分组 64 位。左右各 32 位。函数 F 不一定要求可逆。F 应该是非线性的高级加密标准 AES 思
6、路简介。多轮加密。密钥长度：128,192,256bits。分组长度：128（四字，16 字节）。轮数：10,12,14。扩展密钥长度， （轮数+1）*4 字。每一轮的操作：-字节代换：对每个字节，按字节进行可逆变换-行移位：以字节为单位，按列写入 4*4 字节矩阵，各行进行不同的字节级循环移位-列混淆：对上述以字节为单位的矩阵，左乘一个已知矩阵，采用GF（28）上的乘法和加法-轮密钥叠加：用该轮密钥逐比特抑或AES 的几个环节-字节代换：GF(2)上的(8,8)分组码：c=(1+m)G+b-每一组当成一个 GF(256)的符号，共 16 个符号-列写入+行移位+按列取出：GF(28)上的置换
7、（16 个符号的交织）-列混淆：其实就是对每列 4 个符号进行多表代换，这里采用的也是分组码：c=mG。只不过是 GF(28)上的运算。轮密钥叠加： GF(28)上的加法：c=m+k对称密钥：非对称密码公钥密码体 RSA公钥密码的其它应用密钥交换：通过公钥密码体制实现对称密码体制的密钥交换RSA 的数学基础。欧几里得算法。费马定理。费马定理的扩展：欧拉定理辗转相除法求两个数的最大公约数结论一：。任意两个整数 a,b,总可以找到整数 A，B。使 gcb(a,b) = Aa+Bb上述算法得到的解不是唯一解结论二：。特别地，如果 a,b 互素，则存在 A,B 使得Aa+Bb = 1-此时如果 ab，
8、则有-Bb = 1-Aa = Bb = 1mod a-= (B mod a)*b = 1mod a- 即在模 a 加乘运算构成的环中，b 有乘法逆为 B mod a费马定理：表述 1：若 P 为素数，a 是正整数且与 p 互素，则a(p-1) = 1 mod p-意味着，a 可以比 p 大，只要不是 p 的倍数即可。表述 2：若 P 为素数，a 是正整数，则 ap = a mod p-意味着，a 可以比 p 大，且可以使 p 的倍数-若 a 与 p 不互素，则为 p 的倍数，结果均为 0，等式成立-若 a 与 p 互素，可用表述 1 直接推出来-还可以写成 a(p-1)*t+1) = a mo
9、d p-在域的讨论里，一般只考虑小于 p 的整数费马定理证明中的一个推论。当 a=n 时，只有 a mod n 部分起作用-当 a1,a = bq, b 与 n 互素，因此 b(fai(n)+1) = b mod n.分析 n 的所有不同的素因子，p1,p2,p3,.,pm,.q 只能包含这些素因子。其中任一因子 pi,有(pi)(pi(1-1/pi) = 1,因此有 pi(fai(n)+1) = pi mod n.因此有 q(fai(n)+1) = q mod n因此 a(fai(n)+1) = bq（fai(n)+1) = bq mod n = a mod nRSA 算法基本思路：-找到一
10、组合适的正整数 n,e,d-将信息表示成小于 n，大于 1 的一个整数 M-编码算法为：C= Me mod n-解码算法为：M=Cd mod n = (Me mod n)d mod n = M(ed) mod n-将 n 公开，而对 e 和 d 一个公开，另一个保密合适的 n e d.要求，对任意的整数 a 有a(ed) = a mod n.且由 e 和 n 来确定 d 是不可行的RSA 中的 n,e,d.选定两个素数 p,q(保密）。计算 n = pq,并公开 n。求 n 的欧拉函数 fai(n) = fai(pq) = (p-1)(q-1)保密 ？。找一个与 fai(n)互素并小于 fai
11、(n)且大于 1 的整数 e,将 e 公开。算出在模 fai(n)乘运算中 e 的逆 d = e(-1) mod (fai(n) 保密RSA 中用到的数论概念和定理。欧拉函数：fai(n)为小于 n 且与 n 互素的正整数的个数。若 p 为素数，则 fai(p)= p-1.若 p,q 为不相等的素数，n=pq,则fai(n) = (pq-1)-(p-1)-(q-1) = (p-1)(q-1) = fai(p)fai(q)RSA 中的编解码：1 ed = k*fai(n)+1M(ed) = M(k*fai(n)+1) = M mod nM(ed) mod n = MDiffie-Hellman
12、密钥交换基本出发点：离散对数很难计算离散对数。素数 p,按模 p 加乘构成 GF（p),元素为 0 到 p-1 的整数。选取本原元 a,它的级等于非零元个数 p-1,因此可以用 a 的不同幂次代表所有非零元：a0,a1,a2,.,a(p-2)。任意小于 p 的非零整数 b，可以找到唯一的 i 使得 b = ai.称指数 i 为 b 以 a 为底的模 p 离散对数。注意：以上运算全是 mod p 运算Diffie-Hellman 密钥交换算法。公开的素数 p 和本原元 a。A 任选一个小于 p 的随机整数 Xa，保持私有，并计算 Ya = a(Xa)发给 B。B 任选一个小于 p 的随机整数 Xb，保持私有，并计算 Yb = a(Xb)发给 A.A 收到 Yb 后，求 K = （Yb）(Xa) = a(XaXb).B 收到 Ya 后，求 K= （Ya)(Xb) = a(XaXb)。以上运算全是模 p 运算
