RSA와 RSA 공격법 (d값 계산, 낮은 지수 공격, 소인수 분해, 하스타드 공격, 위너 공격)

RSA 공개키 개인키 구하는 법

1. p, q선택

파이썬에서 p, q값을 생성하는 방법은 다음과 같다

from Crypto.Util.number import getPrime

p = getPrime(1024) #1024 bit
q = getPrime(1024)

pycryptodome가 설치되어 있지 않다면 $ pip install pycryptodome 로 설치해 준다

 

2. n 계산

p와 q를 곱하면 n이 된다

n = p * q

 

3. phi 계산

(p-1)과 (q-1)을 곱하면 phi가 된다

phi = (p - 1) * (q - 1)

 

4. e 선택

주로 65537이다

다른 값이라도 phi와 서로소인 수

 

5. d 계산

mod phi에 대한 e의 곱셈의 역원을 구한다

gmpy2의 invert나 divm으로 계산할 수 있다

d = invert(e, phi)
d = divm(1, e, phi)

invert는 바로 곱셈의 역원을 구해주고, divm는 첫 번째 인자를 1로 지정해주면 역원을 구해준다

 

6. 결과

공개키: (e, n)

개인키: (d, n)

---

RSA 암호화 및 복호화

암호화

암호문 = 평문^e mod n

 

복호화

복호문 = 암호문^d mod n

---

RSA 공격들

1. d값 계산

RSA에서 n값과 phi값을 계산할 수 있으면 d값이 나와서 복호화가 가능하다

아니면 p, q, e값이 주어졌을 때도 n과 phi값을 계산할 수 있다

만약 p, q, e가 주어졌으면 n = p*q로 n 구하고, phi=(p-1)*(q-1)로 phi를 구하면 된다

 

n과 phi값을 구했으면 d를 구하기 위해 mod n에 대한 곱셈의 역원(곱했을 때 1이 나오는 수)을 구한다

곱셈의 역원은 gmpy2의 invert나 divm으로 계산할 수 있다

 

d = invert(e, phi)
d = divm(1, e, phi)

invert는 바로 곱셈의 역원을 구해주고, divm는 첫 번째 인자를 1로 지정해주면 역원을 구해준다

 

from gmpy2 import *

phi = 23079175999650261543000051288341715950034109926658542519727080390553485584836589385804681319018295730173751924209320558260485473378546413216108872802506593333079135314669197743332337508879842413221472886943211445491722723443429004123868556481781431711563268181969712877598553629448215935461900433200909733855850563121229212919614870629815706079606220871508903841727402814339384578549212124030181289268556255605556462262215034668423236882520695239627559904020281499927979831389029969019829095252031822779012678507402377916410144606589983681845721957381827624407936397476592806471370644374868522766022819870197111204440
c = 17690551262096405896997154248725997515162859536189985259882620957841740356071423219560297369474828213466967201771164687541608745959958467063622022419843151428220248429311985180109113409296866627645017481648436647470073637057339226996155027170872942948923904302506711076655585890415141797781507177399516687651493521523703286733762563735525517513570518486400810504153999312891688387831723168627964370935160294311101923119713980141096689780888538850330510146325767650622448208609031278489950532189695427650410320398942689734345440267920479954877726527607076209770130773170212954092147635827833024203399183409626583390820
n = 23079175999650261543000051288341715950034109926658542519727080390553485584836589385804681319018295730173751924209320558260485473378546413216108872802506593333079135314669197743332337508879842413221472886943211445491722723443429004123868556481781431711563268181969712877598553629448215935461900433200909733856156811192771870602856568816330053155412189330149287658917220084117422477737432709948576788031260905005742860826571594847937212100950533703614841755154052910734542215287496941210843206017137581508016542011903277402767402219140077313852775334164577572703553955826477449270131749844530868444193626077136684359727
e = 65537

d = invert(e, phi)

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

phi, c, n, e값을 넣어주고 d값을 구한다

---

2. 낮은 지수

너무 작은 e값과 너무 큰 n값이 같이 주어졌을 때 가능한 공격에 낮은 지수 공격이 있다

보통 이런 경우 e값은 3을 주는데, 암호문의 세제곱근을 구하면 평문이 된다

gmpy2의 iroot나 cbrt를 사용하여 풀 수 있다

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

