공개키 암호 방식(RSA)

공개키 암호 방식 (= 비대칭키 암호)

비대칭키 암호는 공개키를 이용해 암호화하고 공개키에 해당하는 비밀키를 이용해 복호화하는 방식입니다.

대표적인 예로 RSA, 타원 곡선 암호, 전자 서명 등이 있습니다.

 

RSA 알아보기

RSA 알고리즘은 크게 3단계(키 생성, 암호화, 복호화)로 나뉩니다.

 

키 생성

1. 두 개의 큰 소수인 p와 q를 선택합니다. p=123123123, q=590129113
2. p와 q의 곱인 N을 계산(N=p*q)합니다. n=p*q
3. 1부터 N-1 까지의 정수 중 N과 서로소인 정수의 개수를 구합니다.(φ(N)=(p-1)*(q-1)) 이 값을 N에 대한 오일러 파이(φ) 함수 값이라고 합니다. phi=(p-1)*(q-1)
4. 1<e<φ(N) 이고 φ(N)과 서로소인 공개키 e를 생성합니다.
5. (d*e)modφ(N)=1 이고 0<=d<= N 인 d를 구합니다. d = gmpy2.invert(e, phi)

• 생성된 값들 중 N과 e는 공개키로, d는 비밀키로 사용됩니다.

 

암호화

• M은 평문, C는 암호문, N과 e는 공개키입니다.
• C = M^e mod N
• m ** e % n

 

복호화

• 복호화에는 비밀키인 d가 사용됩니다.
• M = C^d mod N
• c ** d % n
• key = RSA.construct(n, e, d)

 

파이썬 코드로 표현

• crypto 라이브러리 설치 (pip install pycrypto)
• gmpy2 설치하기 위해 미리 다운받아야 할 것 
  • MAC (brew install gmp, brew install mpfr, brew install libmpc)
  • Ubuntu (apt-get install libgmp3-dev, apt-get install libmpfr-dev, apt-get install libmpc-dev)
• gmpy2 라이브러리 설치 (pip install gmpy2)

#!/usr/bin/python2
#-*- coding: utf-8 -*-

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

# 키 생성
p = getPrime(1024)      # p 생성 (1024bit)
q = getPrime(1024)      # q 생성 (1024bit)
n = p * q
phi = (p-1) * (q-1)
e = 65537               # e 선택 (phi와 서로소인 수)
d = invert(e, phi)

# 암호화
m = 'RSA TEST'
enc = pow(bytes_to_long(m), e, n)

#  복호화
dec = pow(enc, d, n)

print(long_to_bytes(dec))

 

 

RSA 문제 유형

[1] d값 계산

• p, q, e 값 등이 주어졌을 경우, n 값과 phi 값을 계산 가능하기 때문에 d 값을 구할 수 있습니다.

gmpy2의 invert또는 divm를 사용합니다.

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

d = invert(e, phi)		# 방식1
d = divm(1, e, phi)		# 방식2

 

예시코드 (문제에서 p, q, e, c가 주어졌다고 가정)

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

p = 
q = 
e = 
c = ''

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

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

 

[2] 낮은 지수 공격

• e 값과 매우 작고 n 값이 큰 경우 가능한 공격 방법

보통 e 값은 3인데, 암호문의 세제곱근을 구하면 평문이 됩니다.

gmpy2의 iroot 또는 cbrt를 사용합니다.

m = iroot(c, 3)[0]
m = cbrt(c)

 

예시코드 (문제에서 c, e값이 주어졌고 e 값이 3이라고 가정)

from gmpy2 import *

c = ''

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

 

cbrt는 세제곱근을 구해주는 함수고 iroot의 두 번째 인자를 3으로 주면 세제곱근을 구해줍니다. 

하지만 iroot의 반환 값은 튜플이고 원하는 값은 0번째 있는 값입니다.

ctx.precision 값은 정밀도에 관한 값인데 

만약 결과 값이 재대로 나오지 않는다면 해당 값을 더 높게 수정해서 정밀도를 올려야 합니다.

 

[3] n값 소인수 분해 및 DB 이용

• 작은 수의 n과 e만 주어졌을 경우 또는 DB에 존재하는 소수인 경우 가능한 공격 방법

d 값을 구하기 위해서 phi 값이 필요하고 phi를 구하기 위하여 p, q 값이 필요합니다. 

