4.7 RSA公钥密码

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

密码模型把明文 经带密钥的变换 变成密文 ,再由解密变换 恢复。正确性要求在允许的消息集合上 ;安全性是另外的问题,不能由“可逆”本身推出。

教材先给出凯撒移位:把a至z编码为0至25,,。 时,把“take action at middle night”去掉空格后加密为“wdnhdfwlrqdwplggohqljkw”。明文编码依次为19、0、10、4、0、2、19、8、14、13、0、19、12、8、3、3、11、4、13、8、6、7、19;密文编码依次为22、3、13、7、3、5、22、11、17、16、3、22、15、11、6、6、14、7、16、11、9、10、22。

仿射替换推广为 ,必须要求 才能在26个字母上成为双射。维吉尼亚方法对一段 使用密钥段 ,逐位取 。这些传统方法说明单字母或多字母替换的区别,并不代表简单替换已能提供现代保密通信。

对称密码的通信双方共享秘密密钥,传递、保存和更新密钥是重要问题。若 个用户两两使用不同共享密钥,共需 对通信密钥。公钥密码将可公开的加密信息与应保密的解密信息区分开,教材由此引出RSA;公钥可公开不等于可以不验证它属于谁。

RSA取两个不同素数 ,令 。选正整数 与 互素,求正整数 使 。公钥为 ; 及素因子等保密。把消息编码成 的整数块,按教材的基本数学模型计算

指数必须取正,消息必须限制在一个规范剩余类代表范围。数值解密恢复的是整数块,随后还要按既定编码还原字符;固定两位字符编码中的前导0不能随意丢掉。

正确性证明:。若 ,由欧拉定理直接得到 。若不互素,不应漏掉 ;更统一的办法是分别模 和模 考察:当素数整除 时,两边均为0;不整除时,由费马小定理及 都整除 ,仍得 。因此差值同时被互素的 整除,便被 整除,证明覆盖全部 。

模幂不必先算巨大整数再取余。把指数写作 ,,先取 ,再逐次平方 ,将所有 的 相乘并随时取余。只需与二进位数同阶的平方、乘法步骤; 的结果按模幂约定为 。选择有符号的同余代表也可以,但最后应恢复为0至 的规范输出。

【例4.7.1】,a至z编码为00至25,每字符占两位。加密明文块2106,再解密另一个密文块0981。

解:。对2106连续平方并使用同余代表,得到 ,,,。选第0、2、3项相乘,得 ,故密文为2321。2106是字符21、06,即“vg”。

求逆得到 ,所以 ,二进制为1110101001,即 。从981起连续平方,教材选用的代表依次为 。取第0、3、5、7、8、9项相乘并取模,得到 。恢复四位块为0704,按07、04解码为“he”。这里解密的是0981,不是前面加密所得2321,两个示范不能误配成同一明密文对。

已知 就可计算欧拉函数并求私钥,所以整数分解能用来破解这一RSA模型;不能把RSA求逆与整数分解的一般困难性未经证明便说成严格等价。教材的小素数和直接逐块幂运算用于展示数学原理,不能直接作为真实客户数据的加密实现。实际安全性还涉及参数、编码、随机性和实现,不能沿用教材里对具体十进位数及破解年限的历史估计,作为恒定有效的安全结论。