常用于密码学中的算法

发表于 | 分类于 |

0x0 前言

最近做了不少密码学的题目，对于常见的RSA密钥攻击已经非常熟悉，但是对于比较特殊的密码学攻击手段，我却不甚清楚。下面主要讲解的是几种常见的算法。

0x1 baby step giant step算法

baby step giant step算法常用于ACM竞赛中，该算法的目的是让$a^x=b(mod\ p)$ 求解的速度更快，核心是利用hash表查询的速度较普通查询方式快，当然同样是用空间换时间的一种思想。大概的时间复杂度$O(\sqrt{p}\ )$

设$m=\lceil\sqrt{p}\ \rceil$

那么可以设$x=i*m-j$

所以原式等价于 $a^{i*m-j}=b(mod\ p) $

也即 $(a^{m})^i=b*a^j$

枚举$j$ (从0-m)，将$b*a^j$ 存入hash表中

枚举i(范围1-m)，从hash表中寻找第一个满足$(a^{m})^i=b*a^j$ 的解

此时$x=i*m-j$

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll;
map<ll,int>mp;
ll p,a,b;
ll n,m,now,ans,t;
bool flag;
ll fast_pow(ll x)
{
    ll sum = 1;
    ll aa = a;
    while (x>0)
    {
        if (x&1) 
            sum = (sum*aa)%p;
        x = x>>1;
        aa = (aa*aa)%p;
    }
    return sum;
}
int main()
{
    while(scanf("%lld%lld%lld",&p,&a,&b)!=EOF)
    {
        if(a%p==0)
        {
            printf("no solution\n");
            continue;
        }
        mp.clear();
        m = ceil(sqrt(p));
        flag = false ;
        now = b%p;        //b*a^j 当j==0时 
        mp[now] = 0;
        for(int i=1;i<=m;++i)
        {
            now = (now*a)%p;
            mp[now] = i;
        }
        t = fast_pow(m);
        now = 1;
        for(int i=1;i<=m;++i)    //枚举 (a^m)^i
        {
            now = (now*t)%p;
            if(mp[now])
            {
                flag = true;
                ans = i*m-mp[now];
                printf("%lld\n",(ans%p+p)%p);    //printf("%lld\n",(ans%p+p)%p);
                break;
            }
        }
        if(!flag) printf("no solution\n");
    }
    return 0;
}

0x2 Pohlig-Hellman算法

此算法应用于密码学中比bsgs算法更广，而且效果也更佳！（因为bsgs算法所能求解的p值不能太大，位数多了就不能在有限时间内跑完）

原理：

问题： 已知a,b,p,以及p-1的分解质因数，求x使得 $a^x=b(mod\ p)$

设 $p-1=p_1^{e_1}*p_2^{e_2}...p_k^{e_k}$

若能有 $k$ 组可用的等式 $x=x_i\ (mod\ p_i^{e_i})$ ，就可以用中国剩余定理求解出 $x(mod\ p-1)$

2.1 求解$x_i$

对于 $p_i$ ，设 $x_i=c_0+c_1*p_i+c_2*p_i^2...c_{e_i-1}*p_i^{e_i-1}$ ，则 $x=x_i+s*p_i^{e_i}$

求解 $c_0$ ：

$b^{(p-1)/p_i}=(a^x)^{(p-1)/p_i}\ mod\ p$

$=(a^{c_0+c_1*p_i+c_2*p_i^2...c_{e_i-1}*p_i^{e_i-1}+s*p_i^{e_i}})^{(p-1)/p_i} \ mod\ p$

$=(a ^{c_0})^{(p-1)/p_i}\ mod\ p$

由于 $b^{(p-1)/p_i}$ 已知， 而 $c_0$ 取值范围只在$[0,p_i-1]$ ，因而在 $p_i$ 不是特别大的时候，完全是可解的。

有心的同学会发现，这个求解只需要在 $O(\lceil \sqrt{p_i} \rceil)$ 时间内就可求解，使用的仍是大步小步的思想。

设 $m=\lceil \sqrt{p_i}\ \rceil $ ，$c_0 = u*m - v$

