0%

RSA学习与思考

引言

RSA加密算法是一种非对称加密算法,在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的

​ ————————-Wikipedia

RSA是一种非常广泛使用的非对称加密算法,如其名,这种算法首先是一种加密算法。加密算法可不止是加密,而是包括密钥准备、加密、解密等等全过程的一种算法。那么加密解密为何如此重要呢?

在网络上,信息是可以完美复制的,节点与节点在信号发送上没有区别,这就导致了一个问题,我怎么知道某段冷冰冰的01信号是谁发给我的?同样的,由于信号传递过程中难免要经过其他节点,如果我不想让其他节点知道我发送的信息我又要怎么办呢?

这些问题就可以通过理想的公私钥加密体系完美解决。公钥私钥的区别只在于是否公开,而两者都可以用来加密,只是用公钥加密后的信息只能被私钥解密,被私钥加密后的信息也只能被公钥解密。这就对应了上面两个问题的解决方法。

首先,公钥完全公开透明,每个人都可以用公钥加密,但是产生的密文却只有私钥才能解密成明文,这样保证了有用情报只会被拥有私钥的人接收,我们就能把信息发给拥有私钥的那个人而不用担心被别人得知了。

反过来呢?拥有私钥的人对某段信息用私钥加密之后,产生的密文能被所有人解密成明文,这样又有什么效果呢?为了把明文和无效信息区分开来,假设我们约定了明文中至少要包含的有效信息(比如发布时间等等),那么密文就与加密者产生了对应关系,我们只需用加密者发布的公钥做一下解密,再验证一下明文中是否有这些有效信息,就能确认这段信息是不是由私钥拥有者发布的了。这样信息就有了归属,我们就能确认某段信息是我们想要的人发给我们的了。而这种私钥加密的过程也称为签名

“非对称”并非核心

“ 非对称加密 ”本身没什么厉害的,我们可以随便设计一个非对称的加密算法,就让乘私钥作为加密,乘公钥作为解密,那么整个原理就是message * privatekey * publickey = message,在这里,公钥与私钥的对应关系就是privatekey = 1 / publickey。你应该能发现,这样的加密解密似乎没啥保密性可言,任何学过小学数学的人都能很快地从公钥推出私钥,也就能随意冒充你来发布消息了。因此,“似乎”保证私钥与公钥难以互相推导是非常重要的

不能让公钥简单推到私钥是显然的,但为什么说也不能让私钥简单推到公钥呢?这里我们要明确一点,公钥与私钥只是互成一对,并没有形式上的区别,我既能用公钥加密,也能用私钥加密。那如果算法保证了只知道公钥的时候难以推出私钥的话,反过来也是一样的。在只知道私钥的情况下也难以推出公钥,注意!是只知道私钥!而生成这一对公私钥的过程中是产生了很多过程变量的,这些过程变量才是算法生成公私钥对的某种依据

总结来说,RSA等一众非对称加密算法通过某个数学过程产生了互成一对但难以相互推导的公钥与私钥,然后大家就能愉快地用公私钥来在网络上加密通信了。

取模

求余,一个小学就接触到的数学运算,那时候我们把除法得到的整数后加几个点,再接上一个数表示余数:

$$ 5 \div 3 = 1 \dots 2$$

这样的写法中,余数表现得就像它的名字一样——有点多余。当时的我们可没想到,这么简单的一个余数及其相关的运算,竟然能在数论中爆发出那么强大的力量

废话少说,让我们再多多观察观察这个运算,为了不考虑向下取整与向0取整,我们忽略负数的情况

在上面的例子中,如果我们不关注商而只关注余数,那么包括2、5、8等等在内的一系列数对3求余结果都是2,包括1、4、7在内的一系列数对3求余结果都是1,类似的,如果我们只关注整数n对m求余后的结果,那么所有的n就能根据这个结果分成m个集合,我们把这样划分后在同一个集合内的两个数称为模m同余,这样的集合称为同余类,求余运算的新形式也就这么出现了

两个整数a,b,若它们除以正整数m所得的余数相等,则称a,b对于模数m同余,记作:$$a \equiv b\ (\ mod\ m)$$

对于一个运算符,最重要的概念是什么?