6081

n = int(input(), 16)
for i in range(1, 16):
    print('%X'%n, '*%X'%i, '=%X'%(n*i), sep='')

6082

i = int(input())
for h in range(1, i+1):
    if h%10==3 or h%10==6 or h%10==9:
        print("X", end=' ')
    else:
        print(h, end=' ')

6083

r, g, b = map(int, input().split())
num = 0

for i in range(0, r):
    for j in range(0, g):
        for h in range(0, b):
            print(i, j, h)
            
            num+=1
print(num)

6084

h, b, c, s = map(int, input().split())
space = (h*b*c*s)/8/1024/1024

print(round(space, 1) ,"MB")

h, b, c, s = map(int, input().split())
space = (h*b*c*s)/8/1024/1024

print(format(space, ".1f"), "MB")

6085

#반올림이 아닌 소수점 2자리까지 표기하는거인듯
#전에 했던 코드처럼 입력했더니 0.00으로 나와야하는 값이 0.0으로 출력됨

w, h, b = map(int, input().split())
space = ((w*h*b)/8/1024/1024)

print(format(space, ".2f"), "MB")

6086

n = int(input())
s,c = 0,1

while True:
    s += c 
    c += 1
    if s >= n:
        break

print(s)

6087

n = int(input())

for i in range(1, n+1):
    if i%3 == 0:
        continue
    print(i, end=' ')

6088

a, d, n = map(int, input().split())
count = 1 #a+b부터가 2번째 숫자여서 처음값을 1로 설정

while True:
    a += d 
    count += 1
    if count == n:
        break

print(a)

6089

a, r, n = map(int, input().split())
count = 1 

while True:
    a *= r 
    count += 1
    if count == n:
        break

print(a)

6090

a, m, d, n = map(int, input().split())
count = 1 

for i in range(n-1):
    a = a*m+d
print(a)

#첫번째, 즉 range에서 0은 처음 지정한 a의 값이 아닌 계산된 2번째 수열이 해당되기 때문에 range(n-1)임
#range(n)으로 했을 때 출력결과는 -1 3 -5 11 -21  임

6091

a, b, c = map(int, input().split())
d = 1

while True:
    if d%a==0 and d%b==0 and d%c==0:
        break
    d += 1

print(d)

#문제 제공코드 사용 - 더 빠름
a, b, c = map(int, input().split())
d = 1

while d%a!=0 or d%b!=0 or d%c!=0:
    d += 1
print(d)

6092

n = int(input())
a = input().split()

for i in range(n):
    a[i] = int(a[i])

d = []
for i in range(24):
    d.append(0)

for i in range(n):
    d[a[i]] += 1

for i in range(1, 24):
    print(d[i], end = ' ')

6093

#문제에 제공된 코드 사용
n = int(input())
k = input().split()

for i in range(n-1, -1, -1):
    print(k[i], end=' ')

#다른풀이
n = int(input())
k = input().split()

a = list(reversed(k))
b = list(map(int, a))
c = str(b)[1:-1]
print(c.replace(",",""))

6094

n = int(input())
k = map(int, input().split())

print(min(k))

6095

d = [[0 for j in range(20)] for i in range(20)]

n = int(input())
for i in range(n):
    x, y = input().split()
    d[int(x)][int(y)] = 1

for i in range(1, 20):
    for j in range(1, 20):
        print(d[i][j], end=' ')
    print()


d = []
for i in range(20):
    d.append([])
    for j in range(20):
        d[i].append(0)

n = int(input())
for i in range(n):
    x, y = input().split()
    d[int(x)][int(y)] = 1

for i in range(1, 20):
    for j in range(1, 20):
        print(d[i][j], end=' ')
    print()

6096

d = []
for i in range(20):
    d.append([])
    for j in range(20):
        d[i].append(0)

for i in range(1, 20):
    data = input().split()
    for j in range(1, 20):
        d[i][j] = int(data[j-1]) 
        
n = int(input())

for i in range(n):
    x,y = input().split()
    for j in range(1,20):
        if d[j][int(y)]==1:
            d[j][int(y)]=0
        else:
            d[j][int(y)]=1

        if d[int(x)][j]==1:
            d[int(x)][j]=0
        else:
            d[int(x)][j]=1