则上式可表示为 $b^{(p-1)/p_i}*(a^{(p-1)/p_i})^v = (a^{m*(p-1)/p_i})^u$

利用hash表可以快速求解出来！

求解 $c_i $ :

基于上面的表达式，我们可以快速求解出$c_0$ 等值，然后求解$c_1$ ，依次求解，最终可以将所有解求出来。

组合：

$x_i=c_0+c_1*p_i+c_2*p_i^2+...+c_{e_i-1}*p_i^{e_i-1}$

2.2 中国剩余定理求解x

2.3 范例

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
Let the prime p = 8101, and a generator of Z(8101) be a = 6. Find x so that
a^x = 7531 mod 8101.
Observe that p-1 = 8100 = (2^2)(3^4)(5^2), is a product of small primes. We shall determine the numbers x2 = x mod (2^2), x3 = x mod (3^4) and x5 = x mod (5^2).
Determination of x2.
Since x2 is a number mod 4, we have x2 = c0 + c1 (2), with the coefficients being either 0 or 1. We determine these coefficients as follows.
7531^(p-1)/2 = 7531^4050 = -1 and as this = a^(c0*(p-1)/2), we have c0 = 1.
Now, divide 7531 by a^c0 to get
7531^(a-1) = 7531^(6751) = 8006 mod p.
8006^(p-1)/4 = 8006^2025 = 1 and as this = a^(c1*(p-1)/2), we have c1 = 0.
x2 = c0 + c1 (2) = 1 + 0(2) = 1.
Determination of x3.
Since x3 is a number mod 81, we have x3 = c0 + c1 (3) + c2 (9) + c3 (27), with the coefficients being either 0, 1 or 2. It will be of use to know the numbers a^(p-1)/3 = 5883, and a^(2*(p-1)/3) = 2217.
7531^(p-1)/3 = 2217, so c0 = 2.
Now divide 7531 by ac0 to get
7531^(a-2) = 6735 mod p.
6735^(p-1)/9 = 1, so c1 = 0.
Now divide 6735 by a3c1 to get
6735(a0) = 6735 mod p.
6735^(p-1)/27 = 2217, so c2 = 2.
Now divide 6735 by a9c2 to get
6735^(a-18) = 6992 mod p.
6992^(p-1)/81 = 5883, so c3 = 1.
x3 = 2 + 0(3) + 2(9) + 1(27) = 47.
Determination of x5.
Since x5 is a number mod 25, x5 = c0 + c1 (5), with the coefficients being either 0, 1, 2, 3 or 4. We need to compute a^(p-1)/5 = 3547, a^(2(p-1)/5) = 356, a^(3(p-1)/5) = 7077, a^(4(p-1)/5) = 5221.
7531^(p-1)/5 = 5221, so c0 = 4.
Divide 7531 by a^c0 to get
7531(a-4) = 7613 mod p.
7613^(p-1)/25 = 356, so c1 = 2.
x5 = 4 + 2(5) = 14.
Determination of x.
We now use the Chinese Remainder Theorem to compute the common solution of the congruences,
x = 1 mod 4
x = 47 mod 81
x = 14 mod 25.
M1 = 8100/(4) = 2025 
y1 = M1-1 mod 4, y1 = 1.
M2 = 8100/81 = 100
y2 = M2-1 mod 81, y2 = 64.
M3 = 8100/25 = 324
y3 = M3-1 mod 25, y3 = 24.
x = 1(2025)(1) + 47(100)(64) + 14(324)(24) = 6689 mod 8100.

上文转载于 Pohlig-Hellman范例

相对于用上述方式进行计算，我们其实可以直接使用sage来快速获取结果：

1
2
3
b = mod(6,8101)
a = 7531
discrete_log(a,b)

0x3 Pollard’s rho算法

Pollard’s rho算法是一种常用的因数分解算法，对于分解因子较小的组合数特别有用。对于一个正整数n，在一般情况下，我们主要使用的是枚举1到n^(1/2)来求n的因子，所以算法复杂度是O(n^(1/2))。但是实际上有更好的办法，那就是Pollard's Rho算法，这个算法是一个随机化的算法，简单的说不是完全靠谱，一般我们认为它的平均算法复杂度是O(n^(1/4))。

