for ENG version scroll down
Zadanie polegało na odszyfrowaniu wiadomości szyfrowanej za pomocą RSA mając dostęp do klucza publicznego. Wiadomość to:
kPmDFLk5b/torG53sThWwEeNm0AIpEQek0rVG3vCttc=
A klucz:
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhALYtzp8lgWNXI9trGI8S8EacvuDLxdrL
NsNuDJa26nv8AgMBAAE=
-----END PUBLIC KEY-----
Zadanie wspomniało też, że klucz publiczny nie jest całkiem poprawny i brakuje mu jakiegoś bitu. Dekodujemy klucz publiczny i uzyskujemy:
n = 82401872610398250859431855480217685317486932934710222647212042489320711027708
e = 65537
Widzimy od razu że wartość n jest niepoprawna bo nie jest iloczynem 2 liczb pierwszych (dzieli się przez 4). Zamieniamy więc ostatni bit z 0 na 1 uzyskując liczbę 82401872610398250859431855480217685317486932934710222647212042489320711027709
Klucz jest bardzo krótki - ma tylko 256 bitów co oznacza, że jest podatny na faktoryzację. Dokonujemy jej za pomocą narzędzia yafu:
Na tej podstawie uzyskujemy liczby p oraz q potrzebne do odtworzenia klucza prywatnego. Dokonujemy tego za pomocą rozszerzonego algorytmu Euklidesa:
def egcd(a, b):
u, u1 = 1, 0
v, v1 = 0, 1
while b:
q = a // b
u, u1 = u1, u - q * u1
v, v1 = v1, v - q * v1
a, b = b, a - q * b
return a, u, v
q = 295214597363242917440342570226980714417
p = 279125332373073513017147096164124452877
e = 65537
n = 82401872610398250859431855480217685317486932934710222647212042489320711027709
phi = (p - 1) * (q - 1)
gcd, a, b = egcd(e, phi)
d = a
if d < 0:
d += phi
print("n: " + str(d))
Mając liczbę d możemy teraz dokonać dekodowania wiadomości. Zamieniamy wiadomość na liczbę:
ct = 65573899802596942877560813284504892432930279657642337826069076977341847221975
A następnie wykonujemy:
pt = pow(ct, d, n)
print("pt: " + long_to_bytes(pt))
I uzyskujemy flagę: TMCTF{$@!zbo4+qt9=5}
The task was to crack RSA encoded message based on provided public key. The message was:
kPmDFLk5b/torG53sThWwEeNm0AIpEQek0rVG3vCttc=
And the key was:
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhALYtzp8lgWNXI9trGI8S8EacvuDLxdrL
NsNuDJa26nv8AgMBAAE=
-----END PUBLIC KEY-----
The task description mentioned that there is something wrong with public key and there is a bit missing. We decode the public key and we get:
n = 82401872610398250859431855480217685317486932934710222647212042489320711027708
e = 65537
We can clearly see that the n is incorrect since it's not a product of 2 prime numbers (it is divisible by 4). We swtich last bit from 0 to 1 and we get 82401872610398250859431855480217685317486932934710222647212042489320711027709
The key is very short - only 256 bits so we can factor it. We do it using yafu:
Based on this we get p and q numbers required for private key recovery. We do this with extended euclidean algorithm:
def egcd(a, b):
u, u1 = 1, 0
v, v1 = 0, 1
while b:
q = a // b
u, u1 = u1, u - q * u1
v, v1 = v1, v - q * v1
a, b = b, a - q * b
return a, u, v
q = 295214597363242917440342570226980714417
p = 279125332373073513017147096164124452877
e = 65537
n = 82401872610398250859431855480217685317486932934710222647212042489320711027709
phi = (p - 1) * (q - 1)
gcd, a, b = egcd(e, phi)
d = a
if d < 0:
d += phi
print("n: " + str(d))
With the d number we can now decode the message. We change the message into a number:
ct = 65573899802596942877560813284504892432930279657642337826069076977341847221975
Execute:
pt = pow(ct, d, n)
print("pt: " + long_to_bytes(pt))
And get the flag: TMCTF{$@!zbo4+qt9=5}