n 값이 작다면 소인수 분해를 통해서 p, q 값을 구할 수 있습니다.

매우 큰 소수면 소인수 분해는 못하지만 DB에 존재하는 소수면 바로 p, q 값을 구할 수 있습니다.

 

소인수분해 DB 사이트

• factordb
• ECM

 

[4] 위너 공격

• e 값이 매우 큰 경우 가능한 공격 방법

e 값이 큰 경우 d 값이 작을 확률이 높고 이때 성립합니다.

위너 공격을 해주는 소스 코드를 이용해서 d 값을 알아낼 수 있습니다.

• rsa-wiener-attack

위 링크에서 RSAwienerHacker.py를 다운받고 수정해서 사용합니다.

예시코드 (n, e, c 값이 주어졌다고 가정)

# RSAwienerHacker.py
if __name__ == "__main__":
    n = 
    e = 
    c = ''
    d = hack_RSA(e, n)

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

 

[5] 하스타드 공격

• n값과 c 값이 3개씩 주어 지며 e 값이 작은 경우에 가능한 공격 방법

e 값은 주로 3입니다.

하스타드 공격을 해주는 소스 코드를 이용해서 평문을 알아낼 수 있습니다.

예시코드 (e, n1, n2, n3, c1, c2, c3이 주어졌다고 가정)

import binascii
from Crypto.PublicKey import RSA
from base64 import b64decode

print "\n"
print "\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
print "\t        RSA Hastad Attack         "
print "\t         JulesDT -- 2016          "
print "\t         License GNU/GPL          "
print "\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"

def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)

    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod

def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a / b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1

def find_invpow(x,n):
    high = 1
    while high ** n < x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

def parseC(argv, index, verbose):
    import string
    file = open(argv[index],'r')
    cmd = ' '.join(argv)
    fileInput = ''.join(file.readlines()).strip()
    if '--decimal' in cmd:
        if verbose:
            print "##"
            print "##",fileInput
            print "## Considered as decimal input"
            print "##"
        return long(fileInput)
    elif '--hex' in cmd:
        if verbose:
            print "##"
            print "##",fileInput
            print "## Considered as hexadecimal input"
            print "##"
        return long(fileInput,16)
    elif '--b64' in cmd:
        if verbose:
            print "##"
            print "##",fileInput
            print "## Considered as base64 input"
            print "##"
        return long(binascii.hexlify(binascii.a2b_base64(fileInput)),16)
    else:
        try:
            fileInput = long(fileInput)
            if verbose:
                print "##"
                print "##",fileInput
                print "## Guessed as decimal input"
                print "##"
            return long(fileInput)
        except ValueError:
            if all(c in string.hexdigits for c in fileInput):
                if verbose:
                    print "##"
                    print "##",fileInput
                    print "## Guessed as hexadecimal input"
                    print "##"
                return long(fileInput,16)
            else:
                if verbose:
                    print "##"
                    print "##",fileInput
                    print "## Guessed as base64 input"
                    print "##"
                return long(binascii.hexlify(binascii.a2b_base64(fileInput)),16)
            pass

def parseN(argv,index):
    file = open(argv[index],'r')
    fileInput = ''.join(file.readlines()).strip()
    try:
        fileInput = long(fileInput)
        return fileInput
    except ValueError:
        from Crypto.PublicKey import RSA
        return long(RSA.importKey(fileInput).__getattr__('n'))
        pass


if __name__ == '__main__':
    e = ''

    n1 = 
    n2 = 
    n3 = 

    c1 = 
    c2 = 
    c3 = 

    n = [n1,n2,n3]
    a = [c1,c2,c3]

    result = (chinese_remainder(n, a))
    resultHex = str(hex(find_invpow(result,3)))[2:-1]
    print ""
    print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
    print "Decoded Hex :\n",resultHex
    print "---------------------------"
    print "As Ascii :\n",resultHex.decode('hex')
    print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"

 

[6] 선택 암호문 공격

• 원하는 암호문을 복호화 해주는 경우 가능한 공격 방법 (단, flag는 복호화해주지 않음)

평문의 곱은 암호문의 곱과 동일하다는 성질을 이용합니다.

풀이 방법 (flag를 암호화한 값이 주어지고 암호화, 복호화 기능이 존재한다고 가정)

