水了三题公钥的Crypto题,都是RSA的,而且都是和n的分解相关的

bigRSA·

题目给了两个n,然后后面是两个n对应的正常的两次加密,按照这个信息量很自然的就把n1和n2做一次gcd,发现是不互素的,所以可以分解两个n,然后求出d,再做两次解密得到m。

但是,在实际用Sage操作的时候发现直接用Sage的pow是有点问题的:

1
2
3
# 'SageMath version 9.1, Release Date: 2020-05-20'
print(pow(pow(123, e, n1), e*d2, n2) == pow(123, e, n1)) # False
print(pow(int(pow(123, e, n1)), e*d2, n2) == pow(123, e, n1)) # True

用py写的话则没事:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from gmpy2 import invert, gcd

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

p = gcd(n1, n2)
q1 = n1//p
q2 = n2//p
assert p*q1==n1 and p*q2==n2

phi1 = (p-1)*(q1-1)
phi2 = (p-1)*(q2-1)
d1 = invert(e, phi1)
d2 = invert(e, phi2)

m = pow(c, d2, n2)
m = pow(m, d1, n1)
flag = long_to_bytes(int(m))
print(flag)
#SangFor{qSccmm1WrgvIg2Uq_cZhmqNfEGTz2GV8}

RSA?·

首先p和q是256位的素数,直觉上是可以直接暴力分解的:

题目的提示是RSA,直接看代码的话很难看出和RSA有什么联系,可以先把loop转换成数学的形式,设:

M=[xyDyx]v=(x,y)M = \begin{bmatrix} x & y \\ Dy & x \\ \end{bmatrix} \\ v = (x, y)

那么loop在做的事其实是(这里中括号指的是取第一行):

vMe1=(Me)[0]v*M^{e-1} = (M^e)[0]

看到MeM^e猜想是个矩阵的RSA,自己随便生成一些小数据再验证一下,发现都有:

Mϕ=M (mod n)M^\phi = M\ (mod\ n)

猜想成立。现在n可以分解,就是ϕ\phi知道,e知道,可以求出d;(Me)[0](M^e)[0]知道,如果可以求出Me (mod n)M^e\ (mod\ n)的话,就可以像RSA那样用(Me)d=M (mod n)(M^e)^d = M\ (mod\ n)解密了。

根据观察,可以得到:

(Mx)[1][0]=D(Mx)[0][1](Mx)[1][1]=(Mx)[0][0](M^x)[1][0] = D*(M^x)[0][1] \\ (M^x)[1][1] = (M^x)[0][0]

于是就可以求出(Me)[1][0](M^e)[1][0](Me)[1][1](M^e)[1][1],即求出Me (mod n)M^e\ (mod\ n),脚本:

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
# sage
from Crypto.Util.number import *
from gmpy2 import invert, iroot

n = 13390709926509813526471364597371124446888078365567927211781799241724742352679484983709219580483800891886832613684875066109177882219522305348565532970795023
v = (5404548088049249951619519701935576492239293254135836357417714329205323074367876875480850741613547220698045360461761929952847796420174204143917852624050110, 2110372753170830610718226848526649992911771424441223687775304654852191999130502986109306355582366065947895295520226816523397652918227241733632791793362785)
a = 1762039418842677123086894939949574689744108610561557889235294034870342076452734215004689409493802437034960516295735815195656138656970901855976802991519141
D = (a*a)%n
e = 65537

p = 115718235064789220654263009993128325569382592506655305434488398268608329541037
q = 115718235064789220654263009993128324769382192706654302434478391267607309966379
assert p*q==n

