汝城网站建设公司,获客,广告设计是做什么的,用什么网站做一手楼好公钥密码体制的主要思想是通过一种非对称性#xff0c;即正向计算简单#xff0c;逆向计算复杂的加密算法设计#xff0c;来解决安全通信。本文介绍两种在密码学领域内最为人所熟知、应用最为广泛的数学难题——大整数分解问题与离散对数问题
一、大整数分解问题
#xf… 公钥密码体制的主要思想是通过一种非对称性即正向计算简单逆向计算复杂的加密算法设计来解决安全通信。本文介绍两种在密码学领域内最为人所熟知、应用最为广泛的数学难题——大整数分解问题与离散对数问题
一、大整数分解问题
1问题的定义 假设 是一个合数且 ×其中 和 都是大于1的大质数又叫素数。大整数分解问题的目标是仅给定 找到 和 。更一般地问题是找到所有质数因子而不仅仅局限于两个因子的情况。
【注】质数Prime Number是指在大于1的自然数中除了1和它本身以外不再有其他因数的数。换句话说质数只能被1和它自身整除。例如2、3、5、7、11、13等都是质数。
2非对称性的体现
正向计算容易找到两个大素数并计算它们的乘积是非常简单的。现代计算机可以迅速地找到这样的素数并对它们执行乘法操作。逆向计算困难然而给定来找出它的两个素数因子和是非常困难的。随着的位数增加分解所需的计算资源呈指数级增长。当前的算法在分解大整数时需要耗费大量的时间和计算能力这使得在合理的时间内分解大整数变得不切实际。
3密钥生成与加解密简述
① 密钥生成算法 随机选择两个大素数p和q计算计算欧拉函数选择一个整数e使得1 e φ(N)且e与φ(N)互质计算d作为e关于φ(N)的模逆元即找到d满足de ≡ 1 (mod φ(N))
公钥是(N, e)其中N是模数e是加密指数私钥是(d, N)其中d是解密指数N同样是模数。
② 加密算法
发送方使用接收方的公钥对明文进行加密生成密文
加密过程通常表示为
③ 解密算法
接收方使用自己的私钥对密文进行解密恢复出明文
解密过程表示为 以RSA为例 二、离散对数问题
1问题的定义 给定一个有限域 G以及该域中的一个生成元或称为基一个元素 离散对数问题可以这样表述 对于任意给定的G中的非零元素找到一个整数使得的次方模上 等于即 如果这样的 存在则称 为 相对于基 的离散对数。这里的“离散”一词是因为群G通常是一个离散集合而不是连续的。
【注】G称为模 的有限域其中 必须是一个素数。这样所有加法、减法、乘法和除法运算的结果都会被取模 来确保结果仍然在这个有限域内。
有关离散对数更直观的介绍可以去看可汗学院的视频The discrete logarithm problem
也有国内搬运的版本什么是离散的对数问题
2非对称性的体现
正向计算容易计算是非常直接且快速的可以通过快速幂算法在多项式时间内完成。逆向计算困难然而给定和找到是非常困难的特别是在非常大的情况下。目前没有已知的多项式时间算法能够解决这个问题尽管存在一些算法可以优化搜索过程但当足够大时这些算法仍然需要指数级的时间。
3密钥生成与加解密简述
① 密钥生成算法
以ElGamal加密算法为例。 选择一个大素数 p 、一个原根 g 和模 p。原根意味着 g 的所有幂次模 p 将遍历所有非零的模 p 的剩余类。 选择私钥 这是一个小于 的随机整数。 计算公钥 其中 。
公钥是而私钥是
② 加密算法
假设 Alice 想要向 Bob 发送一条消息 并且 Bob 的公钥是 选择一个随机数 其中 1−1 计算第一个加密分量 计算第二个加密分量
加密后的消息是
③ 解密算法
Bob 收到加密消息后使用他的私钥 来解密 计算中间值 计算消息
这里的 是指 在模 下的乘法逆元也就是说找到一个数 使得