for i in range(1, 20):
    for j in range(1, 20):
        print(d[i][j], end=' ')
    print()

6097

h, w = map(int, input().split())

a = []
for i in range(h):
    a.append([])
    for j in range(w):
        a[i].append(0)

n = int(input())

for i in range(n):
    l, d, x, y = map(int,input().split())
    for j in range(l):
        a[int(x-1)][int(y-1)] = 1
        if d == 1:
            x += 1
        elif d == 0:
            y += 1

for i in range(h):
    for j in range(w):
        print(a[i][j], end=' ')
    print()

6098

d = [[0 for j in range(10)] for i in range(10)]

for i in range(10):
    d[i] = list(map(int, input().split()))

x = 1
y = 1

while True:
    if d[x][y] == 0:
        d[x][y] = 9
    if d[x][y] == 2:
        d[x][y] = 9
        break
    if d[x][y+1] == 1 and d[x+1][y] == 1:
        break
    if d[x][y+1] != 1:
        y += 1
    elif d[x+1][y] != 1:
        x += 1

for i in range(10):
    for j in range(10):
        print(d[i][j], end=' ')
    print()

6060

i, h = map(int, input().split())
print(int(i&h))

6061

i, h = map(int, input().split())
print(int(i|h))

6062

i, h = map(int, input().split())
print(int(i^h))

6063

i, h = map(int, input().split())
print(i if (i>h) else h)

i, h = map(int, input().split())
print(i if (i>=h) else h)

6064

i, h, j = map(int, input().split())
print((i if i<h else h) if ((i if i<h else h)<j) else j)

6065

i, h, j = map(int, input().split())
if i%2==0:
    print(i)
if h%2==0:
    print(h)
if j%2==0:
    print(j)

6066

i, h, j = map(int, input().split())
if i%2==0:
    print("even")
else:
    print("odd")
if h%2==0:
    print("even")
else:
    print("odd")
if j%2==0:
    print("even")
else:
    print("odd")

6067

i = int(input())
if i<0 :
    if i%2==0:
        print('A')
    else:
        print('B')
else:
    if i%2==0:
        print('C')
    else:
        print('D')

6068

i = int(input())
if i>=90:
    print('A')
else:
    if i>=70:
        print('B')
    else:
        if i>=40:
            print('C')
        else:
            print('D')

6069

i = input()
if i=='A':
    print('best!!!')
elif i=='B':
    print('good!!')
elif i=='C':
    print('run!')
elif i=='D':
    print('slowly~')
else:
    print('what?')

6070

i = int(input())
if i//3==1:
    print('spring')
elif i//3==2:
    print('summer')
elif i//3==3:
    print('fall')
else:
    print('winter')

6071

n = 3 
while n!=0 :
  n = int(input())
  if n!=0 :
    print(n)

6072

n = int(input())
while n!=0:
    print(n)
    n = n-1

6073

i = int(input())
while i!=0:
    print(i-1)
    i = i-1

6074

i = ord(input())
h = ord('a')
while h<=i:
    print(chr(h), end=' ')
    h += 1

6075

i = int(input())
h = int('0')
while h<=i:
    print(int(h))
    h+=1

6076

i = int(input())
h = int('0')
while h<=i:
    print(int(h))
    h+=1

6077

i, h = 2, 0 
a = int(input())
while i <= a:
  h += i 
  i += 2 
print (h)

6078

i = ''
while i!='q':
    i = input()
    print(i)

6079

i = int(input())
h, j = 0, 0
while j<i :
  h+=1
  j+=h  

print(h)

6040

