RSA for CTF
2019-09-24 / JSec

목차

  • RSA Key Gen
  • RSA 암호화 및 복호화
    • 암호화
    • 복호화
  • RSA 문제 종류
    • d값 계산
    • 낮은 지수 공격
    • n값 소인수 분해 및 DB 이용
    • 위너 공격
    • 하스타드 공격
    • 선택 암호문 공격
    • p, q값이 비슷할 경우 n 값으로 p, q값 구하기
  • 레퍼런스
  • 문서 역사

RSA Key Gen

  1. p, q 선택

    • python에선 다음과 같이 p, q를 생성할 수 있다.

      • 1
        2
        3
        4
        from Crypto.Util.number import *

        p = getPrime(1024) # 1024bit
        q = getPrime(1024)
  2. n 계산

    • p와 q를 곱하면 n이 된다.
  3. phi 계산

    • (p-1)과 (q-1)을 곱하면 phi가 된다.
  4. e 선택

    • 주로 65537
    • phi와 서로소인 수
  5. d 계산

    • d = mod n

      • mod phi에 대한 e의 곱셈의 역원
    • python에서 d값을 계산하는 방법은 두가지이다.

      • 1
        2
        3
        4
        5
        6
        7
        8
        from gmpy2 import *
        from Crypto.Util.number import *

        p = getPrime(1024) # Crypto.Util.number
        q = getPrime(1024) # Crypto.Util.number
        phi = (p-1) * (q-1)
        e = 65537
        d = invert(e, phi) # gmpy2
      • 1
        2
        3
        4
        5
        6
        7
        8
        from gmpy2 import *
        from Crypto.Util.number import *

        p = getPrime(1024) # Crypto.Util.number
        q = getPrime(1024) # Crypto.Util.number
        phi = (p-1) * (q-1)
        e = 65537
        d = divm(1, e, phi) # gmpy2
      • invert는 곱셈의 역원을 구해주고 divm의 첫 번째 인자를 1로 지정해주면 역원을 구해주는 기능을 한다. (곱셈의 역원이란 곱했을 때 1이 나오는 수를 의미한다.)

공개키(public key) : (e,n)

개인키(private key): (d,n)


RSA 암호화 및 복호화

  • 암호화
    • 암호문 = mod n
  • 복호화
    • 평문 = mod n

RSA 문제 종류

  • d값 계산

    • p, q, e 값 등이 주어졌을 경우 n값과 phi 값을 계산 가능하기 때문에 d 값을 계산하면 된다.
    • gmpy2의 invert또는 divm를 사용한다.

      • d = invert(e, phi)
      • d = divm(1, e, phi)
    • 예시 코드 (문제에서 p, q, e, c가 주어졌다고 가정)

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        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")
  • 낮은 지수 공격

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

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

    • gmpy2의 iroot 또는 cbrt를 사용한다.

      • m = iroot(c, 3)[0]
      • m = cbrt(c)
    • 예시 코드 (문제에서 c, e값이 주어졌고 e 값이 3이라고 가정)

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        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 값은 정밀도에 관한 값인데 만약 결과 값이 재대로 나오지 않는다면 해당 값을 더 높게 수정해서 정밀도를 올려야 한다.

  • n값 소인수 분해 및 DB 이용

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

    • d 값을 구하기 위해서 phi 값이 필요하고 phi를 구하기 위하여 p, q 값이 필요한데, n이 작다면 소인수 분해를 통해서 p, q값을 계산 가능하다.

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

    • 주로 웹 사이트를 이용한다.

  • 위너 공격

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

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

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

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

      • 1
        2
        3
        4
        5
        6
        7
        8
        # RSAwienerHacker.py
        if __name__ == "__main__":
        n =
        e =
        c =
        d = hack_RSA(e, n)

        print ('%x' % pow(c, d, n)).decode("hex")
  • 하스타드 공격

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

    • e 값은 주로 3이다.

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

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

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        47
        48
        49
        50
        51
        52
        53
        54
        55
        56
        57
        58
        59
        60
        61
        62
        63
        64
        65
        66
        67
        68
        69
        70
        71
        72
        73
        74
        75
        76
        77
        78
        79
        80
        81
        82
        83
        84
        85
        86
        87
        88
        89
        90
        91
        92
        93
        94
        95
        96
        97
        98
        99
        100
        101
        102
        103
        104
        105
        106
        107
        108
        109
        110
        111
        112
        113
        114
        115
        116
        117
        118
        119
        120
        121
        122
        123
        124
        125
        126
        127
        128
        129
        130
        131
        132
        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 "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
  • 선택 암호문 공격

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

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

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

      1. 숫자 2를 암호화 한다.

      2. 숫자 2를 암호화한 값과 flag를 암호화한 값을 곱한다.

      3. 결과 값을 숫자 2로 나누면 플래그가 된다.

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

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

    • 이때 n 값만 주어져도 p, q값을 구할 수 있게 된다.

    • gmpy2의 isqrtt_divmod를 이용하면 된다.

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

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        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")

레퍼런스

https://blog.naver.com/yjw_sz/221441769257

https://blog.naver.com/yjw_sz/221396346574

https://xerxes-break.tistory.com/341


문서역사

2019-09-24 JSec: 최초 작성