def fastPow(M, x, n):
if x==0:
return identity_matrix(len(M.columns()))
res = fastPow(M, x//2, n)
if x%2 == 1:
return res*res*M % n
else:
return res*res % n

phi = (p-1)*(q-1)
d = e.inverse_mod(phi)

M = matrix([[v[0], v[1]], [v[1]*D, v[0]]])
#m = M^d%n
m = fastPow(M, d, n)
Y = m[0][1]
print('Y = %s' % Y)

print(long_to_bytes(int(Y)))
# GWHT{pell_equation_is_very_interesting}

easyRSA·

这是道让人非常头疼的题… …当时其实前一晚就已经有思路了,想着第二天九点才结束,八点起来应该也搞得定吧,谁知道后来代码+运行搞了四个多小时。。。(不过感觉上是非预期解?)

题目的意思是,用了这样的一个keyGen生成密钥:

p=2ga+1q=2gb+1h=2gab+a+bp = 2ga + 1 \\ q = 2gb + 1 \\ h = 2gab + a + b

p、q、h都是素数,其中g是“很大”的数,a、b是“很小的数”;整理一下可以得到:

n=pq=4g2ab+2g(a+b)+1n12=2g2ab+g(a+b)n14g2=ab+a+b2g=ab+negl()n = pq = 4g^2ab+2g(a+b)+1 \\ \frac{n-1}{2} = 2g^2ab+g(a+b) \\ \frac{n-1}{4g^2} = ab+\frac{a+b}{2g} = ab+negl()

根据最后一条式子 + 实际代码测试,有:

n14abg\sqrt{\frac{n-1}{4ab}} \approx g

因为a、b是很小的,爆破a和b就可得到g,然后得到p、q,然后就是正常的RSA解密了,于是就有脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from gmpy2 import iroot

# original
n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
gamma = 0.48

# gamma == 0.49
n = 25876225522890846556694449833494254540262333611158337123604777179863694236498355670851480908852313896681043771428258385755840617295126898560098248525302865459336697905788090823970968293147657498562477274750658646012858288861287729533422138185695389851242485849321943069495999658596606801403724051868563060097
gamma = 0.49

lbound = 2**(int(1024*(0.5-gamma))-1)
ubound = 2**int(1024*(0.5-gamma))
print(lbound, ubound)
for a in range(lbound, ubound):
print(a)
for b in range(lbound, ubound):
g = int(iroot((n-1)//(4*a*b), 2)[0])
p = 2*g*a+1
q = 2*g*b+1
if p*q==n:
print('p = %s' % p)
print('q = %s' % q)
exit(0)

经验证,当gamma是0.49的时候脚本是起作用的,但,gamma是0.48(即题目给的)的时候,算了一下要一个星期(比赛才一天啊喂… …);于是又搞了个C版本的,再算一下要两天… …;最后现学了一波C的多线程,才用了一顿饭+的时间搞了出来,最终代码:

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
//gcc get.c -lgmp -lm -lpthread -g && ./a.out
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
#include <pthread.h>

#define NT 16

typedef struct {
mpz_t* n;
mpz_t* n_1_2;
long ast;
long aed;
}para;

void* run(void* arg) {
para* par = (para*) arg;
mpz_t* n = par->n;
mpz_t* n_1_2 = par->n_1_2;
long ast = par->ast;
long aed = par->aed;
//printf("%ld, %ld\n", ast, aed);
//pthread_exit(0);
mpz_t g, p, q, n2;
mpz_inits(g, p, q, n2, 0, NULL);
for (long a=ast; a<aed; a++) {
if (a%1000 == 0) {
printf("%ld\n", a);
}
long a2 = 2*a;
for (long b=524288; b<1048576; b++) {
mpz_div_ui(g, *n_1_2, a2*b);
mpz_sqrt(g, g);

if(mpz_divisible_p(*n_1_2, g) == 1) {
gmp_printf("g = %Zd\n", g);
mpz_mul_ui(p, g, a2);
mpz_add_ui(p, p, 1);
mpz_mul_ui(q, g, 2*b);
mpz_add_ui(q, q, 1);
mpz_mul(n2, p, q);
if(mpz_cmp(*n, n2) == 0) {
printf("a = %ld\nb = %ld\n", a, b);
gmp_printf("p = %Zd\nq = %Zd\n", p, q);
mpz_clears(*n, *n_1_2, g, p, q, n2, NULL);
exit(0);
}
}
}
}
pthread_exit(0);
}

int main() {
mpz_t n, n_1_2, g, p, q, n2;
mpz_inits(n, n_1_2, g, p, q, n2, 0, NULL);
mpz_init_set_str(n, "84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039", 10);
mpz_sub_ui(n_1_2, n, 1);
mpz_div_ui(n_1_2, n_1_2, 2);

pthread_t tids[NT];
para par[NT];
long ub = 1048576;
long lb = ub/2;
long delta = lb/NT;
for (int i=0; i<NT; i++) {
par[i].n = &n;
par[i].n_1_2 = &n_1_2;
par[i].ast = lb+i*delta;
par[i].aed = lb+(i+1)*delta;
pthread_create(&tids[i], NULL, run, par+i);
}

getchar();
printf("sorry?\n");
mpz_clears(n, n_1_2, g, p, q, n2, NULL);
return 0;
}

/*
g = 4935307733735729994278290975792000228775286930114042366725719878267551012927493448259270817917227756849322072959458794406806580920723349325531114469
a = 854851
b = 1011400
p = 8437905502983445042677582637893534375137565614989838462475696727313788501904161403475771835934720130340799646782932619714906025013322551788559197469878239
q = 9983140483800634632426126985832058062766650402234684899412786169759602188949733747138853010482968306554808689182393249326088351886439191015684338347893201
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from gmpy2 import invert, lcm
import libnum

n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
e = 58337
c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668

p = 8437905502983445042677582637893534375137565614989838462475696727313788501904161403475771835934720130340799646782932619714906025013322551788559197469878239
q = 9983140483800634632426126985832058062766650402234684899412786169759602188949733747138853010482968306554808689182393249326088351886439191015684338347893201
assert p*q == n

phi = lcm(p-1, q-1)
d = invert(e, phi)
m = int(pow(c, d, n))
print(libnum.n2s(m))
# SangFor{0a8c2220-4c1b-32c8-e8c1-adf92ec7678b}

(表示最大收获就是学会C语言写多线程了。。。)