CTF_Notes_0x2

Posted on Edited on In Word count in article: 41k Reading time ≈ 37 mins.

0x01 RSA

1
2
3
A=(((y%x)**5)%(x%y))**2019+y**316+(y+1)/x
p=next_prime(z*x*y)
q=next_prime(z)

p,q能够分解得到。

最开始还想用z3库来解，但是解不出来。

wp里面的最优解法就是爆破。

exp:

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
import gmpy2 as gp
from Crypto.Util.number import *
def RSA(p,q,e,c):
    n=p*q
    f=(p-1)*(q-1)
    d=gp.invert(e,f)
    m=gp.powmod(c,d,n)
    return m
A =  2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
n =  117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
c =  41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128
p=842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569
q=139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183
e=2
for e in range(100000):
    if isPrime(e):
        try:
            m=RSA(p,q,e,c)
            flag = long_to_bytes(m)
            flag = str(flag)
            if "CTF" in flag or "flag" in flag:
                print(e,'\n',flag)
        except ZeroDivisionError:
            continue
#  b'RoarCTF{wm-l1l1ll1l1l1l111ll}'

0x02 Feistival

My friend Ridwan is interested into ciphers lately. He sent me the encrypted flag. Can you help me decrypt?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# enc.py
m, n = 21, 22
def f(word, key): #轮函数
    out = ""
    for i in range(len(word)):
        out += chr(ord(word[i]) ^ key)
    return out

flag = open("flag.txt", "r").read()