3.1 通过 𝐁𝐢𝐫𝐭𝐡𝐝𝐚𝐲 𝐓𝐫𝐢𝐜𝐤 提高概率

我们随即地从[1,N]中选择一个数，这个数是 p 或者 q 的可能性是非常小的，所有我们不得不重复运行算法来提高概率。那么，我们现在可以提出一个不同的问题：
不再只选取一个整数，我们能够选取 𝑘 个数，并问是否存在𝑥𝑖 − 𝑥𝑗能够整除N

当 $k=\sqrt{N}$ 时，可能性跳高到了50%

策略：

在区间[𝟐, 𝑵 − 𝟏]中随即选取 𝒌 个数，𝒙𝟏, … … , 𝒙𝒌
判断是否存在𝒈𝒄𝒅(𝒙𝒊 − 𝒙𝒚 , 𝑵) > 𝟏, 若存在，𝒈𝒄𝒅(𝒙𝒊 − 𝒙𝒚 ,𝑵) 是𝑵的一个因子 ( 𝒑 或 𝒒 )

但是很早就出现了一个问题，我们需要选取大约 𝑁^1/4 个数，
这个数量太大了，以至于我们并不能将其存放在内存中

3.2 Pollard‘s rho算法详解

为了解决数太多无法存储的问题，Pollard′s rho algorithm 只将两个数存放在内存中。

我们并不随机生成 k 个数并两两进行比较，而是一个一个地生成并检查连续的两个数。反复执行这个步骤并希望能够得到我们想要的数。我们使用一个函数来生成伪随机数。换句话说，我们不断地使用函数 𝑓 来生成（看上去或者说感觉上像的）随机数。并不是所有的函都能够这样做，但是有一个神奇的函数可以。它就是

$𝑓(𝑥) = ( 𝑥^2 + 𝑎 ) mod 𝑁$

你可以发现对于大部分的数据这个算法能够正常运行，但是对于某些数据，它将会进入无限循环。为什么呢？这是因为存在 𝑓 环的原因。当它发生的时候，我们会在一个有限数集中进行无限循环。

例如，我们可以构造一个伪随机函数并生成如下伪随机数：

1
2, 10, 16, 23, 29, 13, 16, 23, 29, 13 … …

在这个例子中，我们最终将会在16, 23, 29, 13这个圈中无限循环，永远找不到因子。

那么，如何探测环的出现呢？

一种方法是记录当前产生过的所有的数𝑥1, 𝑥2, … … 𝑥𝑛,并检测是否存在𝑥𝑙 = 𝑥𝑛(𝑙 < 𝑛)。在实际过程中，当 𝑛 增长到一定大小时，可能会造成的内存不够用的情况。

另一种方法是由Floyd发明的一个算法，我们举例来说明这个聪明而又有趣的算法。假设我们在一个很长很长的圆形轨道上行走，我们如何知道我们已经走完了一圈呢？当然，我们可以像第一种方法那样做，但是更聪明的方法是让 A 和 B 按照 B 的速度是A 的速度的两倍从同一起点开始往前走，当 B 第一次敢上 A 时(也就是我们常说的套圈)，我们便知道，B 已经走了至少一圈了。

