HBC19944[CQOI2016]密钥破解题解

旧巴黎 算法基础篇 52 0
想要检验自己的编程水平?来试试全网最全C++题库,让您在挑战中不断进步。
一种非对称加密算法的密钥生成过程如下: 1. 任选两个不同的质数 p ,q 2. 计算 N=pq , r=(p-1)(q-1) 3. 选取小于r ,且与 r 互质的整数 e 4. 计算整数 d ,使得 ed≡1 mod r 5. 二元组 (N,e) 称为公钥,二元组 (N,d) 称为私钥 当需要加密消息 n 时(假设 n 是一个小于 N 整数,因为任何格式的

一种非对称加密算法的密钥生成过程如下: 1. 任选两个不同的质数 p ,q 2. 计算 N=pq , r=(p-1)(q-1) 3. 选取小于r ,且与 r 互质的整数 e  4. 计算整数 d ,使得 ed≡1 mod r 5. 二元组 (N,e) 称为公钥,二元组 (N,d) 称为私钥  当需要加密消息 n 时(假设 n 是一个小于 N 整数,因为任何格式的消息都可转为整数表示),使用公钥 (N,e),按照 n^e≡c mod N 运算,可得到密文 c 。 对密文 c 解密时,用私钥 (N,d) ,按照 c^d≡n mod N 运算,可得到原文 n 。算法正确性证明省略。 由于用公钥加密的密文仅能用对应的私钥解密,而不能用公钥解密,因此称为非对称加密算法。通常情况下,公钥由消息的接收方公开,而私钥由消息的接收方自己持有。这样任何发送消息的人都可以用公钥对消息加密,而只有消息的接收方自己能够解密消息。 现在,你的任务是寻找一种可行的方法来破解这种加密算法,即根据公钥破解出私钥,并据此解密密文。

HBC19944[CQOI2016]密钥破解题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)

标签: HBC19944[CQOI2016]密钥破解题解