公钥加密

本页面已浏览271次

公钥密码以及RSA

公钥密码就是所谓通过公开的加密方法加密而得到的密码,也就是说,所有人都可以进行加密。但只有接收方才可以解密一个被加密的信息。

所谓的公钥密码是如何工作的?答案是:有些数学运算很容易进行,但有些却非常困难。我们本章讨论一种特定的公钥密码体系,它被称为RSA加密,并首先由Ronald Rivest,Adi Shamir和Leonard Adelman发布。

RSA概述

假定我们选择两个非常大的素数——比如说,各有200位数字。然后将它们相乘。然后将结果告诉一位朋友,要他进行分解。将两个数字相乘对计算机而言是很容易的,但要将一个数字分解成两个数字的乘积就十分困难。

所以,我们可以将这个400位的数字公诸于世,但其分解方式却只有我们知道。但是,“谁会在乎一个400位数字的分解呢?”答案是:你必定在乎。无法分解一个数字正是公钥加密系统的核心。

如何解密

首先来看几个定理。

定理5.1:如果\(p, q\)是两个不同的素数,而\(W\)是一个自然数且\((W, pq)=1\),那么\(W^{(p-1)(q-1)}\equiv 1\pmod{pq}\)

证明

这个证明不难。根据定理4.21:

定理4.21:令\(m, n\in\mathbb{N}, (m, n)=1, a\in\mathbb{Z}\)\(x\equiv a\pmod{m}\)\(x\equiv a\pmod{n}\implies x\equiv a\pmod{mn}\)

以及费马小定理就可以证明。

定理5.2:令\(p, q\)是两个不同的素数,\(k\)是一个自然数,而\(W\in\mathbb{N}, W\lt pq\),那么\(W^{1+k(p-1)(q-1)}\equiv W\pmod{pq}\)

证明

先假定\((W, pq)=1\),那么根据定理5.1,有\(W^{(p-1)(q-1)}\equiv 1\pmod{pq}\implies (W^{(p-1)(q-1)})^k=W^{k(p-1)(q-1)}\equiv 1\pmod{pq}\implies W^{1+k(p-1)(q-1)}\equiv W\pmod{pq}\)

如果\((W, pq)\ne 1\),我们不妨先假设\(p\mid W\),于是\(W\equiv 0\equiv W^{1+k(p-1)(q-1)}\pmod{p}\)。注意到,此时\((W, q)=1\),于是\(W^{1+k(p-1)(q-1)}=W\times W^{k(p-1)(q-1)}=W\times (W^{k(p-1)})^{q-1}\equiv W\times 1\equiv W\pmod{q}\)。同样可以得到\(W^{1+k(p-1)(q-1)}\equiv W\pmod{p}\)。由于\((p, q)=1\),所以\(W^{1+k(p-1)(q-1)}\equiv W\pmod{pq}\)。QED。

(补充一个定理)

补充定理\(\phi(ab)=\phi(a)\phi(b)\iff (a, b)=1\)

这个定理其实可以帮助证明上面的两个定理,而且更快。

定理5.3:令\(p, q\)为两个不同的素数,而\(E\in\mathbb{N}, (E, (p-1)(q-1))=1\),那么存在一个自然数\(D\),使得\(ED=1+y(p-1)(q-1)\)

证明:(略)

定理5.4:令\(p, q\)为两个不同的素数,而\(W\in\mathbb{N}, W\lt pq\),而\(E, D, y\in\mathbb{N}, ED=1+y(p-1)(q-1)\),那么\(W^{ED}\equiv W\pmod{pq}\)

证明:(略)

我们已经有了构造RSA公钥加密系统的所有组件。我们将通过如下的练习来探索如何构造RSA加密。

graph TD; 选择2个不同的素数p和q-->计算pq的乘积为n-->计算n的欧拉函数φ-->找到一个和φ互质的自然数e-->找到e对φ的模倒数d-->公钥由n和e构成-->私钥由n和d构成

请自行研究这个过程和之前提到的那些定理有怎样的关联。

让我们来用几个比较小的素数进行如上所述的过程。

  1. 找到两个素数\(p\)\(q\)

本例中令\(p=61, q=53\)

  1. 计算\(p\times q\)的乘积为\(n\)

\(n=p\times q=61\times 53=3233\)

  1. 计算\(\phi(n)\)

我们可以借助工具得出\(\phi(3233)=(p-1)\times(q-1)=3120\)

  1. 选择一个\(1\lt e\lt \phi(n), (e, \phi(n))=1\)

我们随便挑一个,比如\(e=17\)

  1. 找到\(e\)\(\phi(n)\)的模倒数\(d\)

\(d=2753\)

最后得到公钥对\((3233, 17)\),私钥对\((3233, 2753)\)

RSA加密、解密的准备工作已经完成!

我们来看看如何加密。

假定我们要对数字\(65\)(你也可以把它认为是字母A)进行加密。

首先,计算\(m^e\equiv c\pmod{n}\),也就是\(65^{17}\)除以\(3233\)的余数。该余数是\(2790\)

我们可以将\(2790\)交给拥有私钥的对方,他将这样来解密:

\(2790^{2753}\equiv 65\pmod{3233}\)

我们重新得到了\(65\)!加密、解密工作全部完成!

思考问题是:如何在得到公钥和密文的情况下进行破解?

困难的问题

RSA加密系统有两个键,一个是公开的加密键,一个是私有的解密键。这样的系统被称为非对称加密,与之相对应的就是所谓对称加密。在实际使用中,RSA在加解密大量数据时并不是很有效,而所谓的AES( Advanced Encryption Standard )更有效——但要求在发送方和接收方间传递一个密钥,而传递密钥的过程可能存在风险。

所以在实践中,往往采用混合加密方式:用RSA方式加密AES的密钥。然后在发送给对方的时候,发送两个内容:一个是经RSA加密的AES密钥,一个是经AES加密的密文。对方首先用RSA私钥解密得到AES密钥,然后再用AES密钥解密密文。所以,RSA更多地用在密钥的交换。

RSA的强度取决于这样一个事实:因子分解非常困难。有多难?按照RSA官网的说法,2005年11月,30个2.2G的CPU用了5个月才将一个193位的数字进行了因子分解。

但是,因子分解并不是唯一困难的问题。

1970年中期,斯坦福大学研究生Whitfield Diffie和他的导师Martin Hellman基于计算logarithms modulo \(p\)开发了一种公钥交换系统,也就是著名的Diffie-Hellman加密

1980年中期,Victor Miller和Neal Koblitz独立地提出使用所谓椭圆曲线(Elliptic Curves)来生成公钥密码。目前认为,这个方法比上面提到的Diffie-Hellman方法更难破解。

这些都是数论在实践中的应用。数论学家进行基础工作时,根本想不到这些成就会有这样的实际应用。但是,公钥加密这一应用表明,人们应该继续探究数学和科学领域的那些想法,因为这些想法是美的。实践应用早晚必然会出现。

Previous Post Next Post