day2,

题目描述

分析

RSA加密, 对于CTF选手来说, 实在太熟悉了, 直接

http://factordb.com/ 分解 n

得到 p = 891234941, q = 1123984201

1
2
3
4
5
6
7
8

import gmpy2
n = 1001733993063167141
d = 212353
c = 20190324
p = 891234941
q = 1123984201
e = gmpy2.invert(d, (p-1)*(q-1))
print(gmpy2.powmod(c, e, n))

得到明文 579706994112328949

但是在赛场上肯定是不能调用这些包的, 所以趁此机会, 把相关的 分解n , 求d的算法学习一下.

分解n

思路一: n算是比较小的,可以采用直接爆破,由于Python计算特别慢, 采用C++ 来把p、q 爆破出来。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include<iostream>
#include<math.h>
using namespace std;

bool isPrime(long x){
    for(long i = 2; i< sqrt(x); i++){
        if(x%i ==0)
            return false;
    }
    return true;

}

int main(){
    long n=1001733993063167141;
    long p=2;
    while(p < sqrt(n)){
        if(n%p==0 && isPrime(p) && isPrime(n / p)){
            cout<<'p:'<<p<<'\t'<<'q:'<<n/p<<endl;
            break;
        }
        if(p % 100 == 0)
            cout<<p<<endl;
        p++;
    }
    return 0;
}

求解 e

已知 $(de) \% ((p-1)(q-1)) = 1$ ， 令 $phi = (p-1) * (q-1)$

即 $d * ? - phi * k = 1$ ， k 为系数，则问号就是要求的逆元

以一个具体的例子来看 $701\times?-1848\times k=1$

step1 先用辗转相除法，"求" 701和1848的最大公因数gcd

设整数a，b不同时为0， 则存在一对整数m，n，使得gcd(a, b) = am + bn

Step 2 推出相邻式子的关系

根据
\( gcd(a,b) = gcd(b, a\%b) \)

已知
\( gcd(a,b)=ax+by\\a\%b = a-(a//b)*b\\gcd(b,a\%b)=bx'+((a-(a//b)*b)*y')=ay'+b(x'-a//b*y') \)
推得
\( x = y'\\y=x'-a//b*y' \)

Step 3 扩展欧几里得

从Step1中，最后得出1和0可以列出$a1+b0=gcd(a,b)=1$这一式子， 再根据Step2推得的$x = y'$可以一步一步往上代入，以此类推，从而推出每一步的因子x和y，顺序如下

推到刚开始的1848和701后，我们得到y为29，即为所求的逆元。

注意：如果得到的y为负数，需要取模才能得到逆元。

容易验证： 701 * 29 = 1 （mod 1848）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def ext_gcd(a, b): #扩展欧几里得算法    
    if b == 0:          
        return 1, 0, a     
    else:         
        x, y, gcd = ext_gcd(b, a % b) #递归直至余数等于0(需多递归一层用来判断)        
        x, y = y, (x - (a // b) * y) #辗转相除法反向推导每层a、b的因子使得gcd(a,b)=ax+by成立         
        return x, y, gcd
    
def computeD(fn, e):
    (x, y, r) = ext_gcd(fn, e)
    #y maybe < 0, so convert it
    if y < 0:
        return fn + y
    return y

e = computeD((p-1)*(q-1), d)
print(e)