[picoCTF] basic-mod2 writeup

문제

https://play.picoctf.org/practice/challenge/254?page=1&search=basic-mod

Take each number mod 41 and find the modular inverse for the result. Then map to the following character set: 1-26 are the alphabet, 27-36 are the decimal digits, and 37 is an underscore.

104 290 356 313 262 337 354 229 146 297 118 373 221 359 338 321 288 79 214 277 131 190 377

풀이

해결 과정

nums = [104, 290, 356, 313, 262, 337, 354, 229, 146, 297, 118, 373, 221, 359, 338, 321, 288, 79, 214, 277, 131, 190, 377]

for num in nums :
    mod = num % 41

    inv = 0
    for i in range(41) :
        if (mod * i) % 41 == 1 :
            inv = i
            break

    if inv == 37 :
        print('_', end = '')
    elif inv >= 27 and inv <= 36 :
        print(str(inv-27), end = '')
    elif inv >= 1 and inv <= 26 :
        print(chr(inv + 64), end = '')
    else :
        print()

각 숫자에 모듈러 41을 취한 후, 브루트포스 방법으로 modular inverse를 찾아주었다. 해당 값이 발견되면 즉시 break로 for문을 탈출한 후
문제에 주어진 대로 매핑해주었다.
modular inverse를 알고 있었다면 더욱 수월하게 풀었을 것.

정답

picoCTF{1NV3R53LY_H4RD_8A05D939}