L, R = flag[0:len(flag)//2], flag[len(flag)//2:]
x = "".join(chr(ord(f(R, m)[i]) ^ ord(L[i])) for i in range(len(L)))
y = f(R, 0)

L, R = y, x
x = "".join(chr(ord(f(R, n)[i]) ^ ord(L[i])) for i in range(len(L)))
y = f(R, 0)

ciphertext = x + y
ct = open("cipher.txt", "w")
ct.write(ciphertext)
ct.close()

算法生成的字符串是由两端拼接成的。其中 再写出算法即可。

0x03 Tony Stark Needs Help

The Ten rings have announced a war against Tony Stark and James Rhodes. Ten Rings have deployed many of their soldiers and also launched many missiles. They also gave a threat of launching a nuclear missile. James Rhodes is trying to defend all kind of attack on the city and Tony Stark is looking for the base of Ten Rings to catch the Mandarin. After searching for a while, Tony Stark found the base. But the Mandarin left the base by then. Though Tony couldn't capture Mandarin in the base, but he found a very important letter.

After reading the letter, Tony understood that, he only have 1 hour to save the city from nuclear attack as there was a broadcast from Ten Rings three hours ago. And he also found a encryption programs in the computers of the base.So, now he need a decryption script to stop the nuclear attack. Can you help him to save the city by creating a decryption program?

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
# encryptor.py
secret = input("Enter your string to encrypt: ")

key = input("Enter the key: ")

secarr = []

keyarr = []

x = 0
 
def keyfunc(key,keyarr,x):

    for character in key:

        keyarr.append(ord(character))

    for i in keyarr:

        x += i

def secretfucn(secret,secarr,key,x):

    for character in secret:

        secarr.append(ord(character))

    for i in range(len(secarr)):

        if 97 <= secarr[i] <= 122:
            
            secarr[i] = secarr[i]-6
        else:
            if 65 <= secarr[i] <= 90:
                
                secarr[i] = secarr[i]-11

    if len(key) % 2 == 0:

        x = x + 1

    else:

        x = x + 3

    if x % 2 == 0:

        secarr[i] = secarr[i] + 3

    else:

        secarr[i] = secarr[i] + 2

    encrypted = ""

    for val in secarr:

        encrypted = encrypted + chr(val)

    print("Encrypted Text: " + encrypted)

            
keyfunc(key,keyarr,x)

secretfucn(secret,secarr,key,x)

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
Hey Actor,
You are doing great!
I didn't expect that you would be able to fool everybody as impressively you are doing the job!

By the way, you have something important to do now.
Go to our base in "6G:653" and launch all the normal missiles and set a timer of 4 hours for launching our "Fat Boy", I mean the nuclear one.
Take half of your army with you as you need to defend the launching site and send others after Tony and James.

I've already sent the password for activating the normal missiles.
And here are the clue keys for activating the Fat Boy:

- T3NR1NG$
- T3nR1ng$
- TenRings
- T3nR!ngs
- T3nR!ng$
- 73NR1GN$
- 73nRing$
- T3nR!nG$

I believe, you already know which one is the valid key. 
Just giving the clues to give you a simple recall.

So, get to the work! And don't forget to make a public broadcast 5 minutes before you launch the missile.

Announce a war against Tony and James.
If Tony surrenders, then stop the timer of Fat Boy.
Otherwise, let the destruction happen!

Hahahahahahaha!

Oh, the password for deactivating the nuclear missile is "IihsIb_7[^7is<inH][l_^D`Ib_;[n7iu"

The password is encrypted and I believe, you know how to decode that, my boy!

That's all for now.
Work according the instruction and then wait for my next instruction.

Regards,
Mandarin

根据题目，两段密文分别为：

1
2
6G:653
IihsIb_7[^7is<inH][l_^D`Ib_;[n7iu

密钥是多个中的一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
a=b'IihsIb_7[^7is<inH][l_^D`Ib_;[n7iu'
b=list(a)
c=''
for i in b:
    if 97 <= i+6 <= 122:
        i+=6
    else:
        if 65 <=i+11 <=90:
            i+=11
    c+=chr(i)
print(c)
print(b)
# TonyTheBadBoyGotScaredOfTheFatBou

无视x的生成，和分段移位所带来的重叠的结果。但放到加密程序后的结果与密文有出入。具体在：

题目密文：IihsIb_7[7is<inH][l_D`Ib_;[n7iu

反向加密：IihsIb_7[7is<inH][l_D`Ib_;[n7iq

可看到最后一个字符出问题，改成y就可以了。

0x04 Tony Stark Needs Help Again

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
import base64
str1 = input("Enter text to encrypt: ")
arr1 = []

l_c = ''.join(chr(c) for c in range (97,123))
u_c = ''.join(chr(c) for c in range (65,91))
l_e = l_c[13:] + l_c[:13]
u_e = u_c[13:] + u_c[:13]
so = ""
for c in str1:
    if c in l_c:
        so = so + l_e[l_c.find(c)]
    elif c in u_c:
        so = so + u_e[u_c.find(c)]
    else:
        so = so + c
d1  = { "A" : "~",
        "B" : "`",
        "C" : "@",
        "D" : "#",
        "E" : "$",
        "F" : "%",
        "G" : "^",
        "H" : "&",
        "I" : "*",
        "J" : "(",
        "K" : ")",
        "L" : "-",
        "M" : "_",
        "N" : "=",
        "O" : "+",
        "P" : "{",
        "Q" : "[",
        "R" : "]",
        "S" : ":",
        "T" : ";",
        "U" : "\'",
        "V" : "\"",
        "W" : ",",
        "X" : "<",
        "Y" : ".",
        "Z" : ">",
        "a" : "?",
        "b" : "/",
        "c" : "5",
        "d" : "1",
        "e" : "3",
        "f" : "2",
        "g" : "4",
        "h" : "9",
        "i" : "0",
        "j" : "8",
        "k" : "6",
        "l" : "7",
        "m" : "K",
        "n" : "Q",
        "o" : "F",
        "p" : "V",
        "q" : "X",
        "r" : "D",
        "s" : "S",
        "t" : "A",
        "u" : "J",
        "v" : "N",
        "w" : "M",
        "x" : "P",
        "y" : "I",
        "z" : "T",
        "~" : "A",
        "`" : "B",
        "@" : "C",
        "#" : "D",
        "$" : "E",
        "%" : "F",
        "^" : "G",
        "&" : "H",
        "*" : "I",
        "(" : "J",
        ")" : "K",
        "-" : "L",
        "_" : "M",
        "=" : "N",
        "+" : "O",
        "{" : "P",
        "[" : "Q",
        "]" : "R",
        ":" : "S",
        ";" : "T",
        "\'" : "U",
        "\"" : "V",
        "," : "W",
        "<" : "X",
        "." : "Y",
        ">" : "Z",
        "?" : "a",
        "/" : "b",
        "5" : "c",
        "1" : "d",
        "3" : "e",
        "2" : "f",
        "4" : "g",
        "9" : "h",
        "0" : "i",
        "8" : "j",
        "6" : "k",
        "7" : "l",
        }
vas1 = ""

for i in so:
    scr1 = str(d1.get(i))
    vas1 += str(scr1)
for c in vas1:
    arr1.append(ord(c))
arr2 = []
for i in arr1:
    if i % 2 == 0:
        i += 2
    else:
        i += 1
    arr2.append(i)
saa2t = ""
for c in arr2:
    saa2t += chr(c)
d2  = { "~" : "A",
        "`" : "B",
        "@" : "C",
        "#" : "D",
        "$" : "E",
        "%" : "F",
        "^" : "G",
        "&" : "H",
        "*" : "I",
        "(" : "J",
        ")" : "K",
        "-" : "L",
        "_" : "M",
        "=" : "N",
        "+" : "O",
        "{" : "P",
        "[" : "Q",
        "]" : "R",
        ":" : "S",
        ";" : "T",
        "\'" : "U",
        "\"" : "V",
        "," : "W",
        "<" : "X",
        "." : "Y",
        ">" : "Z",
        "?" : "a",
        "/" : "b",
        "5" : "c",
        "1" : "d",
        "4" : "e",
        "2" : "f",
        "3" : "g",
        "9" : "h",
        "0" : "i",
        "8" : "j",
        "6" : "k",
        "7" : "l",
        "K" : "m",
        "Q" : "n",
        "F" : "o",
        "V" : "p",
        "X" : "q",
        "D" : "r",
        "S" : "s",
        "A" : "t",
        "J" : "u",
        "N" : "v",
        "M" : "w",
        "P" : "x",
        "I" : "y",
        "T" : "z",
        "A" : "~",
        "B" : "`",
        "C" : "*",
        "D" : "#",
        "E" : "$",
        "F" : "%",
        "G" : "^",
        "H" : "&",
        "I" : "@",
        "J" : "(",
        "K" : ")",
        "L" : "-",
        "M" : "_",
        "N" : "=",
        "O" : "+",
        "P" : "{",
        "Q" : "[",
        "R" : "]",
        "S" : ":",
        "T" : ";",
        "U" : "\'",
        "V" : "\"",
        "W" : ",",
        "X" : "<",
        "Y" : ".",
        "Z" : ">",
        "a" : "?",
        "b" : "/",
        "c" : "5",
        "d" : "7",
        "e" : "3",
        "f" : "2",
        "g" : "4",
        "h" : "9",
        "i" : "0",
        "j" : "8",
        "k" : "6",
        "l" : "1",
        }
vas2 = ""
for i in saa2t:
    scr2 = str(d2.get(i))
    vas2 += str(scr2)
sarev = vas2[::-1]
msg_b = sarev.encode("ascii")
b64_bytes = base64.b64encode(msg_b)
b64_string = b64_bytes.decode("ascii")
print(sarev)
# JUglWEMyZlo9MkpCPSgoWj1pKDJaPSgoe1M9Q1oiayNYPV1KI0paLUpKU0M=

加密算法过程是先用了一个凯撒，然后HashMap替换，然后是一个很迷惑的加密：

1
2
3
4
5
6
for i in arr1:
    if i % 2 == 0:
        i += 2
    else:
        i += 1
    arr2.append(i)

然后再来一个HashMap替换，最后逆序base64。其他步骤都好说，就在这一步加密卡着了。索性把所有可能的情况打印出来，然后一个一个套。

MuHH(AH@H[_G@t'AM_w+&&_K1&L_A&&_TH3_Av3nG

这个是最后的解，套加密算法都是对的，但题目就不给过……无语。

0x05 easypyc

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
# uncompyle6 version 3.5.0
# Python bytecode 3.8 (3413)
# Decompiled from: Python 2.7.5 (default, Nov 16 2020, 22:23:17) 
# [GCC 4.8.5 20150623 (Red Hat 4.8.5-44)]
# Embedded file name: easypyc.py
# Size of source mod 2**32: 272 bytes
whatbox = [0] * 256

def aaaaaaa(a, b):
    k = [0] * 256
    t = 0
    for m in range(256):
        whatbox[m] = m
        k[m] = ord(a[(m % b)])

    for i in range(256):
        t = (t + whatbox[i] + k[i]) % 256
        temp = whatbox[i]
        whatbox[i] = whatbox[t]
        whatbox[t] = temp


def bbbbbbbbbb(a, b):
    q = 0
    w = 0
    e = 0
    for k in range(b):
        q = (q + 1) % 256
        w = (w + whatbox[q]) % 256
        temp = whatbox[q]
        whatbox[q] = whatbox[w]
        whatbox[w] = temp
        e = (whatbox[q] + whatbox[w]) % 256
        a[k] = a[k] ^ whatbox[e] ^ 102


def ccccccccc(a, b):
    for i in range(b):
        a[i] ^= a[((i + 1) % b)]

    for j in range(1, b):
        a[j] ^= a[(j - 1)]


if __name__ == '__main__':
    kkkkkkk = 'Geek2021'
    tttttt = [117, 62, 240, 152, 195, 117, 103, 74, 240, 151, 173, 162, 17, 75, 141, 165, 136, 117, 113, 33, 98, 151, 174, 4, 48, 25, 254, 101, 185, 127, 131, 87]
    ssss = input('Please input your flag:')
    inp = [0] * len(ssss)
    if len(ssss) != 32:
        print('Length Error!!!!')
        exit(0)
    for i in range(len(ssss)):
        inp[i] = ord(ssss[i])

    aaaaaaa(kkkkkkk, len(kkkkkkk))
    bbbbbbbbbb(inp, 32)
    ccccccccc(inp, 32)
    for m in range(32):
        assert not tttttt[m] != inp[m], 'sorry your flag is wrong'

    print('success!!!!!!')
    print('your flag is {}'.format(ssss))

魔改的RC4，需要在RC4解密的基础上，把经过ccccccccc函数加密的密文逆回去：

1
2
3
4
5
6
for(i =31;i>=1;i--){
		ans[i]^=ans[i-1];
	}
	for(j =31;j>=0;j--){
		ans[j]^=ans[(j+1)%32];
	}

而后需要得到密钥序列，具体是把密钥流生成算法求出来：

1
[23,104,57,207,150,242,66,87,81,213,140,172,131,48,106,172,132,173,66,76,58,116,176,222,31,6,52,221,73,137,4,186]

之后就可以编写 exp 了。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
void main()
{
	int i,j,n,m;
int t[]={23,104,57,207,150,242,66,87,81,213,140,172,131,48,106,172,132,173,66,76,58,116,176,222,31,6,52,221,73,137,4,186};
	int ans[]={117, 62, 240, 152, 195, 117, 103, 74, 240, 151, 173, 162, 17, 75, 141, 165, 136, 117, 113, 33, 98, 151, 174, 4, 48, 25, 254, 101, 185, 127, 131, 87};
	for(i =31;i>=1;i--){
		ans[i]^=ans[i-1];
	}
	for(j =31;j>=0;j--){
		ans[j]^=ans[(j+1)%32];
	}
	for(n=0;n<32;n++){
		ans[n]=ans[n]^t[n]^102;
	}
	for(m=0;m<32;m++){
		
		printf("%c",ans[m]);
	}
}

0x06 RSA & what

简简单单共模，得到：

THIS FLAG IS HIDDEN. CAN YOU FIND IT OUT? DO YOU KNOW BASE64? YoungC THINK YOU ARE NOT THAT FAMILIAR WITH BASE64. Base64 is a group of similar binary-to-text encoding schemes that represent binary data in an ASCII string format by translating it into a radix-64 representation. The term Base64 originates from a specific MIME content transfer encoding. The particular set of 64 characters chosen to represent the 64 place-values for the base varies between implementations. The general strategy is to choose 64 characters that are both members of a subset common to most encodings, and also printable. This combination leaves the data unlikely to be modified in transit through information systems, such as E-mail, that were traditionally not 8-bit clean.[1] For example, "MIMEs" Base64 implementation uses A8CZ, a8Cz, and 08C9 for the first 62 values. Other variations share this property but differ in the symbols chosen for the last two values; an example is UTF-7.

这里用到了base64隐写。

base64解码：

  1. 首先把填充字符=去掉
  2. 每个字符查表转换为对应的6位索引，得到一串二进制字符串
  3. 接着从左到右，每8位一组，多余位丢掉，转为对应的字符

base64隐写原理 base64之所以可以隐藏信息，便是在于在解密过程中,在解码的第3步中，会有部分数据被丢弃（即不会影响解码结果），这些数据正是在编码过程中补的0。也就是说，如果在编码过程中不全用0填充，而是用其他的数据填充，仍然可以正常编码解码，因此这些位置可以用于隐写。

解开隐写的方法就是将这些不影响解码结果的位提取出来组成二进制串（一行 base64 最多有 2 个等号, 也就是有 22 位的可隐写位.），然后转换成ASCII字符串。这就是为什么出base64隐写时会有很多大段 base64 的原因

exp:

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
#--------base64隐写--------
def get_base64_diff_value(s1, s2):
    base64chars = b'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
    res = 0
    for i in range(len(s2)):
        if s1[i] != s2[i]:
            return abs(base64chars.index(s1[i]) - base64chars.index(s2[i]))
    return res

def solve_stego(c):
    line=b''
    bin_str=''
    for i in c:
        k=long_to_bytes(i)
        if k==b'\n':
            steg_line = line
            norm_line = base64.b64encode(base64.b64decode(line))
            diff = get_base64_diff_value(steg_line, norm_line)
            #print(diff)
            pads_num = steg_line.count(b'=')
            if diff:
                bin_str += bin(diff)[2:].zfill(pads_num * 2)
            else:
                bin_str += '0' * pads_num * 2
            print(goflag(bin_str))
            line=b''
            continue
        line+=k

def goflag(bin_str):
    res_str = ''
    for i in range(0, len(bin_str), 8):
        res_str += chr(int(bin_str[i:i + 8], 2))
    return res_str

#--------base64隐写--------

0x07 babyRSA

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
import sympy
import random
from gmpy2 import gcd, invert
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes
from z3 import *
flag = b"MRCTF{xxxx}"
base = 65537

def GCD(A):
    B = 1
    for i in range(1, len(A)):
        B = gcd(A[i-1], A[i])
    return B

def gen_p():
    P = [0 for i in range(17)]
    P[0] = getPrime(128)
    for i in range(1, 17):
        P[i] = sympy.nextprime(P[i-1])
    print("P_p :", P[9])
    n = 1
    for i in range(17):
        n *= P[i]
    p = getPrime(1024)
    factor = pow(p, base, n) #base=65537
    print("P_factor :", factor)
    return sympy.nextprime(p)

def gen_q():
    sub_Q = getPrime(1024)
    Q_1 = getPrime(1024)
    Q_2 = getPrime(1024)
    Q = sub_Q ** Q_2 % Q_1
    print("Q_1: ", Q_1)
    print("Q_2: ", Q_2)
    print("sub_Q: ", sub_Q)
    return sympy.nextprime(Q)

if __name__ == "__main__":
    _E = base
    _P = gen_p()
    _Q = gen_q()
    assert (gcd(_E, (_P - 1) * (_Q - 1)) == 1)
    _M = bytes_to_long(flag)
    _C = pow(_M, _E, _P * _Q)
    print("Ciphertext = ", _C)

Q可以直接给出来，P是通过P[9]getprime得到后面的部分，然后while循环-2判断是否为素数得到前面的部分。

exp:

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
from Crypto_box import *
base = 65537
P_p = 206027926847308612719677572554991143421
P_factor = 213671742765908980787116579976289600595864704574134469173111790965233629909513884704158446946409910475727584342641848597858942209151114627306286393390259700239698869487469080881267182803062488043469138252786381822646126962323295676431679988602406971858136496624861228526070581338082202663895710929460596143281673761666804565161435963957655012011051936180536581488499059517946308650135300428672486819645279969693519039407892941672784362868653243632727928279698588177694171797254644864554162848696210763681197279758130811723700154618280764123396312330032986093579531909363210692564988076206283296967165522152288770019720928264542910922693728918198338839
Q_1=  103766439849465588084625049495793857634556517064563488433148224524638105971161051763127718438062862548184814747601299494052813662851459740127499557785398714481909461631996020048315790167967699932967974484481209879664173009585231469785141628982021847883945871201430155071257803163523612863113967495969578605521
Q_2=  151010734276916939790591461278981486442548035032350797306496105136358723586953123484087860176438629843688462671681777513652947555325607414858514566053513243083627810686084890261120641161987614435114887565491866120507844566210561620503961205851409386041194326728437073995372322433035153519757017396063066469743
sub_Q=  168992529793593315757895995101430241994953638330919314800130536809801824971112039572562389449584350643924391984800978193707795909956472992631004290479273525116959461856227262232600089176950810729475058260332177626961286009876630340945093629959302803189668904123890991069113826241497783666995751391361028949651
Ciphertext =  1709187240516367141460862187749451047644094885791761673574674330840842792189795049968394122216854491757922647656430908587059997070488674220330847871811836724541907666983042376216411561826640060734307013458794925025684062804589439843027290282034999617915124231838524593607080377300985152179828199569474241678651559771763395596697140206072537688129790126472053987391538280007082203006348029125729650207661362371936196789562658458778312533505938858959644541233578654340925901963957980047639114170033936570060250438906130591377904182111622236567507022711176457301476543461600524993045300728432815672077399879668276471832
def gen_q():
    Q=gp.powmod(sub_Q,Q_2,Q_1)
    return gp.next_prime(Q)
def gen_p():
    P = [0 for i in range(17)]
    P[9]=P_p
    for i in range(10,17):
        P[i]=gp.next_prime(P[i-1])
    a=9
    while a>0:
        x=P[a]-2
        while not(gp.is_prime(x)):
            x-=2
        P[a-1]=x
        a-=1
    n=1
    fai=1
    for i in P:
        n*=i
        fai*=i-1
    d=gp.invert(base,fai)
    p=gp.powmod(P_factor,d,n)
    return gp.next_prime(p)
m=RSA(gen_p(),gen_q(),base,Ciphertext)
print(long_to_bytes(m))

# b'MRCTF{sti11_@_b@by_qu3st10n}'

0x08 you_raise_me_up

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
import random

n = 2 ** 512
m = random.randint(2, n-1) | 1
c = pow(m, bytes_to_long(flag), n)
print 'm = ' + str(m)
print 'c = ' + str(c)

离散对数求解，需要用到sympy库。

exp:

1
2
3
4
5
6
7
8
from Crypto_box import *
import sympy
m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
n=2 ** 512
f=sympy.discrete_log(n,c,m)
print(long_to_bytes(f))
# b'flag{5f95ca93-1594-762d-ed0b-a9139692cb4a}'

0x09 坏蛋是雷宾

老牌刺客之王混进了女王的住所。一天，女王得到了一个匿名举报，说她的侍卫里有一个刺客，叫做Rabin，而他的信息就在一份文件里，文件中有附带一个Pk，是523798549，密文是162853095，校验码二进制值是110001，根据说明是放在明文后一起加密的，明文与密文长度相同。加密算法和这位老牌刺客同名。快拯救女王，答案是求得的明文，进行32位md5小写哈希字符串，提交即可。 注意：得到的 flag 请包上 flag{} 提交

Rabin算法是基于RSA的扩展。

生成：

，作为私钥，作为公钥

加密：

解密： 使用扩展欧几里得算法求：

根据中国剩余定理求模n的平方根： 这四个值之一是原始明文m，但是如果没有其他信息，就无法确定这四个是正确的。(这道题给出校验码).

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto_box import *
n=523798549
c=162853095
p=10663
q=49123
m_p=gp.powmod(c,(p+1)//4,p)
m_q=gp.powmod(c,(q+1)//4,q)
y_p=gp.invert(p,q)
y_q=gp.invert(q,p)
r=[]
r.append((y_p*p*m_q+y_q*q*m_p)%n)
r.append(n-r[0])
r.append((y_p*p*m_q-y_q*q*m_p)%n)
r.append(n-r[2])
for i in r:
    print(bin(i)[2:])
'''
10010011100100100101010110001
1100110001100011110101100100
110111001100000100101111001
11000010100100111111010011100

Process finished with exit code 0
'''

分析校验码得到第一个是明文，转10进制再md5就是flag。

0x0a EzRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from gmpy2 import lcm , powmod , invert , gcd , mpz
from Crypto.Util.number import getPrime
from sympy import nextprime
from random import randint
p = getPrime(1024)
q = getPrime(1024)
n = p * q
gift = lcm(p - 1 , q - 1)
e = 54722
flag = b'NPUCTF{******************}'
m = int.from_bytes(flag , 'big')
c = powmod(m , e , n)
print('n: ' , n)
print('gift: ' , gift)
print('c: ' , c)

给出了p-1和q-1的最小公倍数，如何求解呢？

考虑到如下公式：

代入题目就是：

gift位数2045，n位数2048，因此gcd位数为3，也即gcd是[4,8]内的数，这样就方便列举了。

同时要注意到e=54722=27361*2，所以加密要变换一下： 解密出来的m要开方。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto_box import *

gift=  2135492653776686212553329560560967285303308936825887355911916917454772197960682240149821138177216833586509090969892419775958406087994054585022894165950768427741545736247918410255804894522085720642952579638418483800243368312702566458196708508543635051350999572787188236243275631609875253617015664414032058822919469443284453403064076232765024248435543326597418851751586308514540124571309152787559712950209357825576896132278045112177910266019741013995106579484868768251084453338417115483515132869594712162052362083414163954681306259137057581036657441897428432575924018950961141822554251369262248368899977337886190114104
n=  17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121
c=  3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319
e = 54722
for i in range(4,8):
    f=gift*i
    d=gp.invert(e//2,f)
    mm=gp.powmod(c,d,n)
    m=gp.iroot(mm,2)
    if m[1]:
        print(long_to_bytes(m[0]))
''' 
b'NPUCTF{diff1cult_rsa_1s_e@sy}'
b'NPUCTF{diff1cult_rsa_1s_e@sy}'
b'NPUCTF{diff1cult_rsa_1s_e@sy}'
b'NPUCTF{diff1cult_rsa_1s_e@sy}'
'''

0x0b Polybius

密文：ouauuuoooeeaaiaeauieuooeeiea hint：VGhlIGxlbmd0aCBvZiB0aGlzIHBsYWludGV4dDogMTQ= flag:解出明文后，请加上BJD{}

b64解密hint:The length of this plaintext: 14

考虑到密文有28位，加密方式应为棋盘密码，aeiou是其位置坐标，但aeiou排列顺序位置，所以要列举。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import itertools
s="aeoiu"
sumresult=[]
numsumresult=[]
ciper="ouauuuoooeeaaiaeauieuooeeiea"
for i in itertools.permutations(s,5):#找出所有全排列
    sumresult.append("".join(i))
for i in sumresult:
    temp=""
    for j in ciper:
        temp+=str(i.index(j)+1)
    numsumresult.append(temp)
for i in numsumresult:
    ans_=""
    for j in range(0, len(i),2):
        xx=(int(i[j])-1)*5+int(i[j+1])+96
        if xx>ord('i'):
            xx+=1
        ans_+=chr(xx)
    print(ans_)


0x0c d3factor

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
from Crypto.Util.number import bytes_to_long, getPrime
from secret import msg
from sympy import nextprime
from gmpy2 import invert
from hashlib import md5

flag = 'd3ctf{'+md5(msg).hexdigest()+'}'
p = getPrime(256)
q = getPrime(256)
assert p > q
n = p * q
e = 0x10001
m = bytes_to_long(msg)
c = pow(m, e, n)

N = pow(p, 7) * q
phi = pow(p, 6) * (p - 1) * (q - 1)
d1 = getPrime(2000)
d2 = nextprime(d1 + getPrime(1000))
e1 = invert(d1, phi)
e2 = invert(d2, phi)

print(f'c = {c}')
print(f'N = {N}')
print(f'e1 = {e1}')
print(f'e2 = {e2}')
'''
c = 2420624631315473673388732074340410215657378096737020976722603529598864338532404224879219059105950005655100728361198499550862405660043591919681568611707967
N = 1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494154077020472814706123209865769048722380888175401791873273850281384147394075054950169002165357490796510950852631287689747360436384163758289159710264469722036320819123313773301072777844457895388797742631541101152819089150281489897683508400098693808473542212963868834485233858128220055727804326451310080791
e1 = 425735006018518321920113858371691046233291394270779139216531379266829453665704656868245884309574741300746121946724344532456337490492263690989727904837374279175606623404025598533405400677329916633307585813849635071097268989906426771864410852556381279117588496262787146588414873723983855041415476840445850171457530977221981125006107741100779529209163446405585696682186452013669643507275620439492021019544922913941472624874102604249376990616323884331293660116156782891935217575308895791623826306100692059131945495084654854521834016181452508329430102813663713333608459898915361745215871305547069325129687311358338082029
e2 = 1004512650658647383814190582513307789549094672255033373245432814519573537648997991452158231923692387604945039180687417026069655569594454408690445879849410118502279459189421806132654131287284719070037134752526923855821229397612868419416851456578505341237256609343187666849045678291935806441844686439591365338539029504178066823886051731466788474438373839803448380498800384597878814991008672054436093542513518012957106825842251155935855375353004898840663429274565622024673235081082222394015174831078190299524112112571718817712276118850981261489528540025810396786605197437842655180663611669918785635193552649262904644919
'''

题目包含如下几个参数：

参数 大小(bit)
p,q 256bit prime
N 512bit
d1,d2 2000bit prime(d1-d2=1000bit)
e1,e2 2000bit

结合题目，有两个值得注意的地方：

  1. d1,d2相差1000bit，可能以|d1-d2|过小构成攻击。
  2. N的产生方式：，不同于常见的p*q，也可能构成攻击。

所以可以归纳出两个关键词：|p1-p2| small，n p r q

通过之前归纳的关键词，能查到很多有关攻击的文章，这里以其中一篇为例：

A STUDY ON CRYPT ANALYSIS OF RSA,Chapter 4: RSA with modulus

论文中提到的第一种的攻击是这样的：

对等式，若参数xy满足 时，可以在多项式时间内分解N。

这种攻击在题目情景下是不能成立的，因为： 第二种攻击方式是这样的：

d1与d2是RSA下两个私钥，且满足，若d1与d2满足 时，可以在多项式时间内分解N。

引理：

设是大整数，且含因子，也即。是齐次线性多项式。则方程 可以在条件下，在线性方程内求解。

的所有解可以在

这种攻击方式在此题情景下成立，因为

攻击思想概括：

由 得 又由，可以得到 设方程 则方程的解即为

假设方程中，根据前面证的定理，当，时，可以在多项式时间内求解。证完。

计算，则有

攻击流程：

  1. 求解模多项式。

    sagemath中使用small_roots求解多项式小值根，以及因子分解问题。其中要设置三个量：X,表示求解根的上界；beta、epsilon，可以利用论文中的求法得到(其实随便写一个就行)。

  2. x=|d1-d2|，代入求g

  3. 求p,q，进而用常规rsa求解

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto_box import *
N=1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494154077020472814706123209865769048722380888175401791873273850281384147394075054950169002165357490796510950852631287689747360436384163758289159710264469722036320819123313773301072777844457895388797742631541101152819089150281489897683508400098693808473542212963868834485233858128220055727804326451310080791
e1=425735006018518321920113858371691046233291394270779139216531379266829453665704656868245884309574741300746121946724344532456337490492263690989727904837374279175606623404025598533405400677329916633307585813849635071097268989906426771864410852556381279117588496262787146588414873723983855041415476840445850171457530977221981125006107741100779529209163446405585696682186452013669643507275620439492021019544922913941472624874102604249376990616323884331293660116156782891935217575308895791623826306100692059131945495084654854521834016181452508329430102813663713333608459898915361745215871305547069325129687311358338082029
e2=1004512650658647383814190582513307789549094672255033373245432814519573537648997991452158231923692387604945039180687417026069655569594454408690445879849410118502279459189421806132654131287284719070037134752526923855821229397612868419416851456578505341237256609343187666849045678291935806441844686439591365338539029504178066823886051731466788474438373839803448380498800384597878814991008672054436093542513518012957106825842251155935855375353004898840663429274565622024673235081082222394015174831078190299524112112571718817712276118850981261489528540025810396786605197437842655180663611669918785635193552649262904644919
c=2420624631315473673388732074340410215657378096737020976722603529598864338532404224879219059105950005655100728361198499550862405660043591919681568611707967
PR.<x> = PolynomialRing(Zmod(N))
f = e1*e2*x-(e1-e2)
f = f.monic() #将f化为最高次系数为一的多项式
k = f.small_roots(beta = 0.656, epsilon = 0.125, X = 2^1000)[0]
t = gcd(e1*e2*k+(e2-e1),N)
p=gp.iroot(t,6)[0]
q=N//pow(p,7)
msg=long_to_bytes(RSA(p,q,65537,c))
flag = 'd3ctf{'+md5(msg).hexdigest()+'}'
print(flag)

# d3ctf{42f79e777e622aef5344b04ad6233130}

# 0x0d babyrsa

1
2
3
4
5
6
7
8
9
10
p4=146068806215073497344459876631371603884129554507314987227041386431864296983800292232765852493230146632246223391161616274352995602128509562953556195654254929572680238155614318159006433172894208760309766144817665852858474274746295434459658946786114485553768622540321693696983334739989582184316792317376817587284066141025953893816735983622448994863347051427279673308801466174898201800602688359956097373676655607179834345973775227535147398518523539179261883968140504230643073698857288314127486345168652339309386405706576632120711116391426300160476076254612138216623537070845645803721685414583459545099925250474009703135469241079408739336592005949980987466671054020054633554508243871664072158338203090563533576053886607251476483441992750608537110739543678599105838456537686029895264928334606913181627024815548789841726411333636163152202116487198575625907392074866811580053962217284776220330628233642351622897902940633662074194963147661868086182955886918339487179905557899816215131118989868243555958033477834658657082003718410617182774845820310639577794302769424451100567749840744304334325501306470124397022077759031911677326433654909824518845224227308515695216456907499080502091628962571645468099748573164070147303131348996440422701533681
q1 = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871
q2 = 114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
p=gp.iroot(p4,4)[0]
n1=p*q1
n2=p*q2
e1 = 15218928658178
e2 = 381791429275130
c1 =  262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 =  7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596

前面一个低解密指数爆破，一个简单的factor顺利解出，最后一步卡住了：

这道题最大的难点在于，所以不能用常规RSA来解。

exp:

1
2
3
4
5
6
7
8
c=[gp.powmod(c1,s1,q1),gp.powmod(c2,s2,q2)]
d=[q1,q2]
l=CRT(c,d)
cd=gp.invert(7,(q1-1)*(q2-1))
m2=gp.powmod(l,cd,q1*q2)
m=gp.iroot(m2,2)[0]
print(long_to_bytes(m))
# de1ctf{9b10a98b-71bb-4bdf-a6ff-f319943de21f}

0x0e 认清形势，建立信心

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 *
from secret import flag

p = getPrime(25)
e = # Hidden
q = getPrime(25)
n = p * q
m = bytes_to_long(flag.strip(b"npuctf{").strip(b"}"))

c = pow(m, e, n)
print(c)
print(pow(2, e, n))
print(pow(4, e, n))
print(pow(8, e, n))

'''
169169912654178
128509160179202
518818742414340
358553002064450
'''

需要用到两个等式求解:

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto_box import *
import sympy
c=169169912654178
c1=128509160179202
c2=518818742414340
c3=358553002064450
p=18195301 
q=28977097
n=p*q 

e=sympy.discrete_log(n,c1,2)
d=gp.invert(e,(p-1)*(q-1))
m=gp.powmod(c,d,n)
print(long_to_bytes(m))

0x0f ezRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import getStrongPrime
from gmpy import next_prime
from random import getrandbits
from flag import flag

p=getStrongPrime(1024)
q=next_prime(p^((1<<900)-1)^getrandbits(300))
n=p*q
e=65537

m=int(flag.encode('hex'),16)
assert m<n
c=pow(m,e,n)
print(hex(n))
print(hex(c))

复原前面的bits

观察可得到：pq前124bit是相同的。并且由于： 可得n的前248位即pq前124位的乘积。

这一步的主要思想是：pq的900~300位由于异或了600个1，故其每一位都是相反的，也即：p的第i位是1，则q的第i位是0；反之亦然。

可以证明：如果相同位的1与0互换，其乘积会比原先的n大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
top_bits = int(gmpy2.iroot(n>>(2048-248),2)[0])
# Put all 1 in p and 0 in q
p = top_bits<<900 | (2**900 - 1)
q = top_bits<<900
# Start from 125th bits (1024-125)
for i in range(899, 301, -1):
	cur = 1<<i
	# Swap p to 0 and q to 1
	# if less than n then is correct order
	# else no changes
	if (p^cur) * (q^cur) < n:
		p ^= cur
		q ^= cur

简单copper即可复原剩下的 bits

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
p = 0xf376c68d76f4ab9b4d247852ef07159a09eeac920ac89148a8dee4f3c359a291b6bf03ab9258ca64783c416fcfeade13cf3c18a7677c29283c7fc6bfcdbba1d6fecbe9e243cc2e3ef0fe60035e1dbc727f3522bfab2bc28d5e29bfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
c = 0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1
PR.<x> = PolynomialRing(Zmod(n))
f=x+p
roots=f.small_roots(X=2**430,beta=0.4)
p=int(p+roots[0])
assert n%p==0
q = n//p
phi = (p-1)*(q-1)
d = inverse(65537, phi)
print(long_to_bytes(pow(c,d,n)))