公钥密码体制的主要思想是通过一种非对称性,即正向计算简单,逆向计算复杂的加密算法设计,来解决安全通信。本文介绍两种在密码学领域内最为人所熟知、应用最为广泛的数学难题——大整数分解问题与离散对数问题
一、大整数分解问题
(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同样是模数。
② 加密算法
发送方使用接收方的公钥对明文进行加密,生成密文
加密过程通常表示为
③ 解密算法
接收方使用自己的私钥对密文进行解密,恢复出明文
解密过程表示为
二、离散对数问题
(1)问题的定义
给定一个有限域 G,以及该域中的一个生成元(或称为基)一个元素 ,离散对数问题可以这样表述:
对于任意给定的G中的非零元素,找到一个整数,使得的次方模上 等于,即
如果这样的 存在,则称 为 相对于基 的离散对数。这里的“离散”一词,是因为群G通常是一个离散集合,而不是连续的。
【注】G称为模 ? 的有限域,其中 ? 必须是一个素数。这样所有加法、减法、乘法和除法运算的结果都会被取模 ? 来确保结果仍然在这个有限域内。
有关离散对数更直观的介绍可以去看可汗学院的视频:The discrete logarithm problem
也有国内搬运的版本:什么是离散的对数问题?
(2)非对称性的体现
- 正向计算容易:计算是非常直接且快速的,可以通过快速幂算法在多项式时间内完成。
- 逆向计算困难:然而,给定?和?,找到?是非常困难的,特别是在?非常大的情况下。目前没有已知的多项式时间算法能够解决这个问题,尽管存在一些算法可以优化搜索过程,但当?足够大时,这些算法仍然需要指数级的时间。
(3)密钥生成与加解密简述
① 密钥生成算法
以ElGamal加密算法为例。
-
选择一个大素数 p 、一个原根 g 和模 p。原根意味着 g 的所有幂次模 p 将遍历所有非零的模 p 的剩余类。
-
选择私钥 ,这是一个小于 的随机整数。
-
计算公钥 ,其中 。
公钥是,而私钥是
② 加密算法
假设 Alice 想要向 Bob 发送一条消息 ,并且 Bob 的公钥是:
-
选择一个随机数 ?,其中 1<?<?−1
-
计算第一个加密分量
-
计算第二个加密分量
加密后的消息是
③ 解密算法
Bob 收到加密消息后,使用他的私钥 来解密:
-
计算中间值
-
计算消息
这里的 是指 ? 在模 ? 下的乘法逆元,也就是说,找到一个数 ?,使得
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » 【密码学】大整数分解问题和离散对数问题
发表评论 取消回复