[原创]RSA公钥密码的破解

xyaoy · 发表于 2021-10-25 17:33

ysr 发表于 2021-10-25 17:31
谢谢沟通指导！我不会VC，用VB程序的确速度太慢。
你这个平方根是用的迭代法吗？据说是迭代法计算速度快 ...

二分法，找一个数n n*n<m<n&(n+1) 这个算法是在网上查的

ysr · 发表于 2021-10-25 17:35

xyaoy 发表于 2021-10-25 09:33
二分法，找一个数n n*n

额，二分可以，谢谢沟通探讨！可惜我不会VC，需要学习一下，欢迎指导！

xyaoy · 发表于 2021-10-26 08:04

ysr 发表于 2021-10-25 17:35
额，二分可以，谢谢沟通探讨！可惜我不会VC，需要学习一下，欢迎指导！

二分是很快的，对于1024位数字，找它最近的整数平方根大概需要不到1秒

xyaoy · 发表于 2021-10-26 08:07

ysr 发表于 2021-10-25 17:35
额，二分可以，谢谢沟通探讨！可惜我不会VC，需要学习一下，欢迎指导！

我研究rsa私钥的获取，感觉余数问题很难，想到的每一个想法都效率低下，对于小数可行的方法，到了大数之后效率就急剧下降，因数太多

ysr · 发表于 2021-10-26 08:39

xyaoy 发表于 2021-10-26 00:07
我研究rsa私钥的获取，感觉余数问题很难，想到的每一个想法都效率低下，对于小数可行的方法，到了大数之 ...

是的大数位数太多，如果方法正确需要提高精确度，比如整数部分仅仅末尾5位数字与实际不同，那就可以分解大数了，如果仅仅最高位等于或者接近实际，那就是差距太大。

余数的变化是波动的非线性的，如何按线性计算呢？方法是大致可以认为余数r改做余数为p+r或者np+r。
当然这是短距离内适用。并不是严格的线性，得到的数值接近实际，需要其它方法修正，我前面的方法就是这样的。

修正公式虽然准确但前提是前一步必须接近实际，二者必须结合起来才能更接近实际。我的方法仅仅供参考。

ysr · 发表于 2021-10-26 08:43

xyaoy 发表于 2021-10-26 00:04
二分是很快的，对于1024位数字，找它最近的整数平方根大概需要不到1秒

是吗？我不会用需要学习，我用的是模仿手工开平方根的方法，效率低速度太慢，结果是准确可靠的。

xyaoy · 发表于 2021-10-26 08:43

ysr 发表于 2021-10-26 08:39
是的大数位数太多，如果方法正确需要提高精确度，比如整数部分仅仅末尾5位数字与实际不同，那就可以分解 ...

p是什么？较小素数么？这种假定不能成立啊？

ysr · 发表于 2021-10-26 08:48

本帖最后由 ysr 于 2021-10-26 00:53 编辑

xyaoy 发表于 2021-10-26 00:43
p是什么？较小素数么？这种假定不能成立啊？

p是试除因子，当然，p也是通过前面的方法求出来的估计值，是接近实际的。
大致是线性变化的，不是严格的线性变化，这样处理后余数大致上不波动了，而是递增的增量不是严格的等差但大致上可以认为是等差。

xyaoy · 发表于 2021-10-26 08:48

ysr 发表于 2021-10-26 08:43
是吗？我不会用需要学习，我用的是模仿手工开平方根的方法，效率低速度太慢，结果是准确可靠的。

二分的结果也很可靠，毕竟他找到的数字满足了不等式就必然是整数的平方根，并且把除法转成了乘法，速度很快

xyaoy · 发表于 2021-10-26 08:53

ysr 发表于 2021-10-26 08:48
p是试除因子，当然，p也是通过前面的方法求出来的估计值，是接近实际的。

我这个数字:
141200934203348100398237203092056603810497665953866503938436185453188653157534841542476799951117838232625775007972565407157639296613520419503480411605352582268797113156766586228582255481135809096970885597928003710586870460226020496368765994413857405308613414568674463104615847526186185331402709548604450804313
试除因子是多少？这个数字是309位，它的试除因子位数是多少位？

		自动登录	找回密码
密码			注册