3.2.1
RSA算法
RSA是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年共同提出的，并由此三人的名字命名。该算法是具有代表性的基于大整数分解的非对称加密算法。下面通过两部分了解RSA算法：公、私钥参数生成以及加、解密过程。
RSA的公、私钥参数生成过程如下。
-
Step 1：选择大素数
p
和
q
。然后根据
p
和
q
直接计算
n
以及
φ
(
n
)，满足
n
=
pq
，且
φ
(
n
)= (
p
-1)(
q
-1)。
-
Step 2：随机选择公钥
t
，使得
t
和
φ
(
n
)的最大公约数为1，且
t
<
φ
(
n
)。
-
Step 3：计算
t
的乘法逆元
h
，满足
t
×
h
mod
φ
(
n
)=1。
上述结果中，{
p
,
q
,
h
}为私钥，{
n
,
t
}为公钥。生成参数之后，就可以进行相应的加、解密操作了。加、解密的过程如下。
-
Step 1：Bob计算RSA密钥参数，并将公钥{
n
,
t
}公开发布，将私钥{
p
,
q
,
h
}本地保存。
-
Step 2：Alice知道公钥{
n
,
t
}，利用函数
s
=
m
t
mod
n
对原文
m
进行加密。
-
Step 3：Bob得到密文
s
，并利用私钥{
p
,
q
,
h
}对密文进行解密，计算函数为
m
=
s
h
mod
n
。
上述所有计算过程都是在集合
Z
n
={0,1,…,
n
-1}中完成的。这些过程看上去复杂，不禁让人产生疑问：为什么这些参数和运算可以将明文加密再恢复成密文呢？我们不妨对该过程进行简单的推导。由于参数生成的过程中有
t
×
h
mod
φ
(
n
)=1，显然
(
m
t
)
h
mod
n
=
m
a
×
φ
(
n
)+1
mod
n
这里
a
为整数。如果加密过程能恢复出明文
m
，需要有
m
a
×
φ
(
n
)
mod
n
=1。大家可以了解
m
φ
(
n
)
mod
n
=1这个结论是成立的。而且，当
m
和
n
的最大公约数为1时，这个结论是数论中非常著名的“欧拉定理”；当
m
和
n
的最大公约数不为1时，由于
n
是两个素数
p
和
q
的乘积，我们可以把
m
表示为
p
或
q
的倍数，那么
m
φ
(
n
)
mod
n
=1这个结论也比较容易验证，在此不展开具体证明。
以上是RSA算法的密钥生成和加、解密的基本过程。下面对RSA背后的数学原理做一些解释。
-
在参数生成的过程中，再一次用到了乘法逆的概念。我们已经知道，
t
的乘法逆
h
存在的充分必要条件是
t
和
φ
(
n
)的最大公约数为1。
-
如果Carl能很容易地把公钥
n
分解且得到
n
=
p
×
q
，并计算
φ
(
n
)，就可以像Bob一样计算出私钥{
p
,
q
,
h
}。但在实际中，这是不可能的。其原理在于大整数
n
的素数分解一直是世界级的数学难题。以目前的研究进展来看，长度为1024位的大整数是无法破解的。
-
当Bob试图生成公、私钥参数时，由于他也无法解决上述难题，不可能先随机找到一个大整数
n
再做素数分解。可行的方法是，Bob先找到两个比较大的素数
p
和
q
，然后用它们来计算
n
和
φ
(
n
)。这里就涉及数论中的另一个经典问题，即素性检测。目前的RSA算法实现常选取512位的
p
和
q
、1024位的
n
。幸运的是，对于这种数量级来说，随机生成一个整数且刚好为素数的概率约为几百分之一。Bob完全可以随机生成
p
和
q
，然后判断它们是否为素数。这种操作的复杂度是可以接受的。目前，比较常见的素性检测算法有费马检测、Miller-Rabin检测和Solovay-Strassen检测等，这些算法都是比较高效的。
-
Bob在得到
n
和
φ
(
n
)后，还需要能快速计算出和
φ
(
n
)互素的整数
t
，以及
t
的乘法逆
h
，这可以用欧几里得算法高效实现。
RSA算法要求将明文
m
也表示成大整数，即
m
∈
Z
n
。如果原文信息
m
太长，超出了RSA算法的要求，可以先对原文进行分块，再对每一块执行RSA加密。
3vgHDBX+NEig1RS12dkogDzbIY76dKiRp027B7aXGj/p84PxmxyWc8pYKCzZ8kLv