3.3 算法实现

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <iostream> 
#include <cstdio> 
#include <algorithm>  
#include <cmath>  
#include <cstring>  
#include <map>  
using namespace std;
const int times = 50;
int number = 0;
map<long long, int>m;
long long Random( long long n )
{
	return ((double)rand( ) / RAND_MAX*n + 0.5);
}
long long q_mul( long long a, long long b, long long mod ) //快速乘法取模
{
	long long ans = 0;
	while(b)
	{
		if(b & 1)
		{
			ans += a;
		}
		b /= 2;
		a = (a + a) % mod;
	}
	return ans;
}
long long q_pow( long long a, long long b, long long mod ) //快速乘法下的快速幂，叼
{
	long long ans = 1;
	while(b)
	{
		if(b & 1)
		{
			ans = q_mul( ans, a, mod );
		}
		b /= 2;
		a = q_mul( a, a, mod );
	}
	return ans;
}
bool witness( long long a, long long n )//miller_rabin算法的精华
{
	long long tem = n - 1;
	int j = 0;
	while(tem % 2 == 0)
	{
		tem /= 2;
		j++;
	}
	
	long long x = q_pow( a, tem, n ); //得到a^(n-1) mod n
	if(x == 1 || x == n - 1) return true;
	while(j--)
	{
		x = q_mul( x, x, n );
		if(x == n - 1) return true;
	}
	return false;
}
bool miller_rabin( long long n )  //检验n是否是素数
{
	if(n == 2)
		return true;
	if(n < 2 || n % 2 == 0)
		return false;
	for(int i = 1; i <= times; i++)  //做times次随机检验
	{
		long long a = Random( n - 2 ) + 1; //得到随机检验算子 a
		if(!witness( a, n ))  //用a检验n是否是素数
			return false;
	}
	return true;
}
long long gcd( long long a, long long b )
{
	if(b == 0)
		return a;
	return gcd( b, a%b );
}
long long pollard_rho( long long n, long long c )//找到n的一个因子
{
	long long x, y, d, i = 1, k = 2;
	x = Random( n - 1 ) + 1;
	y = x;
	while(1)
	{
		i++;
		x = (q_mul( x, x, n ) + c) % n;
		d = gcd( y - x, n );
		if(1<d&&d<n)
			return d;
		if(y == x)//找到循环，选取失败，重新来
			return n;
		if(i == k) //似乎是一个优化，但是不是很清楚
		{
			y = x;
			k <<= 1;
		}
	}
}
void find( long long n, long long c )
{
	if(n == 1)
		return;
	if(miller_rabin( n ))
	{
		m[n]++;
		number++;
		return;
	}
	long long p = n;
	while(p >= n)
		p = pollard_rho( p, c-- );
	find( p, c );
	find( n / p, c );
}
int main( )
{
	long long tar;
	while(cin >> tar)
	{
		number = 0;
		m.clear();
		find( tar, 2137342 );
		printf( "%lld = ", tar );
		if(m.empty())
		{
			printf( "%lld\n", tar );
		}
		for(map<long long, int>::iterator c = m.begin(); c != m.end();)
		{
			printf( "%lld^%d", c->first, c->second );
			if((++c) != m.end())
				printf( " * " );
		}
		printf( "\n" );
	}
	return 0;
}

0x4 Pollard's p-1 算法

4.1 smooth与powersmooth

如果一个整数的所有素因子都不大于B，我们称这个整数是B-Smooth数

如果一个整数的所有素因子的对应指数次幂不大于B，我们称这个整数是B-powersmooth数

$720({2^4}{3^2}{5^1})$ 是一个5-smooth数，6-smooth数，7-smooth数

但5^1\<3^2\<2^4=16，所以它也是一个16-powersmooth数

4.2 原理解释

n 是一个合数，其中一个质数位p，由费马小定理有：$a^{K(p-1)}=1(mod\ p)$

如果 $x=1(mod\ p)$ ，就有 $p|gcd(x-1,n)$

这个算法的思想就是构造p-1，其有多个素因子，并且每个素因子的powersmooth不超过B，开始时随机选取一个x， 计算 $x^w\ mod\ n$ , $w=\prod_{primes\ q\leq\ B}\ q^{\lfloor \log_{q}{B}\rfloor}$ ， 如果有$gcd(x^w-1, n)$ 不等于1， 那么我们就相当于找到一个素数p了

4.3 算法

Inputs: n: a composite number
Output: a nontrivial factor of n or failure

  1. select a smoothness bound B
  2. define $M=\prod_{primes\ q\leq\ B}\ q^{\lfloor \log_{q}{B}\rfloor}$ (note: explicitly evaluating M may not be necessary)
  3. randomly pick a coprime to n (note: we can actually fix a, e.g. if n is odd, then we can always select a = 2, random selection here is not imperative)
  4. compute $g = gcd(a^M − 1, n)$ (note: exponentiation can be done modulo n)
  5. if 1 < g < n then return g
  6. if g = 1 then select a larger B and go to step 2 or return failure
  7. if g = n then select a smaller B and go to step 2 or return failure