1. 숫자 2를 암호화 합니다.
2. 숫자 2를 암호화한 값과 flag를 암호화한 값을 곱합니다.
3. 결과 값을 숫자 2로 나누면 플래그가 됩니다.

 

[7] p, q값이 비슷할 경우 n값으로 p, q값 구하기

gmpy2 모듈의 next_prime 함수를 이용할 경우 p, q 값이 거의 차이가 나지 않습니다.

이때 n 값만 주어져도 p, q값을 구할 수 있습니다.

gmpy2의 isqrt와 t_divmod를 이용합니다.

예시코드 (n 값과 e 값이 주어졌다고 가정)

from gmpy2 import *

n = 
e = 
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")

 

키 인수분해 크랙 (bit 수가 너무 적은 경우)

이미 분해된 인수 (codegate 2013? 유형, ex: SSL pcap decrypt)

lsb oracle attack

RSA 곱셈의 성질

• 암호문 cipher2, cipher5 가 있다.
• (c2 * c5) %n) 을 복호화 한 것은 m2 * m5 와 같다.
• ((c2 * c5) % n)^d mod n == m2 * m5
• (2 암호문 * flag %n) ^d mod n == 2 * flag 평문

 

Tools

• OpenSSL

> openssl rsa -in pubkey.pem -pubin -text -modulus
Modulus (256 bit):
    00:d8:e2:4c:12:b7:b9:9e:fe:0a:9b:c0:4a:6a:3d:
    f5:8a:2a:94:42:69:b4:92:b7:37:6d:f1:29:02:3f:
    20:61:b9
Exponent: 12405943493775545863 (0xac2ac3e0ca0f5607)
Modulus=D8E24C12B7B99EFE0A9BC04A6A3DF58A2A944269B492B7376DF129023F2061B9
writing RSA key
-----BEGIN PUBLIC KEY-----
MEIwDQYJKoZIhvcNAQEBBQADMQAwLgIhANjiTBK3uZ7+CpvASmo99YoqlEJptJK3
N23xKQI/IGG5AgkArCrD4MoPVgc=
-----END PUBLIC KEY-----

• 소인수분해DB
• rsatool
• RsaCtfTool: 작은 수의 N, e, c가 있을 때 크랙하는 도구

$ python3 RsaCtfTool.py -n 57772961349879658023983283615621490728299498090674385733830087914838280699121 -e 65537 --uncipher 36913885366666102438288732953977798352561146298725524881805840497762448828130

[*] Testing key /tmp/tmpc2m7ehf6.
Can't load smallfraction because sage is not installed
Can't load boneh_durfee because sage is not installed
Can't load ecm2 because sage is not installed
Can't load qicheng because sage is not installed
Can't load ecm because sage is not installed
Can't load roca because sage is not installed
[*] Performing pollard_p_1 attack on /tmp/tmpc2m7ehf6.
[*] Performing partial_q attack on /tmp/tmpc2m7ehf6.
[*] Performing primefac attack on /tmp/tmpc2m7ehf6.
[*] Performing cube_root attack on /tmp/tmpc2m7ehf6.
[*] Performing noveltyprimes attack on /tmp/tmpc2m7ehf6.
[*] Performing fermat attack on /tmp/tmpc2m7ehf6.
[*] Performing comfact_cn attack on /tmp/tmpc2m7ehf6.
[*] Performing mersenne_primes attack on /tmp/tmpc2m7ehf6.
[*] Performing siqs attack on /tmp/tmpc2m7ehf6.
[!] Yafu SIQS is not working.
[*] Performing pastctfprimes attack on /tmp/tmpc2m7ehf6.
[*] Performing smallq attack on /tmp/tmpc2m7ehf6.
[*] Performing factordb attack on /tmp/tmpc2m7ehf6.

Results for /tmp/tmpc2m7ehf6:

Unciphered data :
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00tjctf{BOLm1QMWi3c}'

$ RsaCtfTool.py --dumpkey --key ./pubkey.pem
[*] n: 98099407767975360290660227117126057014537157468191654426411230468489043009977
[*] e: 12405943493775545863

• 수학기호 사용 모듈(sympy)

 

레퍼런스

• 암알못의 암호핥기-비대칭키암호 - Hackerz on the Ship
• 암호학 정리(for CTF) - Hyunmini Blog
• CRYPTO RSA - Bob&Gook.log Blog
• RSA for CTF - Defenit 블로그

 

문서 History

• 2020.12.15. 최초작성