RSA公钥算法的新探讨及改进

【 摘 要 】 众所周知，RSA是唯一一个能够同时实现数据加密、数字签名、秘钥交换的算法。其过程可简述为选取两个大的质数乘积n=p*q（非公开），然后选择一个和?准(n)互质的整数e (其中1

【 关键词 】 RSA, 改进，公钥算法

The Discussion about the Improvement of RSA Algorithm

Wu Ya-ning

（The Computer Science Academy of Nanjing University of Science and Technology Jiangsu Nanjing 210094）

【 Abstract 】 As we all know, RSA is the only Algorithm that can be used in Data Encryption, Digital Signature and Key Distribution collectively. The process of RSA can be briefly summarized into 3 stages. First, select an integer n that is the result of 2 prime numbers’ product (n=p*q, private). Then, select an integer e that is relatively prime to ?准 (n) (1

【 Keywords 】 RSA; Improvement; Public-Key Cryptosystem

1 n取多个质数乘积时的结论及证明

1.1 n取三个质数乘积时的结论

假设n=p*q*r, 我们试着推导欧拉函数?准(n)。

根据?准(n)的定义，我们要求小于n并且和n互质的正整数的个数。考虑到在小于n且和n不互质的所有数中，有的是p的倍数，有的是q的倍数，有的是r的倍数，有的既是p又是q的倍数,有的既是q又是r的倍数，还有的既是r又是p的倍数。为了表示方便，我们用S(x)表示小于n的且是x的倍数的正整数的个数。

?准（n）=pqr-1-(S(p)+S(q)+S(r)-S(pq)-S(qr)-S(rp)+0)

=pqr-1-((pq-1)+(qr-1)+(rp-1)-(p-1)-(q-1)-(r-1)+0)

=pqr-pq-qr-pr+p+q+r-1

=（p-1）(q-1)(r-1)

=?准(p)*?准(q)*?准(r)

可以看出计算结果十分巧，正好是p、q、r欧拉函数的乘积。事实上这绝非巧合。这说明用当n=p*q 时的证明方法也同样适用于上述情况（证明见下面1.1.2）。换言之，此时RSA算法依然成立。

1.2 n取三个质数乘积时RSA的正确性证明

算法变为：

（1）选定p、q、r三个质数 （非公开）

（2）计算n=p*q*r （公开）

（3）选择e使得gcd(?准(n),e)=1; 1

（4）计算de^(-1) （mod?准(n)） (求e的逆元，非公开)

证明目标：M^ed mod n=M (M可以看作明文)

正确性证明：

首先我们证明 M^(k(p-1)(q-1)(r-1)+1) mod p=M mod p --［1］

情况1：若M、p不互质，则质数p能整除M, 显然p也能整除M^(k(p-1)(q-1)(r-1)+1), 那么：M^(k(p-1)(q-1)(r-1)+1) mod p=M mod p＝0

情况2：若p、q互质，根据欧拉定理M^?准(p) mod p=1，有

M^(k(p-1)(q-1)(r-1)+1) mod p

=((M)M^k(p-1)(q-1)(r-1)) mod p

=((M)(M^(p-1))^k(q-1)(r-1)) mod p

=((M)(M^?准(p))^k(q-1)(r-1)) mod p

=(M mod p)*[(M ^?准(p)) mod p]^k(q-1)(r-1)