这里的larger B和smaller B有选择性的方法，具体是啥我也不太清楚！

4.4 范例

If we want to factor the number n = 299.

  1. We select B = 5.
  2. Thus $M = 2^2 × 3^1 × 5^1$.
  3. We select a = 2.
  4. $g = gcd(a^M − 1, n) = 13$.
  5. Since 1 < 13 < 299, thus return 13.
  6. 299 / 13 = 23 is prime, thus it is fully factored: 299 = 13 × 23.

0x5 Williams's p + 1 算法

Pollard's p-1算法比较容易懂，但是Williams’s p+1算法却不怎么让人明白！

5.1 算法

选择大于2的整数A，用其生成一个卢卡斯序列：

$V_0=2, V_1=A,V_j=AV_{j-1}-V_{j-2}$ (貌似实际上用的是下面给出的算法)

对于任意的奇素数 $p|gcd(N, V_M -2)$ ，都有M是 $p-(D/p)$ 的因子， $D=A^2-4$ ，而 $(D/p)$ 为雅可比符号

当 $(D/p)=-1$ ，所表示的就是Williams's p+1算法；而 $(D/p)=1$ 时，表示的就是Pollard's p-1算法

对于不同的M，我们计算 $gcd(N, V_M -2)$ ，当结果不等于1或者N时，我们得到N的非平凡因子

下面是计算V的第M个值的算法！！

1
2
3
4
5
6
7
8
9
10
x=B           
y=(B^2-2) mod N     
for each bit of M to the right of the most significant bit
  if the bit is 1
    x=(x*y-B) mod N 
    y=(y^2-2) mod N 
  else
    y=(x*y-B) mod N 
    x=(x^2-2) mod N 
V=x

5.2 范例

With N=112729 and A=5, successive values of V_Mare:

  • V1 = 5
  • V2=23
  • V3=12098
  • V4=87680
  • V5=53242
  • V6=27666
  • V7=110229

At this point, gcd(110229-2,112729) = 139, so 139 is a non-trivial factor of 112729. Notice that$ p+1 = 140 = 2^2 × 5 × 7$. The number 7! is the lowest factorial which is multiple of 140, so the proper factor 139 is found in this step.

Using another initial value, say A = 9, we get:

  • V1=9
  • V2=79
  • V3=41886
  • V4=79378
  • V5=1934
  • V6=10582
  • V7=84241
  • V8=93973
  • V9=91645

At this point gcd(91645-2,112729) = 811, so 811 is a non-trivial factor of 112729. Notice that $p-1 = 810 = 2 × 5 × 3^4$. The number 9! is the lowest factorial which is multiple of 810, so the proper factor 811 is found in this step. The factor 139 is not found this time because p-1 = 138 = 2 × 3 × 23 which is not a divisor of 9!

As can be seen in these examples we do not know in advance whether the prime that will be found has a smooth p+1 or p-1.

0x6 ecm

ecm全称elliptic-curve factorization method。它是一个次指数级运算时间算法，主要用于整数分解。它是第三快的整数分解方法；第二快的是multiple polynomial quadratic sieve；最快的是general number field sieve.

它非常适合寻找小整数因子，并且它仍是分解超过50-60位数字的最佳算法。其运算时间有最小的质数p来决定。

6.1 算法原理

  1. 选择整数域上的椭圆曲线 $y^2=x^3+ax+b (mod n)$ 以及非平凡点 $P(x_0, y_0)$ 。这个过程其实可以先任取a，然后 $b=y_0^2-x_0^3-ax_0 (mod n)$
  2. 对于kP，若其切线u/v有gcd(u,n)=1，而v=0(mod n)，那么u/v表示无穷远，最终会结果为无穷远点，且此时得到的曲线abel群正常。然而，若gcd(v,n)不为1或者n，那么此时仍然会产生一个非平凡的无穷远点，此时的曲线abel群并不是最大的群group (mod n)；但是我们找到了n的因子gcd(v,n)
  3. 我们使用2P，3(2P)，4(3!P)这种方式产生新点，由于B!P中的B!会在一定时间内成为曲线域的大小的倍数，所以当到达其倍数时将会成为无穷远点。
    • 如果完成所有的运算，但并未遇到可逆的分母，我们将选择其他的曲线
    • 若遇到kP= ∞，但是坟墓v=0(mod n)，我们将重新选择一条曲线。
    • 若遇到gcd(v,n)不为1或n，则得到正确的解

