RSA算法.ppt

数据加密与PKI技术第11周数据加密涉及算法复习课 2 2020年2月15日星期六 学习目标 理解凯撒密码与Playfair等古典替换密码掌握DES加密中的IP置换与S盒变换掌握欧几里德最大公因子算法灵活运用费马定理与欧拉定理理解RSA加解密算法理解背包密码体制掌握Diffie Hellman密钥交换计算理解Elgamal算法与DSA算法 3 2020年2月15日星期六 古典密码学作业 1 恺撒与安东尼要举行一个秘密会议 他写了一个密信 ULEHU 请问地点在什么地方 并写出推导出它的数学求解式 写一个就可以了 答 M C K mod26 M 20 3 mod26 17 R 同理其他字母可解 明文 RIBER2 截获了一封密信 已知是恺撒变形密信 并知道了两对明文和相应的密文字母 求解K 并写出数学求解式 明文是 vy 密文是AD 答 k c m mod26 k 0 21 mod26 5 3 用playfair密码加密 Iseeaplane 这句话 密钥就是playfair 答 先将明文两个字母分一组 isexeaplanex C cnkuhplapqku4 用Vigen re密码加密hereishowitw 这些字母 密钥是 V 21 E 4 C 2 T 19 O 14 R 17 注意全部忽略空格和标点符号 答 根据规则将密钥重复 每个字母相当于凯撒加密 C citxwjcsybtn 4 2020年2月15日星期六 Caesar密码表 例2 1恺撒 Caesar 密码是k 3的情况 即通过简单的向右移动源字母表3个字母则形成如下代换字母表若明文为 pleaseconfirmreceipt则密文为 SOHDVEFRQILUPUHFHLSW 5 2020年2月15日星期六 Playfair密码体制 Playfair密码表 12345 12345 该密码体制的密钥是一个单词 比如playfair 将单词中后面重复的字母去掉 只保留不相同的字母 得到playfir 将剩下的字母排列成5 5矩阵的起始部分 矩阵的剩余部分则用26个字母表中未出现的字母填充 并将i与j作为一个字母对待 原因 6 2020年2月15日星期六 各种各样的移位密码是在16世纪发明的 它们大多数来自于Vigen re方法 它是法国密码学家维吉尼亚于1586年提出一种多表替换密码 但是就加密性而言 Vigen re密码体制更复杂和高级 直到20世纪初 这种加密体制在很多地方仍然被认为是安全的 虽然早在19世纪 Babbage和Kasiski就展示了如何攻击它们 在1920年 由Fridman开发了另外一种加密方法 打破了Vigen re及其相关的密码方法 第一步 这个加密的密钥是一个向量 按如下方式选择 首先 确定一个密钥长度 如6 然后从0 25个整数中选择元素项满足这个长度的向量 如k 21 4 2 19 14 17 将其称为向量 这样 系统的安全性所依赖的就是既不能知道密钥内容也不能得知其长度 Vigen re密码 7 2020年2月15日星期六 Vigen re密码 第二步 下面所举的例子就是利用k来加密信息 首先 取明文的第1个字母并将之移21位 然后将第2个字母移4位 第3个字母移2位等等 一旦得到了密钥的结尾 又从头开始 这样第7个字母又移位21位 第8个字母移4位等等 加密过程的密码流程表如下 明文 hereishowitworks 密钥 21421914172142191417214219 密文 CITXWJCSYBHNJVML这样对于这么一段明文就可以用Vigen re完全进行加密了 注意这里没有一个字母的频率比其他大很多 这是因为e在加密的过程中扩散成了几个字母的缘故 8 2020年2月15日星期六 其中Mi是二元数字 为 M58M50M42M34M26M18M10M2M60M52M44M36M28M20M12M4M62M54M46M38M30M22M14M6M64M56M48M40M32M24M16M8M57M49M41M33M25M17M9M1M59M51M43M35M27M19M11M3M61M53M45M37M29M21M13M5M63M55M47M39M31M23M15M7如果再取逆初始置换Y IP 1 X IP 1 IP M 可以看出 M各位的初始顺序将被恢复 9 2020年2月15日星期六 求IP逆置换 例如求矩阵 1的逆 即为 427918635 10 2020年2月15日星期六 图1函数F R K 的计算过程 S盒变换 11 2020年2月15日星期六 F中的代换由8个S盒组成 每个S盒的输入长为6比特 输出长为4比特 其变换关系由表2 7定义 每个S盒给出了4个代换 由一个表的4行给出 对每个盒Si 其6比特输入中 第1个和第6个比特形成一个2位二进制数 用来选择Si的4个代换中的一个 6比特输入中 中间4位用来选择列 行和列选定后 得到其交叉位置的十进制数 将这个数表示为4位二进制数即得这一S盒的输出 例如 S1的输入为011001 行选为01 即第1行 列选为1100 即第12列 行列交叉位置的数为9 其4位二进制表示为1001 所以S1的输出为1001 12 2020年2月15日星期六 费尔玛定理和欧拉定理 费尔玛 Fermat 定理和欧拉 Euler 定理在公钥密码体制中起着重要作用 1 费尔玛定理定理4 2 Fermat 若p是素数 a是正整数且gcd a p 1 则ap 1 1modp Fermat定理也可写成如下形式 设p是素数 a是任一正整数 则ap amodp 13 2020年2月15日星期六 2 欧拉函数设n是一正整数 小于n且与n互素的正整数的个数称为n的欧拉函数 记为 n 例如 6 2 7 6 8 4 若n是素数 则显然有 n n 1 例如 由21 3 7 得 21 3 7 2 6 12 14 2020年2月15日星期六 定理4 3若n是两个素数p和q的乘积 则 n p q p 1 q 1 3 欧拉定理定理4 4 Euler 若a和n互素 则a n 1modn 15 2020年2月15日星期六 欧几里得算法 欧几里得 Euclid 算法是数论中的一个基本技术 是求两个正整数的最大公因子的简化过程 而推广的Euclid算法不仅可求两个正整数的最大公因子 而且当两个正整数互素时 还可求出其中一个数关于另一个数的乘法逆元 16 2020年2月15日星期六 1 求最大公因子Euclid算法是基于下面一个基本结论 对任意非负整数a和正整数b 有gcd a b gcd b amodb 例如 gcd 55 22 gcd 22 55mod22 gcd 22 11 gcd 11 0 11 在求两个数的最大公因子时 可重复使用以上结论 例如 gcd 18 12 gcd 12 6 gcd 6 0 6 gcd 11 10 gcd 10 1 gcd 1 0 1 17 2020年2月15日星期六 例1求gcd 1970 1066 1970 1 1066 904 gcd 1066 904 1066 1 904 162 gcd 904 162 904 5 162 94 gcd 162 94 162 1 94 68 gcd 94 68 94 1 68 26 gcd 68 26 68 2 26 16 gcd 26 16 26 1 16 10 gcd 16 10 16 1 10 6 gcd 10 6 10 1 6 4 gcd 6 4 6 1 4 2 gcd 4 2 4 2 2 0 gcd 2 0 因此gcd 1970 1066 2 18 2020年2月15日星期六 1 密钥的产生 选两个保密的大素数p和q 各100 200位十进制数字 计算n p q n p 1 q 1 其中 n 是n的欧拉函数值 选一整数e 满足1 e n 且gcd n e 1 计算d 满足d e 1mod n 即d是e在模 n 下的乘法逆元 因e与 n 互素 由模运算可知 它的乘法逆元一定存在 以 e n 为公开钥 d n 为秘密钥 算法描述 19 2020年2月15日星期六 2 加密加密时首先将明文比特串分组 使得每个分组对应的十进制数小于n 即分组长度小于log2n 然后对每个明文分组m 作加密运算 c memodn3 解密对密文分组的解密运算为 m cdmodn 20 2020年2月15日星期六 例2 选p 7 q 17 求n p q 119 n p 1 q 1 96 取e 5 满足1 e n 且gcd n e 1 确定满足d e 1mod96且小于96的d 因为77 5 385 4 96 1 所以d为77 因此公开钥为 5 119 秘密钥为 77 119 设明文m 19 则由加密过程得密文为c 195mod119 2476099mod119 66解密为6677mod119 19 21 2020年2月15日星期六 例题3 已知明文m 14 pk 3 55 求密文c和私钥sk分别为多少 解 因为n 55 5 11 所以p 5 或11 q 11 或者5 p 1 q 1 40 e dmod40 1 d e 1 27C memodn 143mod55 49 22 2020年2月15日星期六 RSA算法中的计算问题 1 RSA的加密与解密过程RSA的加密 解密过程都为求一个整数的整数次幂 再取模 如果按其含义直接计算 则中间结果非常大 有可能超出计算机所允许的整数取值范围 如上例中解密运算6677mod119 先求6677再取模 则中间结果就已远远超出了计算机允许的整数取值范围 而用模运算的性质 a b modn amodn bmodn modn就可减小中间结果 23 2020年2月15日星期六 再者 考虑如何提高加 解密运算中指数运算的有效性 例如求x16 直接计算的话需做15次乘法 然而如果重复对每个部分结果做平方运算即求x x2 x4 x8 x16则只需4次乘法 求am可如下进行 其中a m是正整数 将m表示为二进制形式bkbk 1 b0 即m bk2k bk 12k 1 b12 b0因此 24 2020年2月15日星期六 例4求7560mod561 将560表示为1000110000 算法的中间结果如表所示 所以7560mod561 1 25 2020年2月15日星期六 背包密码体制 例5 A 1 3 5 11 21 44 87 175 349 701 是一超递增背包向量 取k 1590 t 43 gcd 43 1590 1 得B 43 129 215 473 903 302 561 1165 697 1523 在得到B后 对明文分组x x1x2 xn 的加密运算为c f x B Bx t A Bxmodk对单向函数f x t t 1和k可作为其秘密的陷门信息 即解密密钥 解密时首先由s t 1cmodk 求出s作为超递增背包向量A的容积 再解背包问题即得x x1x2 xn 这是因为t 1cmodk t 1tABxmodk ABxmodk 而由k ai 知ABx k 所以t 1cmodk ABx 是惟一的 26 2020年2月15日星期六 例6接例5 A 1 3 5 11 21 44 87 175 349 701 是一超递增背包向量 k 1590 t 43 得t 1 37mod1590 设用户收到的密文是 2942 3584 903 3326 215 2817 2629 819 由37 2942 734mod1590 37 3584 638mod1590 37 903 21mod1590 37 3326 632mod1590 37 215 5mod1590 37 2817 879mod1590 37 2629 283mod1590 37 819 93mod1590 得 734 638 21 632 5 879 283 93 27 2020年2月15日星期六 取s 734 由734 701 得x10 1 令s 734 701 33 由33 349 得x9 0 重复该过程得第一个明文分组是1001100001 它对应的英文文本是SA 类似地得其他明文分组 解密结果为SAUNAANDHEALTH 28 2020年2月15日星期六 Diffie Hellman密钥交换是W Diffie和M Hellman于1976年提出的第一个公钥密码算法 已在很多商业产品中得以应用 算法的惟一目的是使得两个用户能够安全地交换密钥 得到一个共享的会话密钥 算法本身不能用于加 解密 算法的安全性基于求离散对数的困难性 Diffie Hellman密钥交换 29 2020年2月15日星期六 图2表示Diffie Hellman密钥交换过程 其中p是大素数 a是p的本原根 p和a作为公开的全程元素 用户A选择一保密的随机整数XA 并将YA aXAmodp发送给用户B 类似地 用户B选择一保密的随机整数XB 并将YB aXBmodp发送给用户A 然后A和B分别由K YB XAmodp和K YA XBmodp计算出的就是共享密钥 这是因为 YB XAmodp aXBmodp XAmodp aXB XAmodp aXBXAmodp aXA XBmodp aXAmodp XBmodp YA XBmodp 30 2020年2月15日星期六 图2Diffie Hellman密钥交换 31 2020年2月15日星期六 因XA XB是保密的 敌手只能得到p a YA YB 要想得到K 则必须得到XA XB中的一个 这意味着需要求离散对数 因此敌手求K是不可行的 例如 p 97 a 5 A和B分别秘密选XA 36 XB 58 并分别计算YA 536mod97 50 YB 558mod97 44 在交换YA YB后 分别计算K YB XAmod97 4436mod97 75 K YA XBmod97 5058mod97 75 32 2020年2月15日星期六 Elgamal算法 密钥对产生办法 首先选择一个素数p 两个随机数 g和x g与x p 计算y gx modp 则其公钥为y g和p 私钥是x 其中g和p可由一组用户共享 ElGamal用于数字签名 被签信息为M 首先选择一个随机数k k与p 1互质 计算a gk modp 再用扩展Euclidean算法对下面方程求解b M xa kb modp 1 实际用b yk Mmodp签名就是 a b 随机数k须丢弃 验证时要验证下式 ya ab modp gM modp 同时一定要检验是否满足1 a p 否则签名容易伪造 33 2020年2月15日星期六 ElGamal用于加密 被加密信息为M 首先选择一个随机数k k与p 1互质 计算a gk modp b ykM modp a b 为密文 是明文的两倍长 解密时计算M b ax modp b ax 1modp 34 2020年2月15日星期六 例题 鲍勃把11选择为p 然后他选择g e1 2 他再选择x d 3并且计算出y e2 e1d 8 所以公钥就是 g y p 2 8 11 私钥是x 3 爱丽丝选择k r 4并且计算出明文7的C1和C2 鲍勃收到密文c a 5和b 6 并且计算出明文 35 2020年2月15日星期六 我们不用P C2 C1d 1 modp解密 就可以避免乘法逆元的计算并且还可以运用P C2 C1 p 1 d modp 在例10 10中 我们可以算出P 6 5 11 1 3 mod11 7mod11 36 2020年2月15日星期六 DSA算法 DigitalSignatureAlgorithm DSA 是Schnorr和ElGamal签名算法的变种 被美国NIST作为DSS DigitalSignatureStandard 数字签名标准 DSS是由美国国家标准化研究院和国家安全局共同开发的 由于它是由美国政府颁布实施的 主要用于与美国政府做生意的公司 其他公司则较少使用 而且美国政府不提倡使用任何削弱政府窃听能力的加密软件 算法中应用了下述参数 p Lbits长的素数 L是64的倍数 范围是512到1024 q 是p 1的160bits的素因子 g g h p 1 q modp h满足h1 x 为秘密密钥 正整数 x q y y g xmodp p q g y 为公钥 k为随机数 0 k q H x One WayHash函数 注 为幂运算符 37 2020年2月15日星期六 签名过程 DSA中选用SHA SecureHashAlgorithm p q g可由一组用户共享 y是公开钥 x是私钥 签名过程如下 1 产生随机数k k q 2 计算r g kmodp modqs k 1 H m xr modqr s即签名结果 38 2020年2月15日星期六 验证过程 验证过程 签名结果是 m r s 3 验证时计算