RSA算法的应用 实现RSA算法体系要做的工作 ■不可抵赖性:Aice发信给Bob,如何保证 m大整数的表示 Bob有充分的理由证明此信是Ace发出而不是 m如何任意选取两个大素数(512、1024甚至2048位的 他人?任何人包括Aice不能否认这是Ace发出 素数)? 的信息 蓬定要是·一数试覓以舒证以足够大的概 ■大整数的加法运算和模加运算 ■大整数的乘法运算和模乘运算 Divide and Conquer可以得到on3)复杂度的乘法 ■幂乘算法的实现 清手大学城想 RSA及其它加密算法的克星 密码系统需要防范的攻击 ■干草堆里找针(大海捞针) Find a needle in a stack of hay,量子计算机可以在sqrt(n)的时间 1.监听与分析 2伪造其中一方(服务器或客户端) 内找到n个散乱数字中的某一个 3.代理(在线路中伪造双方) ■大海捞针:大海里有一根针,需要判断它存在 的位置,如果你有一个具有魔法的吸铁石,可 窜改 以在一秒内判断任何区域内有没有针,则你可 5.重放 以在非常短的时间内把针找到! 综合 ■非确定图灵机可以做到这一点 手大学想 密码系统要考虑的问题 安全协议介绍 ■随机数 ■如何利用对称加密系统实现安全通话: ■哈希函数 设k是双方共享的秘密,可以利用此实现抗击前 ■对称加密算法 面提到的各种攻击 ■非对称加密算法 Alice:生成随机数r1,「2,发送 ■密码协议 (r1,des(k,n2))给Bob Bob:生成随机数r3,r4,发送 (r3,des(k,r4))给Aice 大学证制6 清华大学 宋斌恒 31 RSA算法的应用 „ 不可抵赖性：Alice 发信给 Bob，如何保证 Bob有充分的理由证明此信是Alice发出而不是 他人？任何人包括Alice不能否认这是Alice发出 的信息。 清华大学 宋斌恒 32 实现RSA算法体系要做的工作 „ 大整数的表示 „ 如何任意选取两个大素数（512、1024甚至2048位的 素数）？ „ 没有直接方法可用，利用测试法可以保证以足够大的概 率保证选定的数是一个素数，参见p887.- „ 大整数的加法运算和模加运算 „ 大整数的乘法运算和模乘运算 „ Divide and Conquer 可以得到O(nlg 3 )复杂度的乘法 „ 幂乘算法的实现。 清华大学 宋斌恒 33 RSA及其它加密算法的克星 „ 干草堆里找针（大海捞针）Find a needle in a stack of hay, 量子计算机可以在sqrt(n)的时间 内找到n个散乱数字中的某一个。 „ 大海捞针：大海里有一根针，需要判断它存在 的位置，如果你有一个具有魔法的吸铁石，可 以在一秒内判断任何区域内有没有针，则你可 以在非常短的时间内把针找到！ „ 非确定图灵机可以做到这一点 清华大学 宋斌恒 34 密码系统需要防范的攻击 1. 监听与分析 2. 伪造其中一方（服务器或客户端） 3. 代理（在线路中伪造双方） 4. 窜改 5. 重放 6. 综合 清华大学 宋斌恒 35 密码系统要考虑的问题 „ 随机数 „ 哈希函数 „ 对称加密算法 „ 非对称加密算法 „ 密码协议 清华大学 宋斌恒 36 安全协议介绍 „ 如何利用对称加密系统实现安全通话： „ 设k是双方共享的秘密，可以利用此实现抗击前 面提到的各种攻击： „ Alice：生成随机数r1，r2，发送 (r1，des（k，r2））给Bob „ Bob：生成随机数r3，r4，发送 (r3，des（k，r4））给Alice