非对称加密 - RSA

令人费解的 “公钥加密算法”。

公开密钥密码学

加密需要双方共享一个私密的随机数。从未谋面的两人,如何就此共享密钥达成一致,而又不让第三方监听者知道呢?

离散对数问题

我们需要一种运算,正常容易,反向很难。于是我们找到了模运算,也称时钟运算。

比如 $46 \ \mathrm {mod} \ 12 = 10$,正向计算很容易。

下面采用质数,

对于不同的取值$e$,结果是[0,16]之间均匀分布的。

反向是很困难的

正向加密很容易。

求以上过程的反向,这就很难了。
这被称为离散对数问题(discrete logarithm problem)

反向解密却很难。已知12,我们只能采用试错法求出匹配的指数。

反向有多难
如果模数很小,比较容易。模数若是长达百位的质数,即便借助地球上最强大的计算机,要遍历所有可能情况也需要上千年时间。

单向函数的强度取决于反向过程所需要的时间。

  • 反向的难度,具体计算一下

迪菲·赫尔曼密钥交换

Alice如何向Bob发送信息,而不怕Eve截获信息呢?

首先Alice和Bob公开地就质模数(prime modulus)和生成元(generator)达成一致,也就是这个例子中的p=17,g=3。

然后Alice选择一个私有数,${\color{red}{15}}$,加密后是${\color{blue} 6}$

然后公开将此结果发送给Bob。

Bob选择一个私有数13,计算

然后公开将此结果发送给Alice。

下面就是关键

Alice经过以下计算,得到共享密钥 (shared secret) ${\color{Apricot}{10} }$

Bob也计算得到共享密钥,两者计算结果是相同的。

这是因为

两种计算实质是相同的,只是指数的顺序不同而已。
没有私有数字 ${\color{red}{15}}$、${\color{red}{13}}$,Eve将无法求出结果。Eve会被困在离散对数问题之中,数字足够大时,实践中,她在合理时限内几乎不可能破解。这就解决了交换密钥的问题。这可以同伪随机数生成器结合使用为未曾谋面的人提供通信加密。

Eve将无法求出结果,没太看懂。

  • 这两个私有数字,只要有一个就能解密吗?
  • 17,3 是怎么达成一致的?传输过程被截获呢?是public的吗?

RSA加密第一步

对称加密中,要求通信双方共享密钥。但如果Alice和Bob不能实际见面,则需要额外的通信开销,比如使用迪菲-赫尔曼密钥交换。

另外,如果Alice希望同很多人通信,那么她将需要同每个人交换不同密钥。她必须管理好所有这些密钥,发送数以千计的信息,仅仅为了建立它们。

是否有更简单的额方式?

1970年,英国数学家James Ellis试图实现公开密钥加密(non-secret encryption)。

加密和解密是互逆操作,Alice可以买一把锁,把钥匙留在手里,然后把打开的锁发给Bob。Bob可以将自己的信息上锁,然后发回给Alice。这里无需交换密钥。

这意味着锁是可以公开的,可以让世界上任何人使用它来发信息。而现在Alice只需要留一把钥匙。

Ellis并未找到相关的数学方法,但他提出了应该怎样做的思路。关键在于将密钥分为两个部分,一部分是加密密钥,一部分是解密密钥。解密密钥用于解密这一逆操作,而加密是通过加密密钥进行的。

RSA加密第二步

需要构建一种特殊的单向函数,也叫陷门单向函数(trap door one-way functioin)

这种函数,正向很容易,反向很难,除非你有关于trap door的特殊信息。为此,考虑了模幂运算。

扩展阅读