欧拉,永远滴神!

貌似对这段历史格外感兴趣。

对称加密

几千年来,人们对与加密的方法都是基于对称加密的思想,即双方协商一个相同的密钥,用于加密和解密.这在以前的环境当然是可以的,但是随着互联网的发展,我们需要在一个公开的环境,即两个互不相见的人协商出一个相同的密钥.如果我们把密钥直接再互联网上交换,势必是不安全的.那么如何解决这个问题呢

1976年,在一篇名叫密码学的新方向的论文中,Whitefield与Martin Hellman首次提到了一种解决方法.该方法被称为Diffie-Hellman密钥协商算法(DiffieHellmanKeyExchange/AgreementAlgorithmDiffie-Hellman Key Exchange/Agreement Algorithm).

原理可如下图描述

image-20200502000144488

DH密钥协商主要解决秘钥配送问题,本身并非用来加密用的;该算法其背后有对应数学理论做支撑,简单来讲就是构造一个复杂的计算难题,使得对该问题的求解在现实的时间内无法快速有效的求解(computationally infeasible)

那目前看来我们解决了密钥分配的问题,但是我们发现如果在一个有n人需要通信的系统里,对于我们的Alice则需要n1n-1个密钥s.对于整个系统来说,更是密钥数量达到了惊人的n(n1)/2n(n-1)/2,这个对于密钥的管理和分发都是十分困难的,那么又如何解决这个新的问题?

灵光一闪

1970年,一位名叫James Ellis的密码学家为英国政府通信总部工作,在wiki百科中有一段话写道:

Ellis said that the idea first occurred to him after reading a paper from World War II by someone at Bell Labsdescribing the scheme named Project C43, a way to protect voice communications by the receiver adding (and then later subtracting) random noise

它的大致意思就是对于在公开的信道的消息,我们可以在消息中加上一些噪音,相当于加密.而对于真正的收信人有去除对应的噪音的方法.在这样的系统中,我们的Alice只需要在本地保留自己的解密方法,而把噪音发送出去.这样就不会产生密钥交换了,并且她不需要为每个人准备特定的钥匙.他的想法在于把一个钥匙分为两部分,一个用于加密,一个用于解密,分别称之为公钥和私钥

我们不妨用颜色来给出一个直观的说明

但是Ellis并没有归纳出一个数学方法去实现这样的一个效果.但是他的想法的确是正确的.

简单原理

1973年,在英国政府通讯总部工作的数学家克利福德·柯克斯(Clifford Cocks)提出了这样算法

他的构想是我们需要寻找一种单向函数(在我们上一个例子当中就是把颜色混合),就是我们正向计算的时候很简单,但是我们希望通过结果计算原值的时候是会变的非常难的

在现代密码学教科书上写到:

单向函数的例子在现实生活中很普遍,如将挤出的牙膏弄回管子里要比把牙膏挤出来困难得多;把盘子打碎成数片碎片很容易,但要把所有这些碎片再拼成为一个完整的盘子则很难。
但是这个函数不能仅仅是单向的,他还需要一些陷阱,当我们知道某些信息的时候逆计算也会变得很容易在现实生活中.
这样的例子也不少,比如将–个手表拆分为数百个细小的零件很简单,但是若要想将这些零件重新组合起来成为–个可工作的手表却很难,这就需要知道陷门(手表的结构图及装配指令)才能完成重新组合。

而我们得Clifford Cocks找到的陷门单向函数就是模的指数运算,如果我们给出了m,e,Nm, e,N我们进行对mmee模运算得到余数cc,这样一个操作时十分简单得,但是如果我们知道了余数cc想求得mm得值到底是多少则是十分困难得

这个 emodN^{e}\bmod N 运算就变成了我们得数学锁,对于一个消息mm,我们只需要在进行一个运算即可.那么如何解密呢?

对于解密我们则需要知道这个emodN^{e}\bmod N 单向陷门函数的陷门在哪里.对于一个模幂运算,我们存在另一个数dd可以使得ccdd次方逆反掉ee次方的效果,所以这两次操作如下表示

memodN=ccdmodN=mm^{e}\bmod N = c \\ c^{d}\bmod N= m

那么我们可以得到

(me)dmodN=m(m^{e})^{d}\bmod N= m

可以发现整个操作中,我们需要找到两个参数eedd,此外那么我们还需要使得这个dd很难被Alice以外的人发现

我们的Clifford Cocks找到了第二个单向函数来解决这个问题-欧拉函数(EulerstotientfunctionEuler's totient function)

mφ(n)1modNm^{\varphi(n)}\equiv1\bmod N

我们现在只需要简单的改写一下这个函数,把左边再取kk次方当然结果不变,则式子变为

mkφ(n)1modNm^{k*{\varphi(n)}}\equiv1\bmod N

左右两边再同时乘mm

mkφ(n)+1mmodNm^{k*{\varphi(n)+1}}\equiv m\bmod N

这与我们的上式(me)dmodN=m(m^{e})^{d}\bmod N= m的指数是相同的,那么我们得到了ededφ(n)\varphi(n)的关系

ed=kφ(n)+1ed1modφ(n)ed= k*\varphi(n)+1 \Rightarrow ed\equiv 1 \bmod \varphi(n)

通过这个式子我们可以得到只要我们知道eenn的因数分解式,计算dd使很容易的,因为φ(n)\varphi(n)是很容易算的

d=kφ(n)+1ed= \frac {k*\varphi(n)+1}{e}

所以dd则是Alice的私钥,ee是用来加密的公钥,至此以上的步骤正是RSA公钥密码系统的教科书式的步骤

当时我们的Cocks发现了这一秘密并没有公布出来,因为此算法被列为了机密.但是1977我们的RSA三兄弟还是最后独立发现了并公布了出来,所以这一算法被命名为了RSA

image-20200502004319053

好了以上就式本文的全部内容,简单了叙述了一下相关背景故事和简单的数学推导,希望能让你对密码学的兴趣提升那么一点…

评论