红包
◆ [2024-3-28 星期四 20:54] ◆ 您来自:3.215.183.194,欢迎您访问風雲工作室。 收藏本站 ◆ | ◆ 设为首页
联系站长(腾讯QQ)
5029111 [風雲]
站长当前离线
首  页 论坛交流 游戏频道 无忧脚本 旧版论坛 云服务器 聊 天 室 自助链接 来访记录 访客留言 搜索提供
位置:風雲工作室 - 论坛交流 - 技术专栏 - 后台开发 - 【转帖】RSA实现原理 返回
主题:【转帖】RSA实现原理
Rimifon
★☆☆☆☆☆☆☆☆☆
积分:285
发帖:317
登录:2024/3/26
注册:2006/6/28
(1楼)【转帖】RSA实现原理
第一步,选择两个不等质数p,q(实际密钥一般为1024位或2048位)
这里我们选择 61 和53。

第二步,计算乘积n
n = p*q = 3233 (二进制110010100001,只有12位)

第三步,计算n的欧拉函数φ(n)
φ(n) = φ§*φ(q)= (p-1)(q-1) = 3120 。一个质数p的欧拉函数等于p-1

第四步,随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。
取e = 17 (实际应用中,常常选择65537)。

第五步,计算e对于φ(n)的模反元素d。
即找出一个d满足 ed互质,且对于φ(n) 取模为1 ,即 ed = 1 (mod φ(n))。

即 ed -1 = kφ(n) ,带入上面已知条件:

17d -1 = k3120 即 17x +3120y = 1 (据说可以使用 扩展欧几里得算法求解)

这里直接给出答案 d = 2753。

第六步,将n和e封装成公钥,n和d封装成私钥。
代入本次的推导过程中的数字,n = 3233,e = 17, d=2753。公钥为(3233,17),私钥为(3233,2753)。

加密使用 (3233,17),解密使用(3233,2753)。

第七步,分析,私钥的获取
由六可以看出来,公钥和私钥的区别其实只是d,也就是说d的推导是否可以在已知n,e的情况下推导出来。

由第五步,要得出d,已知n,e。需要φ(n)。

由第三部,要得出φ(n),需要p,q。

而已知n=p*q。而n已知,只需要分解n因子即可。

结论:只要n可以被分解,公私玥加密即可被破解。

第八步,n可以被分解吗?
在本例中,3233可以很快被破解,但是实际应用中,两个大质数的积是不容易被分解出来的

例如:

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

是以下两个质数的乘积:

a:

33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489

b:

36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

人类已经分解的最大整数(232个十进制位,768个二进制位)。比它更大的因数分解,还没有被报道过,因此目前被破解的最长RSA密钥就是768位。而RSA加密一般使用1024位或者2048位,基本可以理解为不可破解

三,RSA加密的过程
1,公钥(n,e)加密
所有字符串都可以使用ascil码/unicode值来表示,假设一个字符 m = a,ascii码为65,需要满足 m < n 对他进行加密。

m^e ≡ c (mod n),c为加密字符串

n = 3233,e = 17。 上式可以表示为: (65^17)%3233 = c ,c = 2790。

2,私钥(n,d)解密
(n,d) = (3233,2753) 。在拿到c = 2790之后,进行以下操作:

c^d ≡ m (mod n) 即可得到m 。

推导,m = (2790^2753) %3233 ,在这里使用 必备知识六中的快速幂取模,可以轻松得到答案,m = 65。


时间:2021年5月24日 9:56:32 IP:已记录 引用 回复
Rimifon
★☆☆☆☆☆☆☆☆☆
积分:285
发帖:317
登录:2024/3/26
注册:2006/6/28
(2楼)来个简单的例子
任意选择两个质数,例如 p=3和 q=11
得到 N 值:3 * 11 = 33
计算L值:2 * 10 = 20
随机取值E:例如 E = 3(1<E<L,且与L互质,用于加密数据)
计算D值: 3D % 20 = 1, D = 7(1<D<L,用于解密数据)
这样,我们就有了加密的密钥(3,33)和解密密钥(7,33)。

测试用加密密钥对明文 9 加密(数字不能大于N(33))
Math.pow(9, 3) % 33 = 729 % 33 = 3

然后用解密密钥对密文 3 进行解密:
Math.pow(3, 7) % 33 = 2187 % 33 = 9

就是这么神奇。


时间:2021年7月9日 22:37:07 IP:已记录 引用 回复
Rimifon
★☆☆☆☆☆☆☆☆☆
积分:285
发帖:317
登录:2024/3/26
注册:2006/6/28
(3楼)简单的密钥生成方法
[您可以先修改代码再运行]


时间:2021年7月10日 10:56:38 IP:已记录 引用 回复
pojin
★☆☆☆☆☆☆☆☆☆
积分:2
发帖:2
登录:2021/10/1
注册:2021/8/4
(4楼)学习了!
好神奇,学习了!
时间:2021年8月4日 17:31:42 IP:已记录 引用 回复
風雲
★☆☆☆☆☆☆☆☆☆
积分:58
发帖:62
登录:2024/3/26
注册:2006/9/17
(5楼)简单的 ASP 版 RSA 加密解密
var xml = new ActiveXObject("htmlfile").createElement("xml");
var root = xml.createElement("r"); root.dataType = "bin.base64";
var utf = new ActiveXObject("System.Text.UTF8Encoding");
var rsa = new ActiveXObject("System.Security.Cryptography.RSACryptoServiceProvider");
// RSA 加密
root.nodeTypedValue = rsa.Encrypt_2(utf.GetBytes_4("大家好"), false);
var encStr = root.text;
// RSA 解密
var decStr = utf.GetString(rsa.Decrypt_2(root.nodeTypedValue, false));
return { msg: "OK", encStr: encStr, decStr: decStr };
时间:2022年3月19日 15:40:10 IP:已记录 引用 回复

© Copyright 2006-2024,風雲工作室 All rights reserved.
湘ICP备05009306号QQ登录
操作 1 个库,连接 6 次,执行 13 次,耗时 156 毫秒。