# §03.4_非对称密码算法（Rsa 离散对数）【最且唯一难】 LLMS index: [llms.txt](/wikis/llms.txt) --- ### 离散对数问题 1. 有限域：DSA、ElGamal 2. 椭圆曲线：ECDSA、SM2 ### 加密表达式 通常遵循一些书写规则，以确保清晰和一致性： 1. **变量命名**： - 使用简明且具有描述性的符号，例如 C表示密文，M表示明文，K表示密钥。可以加上下标以指明具体上下文， ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/959ab9b1ca1b3bc5682fdfb1025ab8c0_MD5.png) 。 2. **函数表示**： - 使用清晰的函数表示法 E，以表明这是一个加密操作。保持函数名称简短，便于理解。 3. **括号使用**： - 函数参数使用括号明确区分，确保逻辑清晰。例如，![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/e217822e8f8ee66838d9524663d6c265_MD5.png)中，括号包围了所有输入。 4. **一致性**： - 在整个文档或讨论中保持符号和术语的一致性，以避免混淆。 5. **上下文说明**： - 在首次使用表达式时，最好提供简要说明，以帮助读者理解每个符号的含义。 遵循这些规则有助于确保表达式的可读性和可理解性，使得复杂的密码学概念更易于传达。 ### 素数 不可被“分解”的数， 素数是大于1的自然数，且只能被1和它自身整除。换句话说，素数没有其他的因数。比如，2、3、5、7、11都是素数。最小的素数是2，它也是唯一的偶素数，其余的素数都是奇数。 ### 欧拉函数 ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/c4bbb02b440e4f0cf4cc257732196d1e_MD5.png) ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/37e35bd300604e29f29f81f150aa16fd_MD5.png) ### 乘法逆元 ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/4bf80ce3d3185425afd233e9a2f7a84d_MD5.png) 2与二分之一互为倒数，乘积为1. ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/39a2d15b2753f34d5e898157bd8754fd_MD5.png) ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/c52864898be5455f87b40c342ea56e39_MD5.png) ### 欧几里得算法与同余 ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/b9fb48f05adac12122f471c65c24ee27_MD5.png) ### 求解乘法逆元 ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/94ef5ca083896c8295b449446979edee_MD5.png) ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/967d1af49c9985cdd33f8212a3b69e7e_MD5.png) ### RSA计算 ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/58258d35a52a302c8ede56ce6ea1b09f_MD5.png) ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/987f52c75422e32728e39fc4e3898c9f_MD5.png) ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/fc2f7c09d5b61056b95ab9a43bd339f8_MD5.png) d为整数，n从1开始带入即可 ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/9cebffa1a451374d8ad35d8a30803142_MD5.png) ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/d4961f667a3bec9d72c628a33b95e742_MD5.png) 私钥数字签名 公钥数据加密 ### RSA安全性 ![](/wikis/_resources/%C2%A73.4_%E9%9D%9E%E5%AF%B9%E7%A7%B0%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95%EF%BC%88RSA-%E7%A6%BB%E6%95%A3%E5%AF%B9%E6%95%B0%EF%BC%89%E3%80%90%E6%9C%80%E4%B8%94%E5%94%AF%E4%B8%80%E9%9A%BE%E3%80%91/6903157b3a810ff0bc6a940b5529ab07_MD5.png)