rsa已知e*d分解N
Created At :
Views 👀 :
基本特征
前面说过RSA的基本参数，我们知道ed≡1 mod (p-1)(q-1).
这个题型是说，当我们从题目中得到e*d和N的值时，如何通过分解N来解密ｒｓａ
简述
输入e,d
e,d都是奇数，因为它们相对于(p-1)*(q-1)都是素数
通过建立e*d=1 mod Φ(N)
让e*d-1=2^k * r(r 是奇数)
让(1<b<N)，从中随机挑选b
如果gcd(b,N)>1,我们就停止
否则 b∈ZN, 那么b^(ed-1)=1 mod N
让ed-1=2^k *r 当r是奇数，b^(ed-1)=1 mod N ,求mod N\
a0 = b^r, a1 = (a0)^2, a2 = (a1)^2,…, ak = (ak-1)^2.
1
2
| 1.我们知道ak=1 让j是aj =1mod N 的最小指数
2. 如果0<j并且a(j-1) 不等于N-1那么a(j-1)是关于1mod N 的一个非平凡根
|
定理
1
2
3
4
5
6
7
8
9
| 至少有一半的b，1<b<N，满足是1 mod N 的一个非平凡根
证明过程：
如果x^2=1 mod N 并且 x不等于1，N-1 那么gcd(x+1,N)>0
证明过程：x^2 -1 =(x+1)*(x-1) . N除以乘积，但是x不等于N-1,1.
因此N不能除以(x-1)或者(x+1)
所以p必须除以其中一个,q除以另外一个
|
范围
1
2
3
4
5
6
7
8
| 输入d,e,N,随机选择b
让e*d-1=2^k *r (r是奇数)，b^(e*d-1)=1 mod N
求mod N
a0 = b^r, a1 = (a0)^2, a2 = (a1)^2,…, ak = (ak-1)^2.
由定理可知，对于概率大于 0.5，aj中的一个是1模N的非平凡平方根，这样的根产生N的因式分解
所有的操作都是在log N内
|
例题
1
2
3
4
5
6
7
8
9
10
| N=2773 e=17 d=157
计算过程:
e*d-1=2668=2^2 *667
随机挑选b，进行mod 2773的操作
b=7 7^667=1 mod N 不好
b=8 8^667=471 mod N, 并且 471^2=1 mod N,所以471是1 mod 2773的非平凡平方根
Gcd(472,N)=59 gcd(470,N)=47
2773//59=47
|
总结：
1
2
3
4
5
| 1、设定k=e*d-1
2、从2到N-1的范围内随机选择一个数字g
3、将k写成2^t *r 的形式
4、如果t能被2整除，那么t=t/2,并且x=g^t mod N ,直到x>1
5、在满足x>1的情况下，如果y=gcd(x-1,N)>1,那么其中一个因数p=y， 另一个因数为N/y,如果不满足条件，返回步骤2，重新选择数字g
|
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1259742453@qq.com
