CS►security►密码学►非对称加密

非对称加密 - RSA

公开密钥密码学

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

离散对数问题

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

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

下面采用质数，

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

反向是很困难的

$$3^{\color{red}{29}} \mathrm {mod} \ 17 \xrightarrow[encrypt]{\color{green}{EASY}} {\color{blue}12}$$
正向加密很容易。

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

$$3^{\color{red}?} \mathrm {mod} \ 17 \xleftarrow[decrypt]{\color{red}{HARD}} {\color{blue}{12}}$$
反向解密却很难。已知12，我们只能采用试错法求出匹配的指数。

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

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

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

迪菲·赫尔曼密钥交换

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

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

然后Alice选择一个私有数，${\color{red}{15}}$，加密后是${\color{blue} 6}$
$$3^{\color{red}{15}} \mathrm {mod} \ 17 \equiv {\color{blue} 6}$$
然后公开将此结果发送给Bob。

Bob选择一个私有数13，计算
$$3^{\color{red}{13}} \mathrm {mod} \ 17 \equiv {\color{blue} {12}}$$
然后公开将此结果发送给Alice。

下面就是关键

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

$${\color{blue}{12} }^{\color{red}{15} } \mathrm {mod} \ 17 \equiv {\color{Apricot}{10} }$$

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

这是因为
$$3^{\color{red}{13 ^{15}} } \mathrm {mod} \ 17 \equiv 3^{\color{red}{15 ^{13}} } \mathrm {mod} \ 17 $$

两种计算实质是相同的，只是指数的顺序不同而已。
没有私有数字 ${\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的特殊信息。为此，考虑了模幂运算。

扩展阅读