独孤密码-非对称加密算法RSA解析

一.RSA算法

一种常用的非对称加密算法. 非对称加密算法家族包含了鼻祖DH算法,基于因子分解难题的RSA算法,基于离散对数难题的ElGamal算法和ECC算法等.在本人对接过的多家银行和第三方支付接口中,RSA算法是非对称加密中的网红花旦,今天就浅谈下RSA算法.

二.RSA应用

在JAVA中运用RSA算法,在网上都有成熟的案例,不再重复.公私钥的生成可以通过现成的工具软件或者写java代码来生成RSA公私钥对,java密钥类及keytools都可以.常用的RSA密钥长度有1028位和2048位,JAVA7本身实现了1028位.如果使用2048位可通过BouncyCastle实现.

三.RSA原理 1个数学题

RSA算法是基于一个数学题:大数因子分解难题,一个大数很难分解成2个素数的乘积.
素数:只能被1和本身整除的数,也叫质数. 自然界中的素数有2,3,5,7,11等,注意1不是素数.
举例:一个数是15,可以分解成素数3乘以素数5, 但一个很大很大的数,很难分解成2个素数.但是反过来,即使2个很大的素数,计算2个数的乘积是容易的.
思考: 为什么不可以?穷举不可以吗?
答案: 素数是无穷的,几百年来,人类总共发现了 51 个梅森素数,最大素数是2^82,589,933-1,对于一个很大的数N,比如1024位的二进制数,穷举需要从2开始穷举到N/2寻找素数,以目前计算机能力还做不到.

1个例子 背景

基于大数的因子分解计算较复杂,我就用一个小的"大数"来解释,原理都一样.
这个"大数"是15.
任务背景: 风清扬要通过书信传授独孤九剑给令狐冲,又不能泄露武功秘籍.

计算公私钥

令狐冲先选出2个素数,分别是3和5,将2个数字相乘.
公式: n= p*q. 其中n=15,p=3,q=5;

准备φ(n).
公式: 欧拉总计函数,φ(n)=(p-1)(q-1). 其中φ(n)是指小于n中与n互素的个数.互素的概念指2个数字没有公共因子(比如7和8).
计算: φ(15)=φ(35)=φ(3)φ(5)=(3-1)(5-1)=8.
验证: 按定义小于15且与15互素的数字有1,2,4,7,8,11,13,14.确实是8个.

公钥
公钥e 满足 1< e < φ(n) 且 e和φ(n)互素
计算: 满足小于8且和8互素(没有公共因子)数字有7,5,3等. 选个3吧.
公钥e = 3.

私钥
私钥d满足模逆元 e*d/φ(n)余1.
计算: e=3,φ(15)=8, 满足3d%8==1, 很多数字可以满足,比如数字11.
私钥d = 11.

发送公钥 令狐冲把大数n, 公钥e写信给风清扬.
这个例子中 n=15, e=3 风清扬写信 风清扬先把独孤九剑的前8式传给令狐冲,数字m=8.(注意m小于n)
公式: 数字c = m的e次方除以n求余.
计算: 8的3次方除以15求余等于2,也就是c = 2
风清扬写信给令狐冲,只写了数字c=2. 没有写m=8(防止秘籍泄露). 令狐冲收信 令狐冲收信,拿到了c=2.开始计算.利用手中的私钥d=11,大数n=15.
公式: c的d次方除以n求余 = m.
计算 2的11次方除以15求余=8. 这个数字正是风清扬想要传递的数字m=8.
注意: m只是一个数字代号.实际n是个大数,满足m<n就可以.如果秘籍内容太长,就分开来发送,不影响安全性,信息的底层都是二进制数. 东方不败偷信

东方不败窃取了第5步和第6步的书信,有风清扬书信中的c=2, 有大数n=15.公钥e=3,没有私钥d,怎么破解?

东方不败需要知道私钥d,就要获取φ(n),也就是φ(15),而φ(15)是有(p-1)*(q-1)计算出来的,也就是需要把大数15分解成2个质数p和q. 基于前面的数学题,现有计算机能力还解不出大数因子分解.

思考 如果东方不败获取了量子计算机,怎么办:
答案: 密码学是个矛和盾.如果矛厉害了,盾也会做相应的升级.如果非对称加密被破解,那现有金融系统都需要升级,区块链基于非对称加密的账户体系也要重构,这是后话了…

以上,如有出入,烦请指正.感谢感谢!!
PS:第一次写技术BLOG.如转载请说明出处.码字不易,感谢支持.

作者：独孤瓦力

加密 非对称加密 rsa