可以看到该算法的运算时间为$exp[(\sqrt{2}+o(1))\sqrt{lnp\ ln\ lnp}]$

6.2 范例

The following example is from Trappe & Washington (2006), with some details added.

We want to factor n = 455839. Let's choose the elliptic curve $y^2 = x^3 + 5x – 5$, with the point P = (1, 1) on it, and let's try to compute (10!)P.

The slope(斜率) of the tangent line(切线) at some point A=(x, y) is $s = (3x^2 + 5)/(2y) (mod n)$. Using s we can compute 2A. If the value of s is of the form a/b where b > 1 and gcd(a,b) = 1, we have to find the modular inverse of b. If it does not exist, gcd(n,b) is a non-trivial factor of n.

First we compute 2P. We have s(P) = s(1,1) = 4, so the coordinates of 2P = (x′, y′) are $x′ = s^2 – 2x = 14$ and $y′ = s(x – x′) – y = 4(1 – 14) – 1 = –53$, all numbers understood (mod n). Just to check that this 2P is indeed on the curve: $(–53)^2 = 2809 = 14^3 + 5·14 – 5$.

Then we compute 3(2P). We have s(2P) = s(14,-53) = –593/106 (mod n). gcd(455839, 106) = 1, and working backwards (a version of the extended Euclidean algorithm): 106^(−1) = 81707 (mod 455839), and –593/106 = –133317 (mod 455839). Given this s, we can compute the coordinates of 2(2P), just as we did above: 4P = (259851, 116255). After this, we can compute 3(2P)=4P+2P.

We can similarly compute 4!P, and so on, but 8!P requires inverting 599 (mod 455839). The Euclidean algorithm gives that 455839 is divisible by 599, and we have found a factorization 455839 = 599·761.

The reason that this worked is that the curve (mod 599) has $640 = 2^7·5$ points, while (mod 761) it has 777 = 3·7·37 points. Moreover, 640 and 777 are the smallest positive integers k such that kP = ∞ on the curve (mod 599) and (mod 761), respectively. Since 8! is a multiple of 640 but not a multiple of 777, we have 8!P = ∞ on the curve (mod 599), but not on the curve (mod 761), hence the repeated addition broke down here, yielding the factorization.

0x7 smooth质数

7.1 p - 1 光滑

当 p 是 N 的因数，并且 p - 1 是光滑的时候，可能可以使用 Pollard's p − 1 算法来分解 N，但是也不是完全可以成功的。

7.2 p + 1 光滑

当 p 是 n 的因数，并且 p + 1 是光滑的时候，可能可以使用 Williams's p + 1 算法来分解 N，但是也不是完全可以成功的。

7.3 primefac包

上面的两种光滑，都可以使用包primefac 来做

primefac是一个贼好用的工具，环境一般在linux上，cygwin上也能用，运行速度贼快！

不能在windows上使用的原因

在Windows中，多进程multiprocessing使用的是序列化pickle来在多进程之间转移数据，而socket对象是不能被序列化的，但是在linux操作系统上却没问题，因为在linux上多进程multiprocessing使用的是fork，所以在windows上可以改用多线程。

常用的命令行使用方式：

