在RSA对于大数无需分解就可以找到私钥的部分特例
最近有一个程序的注册码用到rsa需要分解数据，因为是256位他们用了1个多小时就分解开了，后来发现不分解这个数据也可以
算出他的私钥。
[url]http://blog.sina.com.cn/u/4bd62ac4010007zi[/url]
生成私要一般需要分解大数n为两个大素数p,q
生成私钥需要计算 （p-1）*（q-1）
对于一些特定的大数是无须分解的。
现说明如下：
假设n满足如下：条件就无须分解。
设 n^(1/2)+1 为 x。
如果能找到合适一个数 y 且
x+y=q x-y=p [经scz指出与原来地方已修改]
且（x-1）^2 < n
如果数据满足上述条件则:无须分解此大数
可以看出: (q-1)*(p-1) = n - 2x + 1 [经scz指出与原来地方已修改]
我们看出计算 n的平方根应该比较简单.
但我们是否发现,没有分解大数,怎么知道是否满足上述条件.
其实我们可以先假设n满足条件,计算出它的平方根，就可以得到
(q-1)*(p-1) = n - 2x + 1。然后计算出私钥 d,
然后用他加密一段明文,然后用共钥看能否解开就可以了；
也可以用这个方式检测，算出它的平方根整数后
作n - x^2,如果此数正好是等于一个数的平方。也不用分解此数
如果此数不满足上面的任何一个再分解大数n也不迟.
另外昨天写一个求大数平方根的子程序思路如下：
[url]http://blog.sina.com.cn/u/4bd62ac40100080m[/url]
对于给定数据位数[表示成32dword进位]，可以先在合适的x位置1，其他低位全都清零，
算他的平方，如果大于给定数据n，则清掉该位，再对x-1位置1，重复直到0，就可以得到
这个数最近平方根整数
主要是让大家记住下面的结论：
所以找大素数作共钥与私钥时，不要选择两个数很相近。也就是两个相邻近的大素数的积n，有
共钥d后，是不用分解这个n的
下面是当时要分解的大数：
ADD1D47967E6ED701852554F88EEE22C416B71A26F3961AE922CFD6ECEC39D73=N
它的平方根用我写的程序求得
D2F1F1429A4A565657B25A75341392CD
也就是在这里x为：
D2F1F1429A4A565657B25A75341392CE
另给出当时从网上下载得程序分解后数据是：
D2F1F1429A4A565657B25A75341392C5=Q
D2F1F1429A4A565657B25A75341392D7=P
[[i] 本帖最后由 softice_debug 于 2007-1-7 20:29 编辑 [/i]] > 设 n^(1/2)+1 为 x。
是说n的平方根的整数部分等于x-1吧。
> x+y=q[p] x-y=p[q]
这里的[]是什么意思？ [quote]原帖由 [i]scz[/i] 于 2007-1-5 14:08 发表
> 设 n^(1/2)+1 为 x。
是说n的平方根的整数部分等于x-1吧。
是的，老大果然是搞学术啊，细致啊，当时是想求 X^2>N
结果写程序发现求的x是 x^2<n<(x+1)^2
也没有改
> x+y=q x-y=p
这里的[]是什么意思？ [/quote]
这里是或者，看来当时我想的多了 :loveliness:
把一个简单的问题搞复杂了。 我没看明白啊。
(x-1)^2<n<x^2
x+y=p
x-y=q
x^2-y^2=pq=n
无论如何无法直接得出下面这个结论啊
d=(p-1)(q-1)=n-x [quote]原帖由 [i]scz[/i] 于 2007-1-5 18:10 发表
我没看明白啊。
(x-1)^2<n<x^2
x+y=p
x-y=q
x^2-y^2=pq=n
无论如何无法直接得出下面这个结论啊
d=(p-1)(q-1)=n-x [/quote]
晕啊又写错了。:funk:
d=(p-1)(q-1)=p*q-q-q+1=n-(q+p)+1=n-2x+1 :loveliness:
[[i] 本帖最后由 softice_debug 于 2007-1-5 21:44 编辑 [/i]] 今天又思考一下，发现后面的检测部分，也可以改为，算出它的平方根整数x后
作n-（x+1）^2,如果此数正好是等于一个数的平方就可以了。 你改一下你最上面的那篇吧。把那些变量统一到一个上下文中，别人好看一些。
页:
[1]