RSA算法(一):简介

原创 小赛艇  2018-06-01 15:19  阅读 927 次

1 前言

最近在认真研究RSA算法及其实现方式。一方面数论知识涉及到"很简单"的整数运算问题,另一方面作为密码学伟大发明之一的RSA我一直很好奇它的原理,于是开始认真研究了一下RSA算法,写个小总结。

2 公开密钥加密简介

首先来考虑信息如何加密传输,设想以下场景:

你(a)写一封信i给同学b,但这封信是由同学c来帮你给b,你的小秘密不想让同学c知道,怎么办?

简单的方法就是采用对称密钥加密,你用你的生日(假设为20000101)给信i加密,变成加密信I,然后在信后面附上:密码是我的生日。如果同学c不知道你的生日,而b知道,就完成了加密传输。b拿到加密信I后,使用你的生日(20000101)解密就得到信的内容i。
这种加密的前提就是a和b事先有商量好的密钥,且不被传递者c知道,就可以完成加密传输。

但是,如果现在把b换成陌生人呢?他也不知道你的生日,怎么办?

如果还用前面的方法,你就要把密码附在信后告诉b,这样c也能得到密码,解密就能偷看你的信件。
这就需要用到公开密钥加密。公开密钥有两个密钥,一个用于加密(设为e),一个用于解密(设为d),在公开密钥加密中,由e很难得到d,由d也很难得到e。于是,你们的秘密不想被信使c知道,就可以这样操作:
你先把你的加密密钥e发给b,b想出一个密码i用来加密你们之间的信件(就像前面的生日),b用你的加密密钥e给i加密成I再发给你。你用解密密钥d解密I得到i,之后,就可以用i来加密你们之间所有的信件了。

如果从信使c的角度看,他能得到你和b之间发送的加密密钥e和密码的加密I,但是由于不能由加密密钥e推出解密密钥d,就没办法从I解出i。

图解如下:

RSA算法就是可以用于公开密钥加密之一的算法。基于一个简单的数论事实:计算两个质数的乘积很容易,而分解一个合数很难。

例如:8017×6151=49 312 567

而想要把71 259 751分解很难(71259751=9833×7247)

接下来会具体介绍RSA的原理,即为什么用e加密可以用d解密,以及RSA算法与质数、质数乘积的联系。

本文地址:https://xsaiting.com/rsa-1.html
版权声明:本文为原创文章,版权归 小赛艇 所有,转载请保留出处!
喜欢请点赞/打赏/分享这篇文章哦!

发表评论


表情