RSA Hard

Files

main.py

​x
from sage.all           import *
from Crypto.Util.number import *

p = getPrime(1024)
q = getPrime(1024)
N = p*q
e = 5

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

print(f'e = {e}')
print(f'N = {N}')
print(f'l = {len(flag)}')
print(f'c = {pow(bytes_to_long(flag), e, N)}')

output.py

xxxxxxxxxx
e = 5
N = 12015877997327252175076120312423175105723461868777059585810222036358918783467414287643432190947190786537093339282160308346975288678674432143426250190709021016831250908101810274658898975353281727552890093414187602315603911322814265706034002878643080070591319446411326545606427027907006051688317769461922389975196872900254522093565875140439944562548515732597932150601402602403195253684885360376374685106193161372933888346449329403651387981516301918661360919515900594095694744927900343002829948284125210613977913862883912507003034134770232874412487878644640842887800510975707753471130578272563122578877626551522287674097
l = 53
c = 5562931535583484617256604644509628645834662861704445289348492775196895168427686091725679215263205879725144908431055742780470842895864519394889001940231547646790107249009489416972289701307862269450771340549640328909814417579965795018784605202248304929088399220539858726813553822946788808764467934624443033406429967536285715991274724142143817267673695159323420482466290407287110266003347181790634451481348871446847434958148110080492955701749604087626156503554584480028851337053826052171567169497489536695272674103468427199662543313920099195353803442752089147439391576939086697556515968236200200239877271511921097985456

Phân tích

Giống như bài trước, main.py hoàn toàn không có lỗi nha, lỗi là nằm ở cái flag hư đốn kia 😗

