RSA公钥加密系统

RSA公钥加密系统

公钥加密系统(public key cryptosystem)可以对传输于两个通信单位之间的消息进行加密,这样即使窃密者窃听到被加密的信息,也不能对加密信息进行破译。

RSA公钥加密系统主要是基于以下事实:寻找大素数是很容易的,但是要把一个数分解为两个大素数的积确实相当困难的。

貌似看起来这套系统是很神秘的,其实RSA系统分析后,确实两个很简单的公式就能表达,这也从一个侧面表现了数学之美。下面我就总结一下这周学习这个系统的一些内容。

RSA加密系统中,每个参与者都有一把公钥和一把密钥。密码学上习惯把参与者叫做“Alice”和“Bob”。用[math]P_A[/math]和[math]S_A[/math]分别代表alice的公钥和密钥。[math]P_B[/math]和[math]S_B[/math]分别代表bob的公钥和密钥。M为要加密的信息。有如下公式成立:

  • [math]M=S_A(P_A(M))[/math]
  • [math]M=P_A(S_A(M))[/math]

这下明白了吧,有这两个公式成立,那么经过密钥处理过的信息,再经过公钥处理,就能还原成源信息。这里存在的一个技术问题是,如何保证公开了公钥,而外界的敌人不会通过公钥还原出密钥。这也就是RSA的重要假设一个数分解为两个大素数的积确实相当困难的。

RSA系统可以有这么几种应用:

  1. bob取得alice的公钥,bob把信息用公钥加密,然后发给alice,alice再用密钥解开。
  2. alice可以用RSA系统签名。例如她可以用用密钥签署信息M,把签名和M一块发送给bob,bob再用alice的公钥来还原签名,如果和信息M相同,则证明是alice签名的信息。
  3. 签署者首先把他的数字签名附在信息的后面,然后再用他希望的接受者的公钥对得到的信息/签名对进行加密。接受者运用他的密钥对收到的消息进行解密,以同时获取原始信息和数字签名,然后,他可以用签署者的公钥对签名进行验证。
  4. 无公钥加密系统。这个系统加密密钥和解密密钥是相同的。如果alice希望私下把一条很长的消息M发送给bob,在无公钥加密系统中,她选取一把随机密钥K,然后运用K对M进行加密,得到密文C。她利用bob公开的RSA密钥对K进行加密。她把(C,[math]P_B(K)[/math])传送给bob,bob对[math]P_B(K)[/math]解密后得到K,然后再用K对C进行解密从而得到M。
  5. “混合”模式。如果Alice希望签署一条消息M,她首先用hash函数h作用于M得到指纹h(M),然后,她用密钥来加密h(M)。她把(M,[math]S_A(h(M))[/math])做为她签署的M版本发送给bob。bob可以通过计算h(M),然后验证用[math]P_A[/math]作用于他收到的[math]S_A(h(M))[/math],看是否等于h(M)来验证签名的真实性。

RSA系统是这么实现的:(偷懒用原文了)

  1. Select at random two large prime numbers p and q such that p ≠ q. The primes p and q might be, say, 512 bits each.
  2. Compute n by the equation n = pq.
  3. Select a small odd integer e that is relatively prime to φ(n), which equals (p – 1)(q – 1).
  4. Compute d as the multiplicative inverse of e, modulo φ(n).
  5. Publish the pair P = (e, n) as his RSA public key.
  6. Keep secret the pair S = (d, n) as his RSA secret key.

For this scheme, the domain is the set Zn. The transformation of a message M associated
with a public key P = (e, n) is

[math]P(M)=M^e(mod n)[/math]

The transformation of a ciphertext C associated with a secret key S = (d, n) is

[math]S(C)=C^d(mod n)[/math]

证明过程

P(S(M)) = S(P(M)) = [math]M^{ed}[/math] (mod n).

Since e and d are multiplicative inverses modulo φ(n) = (p – 1)(q – 1),

ed = 1 + k(p – 1)(q – 1)

for some integer k. But then, if M ≢ 0 (mod p), we have

[math]M^{ed}[/math] ≡ [math]M(M^{P-1})^{k(q-1)} (mod p)[/math]
≡ [math]M(1)^{k (q-1)} (mod p)[/math] (by Theorem 31.31)
≡ M (mod p)

Also, [math]M^{ed}[/math]≡ M (mod p) if M ≡ 0 (mod p). Thus,

[math]M^{ed}[/math]≡ M (mod p)

for all M. Similarly,

[math]M^{ed}[/math]≡ M (mod q)

for all M. Thus, by Corollary 31.29 to the Chinese remainder theorem,

[math]M^{ed}[/math]≡ M (mod n)
for all M.

发现才完成了自己想完成的一部分,就花了大概1个多小时了。真耗时啊。

Leave a Reply

Your email address will not be published. Required fields are marked *