1
2
python -m primefac [-vs] [-v|--verbose] [-s|--summary] [-t=NUM] [-r=NUM]
                [-m=[prb][,p-1][,p+1][,ecm][,mpqs]] rpn
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
rpn is an expression in revese Polish notation and is evaluated using integer arithmetic. Each number that remains on the stack after evaluation is then factored.
-t sets the trial division limit; the default value is 1000. Use -t=inf to use trial division exclusively.
-r sets the number of rounds of Pollard’s rho algorithm to try before calling a factor “difficult”. The default value is 42,000. Use -r=inf to use Pollard’s rho exclusively once the trial division is completed.
If verbosity is invoked, we indicate in the output which algorithm produced which factors during the multifactor phase.
If the -s (or --summary) flag is absent, then output is identical to the output of the GNU factor command, except possibly for the order of the factors and, if verbosity has been turned on, the annotations indicating which algorithm produced which factors.
If the -s (or --summary) flag is present, then output is modified by adding a single newline between each item’s output, before the first item, and after the last item. Each item’s output is also modified by printing a second line of data summarizing the results by describing the number of decimal digits in the input, the number of decimal digits in each prime factor, and the factors’ multiplicities
The -v and -s flags may be combined into a single flag in either order — i.e., into -vs or -sv.
The -m= flag controls the functions used during the multifactor phase. The options are prb, p-1, p+1, ecm, and mpqs, representing Pollard’s rho, Pollard’s p-1, Williams’ p+1, the elliptic curve method, and the multiple polynomial quadratic sieve, respectively. The options must be separated by commas. The options can be repeated: if prb is listed twice, for example, then multifactor will run two instances of pollardRho_brent simultaneously. In the case of prb and ecm, this decreases the expectation value of the time to find a factor, whereas the other three algorithms (p-1, p+1, and MPQS) have no randomized component so that running duplicate instances of these three algorithms confers no benefit. We therefore ignore repeated listings of the latter three methods: for example, calling
1
python -m primefac -m=prb,prb,ecm,ecm,ecm,mpqs,mpqs 38 ! 1 +

从上面的说明中可以看出，primefac可以使用多种常用的分解质因数的方法，而rpn时使用逆波兰表示法表示的数。

7.4 整数分解的方法

0x8 ctf中范例

8.1 2017 SECCON very smooth

将题目从文件中binwalk出来之后，发现了一个证书，给出了大整数n

1
2
3
4
python -m primefac -vs -m=p+1  149767527975084886970446073530848114556615616489502613024958495602726912268566044330103850191720149622479290535294679429142532379851252608925587476670908668848275349192719279981470382501117310509432417895412013324758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897
149767527975084886970446073530848114556615616489502613024958495602726912268566044330103850191720149622479290535294679429142532379851252608925587476670908668848275349192719279981470382501117310509432417895412013324758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897: p+1 11807485231629132025602991324007150366908229752508016230400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 12684117323636134264468162714319298445454220244413621344524758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897
Z309  =  P155 x P155  =  11807485231629132025602991324007150366908229752508016230400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 x 12684117323636134264468162714319298445454220244413621344524758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897

至于这里为什么只能用Williams's p + 1 算法而不能用 Pollard's p − 1 算法分解，其原因可能如下：

1
2
3
4
5
6
7
8
9
➜ python -m primefac -vs 1180748523162913202560299132400715036690822975250801623040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002
1180748523162913202560299132400715036690822975250801623040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002: 2 7 43 503 761429 5121103123294685745276806480148867612214394022184063853387799606010231770631857868979139305712805242051823263337587909550709296150544706624823
Z154  =  P1 x P1 x P2 x P3 x P6 x P142  =  2 x 7 x 43 x 503 x 761429 x 5121103123294685745276806480148867612214394022184063853387799606010231770631857868979139305712805242051823263337587909550709296150544706624823
➜ python -m primefac -vs 1180748523162913202560299132400715036690822975250801623040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 
1180748523162913202560299132400715036690822975250801623040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
Z154  =  P1^185 x P1^62 x P1^97  =  2^185 x 3^62 x 5^97

其实从此处看出，对于 p-1 确实有很多小因子，但是个数太多，这就会使得进行枚举的时候出现指数爆炸的情况，因此没有分解出来。

8.2 2018 Backdoor Awesome-mix2

这道题是一道验证题，但是需要解决一个问题：

已知s，m，（都是不超过1024位的大整数），求使得 $s^e=m(mod n)$ 的 e和n，约束条件是:

$e>=3, n>=s, n.bit_length <= 1025$

这个时候可以让n为smooth素数，也即Pollard's p-1，然后就可以求出e