初识:RSA 算法(理解)

“对称加密算法”模式:
甲方和乙方协商好一种规则,甲方用这套规则进行加密。而乙方则用这套规则进行解密。

这种算法模式很容易理解,例如电影、电视剧等可以常见的摩斯密码,这种模式的缺点较为明显的是只要懂这套规则的人都能轻松解密。

“RSA加密算法”模式就是为了解决这样尴尬的局面而诞生的。

1976年,美国计算机学家Whitfield Diffie 和 Martin Hellman提出了"Diffie-Hellman密钥交换算法",这种算法能在“不直接”传递秘钥的情况下完成解密。

我们假设我们加密的内容为 X;
原理举例:

13 * 77 = 1001
1001 % 1000 = 1
1001 = 1 (mod 1000)
1001 * X = X (mod 1000)
(1001 * X) %1000 = X
[13 * X * 77] % 1000 = X
{[(13 * X) % 1000] * 77} % 1000 =X

这个时候,我们再假设我们有一个数字 666 需要再“不直接”传递秘钥的情况下完成加密和解密的动作将会发生如下 <1> 过程:

甲方加密(秘钥:13):
666 * 13 = 8 658;
8658 % 1000 = 658;

甲方传递(公钥:658):
658

乙方解密(秘钥:77):
658 * 77 = 50 666;
50666 % 1000 = 666;

RSA就是通过 类似 上述的方式,在不直接传递秘钥的情况下完成加密和解密的动作。

当然,这种算法在第一步是取的两个数是有前提的,如果随便取就会。。。

2 * 6 = 12
12 % 10 = 2
3 * X * 4 = 2 * X (mod 10);
{[(3 * X) % 10] * 4} % 10 =X

我们取666试试:

3 * 666 = 1 998
1998 % 10 = 8
8 * 4 = 32
32 % 10 = 2
// Wow!!!发生了什么

该算法的前提是中国剩余定理:
原理理解:

假设一个数X ,已知:
X % 7 = 6;
X % 5 = 3;

通过上面的条件我们能否知道X的值呢?

X     ...     13     ...     20     ...     27     ...     34     ...     41     ...     48
%7            6               6              6              6              6              6     
%5            3               0              2              4              1              3

答案是否定的,
我们会发现13符合条件,48符合条件,后面是以 13+(5*7)n 为周期的循环,
也就是说对于上述的%操作并不能确定唯一的值与之对应。

所以,我们确定一个数还需要一个条件,那就是限定取值范围。
我们可以发现(X%7 和 X%5)在 [0,57]的区间内是不会重复的,
而上面的秘钥2、6显然不足以确定一个比 2
6 大的多的数,
因此,我们在选择加密的内容时是需要限定内容区间的。

还要强调一点(中国剩余定理的前提条件),
这两个数必须还是互质关系(两个正整数,除了1以外,没有其他公因子)

比如说下面的情况是不成立的,

已知:
X % 4 = 1;
X % 2 = 1;
范围:[ 0 , 8 ]
结果:1 和 5 均满足条件,不能确定唯一的数值

下面开始进入正题

设 :
P 和 Q 为两个互不相同且差值较大的大素数,
N = P * Q
D 和 E 为私钥
T = ( P - 1)( Q - 1)
i : 是正整数变量 ( 1, 2, 3, 4, 5, ...)

先了解一下费马小定理的结论:
1、如果n是一个质数,对于任意的a有an - a = n的倍数
那么,由
an - a = n的倍数 ===>
an - a = 0 ( mod n ) =>
an % n = a % n
另一种说法是,对于任意的 a,随着 i 的增加,ai % n 呈长度为 n - 1 的周期性;
2、给出两个质数 P 和 Q,其乘积为 N,
那么随着 i 的增加,Xi % N 呈现周期为 ( P - 1)( Q - 1) 的循环。

由上述结论可得:
X % N = X iT+1 % N

接着我们用私钥 D 和 E 等价于上式
X % N = XDE % N
( 即 DE % T = 1)

而且,因为 X < N,则有:
X = XDE % N

那么我们可以得到加密和解密的公式如下:
X = ( XD % N )E % N

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 姓名:李浩然 学号:16030410020 转自:http://blog.csdn.net/Dreaming_My...
    洛花无阅读 2,681评论 0 1
  • 姓名:于川皓 学号:16140210089 转载自:https://baike.baidu.com/item/RS...
    道无涯_cc76阅读 2,648评论 0 1
  • 公钥密码系统及RSA公钥算法 本文简单介绍了公开密钥密码系统的思想和特点,并具体介绍了RSA算法的理论基础,工作原...
    火狼o阅读 4,342评论 2 15
  • 终端之间信息传递安全性的保证始终是业务的刚性需求。不同的加密算法针对不同的业务需求,因为公司是金融公司性质,又不是...
    语歌阅读 2,845评论 0 5
  • 少年自有少年狂, 藐挫折, 笑风浪。 磨剑十载, 今朝亮锋芒。 挥斥方遒斗志昂, 好儿郎, 当自强。 披荆斩棘神飞...
    古曦阅读 757评论 14 14