6주차 암호

RSA 암호 알고리즘

두 개의 키가 사용된다. 하나는 공개키이고 다른 하나는 비밀키이다.

공개키(Public key): 모든 사용자에게 공개되며, 평문을 암호화할 때 사용

비밀키(Private key): 타인에게 노출되어서는 안 되며, 공개키로 암호화된 암호문을 복호화할 때 사용됩니다.

키 생성

공개키와 비밀키를 생성하는 키 생성 과정이 필요하다. RSA는 소인수분해를 어렵게 만들기 위해 복잡한 연산을 거쳐 키를 생성해야 한다.

1. 먼저 서로 다른 두 소수 와 를 선택한다. 일반적으로 1024비트 이상에서 비트 길이가 같은 수로 생성한다. 그 뒤, 와 를 곱하여 을 구하고, 을 계산합니다.

2. 보다 작은 수 중 과 서로소인 를 선택하고, 인 를 구합니다. 의 곱셈의 역원이 존재하기 위해서는 과 가 서로소임이 필수적다.

과 는 공개키로 는 비밀키로 사용된다. 뜻은 각각

법(Modulus)

공개 지수(Public exponent),

비밀 지수(Private exponent)

이다.

RSA의 암호화와 복호화

암호문 c를 각각 암호화 복호화 하는 법은 다음과 같다.

암, 복호화 원리

오일러의 정리에 따르면 다음과 같은 등식이 성립한다.

예제는 다음과 같다.

from Crypto.Util.number import getPrime

class RSA:
    def __init__(self, bitlen):
        while True:
            p, q = getPrime(bitlen // 2), getPrime(bitlen // 2)

            self.n = p * q   # Public key
            self.e = 0x10001 # Public key

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

            if phi % self.e == 0:
                continue

            self.d = pow(self.e, -1, phi) # Private key

            break

    def encrypt(self, pt):
        # Encryption only relys on public key
        # Which means everyone who has public key can encrypt any plaintext.

        assert 0 <= pt < self.n
        
        ct = pow(pt, self.e, self.n)
        return ct

    def decrypt(self, ct):
        # Decryption needs d which is a private key
        # Only who has the private key can decrypt.

        assert 0 <= ct < self.n

        pt = pow(ct, self.d, self.n)
        return pt

if __name__ == "__main__":
    rsa = RSA(1024)

    plaintext = 1234
    ciphertext = rsa.encrypt(plaintext)

    assert rsa.decrypt(ciphertext) == plaintext

RSA와 RSA-CRT

RSA 시스템은 큰 수 끼리의 곱셈 과정을 사용하여 상대적으로 오랜 시간이 소요되고, 많은 양의 메모리를 필요로 한다. 전자 서명을 동반한 키 공유 등에 오히려 더 적합하다. PEM (Privacy Enhanced Mail) 서명 시스템은 여러 종류가 있고, 이 중에서는 RSA 서명을 포함한 종류 또한 존재다.

PEM RSA 공개키의 경우 다음과 같은 형식으로 표현된다.

PEM RSA 비밀키의 경우 다음과 같은 형식으로 표현된다.

비밀키의 경우 뿐만 아니라 다음의 세 값을 저장한다.

RSA에 대한 공격

잘못된 값을 설정하거나 오용으로 인해 취약점이 생기는 경우가 존재한다. 여러 취약점에 각각 따른 알려진 공격들이 존재다

Common modulus attack

같은 과 서로소인 두 공개 지수 를 사용하여 같은 평문 을 암호화해서 두 암호문 을 만들었을 때, 이를 공격하는 기법다.

작은 에 대한 공격

e=3인 경우

Cube attack

작은 크기의 평문 을 작은 공개 지수 를 사용해 암호화하는 경우, 거듭제곱을 한 후에도 보다 크기가 작을 가능성이 존재한다. 이러한 경우는 를 으로 나눈 나머지와 의 결과가 동일다.

Håstad's broadcast attack

prob.py

from Crypto.Util.number import getPrime, GCD, bytes_to_long

FLAG = b"DH{????????????????????????}"
FLAG = bytes_to_long(FLAG)

while True:
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q

    # e = 0x10001 
    # assert GCD((p - 1)*(q - 1), e) == 1... Oh, COME ON.. Stop generating that stupid COMMON e.
    for e1 in range(0x100, 0x10001):
        if GCD(p - 1, e1) >= 0x100: # much better!
            break

    for e2 in range(0x100, 0x10001):
        if GCD(q - 1, e2) >= 0x100: # This is nice!!
            break

    if GCD(e1, e2) == 1: # UN-UN common == common :P
        break

print(f"{N = }")
print(f"{e1 = }")
print(f"{e2 = }")

FLAG_enc1 = pow(FLAG, e1, N)
FLAG_enc2 = pow(FLAG, e2, N)

print(f"{FLAG_enc1 = }")
print(f"{FLAG_enc2 = }")

Common modulus attack의 사용 조건과 정확히 일치함을 알 수 있다.

익스플로잇 설계

이 상황에서 을 복구하는 것이 목적이고, 을 만족하는 쌍을 찾는 것으로부터 공격이 시작된다. 의 식에서 양변을 위에서 생각하면 다음과 같이 식이 변형된다.

, 즉 pow(e1, -1, e2) 또는 inverse(e1, e2)를 사용하여 원하는 을 구할 수 있다.

솔브코드

from Crypto.Util.number import GCD, long_to_bytes

N = ...
e1 = 26107
e2 = 416
FLAG_enc1 = ...
FLAG_enc2 = ...

assert GCD(e1, e2) == 1
r = pow(e1, -1, e2)
s = (1 - r * e1) // e2

assert r * e1 + s * e2 == 1

m = (pow(FLAG_enc1, r, N) * pow(FLAG_enc2, s, N)) % N

print(long_to_bytes(m).decode())

스터디

6주차 암호

RSA 암호 알고리즘

키 생성

RSA의 암호화와 복호화

암, 복호화 원리

RSA와 RSA-CRT

RSA에 대한 공격

Common modulus attack

작은 에 대한 공격

Cube attack

Håstad's broadcast attack

prob.py

익스플로잇 설계

솔브코드

티스토리툴바

6주차 암호

RSA 암호 알고리즘

키 생성

RSA의 암호화와 복호화

암, 복호화 원리

RSA와 RSA-CRT

RSA에 대한 공격

Common modulus attack

작은 e에 대한 공격

Cube attack

Håstad's broadcast attack

prob.py

익스플로잇 설계

솔브코드

티스토리툴바

작은 에 대한 공격