经典与现代对称加密算法 非对称加密算法 字符移位 ■解决对称加密算法在分布系统中的密钥 ■字符置换 人通讯,需要每个人记载n个密码,秘码 每个人有一个(公钥,私钥)对,其中公 布到任何地方。每个人只需要保存自己的私 利用公钥加密可以用私钥解密,反之亦然 a可以验证信息的发送人 保证只有信息的接收人才能得到消息 清手大学城想 公钥理论 RSA算法 ■理论上要达到以上要求,公钥和私钥是可以互 m取2个不等的大素数pq,如其长度为512【或更 相确定的,即给定公钥可以求出私钥,反 长】位 然,如果给定公钥能求出私钥,那公钥体系岂 计算n=pq 不没有任何意义! 选择较小的奇数e,它和◆n)=(p-1)(q-1)互素 ■问题是:理论上要存在,而实际上不可算,就 计算e在模◆n)下的逆d 能达到目标。 发布(e,n)作为公钥 保存(dn)作为私钥 手大学想 RSA加密算法 RSA被攻击的可能性 n A message m is a number in zn 由于(en)公开,从(e,n)计算dn) m用公钥转换:P(M)=Me(modn) 目前没有发现比分解n=pq更为容易的算法,而 用私钥转换:S(M=M(modn) 因式分解是NPC问题,故目前攻击困难 ■定理:PS(M=SP(M)=M m两次转换的复杂性:如果n的长度是k,则需要lge+lgd 的长度是k的数的乘法,若乘法复杂度为长度的平 方,则整个复杂度为K3。如果k=1024则需要1gga的 运算量。 大学证制5 清华大学 宋斌恒 25 经典与现代对称加密算法 „ 字符移位 „ 字符置换 „ DES „ 双重DES 清华大学 宋斌恒 26 非对称加密算法 „ 解决对称加密算法在分布系统中的密钥管理缺陷：n个 人通讯，需要每个人记载n个密码，秘码存储量总数为 n2。 „ 工作原理：每个人有一个（公钥，私钥）对，其中公 钥可以发布到任何地方。每个人只需要保存自己的私 钥即可，其中要求： „ 利用公钥加密可以用私钥解密，反之亦然， „ 可以验证信息的发送人 „ 保证只有信息的接收人才能得到消息等 清华大学 宋斌恒 27 公钥理论 „ 理论上要达到以上要求，公钥和私钥是可以互 相确定的，即给定公钥可以求出私钥，反之亦 然，如果给定公钥能求出私钥，那公钥体系岂 不没有任何意义！ „ 问题是：理论上要存在，而实际上不可算，就 能达到目标。 清华大学 宋斌恒 28 RSA算法 „ 取2个不等的大素数p,q, 如其长度为512【或更 长】位 „ 计算n=pq „ 选择较小的奇数e，它和φ(n)＝(p-1)(q-1)互素 „ 计算e在模φ(n)下的逆d „ 发布(e,n)作为公钥 „ 保存(d,n)作为私钥 清华大学 宋斌恒 29 RSA加密算法 „ A message m is a number in Zn, „ 用公钥转换：P(M)=Me (mod n) „ 用私钥转换：S (M)=Md (mod n) „ 定理：PS(M)=SP(M)=M „ 两次转换的复杂性：如果n的长度是k，则需要lge＋lgd 次的长度是k的数的乘法，若乘法复杂度为长度的平 方，则整个复杂度为k3。如果k=1024,则需要1 giga的 运算量。 清华大学 宋斌恒 30 RSA被攻击的可能性 „ 由于(e,n) 公开，从(e,n)计算(d,n) „ 目前没有发现比分解n＝pq更为容易的算法，而 因式分解是NPC问题，故目前攻击困难