fibinary
Bài này chúng ta có source code encrypt:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
fib = [1, 1]
for i in range(2, 11):
fib.append(fib[i - 1] + fib[i - 2])
def c2f(c):
n = ord(c)
b = ''
for i in range(10, -1, -1):
if n >= fib[i]:
n -= fib[i]
b += '1'
else:
b += '0'
return b
flag = open('flag.txt', 'r').read()
enc = ''
for c in flag:
enc += c2f(c) + ' '
with open('flag.enc', 'w') as f:
f.write(enc.strip())
#flag.enc = '10000100100 10010000010 10010001010 10000100100 10010010010 10001000000 10100000000 10000100010 00101010000 10010010000 00101001010 10000101000 10000010010 00101010000 10010000000 10000101000 10000010010 10001000000 00101000100 10000100010 10010000100 00010101010 00101000100 00101000100 00101001010 10000101000 10100000100 00000100100'
Thuật toán khá đơn giản đó là chuyển đổi kí tự sang hệ 10 sau đó so sánh với dãy số Finbonanci từ hàm xxx Nếu số hệ 10 của kí tự trong flag bé hơn Finbonanci sẽ là 0 và ngược lại là 1 cho số lớn hơn, từ đó ta có 1 số binary mới tương ứng với từng kí tự. Đối với bài này ta có thể đảo ngược thuật toán, tuy nhiên có cách nhanh hơn đó là ta tính hết tất cả các kí tự sau đó parse ra theo flag được ban tổ chức đã cho.
Source code decrypt của mình:
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
import string
#gen finbonanci
fib = [1, 1]
for i in range(2, 11):
fib.append(fib[i - 1] + fib[i - 2])
#fib = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
def c2f(c): #encrypt đổi kí tự thành 11 số binary
n = ord(c)
b = ''
for i in range(10, -1, -1):
if n >= fib[i]:
n -= fib[i]
b += '1'
else:
b += '0'
return b
def parsecharacter(): #tiềm các số bin tương ứng cho mỗi ký tự đọc được
chars = string.printable
parse = {}
for c in chars:
parse[c2f(c)] = c
return parse
def decrypt():
flag =''
cipher=['10000100100', '10010000010', '10010001010', '10000100100', '10010010010', '10001000000', '10100000000', '10000100010', '00101010000', '10010010000', '00101001010', '10000101000', '10000010010', '00101010000', '10010000000', '10000101000', '10000010010', '10001000000', '00101000100', '10000100010', '10010000100', '00010101010', '00101000100', '00101000100', '00101001010', '10000101000', '10100000100', '00000100100']
for i in cipher:
flag+=str(parsecharacter().get(i)) #lấy kí tự theo cipher qua hàm get của dict
print(flag)
decrypt()
Flag: corctf{b4s3d_4nd_f1bp!113d}
4096
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import getPrime, bytes_to_long
from private import flag
def prod(lst):
ret = 1
for num in lst:
ret *= num
return ret
m = bytes_to_long(flag)
primes = [getPrime(32) for _ in range(128)]
n = prod(primes)
e = 65537
print(n)
print(pow(m, e, n))
#n=50630448182626893495464810670525602771527685838257974610483435332349728792396826591558947027657819590790590829841808151825744184405725893984330719835572507419517069974612006826542638447886105625739026433810851259760829112944769101557865474935245672310638931107468523492780934936765177674292815155262435831801499197874311121773797041186075024766460977392150443756520782067581277504082923534736776769428755807994035936082391356053079235986552374148782993815118221184577434597115748782910244569004818550079464590913826457003648367784164127206743005342001738754989548942975587267990706541155643222851974488533666334645686774107285018775831028090338485586011974337654011592698463713316522811656340001557779270632991105803230612916547576906583473846558419296181503108603192226769399675726201078322763163049259981181392937623116600712403297821389573627700886912737873588300406211047759637045071918185425658854059386338495534747471846997768166929630988406668430381834420429162324755162023168406793544828390933856260762963763336528787421503582319435368755435181752783296341241853932276334886271511786779019664786845658323166852266264286516275919963650402345264649287569303300048733672208950281055894539145902913252578285197293
#c=pow(m, e, n)=15640629897212089539145769625632189125456455778939633021487666539864477884226491831177051620671080345905237001384943044362508550274499601386018436774667054082051013986880044122234840762034425906802733285008515019104201964058459074727958015931524254616901569333808897189148422139163755426336008738228206905929505993240834181441728434782721945966055987934053102520300610949003828413057299830995512963516437591775582556040505553674525293788223483574494286570201177694289787659662521910225641898762643794474678297891552856073420478752076393386273627970575228665003851968484998550564390747988844710818619836079384152470450659391941581654509659766292902961171668168368723759124230712832393447719252348647172524453163783833358048230752476923663730556409340711188698221222770394308685941050292404627088273158846156984693358388590950279445736394513497524120008211955634017212917792675498853686681402944487402749561864649175474956913910853930952329280207751998559039169086898605565528308806524495500398924972480453453358088625940892246551961178561037313833306804342494449584581485895266308393917067830433039476096285467849735814999851855709235986958845331235439845410800486470278105793922000390078444089105955677711315740050638
Bài này là một dạng cơ bản của thuật toán RSA. Ta có công thức tính encrypt m là m^e ≡ c mod n. Để decrypt ta giải theo công thức c^d ≡ m mod n. Nhưng số d là gì? d được tính theo công thức d*e ≡ 1 (mod λ(n)). Trong đó λ(n) =(p-1)*(q-1). Sử dụng sage:
Với λ(n) = t
1
2
3
4
5
n = 50630448182626893495464810670525602771527685838257974610483435332349728792396826591558947027657819590790590829841808151825744184405725893984330719835572507419517069974612006826542638447886105625739026433810851259760829112944769101557865474935245672310638931107468523492780934936765177674292815155262435831801499197874311121773797041186075024766460977392150443756520782067581277504082923534736776769428755807994035936082391356053079235986552374148782993815118221184577434597115748782910244569004818550079464590913826457003648367784164127206743005342001738754989548942975587267990706541155643222851974488533666334645686774107285018775831028090338485586011974337654011592698463713316522811656340001557779270632991105803230612916547576906583473846558419296181503108603192226769399675726201078322763163049259981181392937623116600712403297821389573627700886912737873588300406211047759637045071918185425658854059386338495534747471846997768166929630988406668430381834420429162324755162023168406793544828390933856260762963763336528787421503582319435368755435181752783296341241853932276334886271511786779019664786845658323166852266264286516275919963650402345264649287569303300048733672208950281055894539145902913252578285197293
nf = factor(n)
2148630611 * 2157385673 * 2216411683 * 2223202649 * 2230630973 * 2240170147 * 2278427881 * 2293226687 * 2322142411 * 2365186141 * 2371079143 * 2388797093 * 2424270803 * 2436598001 * 2444333767 * 2459187103 * 2491570349 * 2510750149 * 2525697263 * 2572542211 * 2575495753 * 2602521199 * 2636069911 * 2647129697 * 2657405087 * 2661720221 * 2672301743 * 2682518317 * 2695978183 * 2703629041 * 2707095227 * 2710524571 * 2719924183 * 2724658201 * 2733527227 * 2746638019 * 2752963847 * 2753147143 * 2772696307 * 2824169389 * 2841115943 * 2854321391 * 2858807113 * 2932152359 * 2944722127 * 2944751701 * 2949007619 * 2959325459 * 2963383867 * 3012495907 * 3013564231 * 3035438359 * 3056689019 * 3057815377 * 3083881387 * 3130133681 * 3174322859 * 3177943303 * 3180301633 * 3200434847 * 3228764447 * 3238771411 * 3278196319 * 3279018511 * 3285444073 * 3291377941 * 3303691121 * 3319529377 * 3335574511 * 3346647649 * 3359249393 * 3380851417 * 3398567593 * 3411506629 * 3417563069 * 3453863503 * 3464370241 * 3487902133 * 3488338697 * 3522596999 * 3539958743 * 3589083991 * 3623581037 * 3625437121 * 3638373857 * 3646337561 * 3648309311 * 3684423151 * 3686523713 * 3716991893 * 3721186793 * 3760232953 * 3789253133 * 3789746923 * 3811207403 * 3833706949 * 3833824031 * 3854175641 * 3860554891 * 3861767519 * 3865448239 * 3923208001 * 3941016503 * 3943871257 * 3959814431 * 3961738709 * 3978832967 * 3986329331 * 3991834969 * 3994425601 * 4006267823 * 4045323871 * 4056085883 * 4073647147 * 4091945483 * 4098491081 * 4135004413 * 4140261491 * 4141964923 * 4152726959 * 4198942673 * 4205028467 * 4218138251 * 4227099257 * 4235456317 * 4252196909 * 4270521797 * 4276173893
t = (2148630611-1)* (2157385673-1)* (2216411683-1)* (2223202649-1)* (2230630973-1)* (2240170147-1)* (2278427881-1)* (2293226687-1)* (2322142411-1)* (2365186141-1)* (2371079143-1)* (2388797093-1)* (2424270803-1)* (2436598001-1)* (2444333767-1)* (2459187103-1)* (2491570349-1)* (2510750149-1)* (2525697263-1)* (2572542211-1)* (2575495753-1)* (2602521199-1)* (2636069911-1)* (2647129697-1)* (2657405087-1)* (2661720221-1)* (2672301743-1)* (2682518317-1)* (2695978183-1)* (2703629041-1)* (2707095227-1)* (2710524571-1)* (2719924183-1)* (2724658201-1)* (2733527227-1)* (2746638019-1)* (2752963847-1)* (2753147143-1)* (2772696307-1)* (2824169389-1)* (2841115943-1)* (2854321391-1)* (2858807113-1)* (2932152359-1)* (2944722127-1)* (2944751701-1)* (2949007619-1)* (2959325459-1)* (2963383867-1)* (3012495907-1)* (3013564231-1)* (3035438359-1)* (3056689019-1)* (3057815377-1)* (3083881387-1)* (3130133681-1)* (3174322859-1)* (3177943303-1)* (3180301633-1)* (3200434847-1)* (3228764447-1)* (3238771411-1)* (3278196319-1)* (3279018511-1)* (3285444073-1)* (3291377941-1)* (3303691121-1)* (3319529377-1)* (3335574511-1)* (3346647649-1)* (3359249393-1)* (3380851417-1)* (3398567593-1)* (3411506629-1)* (3417563069-1)* (3453863503-1)* (3464370241-1)* (3487902133-1)* (3488338697-1)* (3522596999-1)* (3539958743-1)* (3589083991-1)* (3623581037-1)* (3625437121-1)* (3638373857-1)* (3646337561-1)* (3648309311-1)* (3684423151-1)* (3686523713-1)* (3716991893-1)* (3721186793-1)* (3760232953-1)* (3789253133-1)* (3789746923-1)* (3811207403-1)* (3833706949-1)* (3833824031-1)* (3854175641-1)* (3860554891-1)* (3861767519-1)* (3865448239-1)* (3923208001-1)* (3941016503-1)* (3943871257-1)* (3959814431-1)* (3961738709-1)* (3978832967-1)* (3986329331-1)* (3991834969-1)* (3994425601-1)* (4006267823-1)* (4045323871-1)* (4056085883-1)* (4073647147-1)* (4091945483-1)* (4098491081-1)* (4135004413-1)* (4140261491-1)* (4141964923-1)* (4152726959-1)* (4198942673-1)* (4205028467-1)* (4218138251-1)* (4227099257-1)* (4235456317-1)* (4252196909-1)* (4270521797-1)* (4276173893-1)
Đúng là λ(n)=(p-1)*(q-1) nhưng vì ở đây chúng ta có quá nhiều p, q nên cứ tiến hành tương tự như vậy; điều này không ảnh hưởng tới bài toán.
Bây giờ ta tính d:
1
2
3
d*e ≡ 1 (mod λ(n))
<=> d ≡ 1/e * 1 (mod λ(n))
<=> d ≡ e^(-1) (mod λ(n))
Trong python ta có thể tính từ công thức trên theo hàm pow:
1
d = pow(e,-1,t)
Vậy là các biến yêu cầu đã đủ:
1
2
from Crypto.Util.number import long_to_bytes
printf(long_to_bytes(pow(c,d,n)))
Flag: corctf{to0_m4ny_pr1m3s55_63aeea37a6b3b22f}
Cheer (☞ﾟヮﾟ)☞ ☜(ﾟヮﾟ☜)