i, h = input().split()
i = int(i)
h = int(h)
print(i//h)

6041

i, h = input().split()
i = int(i)
h = int(h)
print(i%h)

6042

i = input()
i = float(i)
print(format(i, '.2f'))

6043

i1, i2 = input().split()
i1 = float(i1)
i2 = float(i2)
print(format(i1/i2, '.3f'))

6044

i, h = input().split()
i = int(i)
h = int(h)
print(i+h)
print(i-h)
print(i*h)
print(i//h)
print(i%h)
print(format(i/h, '.2f'))

6045

i, h, j = map(int, input().split())
print(i+h+j, format((i+h+j)/3, '.2f'))

6046

i = int(input())
print(i<<1)

6047

i, h = map(int, input().split())
print(i<<h)

6048

i, h = map(int, input().split())
print(i<h)

6049

i, h = map(int, input().split())
print(i==h)

6050

i, h = map(int, input().split())
print(i<=h)

6051

i, h = map(int, input().split())
print(i!=h)

6052

i = int(input())
print(i!=0)

6053

i = bool(int(input()))
print(not i)

6054

i, h = input().split()
print(bool(int(i)) and bool(int(h)))

6055

i, h = input().split()
print(bool(int(i)) or bool(int(h)))

6056

i, h = input().split()
i = bool(int(i))
h = bool(int(h))
print((i and (not h)) or ((not i) and h))

6057

i, h = input().split()
i = bool(int(i))
h = bool(int(h))
print(((not i) and (not h)) or (i and h))

6058

i, h = input().split()
i = bool(int(i))
h = bool(int(h))
print(not(i or h))

6059

i = int(input())
i = ~i 
print(int(i))

주말에 이것저것 찾아보다가 새로운 워게임 사이트를 발견했다

Crypto - noisy

encrypt.py

from Crypto.Util.number import *

flag = "UNKNOWN"

p = getPrime(2048)
q = getPrime(2048)
e = 3
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
N = p * q

a = getPrime(256)
b = getPrime(256)
flag = bytes_to_long(flag)
flag1 =  a * flag + b

c1 = pow(flag1, e, N)
c2 = pow((flag), e, N)

assert(pow(c1, d, N) == flag1)
assert(pow(c2, d, N) == flag)

print(N)
print(e)
print(c1)
print(c2)
print(a)
print(b)

encrypt.py를 보면 내가 구하려는 것은 flag이기 때문에 주어진 6개의 요소 중 c1, a, b는 사용하지 않았다.
다운받은 enc.txt도 보면 e값이 3으로 매우 작은것을 알 수 있었고 낮은지수 공격을 이용하여 문제를 풀었다.

from gmpy2 import *
from Crypto.Util.number import *
import time 
n = 317040651679373211203052920616005723678020156043628323332424772070975737453408838469787064188786011573404860315719531289497744855149648693106833220893566469137933367925417989088393428081488338940326190378085032657287146700415402636680277863355428263621630525484435545273639843015411759501613170657498993265825219268635185095788704667818488133253959599802463638649406699422719391733724583724025291694081932388296146208021483007849056796340521197771858162785429158848258434728868971277822370788477078046638988244145956273926422409006854446490844902097353140906585907615729831021135264713171213218099904040054190835213689864989036128553169219265026898127693711592592146507088549862468638817790078090116453255902533987667528301890465974635865742293209293806778416593653897850790336390681201239324555097941294112232117306893385741521626628689787545632725387549814767531756371737740572219769069441283585425896640819299563592008738345302900504187795287179485677802770486028077737997406541494777650298180989153685352404527946553530659987383623342371095072298448494604853114349302537264362538517244435429874419107749816127165211721817516961841383469631957904885678760629435470386620807103484614770446981317888580422731368821491703012190183243
c = 8297423020022584155011048994131832532824769074603023730133414978795876083975829767265894418737130405482092398749557510849356438382806334207752350424328189587538835124850818790342725062432577666660785216065345678061943982215620548836592472455231224905601436909814422212405387665285635705441455639510030326136599676781656710020740773913531981988901910524876336689922252137646035508407628715768925469851812056183896960489642237162363954459588105185425583983516407862459239754702318180363135870652414123417287108500334785797074965659493879646074666170795550533107295994421467507825853297020990968465269194425974012716422816703183529876173808423121297943817528992643716946584739099328084201918671645348445667073297906942267193317797356444500014074902610476607216717889696917598060829137189261664903853879838844091472012719908117333187156067157240412062289054821454999696908286081864861687576456825071844285971295647010885157801032909560332164820250910702287272446130959717
e = 3


with local_context() as ctx:
    ctx.precision=3000
    m=iroot(c,e)[0]

flag = long_to_bytes(m)

print(flag)

chall.py

import string
from secret import MSG

def encryption(msg):
    ct = []
    for char in msg:
        ct.append((123 * char + 18) % 256)
    return bytes(ct)

ct = encryption(MSG)
f = open('./msg.enc','w')
f.write(ct.hex())
f.close()

msg.enc

6e0a9372ec49a3f6930ed8723f9df6f6720ed8d89dc4937222ec7214d89d1e0e352ce0aa6ec82bf622227bb70e7fb7352249b7d893c493d8539dec8fb7935d490e7f9d22ec89b7a322ec8fd80e7f8921

sol.py

from Crypto.Util.number import *

ct = '6e0a9372ec49a3f6930ed8723f9df6f6720ed8d89dc4937222ec7214d89d1e0e352ce0aa6ec82bf622227bb70e7fb7352249b7d893c493d8539dec8fb7935d490e7f9d22ec89b7a322ec8fd80e7f8921'

def decryption(ct):
    pt = []
    for char in ct:
        pt.append((char - 18) * inverse(123, 256) % 256)
    return bytes(pt)

print(decryption(bytes.fromhex(ct)))

주어진 코드를 보고 암호문을 대상으로 거꾸로 실행하면 된다.

 

output

b'Th3 nucl34r w1ll 4rr1v3 0n fr1d4y.\nHTB{l00k_47_y0u_r3v3rs1ng_3qu4710n5_c0ngr475}'

HTB{l00k_47_y0u_r3v3rs1ng_3qu4710n5_c0ngr475}

'wargame > hack the box' 카테고리의 다른 글

HTB Lost Modulus writeup  (0) 2023.03.30
HTB RSAisEasy writeup  (0) 2023.03.30
HTB xorxorxor writeup  (0) 2023.03.30

번역 오류 - RSA

RSA의 두 소수인 p,q를 sexy prime으로 정하여 암호화를 진행했다.
Python 코드를 보고 sexy prime을 이용했다는 사실을 알아내면 쉽게 풀 수 있다.

시나리오
한세가 해외에 있는 친구에게 CTF 문제를 받았다.
영어를 잘 못하는 한세는 번역기를 이용하여 지문을 한글로 번역했는데 '섹시한 전성기' 라는 좀 특이한 말이 나왔다.
한세: 번역 오류인가…?
#암호화 과정에 사용되는 코드의 일부분이다.

from Crypto.Util.number import *

def ????????????(n=512):

    while True:
        p = getPrime(n)
        if isPrime(p+6):
            return p, p+6
n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147
e = 4294967297
c = 6430247517459839550819948528043546662220213283222011078853709086595801980582952628540465603132800123118448644982850090295098382544235129216039103121116669154107985284621853508059922122931259093211612076479073223996615242648597460278767826566208475843728873065225999150624847387541305731206359041053619452936

위와 같이 python 코드와 n, e, c 값이 있는 txt 파일을 주었다.
우선 python 코드 파일을 보면 전에 봤던 50점짜리 RSA 문제와는 p, q 값이 다르게 주어졌다는 것을 알 수 있다.
좀 더 자세히 코드를 보면 p, q가 6씩 차이나는 소수라는 것을 알 수 있는데 이처럼 두 수 간의 차이가 6인 소수 쌍을 sexy prime이라고 한다.
sexy prime:
https://ko.wikipedia.org/wiki/%EC%84%B9%EC%8B%9C_%EC%86%8C%EC%88%98
따라서 우리는 문제 python 코드를 통해 p, q가 sexy prime이라는 것을 알 수 있다. 이 방법 말고도 시나리오에 나와있는 '섹시한 전성기'라는 말을 번역하면 sexy prime이 되는데 '섹시한 전성기'라는 단어에 집중해보면 sexy prime을 유추해낼 수 있다.

이 방법의 경우 만약 이 문제를 풀기 전에 RSA 문제를 풀어봤다면 N이 소수인 p, q로 이루어져있다는 것을 알고있을 것이다.
그럼 이 문제에서 sexy prime을 과연 어디에 적용했을지에 대해 생각해보면 p, q에 적용했다는 것을 짐작할 수 있다.
* 참고로 주어진 python 파일에 코드 일부분을 ???????????? 와 같이 물음표로 처리한 이유는 그 부분에 쓰이는 함수가 getSexyPrime이기 때문이다.
 
그럼 대충 어떤식으로 두 소수를 구할지 알아보자

sexy prime이 6씩 차이나는 소수라는 점을 감안하면 위와 같이 생각해볼 수 있다.

 
위에 작성한 식을 응용하여 풀이 코드를 작성해보면 여러 방향으로 작성해볼 수 있는데

(1) 위 식을 활용해서 p, q 먼저 구하고 그 값을 통해 복호화 진행하기
출력결과에서 먼저 출력해주는 q 값이 음수로 나올것이다. 근데 python 코드에도 나와있듯이 sexy prime을 이용한 것이기 때문에 음수로 나오는 값은 무시했다..

from sympy.solvers import solve
from sympy import Symbol

n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147

x = Symbol('x')
q = (x+6)-n/x
p = x
print(solve(q, p))

#출력결과
#q = 10491301818794197956870533631920141403582366486363388796717340358676229364128532294712102202896995090338673728372102793882839671201902933776303545620582969
#p = 10491301818794197956870533631920141403582366486363388796717340358676229364128532294712102202896995090338673728372102793882839671201902933776303545620582963
from Crypto.Util.number import *

n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147
e = 4294967297
c = 6430247517459839550819948528043546662220213283222011078853709086595801980582952628540465603132800123118448644982850090295098382544235129216039103121116669154107985284621853508059922122931259093211612076479073223996615242648597460278767826566208475843728873065225999150624847387541305731206359041053619452936

q = 10491301818794197956870533631920141403582366486363388796717340358676229364128532294712102202896995090338673728372102793882839671201902933776303545620582969
p = 10491301818794197956870533631920141403582366486363388796717340358676229364128532294712102202896995090338673728372102793882839671201902933776303545620582963

phi = (p-1)*(q-1)
d = inverse(e,phi)

flag = pow(c, d, n)

print(long_to_bytes(flag))

(2) 이진탐색 방식 - 다른 블로그 참고함

from Crypto.Util.number import *

n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147
c = 6430247517459839550819948528043546662220213283222011078853709086595801980582952628540465603132800123118448644982850090295098382544235129216039103121116669154107985284621853508059922122931259093211612076479073223996615242648597460278767826566208475843728873065225999150624847387541305731206359041053619452936

low = 0
high = n
while(high - low > 1):
    mid = (high + low) // 2
    if(mid*(mid+6) >= n):
        high = mid
    else:
        low = mid

p = high
q = high + 6
e = 4294967297
phi = (p-1)*(q-1)
d = inverse(e,phi)

flag=pow(c,d,n)
print(long_to_bytes(flag))

(3) isqrt(n의 음이 아닌 정수 제곱근을 반환해줌) 사용 - 다른 블로그 참고함

from Crypto.Util.number import *
from math import isqrt

n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147
e = 4294967297
c = 6430247517459839550819948528043546662220213283222011078853709086595801980582952628540465603132800123118448644982850090295098382544235129216039103121116669154107985284621853508059922122931259093211612076479073223996615242648597460278767826566208475843728873065225999150624847387541305731206359041053619452936


def fermat_method(N, attempt=None):
    a = isqrt(N) + 1
    while attempt != 0:
        b2 = a * a - N
        if isqrt(b2)**2 == b2:
            return (a - isqrt(b2), a + isqrt(b2))
        a += 1
        if attempt is not None:
            attempt -= 1
    return None

p, q = fermat_method(n)

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

print(long_to_bytes(m))

(4) x를 기준으로 p, q가 3씩 차이난다는 점을 이용

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

n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147
e = 4294967297
c = 6430247517459839550819948528043546662220213283222011078853709086595801980582952628540465603132800123118448644982850090295098382544235129216039103121116669154107985284621853508059922122931259093211612076479073223996615242648597460278767826566208475843728873065225999150624847387541305731206359041053619452936


def decrypt(n,e,c):

    x = isqrt(n+9)
    p = x+3
    q = x-3

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

print(decrypt(n, e, c))

flag: HSOC{Th3_P@pag0_1s_1nnoc3nt}
(문제 제작에는 구글번역기를 사용했지만 문제에 알맞게 번역기 이름을 플래그에 넣고 싶었다. 번역기하면 파파고가 떠오르더라구요..)
 
위 4가지 방법 모두 출력결과로 플래그가 잘 나온다.
이 외에도 다른방식으로 코드를 작성할 수 있고 sexy prime의 특성만 이해하고 있다면 툴을 이용해서 n을 소인수분해한 다음 p, q를 구하고 복호화하거나(내가 했을 때는 소인수분해에 실패했다.) Python으로 p, q를 구하고 툴로 플래그를 얻어낼 수 있을 것이다.
또한 브루트포스를 이용하여 풀어도 플래그값이 나오기는 할 것 같다. 
 
처음에 설명한 것처럼 2가지 접근방법을 통해 sexy prime 이라는 것을 알 수 있도록 문제를 제작하였지만 사실 sexy prime이라는 것을 몰라도 p, q가 6씩 차이난다는 것을 활용하면 문제를 풀 수 있다.
주어진 값과 코드를 이용해서 RSA에 핵심적으로 이용되는 값들을 정리해보면 아래와 같다.

#주어진 값
n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147
e = 4294967297
c = 6430247517459839550819948528043546662220213283222011078853709086595801980582952628540465603132800123118448644982850090295098382544235129216039103121116669154107985284621853508059922122931259093211612076479073223996615242648597460278767826566208475843728873065225999150624847387541305731206359041053619452936

#구할 수 있는 값
q = 10491301818794197956870533631920141403582366486363388796717340358676229364128532294712102202896995090338673728372102793882839671201902933776303545620582969
p = 10491301818794197956870533631920141403582366486363388796717340358676229364128532294712102202896995090338673728372102793882839671201902933776303545620582963
phi = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385866214933599301649088771042832253374216040038133772221497120204739641131707798971948525466766989162765960908733420538816418446236549761226777345066448191216
d = 15098229052637160358532865616389298506396159965552798705730231466638846621357610535466416013940312645793598912529231727525911386433046899145504172681621130407086662312734205341155034093231254932808853267354434062164601943943394941506606066039410904591461324161029868452303484330376860103353089292266012833025

 
원래는 처음에 만든 50점 RSA 문제 이후 다음 문제를 DES 문제로 만들려고 생각했었다. 근데 하다보니 뜻대로 안될때도 꽤 있었고 DES 문제를 만들려면 키를 weak key나 semi weak key를 사용해서 하려고했는데.. 문제를 만들다 중간에 검토해봤는데 뭔가 좀 마음에 안들어서 RSA 활용(?) 문제를 만들게되었다.

이 문제도 첫번째 50점 문제를 풀었으면 쉽게 풀 수 있는 문제라서 50점으로 바꿀까 고민을 했었다. 근데 다행히도 교내대회 100점에 적당했던 것 같다. 웬만하면 겹치는 유형 없이 최대한 다양하게 문제를 출제하고 싶었는데 아쉽다...

 

(sexy prime이 아닌 twin prime을 사용했을 경우에는..??)

저저번주 금요일(9/23)에 교내 해킹방어대회가 열렸다. hsoc 동아리 부원들이 문제를 출제하고 운영하는 대회이며 나같은 경우 이번에 씨텦 문제도 첨 만들어봐서 어려움을 좀 겪었다. 현재 hsoc의 암호학 분야에 속해있기 때문에 총 3문제를 만들었고 50, 100, 200점으로 최대한 다양하게 만들었다.
 
솔직히 문제를 만들기 전에는 3일 정도면 문제를 다 만들고도 남을줄 알았다..ㅎ 어림도 없었다. 생각보다 문제를 만드는데 처음에 내가 만들고자 했던것과 다르게 흘러가는 경우가 많았고 만들고보니까 너무 쉽게 만들어진 경우가 많아서 몇번을 갈아엎었는지 모르겠다.
안그래도 시간이 없는데 계속 갈아엎고 다시 만드느라 나중에는 라잇업이랑 열려있는 대회 사이트 여기저기에 다 들어가보면서 새로운 문제 유형을 계속 찾아봤던 것 같다. 그래서 아마 문제들을 보면 다른 대회에서 한번쯤은 나온 유형의 문제다,, 교외대회가 아닌 교내대회라 그나마 다행이라 해야할까... 암튼 좀 질좋은 문제를 만들어보고싶었는데 그닥 만족스럽지는 않다.
 
근데 당일날 대회를 진행하다보니 50, 100점 문제를 푼 사람이 많이 없어서 150, 200점 문제는 공개하지도 못했다.
그래도 이번에 문제를 출제하면서 새로운 문제 유형도 진짜 많이 보고 심도있게 공부할 수 있어서 유익하고 좋았다. 다음에 중학생 대상으로 하는 교외대회에서는 기간을 좀 넉넉하게 잡고 문제를 푸는분들이 알차고 질좋다고 느낄만한 문제를 출제하고싶다. 또 시간이 좀 남는다면 크립토 외에 다른 분야 문제도 공부해보고 출제해보고 싶다. 
 
마지막으로 평일날 학교 끝나고 짧은시간 동안 진행했던 대회인데도 불구하고 끝까지 열심히 풀어주신 참가자분들께 너무 감사하고 계속 학교에 남아서 같이 문제를 출제했던 동아리 부원분들과 외부 강사님들께도 진짜 감사하다는 말씀드리고싶다. (특히 대회의 전반적인 부분들을 진행/운영해주신 선배님들 넘 감사드리고 존경합니다..)
 

easy RSA - 50점

대표적인 공개키 알고리즘인 RSA를 활용한 문제이다.

<시나리오>
한세가 비밀 문서를 보기 위해 잠금을 해제하려고 노력하고 있다. 노트북에 e, c, p, q 4개의 파일이 있다.
파일을 보니 안에 알 수 없는 숫자들이 있어서 메모장에 메모를 해 놓았다. 이 메모를 활용하여 잠금을 해제할 수 있을 것 같다.
from Crypto.Util.number import *

e = 257

p = getPrime(1024) 
q = getPrime(1024) 
n = p * q

flag = b"HSOC{????????????}"
c = pow(bytes_to_long(flag), e, n)

print(f"e = {e}")
print(f"c = {c}")
print(f"p = {p}")
print(f"q = {q}")
e = 257
c = 5170614309301223184388980439033937972958595751713320965808860175588790115219381694288306180451949710261512480304973718112228889626940113529439227149734487012037630024859786546305225093967154391890149077265714446582747768706411436149671496479109814775690406008776885497246411111989054712865047658076549493437166223452452855195649368804859350881162375200684571102147323943146082552216356213851098024600173550937621944196190441066471923633389014705391050788386027507663015531178749441167149946800122899769099206880827114130951143393000212588720045757847160070434793928195140628142207776720680351969286852634379093267395
p = 121082940632566084365045468274080389844245747988255783680486430339285622475938449072789554464746638386992904689290579744213300917014736134613903560443148772127353839823710670680986528534128280877375044770611360109829049475842435278969303947209412658556907276581778492754960030258658453902050691012787944153029
q = 93773260875800805924403007041088524372825300383500367049104233796459989047050929611151854646094506486446127494624906576319038878918384371070507039400233234869045356878874646585055502928435133167377331216852702026481058788799943840756755689058510106076276525924408876911194766461521214272472920976958554265097

위처럼 python 파일 하나와 txt 파일을 문제파일로 제공해주었다.
 
1. 문제를 보면 e, c, p, q 4개의 값이 주어졌는데 이는 각각 공개키, 암호문, 두 소수를 나타낸다.
우리가 구하고자 하는것은 플래그값인 M(평문)인데, 이를 구하기 위해서는 개인키인 d와 N이 필요하다.
참고로 마지막 식에서 N이 아닌 Φ(N)을 법으로 둔 이유는 지수들이 Zn*의 원소 자체가 아니고 원소의 색인으로 작용하기 때문이라 한다. (이제부터 Φ(N)을 phi라 하겠음)
위 식에 따라서 phi를 아는 공격자는 e의 역원을 계산해서 d를 쉽게 유도할 수 있고 그렇게 때문에 p와 q가 노출되면 안된다.
phi = (p-1)*(q-1)이기 때문이다.
 
2. 주어진 문제에서는 p와 q가 주어졌기 때문에 이 값을 통해서 phi를 구할 수 있다. 주어진 p, q를 통해 N 또한 구할 수 있다.
구한 phi와 주어진 e를 이용하여 mod의 역원을 계산하여 d를 구할 수 있다.
M을 구하는데 필요한 요소인 c, d, n을 통해 평문을 얻어낼 수 있다.
 
3. 최종적으로 코드를 작성해보면 아래와 같다.

from gmpy2 import *

p = 121082940632566084365045468274080389844245747988255783680486430339285622475938449072789554464746638386992904689290579744213300917014736134613903560443148772127353839823710670680986528534128280877375044770611360109829049475842435278969303947209412658556907276581778492754960030258658453902050691012787944153029
q = 93773260875800805924403007041088524372825300383500367049104233796459989047050929611151854646094506486446127494624906576319038878918384371070507039400233234869045356878874646585055502928435133167377331216852702026481058788799943840756755689058510106076276525924408876911194766461521214272472920976958554265097
e = 257
c = 5170614309301223184388980439033937972958595751713320965808860175588790115219381694288306180451949710261512480304973718112228889626940113529439227149734487012037630024859786546305225093967154391890149077265714446582747768706411436149671496479109814775690406008776885497246411111989054712865047658076549493437166223452452855195649368804859350881162375200684571102147323943146082552216356213851098024600173550937621944196190441066471923633389014705391050788386027507663015531178749441167149946800122899769099206880827114130951143393000212588720045757847160070434793928195140628142207776720680351969286852634379093267395

n = p * q
phi = (p-1) * (q-1)
d = invert(e, phi) # d = divm(1, e, phi)

print ('%x' % pow(c, d, n))

#출력결과: 48534f437b495f406d5f68756e6772797d
m = '48534f437b495f406d5f68756e6772797d'
print(bytes.fromhex(m))

#출력결과: HSOC{I_@m_hungry}

구한 요소들을 RSA 복호화 사이트에 넣어도 평문이 정상적으로 나온다.
flag: HSOC{I_@m_hungry}

base64?

base64를 이용한 문제이다.

 

우선 주어진 파일 중 encode_data.txt 파일을 cyberchef에 from base64를 이용하여 돌려봤는데 평문이 나오지 않는 것을 확인했다.

그래서 우리가 일반적으로 사용하는 base64와는 알파벳 순서를 다르게 설정하여 encode 했다고 추측했다.

우선 data.txt를 일반적인 base64로 돌린 후 encode_data.txt와 비교해보았는데 받은 txt 파일과는 다른 것을 확인할 수 있다.

 

이를 보고 원래 encode문과 주어진 encode문을 비교해가며 알파벳 순서를 작성해서 이후 일반적인 base64로 decode하면 플래그가 나올 것이라 생각했다.

 

위 사진과 같이 비교해가며 문제에 사용된 base64 알파벳 순을 다시 작성한 후 문제에서 flag로 준 base64문을 원래 base64 알파벳 순을 이용하여 다시 바꿨다.

Y2NlMjAyMnt3ZWxjMG1lX2NjMl9nb29vb29kXzp1Y2sp Q==

그럼 변환하지 못한 '9'자리에 위치한 한글자 빼고는 모두 변환을 완료했고 이를 cyberchef로 돌려보면 아래와 같은 결과가 나온다.

 

빈 곳을 입력하지 않고 decode하자 플래그의 일부분이 나왔고 마지막 단어인 :uck을 luck이라고 추측하여 입력했더니 맞다고 떴다. 

6020

i, h= input().split('-')
print(i, h, sep='')

6021

i = input()
print(i[0])
print(i[1])
print(i[2])
print(i[3])
print(i[4])

6022

i = input()
print(i[0:2], i[2:4], i[4:6])

6023

i, h, j = input().split(':')
print(h)

6024

i, h = input().split()
j = i + h
print(j)

6025

i, h = input().split()
j = int(i) + int(h)
print(j)

6026

i = input()
h = input()
i = float(i)
h = float(h)
print(i + h)

6027

i = input()
i = int(i)
print('%x' %i)

6028

i = input()
i = int(i)
print('%X' %i)

6029

i = input()
h = int(i, 16)
print('%o' %h)

6030

i = ord(input())
print(i)

6031

i = int(input())
print(chr(i))

6032

i = int(input())
print(-i)

6033

i = input()
i = ord(i)
print(chr(i+1))

6034

i, h = input().split()
i = int(i)
h = int(h)
print(i-h)

6035

i1, i2 = input().split()
i1 = float(i1)
i2 = float(i2)
print(i1 * i2)

6036

i, h = input().split()
print(i*int(h))

6037

i = input()
h = input()
print(int(i)*h)

6038

i, h = input().split()
i = int(i)
h = int(h)
print(i**h)

6039

i1, i2 = input().split()
i1 = float(i1)
i2 = float(i2)
print(i1**i2)