【密码学】大整数分解问题和离散对数问题

        公钥密码体制的主要思想是通过一种非对称性，即正向计算简单，逆向计算复杂的加密算法设计，来解决安全通信。本文介绍两种在密码学领域内最为人所熟知、应用最为广泛的数学难题——大整数分解问题与离散对数问题

一、大整数分解问题

（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加密算法为例。

1. 选择一个大素数 p 、一个原根 g 和模 p。原根意味着 g 的所有幂次模 p 将遍历所有非零的模 p 的剩余类。

2. 选择私钥 ，这是一个小于 的随机整数。

3. 计算公钥 ，其中 。

公钥是，而私钥是

② 加密算法

假设 Alice 想要向 Bob 发送一条消息 ，并且 Bob 的公钥是：

1. 选择一个随机数 𝑘，其中 1<𝑘<𝑝−1

2. 计算第一个加密分量 

3. 计算第二个加密分量

加密后的消息是

③ 解密算法

Bob 收到加密消息后，使用他的私钥  来解密：

1. 计算中间值 

2. 计算消息 

这里的 是指 𝑠 在模 𝑝 下的乘法逆元，也就是说，找到一个数 𝑧，使得