数论概论读书笔记 18.幂、根与不可破密码
幂、根与不可破密码
前面我们已经了解了k次幂和k次根。
对于一个同余式 ,如果我们知道了k,b,m 且b和m互质,k和互质,则可求出解x
这里求解 是关键。即要对进行分解。这是设计许多密码的基础。
首先选取两个大素数 ,接下来将它们相乘得到模 ,计算
再选取一个和互素的整数
现在我们向全宇宙公开数和,用和对信息进行加密。
例如对于一个百万级的数,可将信息写成6位数的表,信息数是,下一步,使用逐次平方法(快速幂)计算 ,这些值记为 ,作为传输的数据。
有了b表如何求a表呢?即上一节所讨论的问题。即完成了加密和解密。
上面的加密方案的思想是很简单的一种:容易将两个大数乘起来,但是,很难将大数分解因数。
上述密码学方法称为公钥密码*,由模m和指数k组成的加***可公布于众,而解密方法是安全的。本节的思想称为RSA公钥密码*。