Hackctf Rsa 전체롸업

LeeDoHyun · March 5, 2020

RSA 1번 문제입니다.

p = 165500656692790480820099871308511495889550056248884963056391533737398719640777027536552348753003910353538512236389328276408434154714592616388810121411482595574799223632695324557638432891315001647024573557093357114908462069403023829967780936191142143068307535312844772151507357729244716123687935330409738850181
q = 122141438575770439104084639124669389798489623069980415671656975299923395151301777382093192959734330849008684250930530493655750402979451442939127736597078242925067195617957339753271262399847630938612930834827285581446954616798548644945058711157525778059878711651283927027641401287892466364366504983328484106481
e = 65537
c = 0x4730dcb8284416e44265091248de1ba51ce685ae5ff1276e263f72a1c90e34bcddc0ad1aa7757f1130c2f497b0629fb620e63b0b613ebe82c8b0a8d6f91a6652947f25c026307446cb7552e075e4754f1d60685a2b45e6238d3aca9934e47c0447e06d6162c91f912d14fb262ffce00e59fc8d04cbeb86cc5f087fbfe620b10e4d6a2c7ca9cb2ed315c31ee07b994b38c2827308c82de3b9ca7352505fe9b10a0ab4c81acc8334587f1277647509dca65001ad418f71e537d32bd71c10c89966b91a9426b440f3db5c52d4faf7440fbdae309bdd70769198e64995a6b3fdae748cc5db22dff8aa4fb235af657c96390d923a2b216dc34c07e28c588d8ef7c882

이라는 값을 주는데 여기서 우리가 디크립트 하기위해서 알아야 되는것은 c, d, n값입니다. 근데 현제 p, q, e값을 알고있기때문에 d와 n값을구할 수 있습니다.

n 값은 p * q으로 얻을 수 있습니다. d는 phi에 대한 e의 곱셈의 역원을 구해주면 됩니다.

solve.py

from Crypto.Util.number import *

p = 165500656692790480820099871308511495889550056248884963056391533737398719640777027536552348753003910353538512236389328276408434154714592616388810121411482595574799223632695324557638432891315001647024573557093357114908462069403023829967780936191142143068307535312844772151507357729244716123687935330409738850181
q = 122141438575770439104084639124669389798489623069980415671656975299923395151301777382093192959734330849008684250930530493655750402979451442939127736597078242925067195617957339753271262399847630938612930834827285581446954616798548644945058711157525778059878711651283927027641401287892466364366504983328484106481
e = 65537
c = 0x4730dcb8284416e44265091248de1ba51ce685ae5ff1276e263f72a1c90e34bcddc0ad1aa7757f1130c2f497b0629fb620e63b0b613ebe82c8b0a8d6f91a6652947f25c026307446cb7552e075e4754f1d60685a2b45e6238d3aca9934e47c0447e06d6162c91f912d14fb262ffce00e59fc8d04cbeb86cc5f087fbfe620b10e4d6a2c7ca9cb2ed315c31ee07b994b38c2827308c82de3b9ca7352505fe9b10a0ab4c81acc8334587f1277647509dca65001ad418f71e537d32bd71c10c89966b91a9426b440f3db5c52d4faf7440fbdae309bdd70769198e64995a6b3fdae748cc5db22dff8aa4fb235af657c96390d923a2b216dc34c07e28c588d8ef7c882

n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
dec = long_to_bytes(pow(c, d, n))
print dec

RSA 2번 문제입니다.

(n, c) = 
675517326695494061190287679557796696358902817969424171685361,
0xe3712876ea77c308083ef596a32c5ce2d7edf22abbc58657e

위와 같은 값이 주워지는데 n을 소인수 분해한 후, p, q값을 얻어 phi값을 구해준뒤 d값을 구해야 되는데 e값이 없습니다. 하지만 e값을 유추할 수 있습니다.

평소에 RSA암호에서 e값은 65537이라는 값이 많이 쓰입니다. 이값을 넣고 돌리면 디크립트할 수 있습니다.

solve.py

from Crypto.Util.number import *

p = 804811499343607200702893651293
q = 839348502408870119614692320677
n = 675517326695494061190287679557796696358902817969424171685361
c = 0xe3712876ea77c308083ef596a32c5ce2d7edf22abbc58657e
e = 65537

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
dec = long_to_bytes(pow(c, d, n))
print dec

RSA 3번 문제입니다.

n = 10283681839193276126097189449431804469761940095295471888398234447479454966284763902940257262270896218602885591849219329295416054197234326881779747263501982465102957508563705432633950651360492963151374387619070656704554971992649022858286686244477458518219811343940208016922937570643216329114427596008380607613093481777894261584227765149699743645734317383348201997748556656749211035951710759363655486663011079526697122026161182876988679088458171192764980121987583057238040415225285169219391637708267493561674900564748140379192079752942242600521017002960185256025253900075152690586476143729320416895984549165574371936823
c = 0x5c93ba85692a8b3981a5d47be0e80d129b8a2f6cf4dc134547aa7e1620f6691513b1dc1d69e085c39e261c2b49026436bb243dba70a86f7fcd1a3a7e6b0f0ecfac015becad0a76e9cf208d5d31e2b4865
e = 3

이 문제는 위 두문제와 조금 다릅니다. e값이 너무작고 n값이 너무큽니다. 이때 사용할 수 있는방법은 c의 e제곱근을 하면됩니다.

이번에는 조금 다른 모듈을 섞어서 사용하겠습니다 gmpy2모듈을 추가로 사용하는데, 이모듈에 cbrt라는 함수가 인자값에 3제곱근을 해줍니다.

solve.py

from Crypto.Util.number import *
from gmpy2 import *

n = 10283681839193276126097189449431804469761940095295471888398234447479454966284763902940257262270896218602885591849219329295416054197234326881779747263501982465102957508563705432633950651360492963151374387619070656704554971992649022858286686244477458518219811343940208016922937570643216329114427596008380607613093481777894261584227765149699743645734317383348201997748556656749211035951710759363655486663011079526697122026161182876988679088458171192764980121987583057238040415225285169219391637708267493561674900564748140379192079752942242600521017002960185256025253900075152690586476143729320416895984549165574371936823
c = 0x5c93ba85692a8b3981a5d47be0e80d129b8a2f6cf4dc134547aa7e1620f6691513b1dc1d69e085c39e261c2b49026436bb243dba70a86f7fcd1a3a7e6b0f0ecfac015becad0a76e9cf208d5d31e2b4865
e = 3

with local_context() as ctx:
    ctx.precision = 3000
    dec = long_to_bytes(cbrt(c))
    print dec

Twitter, Facebook