cbrt는 세제곱근을 구해주고, iroot는 두 번째 인자를 3으로 주면 세제곱근을 구해준다

주의할 점은 iroot는 반환값이 튜플이라 0번째 있는 값이 원하는 값이다

 

예시 코드

from gmpy2 import *

c = 2523454692080985130926824733361219117105925267704273748310491104599011343499491160640561478562668718117804355694949

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

---

3. n값 소인수 분해

작은 수의 n과 e만 주어졌을 경우, p, q값을 구하기 위해서 n을 무작정 소인수 분해해 볼 수 있다

아니면 소인수 분해 DB에 나와있는 소인수 분해값인 경우에도 이런 식으로 구할 수 있다

주로 웹 사이트를 이용한다 www.factordb.com/

 

4. 위너 어택

e값이 너무 큰 경우 가능한 공격 방법

e값이 65537보다 훨씬 클 경우에 d값을 도출할 수 있는 특징을 이용한다

 

위너 공격을 해 주는 소스코드를 사용한다(RSAwienerHacker.py)

github.com/pablocelayes/rsa-wiener-attack

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

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

 

5. 하스타드 어택

e값이 작고(주로 3), n값과 c값이 3개씩 주어질 때 사용 가능한 공격 방법

 

{n1, n2, n3}에 대해 동일한 평문 m이 3개 있을 때

암호문 c1, c2, c3이 있고 각각의 암호문을 (n1, e), (n2, e), (n3, 3)로 암호화

중국인의 나머지 정리(CRT)로 c^t == x (mod n1n2n3)를 계산한다

m^3 < n1n2n3 이기 때문에 c^t = m^3

즉, 공개키 e가 작은 경우 일반적으로 모든 공개키가 같고, k>=e 이기만 하면 평문 m을 복호화할 수 있다

 

github.com/aaossa/Computer-Security-Algorithms/blob/master/11%20-%20H%C3%A5stad's%20Broadcast%20Attack/hastads-broadcast-attack.py#L7 이곳의 코드를 참조했다

import gmpy2
gmpy2.get_context().precision = 4096

from binascii import unhexlify
from functools import reduce
from gmpy2 import root

# Håstad's Broadcast Attack
# https://id0-rsa.pub/problem/11/

# Resources
# https://en.wikipedia.org/wiki/Coppersmith%27s_Attack
# https://github.com/sigh/Python-Math/blob/master/ntheory.py

EXPONENT = 3

CIPHERTEXT_1 = "ciphertext.1"
CIPHERTEXT_2 = "ciphertext.2"
CIPHERTEXT_3 = "ciphertext.3"

MODULUS_1 = "modulus.1"
MODULUS_2 = "modulus.2"
MODULUS_3 = "modulus.3"


def chinese_remainder_theorem(items):
    # Determine N, the product of all n_i
    N = 1
    for a, n in items:
        N *= n

    # Find the solution (mod N)
    result = 0
    for a, n in items:
        m = N // n
        r, s, d = extended_gcd(n, m)
        if d != 1:
            raise "Input not pairwise co-prime"
        result += a * s * m

    # Make sure we return the canonical solution.
    return result % N


def extended_gcd(a, b):
    x, y = 0, 1
    lastx, lasty = 1, 0

    while b:
        a, (q, b) = b, divmod(a, b)
        x, lastx = lastx - q * x, x
        y, lasty = lasty - q * y, y

    return (lastx, lasty, a)


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 get_value(filename):
    with open(filename) as f:
        value = f.readline()
    return int(value, 16)

if __name__ == '__main__':

    C1 = get_value(CIPHERTEXT_1)
    C2 = get_value(CIPHERTEXT_2)
    C3 = get_value(CIPHERTEXT_3)
    ciphertexts = [C1, C2, C3]

    N1 = get_value(MODULUS_1)
    N2 = get_value(MODULUS_2)
    N3 = get_value(MODULUS_3)
    modulus = [N1, N2, N3]

    C = chinese_remainder_theorem([(C1, N1), (C2, N2), (C3, N3)])
    M = int(root(C, 3))

    M = hex(M)[2:]
    print(unhexlify(M).decode('utf-8'))

 

defenit.kr/2019/09/24/Crypto/%E3%84%B4%20Research/RSA_for_CTF/ 이곳의 코드처럼 하는 방법도 있다

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 "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"

 

 

참고

xerxes-break.tistory.com/341

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