Crypto for CTF

RSA

• 개인키(d값) 구하기

from gmpy2 import *

p = 
q = 
e = 65537
c = 

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

print ('%x' % pow(c, d, n)).decode("hex")

• 선택 암호문 공격 (Cycling Cliphertext Attack)
  • e 값이 매우 작고, n 값이 큰 경우
  • e = 3 경우가 많다

from gmpy2 import *

c = 
e = 

with local_context() as ctx:
    ctx.precision = 3000
    m = iroot(c, e)[0]
    
    print ('%x' % int(m)).decode("hex")

• 위너 공격 (Weiner's Attack)
  • e 값이 매우 큰 경우
  • git clone https://github.com/pablocelayes/rsa-wiener-attack.git 설치하여 RSAwienerHacker.py 수정

if __name__ == "__main__":
    e = 
    n =
    c = 
    d = hack_RSA(e, n)

    print ("D = " + str(d))
    print ('%x' % pow(c, d, n)).decode("hex")

• C값이 매우 큰 경우

from pwn import *

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

c = 
n = 
e = 65537

phi = 

d = modinv(e, phi)
m = pow(c, d, n)

flag = unhex(hex(m)[2:])

print('flag: {}'.format(flag))

• p와 q 값이 비슷한 경우

from gmpy2 import *

n = 
e = 65537
c = 

p = isqrt(n)

while True:
    q, r = t_divmod(n, p)
    if r == 0:
        break
    p += 1
    
phi = (p-1) * (q-1)
d = invert(e, phi)

print ('%x' % pow(c, d, n)).decode("hex")

 

 

서포트

Integer factorization calculator : 소인수분해 계산

FactorDB : 소인수분해 데이터베이스

RsaCtfTool : RSA 도구

Brainfuck : (ex. "[>+++++++++") 암복호화

quipqiup : 치환암호 복호화

CyberChef : 다양한 인코딩 지원

Cryptii : 다양한 인코딩 지원

 

 

References

https://defenit.kr/2019/09/24/Crypto/%E3%84%B4%20Research/RSA_for_CTF/