费马小定理在公钥加密中的应用及原理

痛定思痛。 2021-10-19 08:42 217阅读 0赞

SICP第35页提到[费马小定理][Link 1]在密码学中有很重要的应用, 还没有学过<密码学>这门课, 但我又对加密解密有点兴趣, 决定一探究竟. 费马小定理维基百科里是这么定义的:

> 假如a是一个整数，p是一个素数，那么
> 
> ![2011020521224028.png][]
> 
> 如果a不是p的倍数，这个定理也可以写成
> 
> ![2011020521230874.png][]

但我发现SICP第34页对费马小定理的描述是这样的:

> 如果n是一个素数, a是小于n的任意正整数, 那么a的n次方与a模n同余.

经过我举了几个小例子验证之后, 觉得维基百科的解释更合理一些, SICP里所讲的"a是小于n的任意正整数"可能是为了适合当页所讲的内容"费马检查", 顺便提一下如何检查一个数是否是素数.

# 费马检查 #

> 如果所有符合1 < b < p的*b p*都满足下列条件的话：
> 
> ![2011020521242392.png][], 则*p*必定是一个素数. 实际上没有必要检测所有小于p的正整数, 而仅需测试所有的小于*p*的素数即可.

# 公钥加密是怎么回事 #

想起前一段时间读过的[谈谈密码学的数学原理][Link 2], 这篇文章里面描述了公钥加密的过程:

> 1. 找两个很大的素数（质数）P 和 Q, 越大越好, 比如 100 位长的, 然后计算它们的乘积 N=P×Q, M=(P-1)×(Q-1)  
> 2. 找一个和 M 互素的整数 E, 也就是说 M 和 E 除了 1 以外没有公约数  
> 3. 找一个整数 D, 使得 E×D 除以 M 余 1, 即 E×D mod M = 1  
> 现在, 世界上先进的、最常用的密码系统就设计好了, 其中 E 是公钥谁都可以用来加密, D 是私钥用于解密, 一定要自己保存好. 乘积 N 是公开的, 即使敌人知道了也没关系.  
> 现在, 我们用式子 X^E mod N 对 X 加密得到密码 Y, 破解密文时用式子 Y^D mod N 得到原文X.

这就相当于可以给每个人发一把钥匙(公钥)用于加密数据, 但是解开这段加密数据需要的是另外一把钥匙(私钥).

# 证明过程 #

原文X = Y^D mod N = (X^E mod N)^D mod N, 根据同余定理这个式子等价为: X^(E\*D) mod N = X, 目的就是证明这个式子的正确性.

> 根据费马小定理![2011020521230874.png][], 所以X^(E-1) = 1(mod E),
> 
> 设整数k使得((P-1)(Q-1))k+1=E\*D, 所以X^(E\*D)=X^((P-1)(Q-1)k+1) = X\*X^((P-1)^(Q-1)) = X(mod  P),
> 
> 同理X^(E\*D) = X(mod  Q), 即X^(E\*D) – X能被P\*Q整除,
> 
> 因为N=P\*Q, 所以X^(E\*D) = X(mod N), 即得证.

这个加密解密过程也就是RSA公钥密码的原理.

# 回顾 #

费马检查用于检查一个数是否是素数, 根据这个基本原理, 用来找到一个比现在已知素数还要大的素数, 这样的素数在密码学中有什么用呢? 上面公钥加密过程第一步已经提到需要两个很大的素数构造N, 而一旦破解N是由哪两个素数相乘, 整个公钥加密系统也就没有什么秘密了, 但目前还没有发现求一个数的因子的很好算法, 除非一个个试, 但这需要很漫长的时间, 据说分解一个200位的数就得花上上万年...因此可见位数越多的素数乘积起来, 再进一步构造出来的密码, 要破解它是相当困难的.

转载于:https://www.cnblogs.com/technology/archive/2011/02/04/1949086.html

[Link 1]: http://zh.wikipedia.org/zh-cn/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86
[2011020521224028.png]: /images/20211018/a37ef9ccd3634460a0aff7fec9108145.png
[2011020521230874.png]: /images/20211018/b106a07d77794c75bc1095be8a70e71b.png
[2011020521242392.png]: /images/20211018/4d2fc506812c43b092189931e6e8aaf9.png
[Link 2]: http://www.google.com.hk/ggblog/googlechinablog/2007/09/blog-post_5853.html