◆ [2025-7-20 星期日 9:53] ◆ | ◆ 收藏本站 ◆ | ◆ 设为首页 ◆ |
![]() |
|
---|
首 页 | 论坛交流 | 游戏频道 | 无忧脚本 | 旧版论坛 | 云服务器 | 聊 天 室 | 自助链接 | 来访记录 | 访客留言 | 搜索提供 |
位置:風雲工作室 - 论坛交流 - 技术专栏 - 后台开发 - 【转帖】RSA实现原理 | 返回 |
主题:【转帖】RSA实现原理 | |||||||
|
(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。 |
||||||
|
|||||||
|
(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 就是这么神奇。 |
||||||
|
|||||||
|
(3楼)简单的密钥生成方法
[您可以先修改代码再运行]
|
||||||
|
|||||||
|
(4楼)学习了!
好神奇,学习了!
|
||||||
|
|||||||
|
(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 }; |
||||||
|