数论概论读书笔记 18.幂、根与不可破密码

幂、根与不可破密码

前面我们已经了解了k次幂和k次根。

对于一个同余式xk≡b( mod m)$x^k\equiv b(modm)$ ，如果我们知道了k,b,m 且b和m互质，k和φ(m)$\phi (m)$互质，则可求出解x

这里求解φ(m)$\phi (m)$ 是关键。即要对m$m$进行分解。这是设计许多密码的基础。

首先选取两个大素数p,q$p,q$ ，接下来将它们相乘得到模m=pq$m=pq$ ，计算φ(m)=φ(p)φ(q)=(p−1)(q−1)$\phi (m)=\phi (p)\phi (q)=(p-1)(q-1)$

再选取一个和φ(m)$\phi (m)$互素的整数k$k$

现在我们向全宇宙公开数m$m$和k$k$，用m$m$和k$k$对信息进行加密。

例如对于一个百万级的数m$m$，可将信息写成6位数的表，信息数是a1,a2,...,ar$a_1,a_2,...,a_r$，下一步，使用逐次平方法(快速幂)计算ak1( mod m),...,akr( mod m)$a_1^k(modm),...,a_r^k(modm)$ ，这些值记为b1,b2,...,br$b_1,b_2,...,b_r$ ，作为传输的数据。

有了b表如何求a表呢？即上一节所讨论的问题。即完成了加密和解密。

上面的加密方案的思想是很简单的一种：容易将两个大数乘起来，但是，很难将大数分解因数。

上述密码学方法称为公钥密码*，由模m和指数k组成的加***可公布于众，而解密方法是安全的。本节的思想称为RSA公钥密码*。