Tuy nhiên, ở bài này file output.txt đã có sự khác biệt nhẹ, đó là từ l=43 chúng ta đã nâng cấp thành l=53. Áp dụng tư duy từ bài trước, ta có số bit của flag^5 phải là 53*8*5 = 2120 > n là 2048 bits. Vì vậy không thể dùng trick căn bậc 5 được rồi, rất tiếc :(

Có thể một số bạn cũng sẽ lập luận như sau:

Vì

nên ta có:

và mò k từ 0 đến một số tít trời mây nào đó và căn bậc 5 để ra $flag$$flag$. Đây cũng là 1 cách suy nghĩ thú vị, tuy nhiên chỉ làm được nếu k bé mà thôi.

Vì flag^5 có 2120 bit, và n chỉ có 2048 thôi, nên k phải có tầm 2120 - 2048 = 72 bits. Do vậy, số tít trời mây nào đó mà bạn muốn mò ra cũng phải bay đến tận 2**72, và mình khuyên là bạn không nên làm thế, vì nó to hơn bạn nghĩ nhiều đó 😗

Cách giải

thuật toán Coppersmith

Để giải được bài này, chúng ta cần biết đến 1 thuật toán rất hữu ích trong việc giải các phương trình dạng f(x) = 0 mod n với x < X và X là một số mình cho trước. Và tên của nó chính là Coppersmith.

Vì flag là nghiệm của phương trình $x^5=c\mathrm{mod}n$$x^5 = c \mod n$, nên sử dụng Coppersmith áp dụng cho hàm f(x) = x^5 - c để giải ra flag là một suy nghĩ hoàn toàn hợp lí.

Giới hạn

Tuy vậy, thuật toán Coppersmith có 1 giới hạn, đó chính là nếu degree của f(x) là d, thì X phải bé hơn n^(1/d), và trong trường hợp này thì X < n^(1/5). Vì flag^5 to hơn n, nên flag to hơn n^(1/5), do vậy mà mình không thể dùng Coppersmith để giải ra flag ngay lập tức được.

Để tạo ra phương trình mà có nghiệm < n^(1/5) và giải = Coppersmith, mình sẽ phải sử dụng 1 thông tin khác rất quan trọng mà mọi người thường hay bỏ lỡ:

Đó là flag luôn có dạng BKSEC{...}.

Vì theo đề bài ta có l = 53, nên phần ... trong flag chỉ chiếm có 53 - 7 = 46 bytes mà thôi. Và vì con số đó tương đương với 46*8=368 bits, trong khi n^(1/5) sẽ xấp xỉ 2048/5 = 409.6 bits, chúng ta nên suy nghĩ theo hướng là cần tạo ra hàm để giải cho phần ... thay vì tìm cách giải cả cái flag.

(hoặc nếu bạn nào giải được cả flag thì bảo mình nhá :') mình cũng không biết có được không nữa hix, tại mò mãi mà không ra ý)

Tạo ra phương trình

May thay hàm bytes_to_long hoạt động cũng không phức tạp lắm. Nếu bạn dành thời gian đi thử nghiệm 1 chút thì bạn có thể nhận ra rằng hàm này có quy luật như sau:

xxxxxxxxxx
bytes_to_long(byte[0] + byte[1] + byte[2] + ... + byte[n-1]) 
= byte[0] * 256^(n-1) + byte[1] * 256^(n-2) + ... + byte[n-1]

Như vậy, ta có thể suy ra được:

xxxxxxxxxx
bytes_to_long(b'BKSEC{...})
= 'B' * 256^52 + 'K' * 256^51 + 'S' * 256^50 + 'E' * 256^49 + 'C' * 256^48 + '{' * 256^47 + ? * 256^46 + ... + ? * 256^1 + '}'
= 11218995871735093487161080956769118277607957494981887808631780963798464689101531164867880752334038264192570603194059857495851133 + ? * 256^46 + ... + ? * 256^1
= 11218995871735093487161080956769118277607957494981887808631780963798464689101531164867880752334038264192570603194059857495851133 + 256 * (? * 256^45 + ? * 256^44 + ... + ?)
= 11218995871735093487161080956769118277607957494981887808631780963798464689101531164867880752334038264192570603194059857495851133 + 256 * x

Với x là một số có 368 bits.

Vì vậy, ta có thể đặt

Và dùng Coppersmith để giải $g(x)=0\mathrm{mod}n$$g(x) = 0 \mod n$ với $X=2^{368}$$X = 2^{368}$.

Code giải

Tuy lí thuyết là vậy, nhưng khi thực hành sẽ khó khăn hơn 1 chút. May thay theo Wiki, thuật toán Coppersmith được thực hiện dưới dạng hàm small_roots trong sage. Với những ai chưa dùng sage, thì đại loại nó là 1 ngôn ngữ lập trình nhìn 99.999% giống Python.

Code mẫu

xxxxxxxxxx
from Crypto.Util.number import *

set_verbose(2) # Show output of Coppersmith

e = 5
N = 12015877997327252175076120312423175105723461868777059585810222036358918783467414287643432190947190786537093339282160308346975288678674432143426250190709021016831250908101810274658898975353281727552890093414187602315603911322814265706034002878643080070591319446411326545606427027907006051688317769461922389975196872900254522093565875140439944562548515732597932150601402602403195253684885360376374685106193161372933888346449329403651387981516301918661360919515900594095694744927900343002829948284125210613977913862883912507003034134770232874412487878644640842887800510975707753471130578272563122578877626551522287674097
l = 53
c = 5562931535583484617256604644509628645834662861704445289348492775196895168427686091725679215263205879725144908431055742780470842895864519394889001940231547646790107249009489416972289701307862269450771340549640328909814417579965795018784605202248304929088399220539858726813553822946788808764467934624443033406429967536285715991274724142143817267673695159323420482466290407287110266003347181790634451481348871446847434958148110080492955701749604087626156503554584480028851337053826052171567169497489536695272674103468427199662543313920099195353803442752089147439391576939086697556515968236200200239877271511921097985456

s = bytes_to_long(b'BKSEC{') * 2**(l*8 - 48) + bytes_to_long(b'}')
P.<x> = PolynomialRing(Zmod(N))
f = (x*256 + s)**e - c
root = f.monic().small_roots(
    X=2**368,
    beta=1,
    epsilon=0.023,
)[0]

print(b'BKSEC{' + long_to_bytes(int(root)) + b'}')

Phân tích code

• s = bytes_to_long(b'BKSEC{') * 2**(l*8 - 48) + bytes_to_long(b'}')

  chỉ là 1 cách viết nhanh gọn để tính

  xxxxxxxxxx
  'B' * 256^52 + 'K' * 256^51 + 'S' * 256^50 + 'E' * 256^49 + 'C' * 256^48 + '{' * 256^47 + '}'
  

  mà thôi.

• P.<x> = PolynomialRing(Zmod(N)) là để tạo ra ẩn x nằm trong ring ${\mathbb{Z}}_n$$\Z_n$ nha. Đại khái là mọi biến được gán bằng việc kết hợp x với một số thứ khác sẽ trở thành 1 hàm ẩn x và mod n luôn.

• f = (x*256 + s)**e - c là ví dụ cho hàm được nói ở trên đó :3

• root = f.monic().small_roots( X=2**368, beta=1, epsilon=0.023)[0] để lấy nghiệm đầu tiên của hàm f mà small_roots tìm được.

  • f.monic() được dùng để biến f(x) thành 1 hàm cùng nghiệm với nó với chút sự khác biệt đó là hệ số của x^5 của f.monic() = 1.

    f.monic() được tính bằng cách chia f(x)cho hệ số của x^5 trong ring ${\mathbb{Z}}_n$$\Z_n$.

    Lí do ta phải làm thế là vì Coppersmith hay là small_roots không chạy được nếu hệ số của số mũ cao nhất của f(x) không bằng 1.

Lưu ý

Khi giải bài này thì nhớ chú ý đến 3 arguments X, beta và epsilon nha. Nếu chỉ dùng f.small_roots() không thì sẽ không giải được. Đặt X = 2^368 vì mình biết x luôn có ít hơn hoặc bằng 368 bits nên luôn nhỏ hơn 2^368, còn hai giá trị beta và epsilon thì cứ mò đến khi nào ra nghiệm thì thôi :3

Nếu mà bạn nào cảm thấy bài này quá guessing phần beta và epsilon, thì có thể dùng code Coppersmith của ông này. Code ở đây sẽ print chi tiết hơn về điều kiện để mà thuật toán chạy okela và in chi tiết những giá trị của điều kiện đó ra để mò biến và debug 1 cách dễ dàng hơn :)

tuy vẫn phải mò nhưng mà mò này có phương hướng hơn 1 tí :#

Flag

xxxxxxxxxx
BKSEC{~g00d-a55umptions-br1ng-y0U-t0-A-cl05er-TrutH~}