Recent Posts
RSA 算法证明
RSA 算法证明 RSA 算法是加密学中非常重要的一个算法,具体介绍援引 wiki百科:
RSA加密演算法是一种非对称加密演算法,在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。[1]
1973年,在英国政府通讯总部工作的数学家克利福德·柯克斯(Clifford Cocks)在一个内部文件中提出了一个与之等效的算法,但该算法被列入机密,直到1997年才得到公开。[2]
對极大整数做因数分解的難度決定了 RSA 算法的可靠性。換言之,對一极大整数做因数分解愈困难,RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话,那么用 RSA 加密的信息的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 钥匙才可能被强力方式破解。到2020年为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被破解的。
我在网上找了很多关于 RSA 算法的证明,但总是有某几个步骤语焉不详,花费了一些精力之后,终于搞懂了,因此记录一下。
RSA 用到的几个数学概念: 在进行 RSA 算法证明之前,我们先介绍几个数学概念:
模反元素:如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1,即ab ≡ 1 (mod n) φ(n):小于n且与n互质的正整数的个数,比如φ(10) = 4,因为小于10且与10互质的的数为1,3,7,9 欧拉定理:m和n互质,则m^φ(n) ≡ 1 (mod n) 欧拉函数:如果n为质数,φ(n)=n-1 欧拉函数是积性函数:若m,n互质, φ(mxn)=(m-1)(n-1) 同余性质: 1).反身性:a≡a (mod n); 2).对称性:若a≡b(mod n),则b≡a (mod n); 3).传递性:若a≡b(mod n),b≡c(mod n),则a≡c(mod n); 4).同余式相加:若a≡b(mod n),c≡d(mod n),则a+c≡b+d(mod n); 5).同余式相乘:若a≡b(mod n),c≡d(mod n),则axc≡bxd(mod n)。(特殊情况c=d下也成立) 6).幂运算:如果a≡b(mod n),那么a^k≡b^k(mod n); 以上都是已经被证明的数学定律,由于篇幅以及智商(占主要)原因,本篇不研究其证明过程,直接拿来使用。
read more