[SISS/암호학 스터디] 여름 6주차 스터디

[SISS/암호학 스터디] 여름 6주차 스터디 - RSA

24-여름 SISS/암호학 2024. 8. 8. 00:27

: 6주차 08/05 ~ 08/11 공개키 암호

공개키 암호 - RSA

RSA 알고리즘 → 소인수분해 문제의 어려움을 이용 / 연산량이 많으므로 적은 양의 중요 정보 전달 시 이용
- 키 생성
  1. 서로 다른 두 소수 p와 q 선택 → n = p⋅q → ϕ(n) = (p − 1)(q − 1)
  2. ϕ(n)과 서로소인 e 선택 후 d 구하기→ d ≡ e^(−1) mod ϕ(n)
  ⇒ n과 e는 공개키로, d는 비밀키로 사용
  - 공개 지수 e는 65537(0x10001)을 가장 많이 사용
    - 소수
    - 이진법에서 1인 비트가 적어 거듭제곱 연산 시 적은 시간이 소요
    - 적당한 크기이므로 공격으로부터 안전

암, 복호화

암호문 c = m^e mod n
평문 m = c^d mod n
c 복호화
- m^(ed) ≡ m^(k⋅ϕ(n) + 1) ≡ m^(k⋅ϕ(n))m ≡ (m^ϕ(n))^km (mod n)
- 오일러 정리에 따라 d ≡ e^(−1) (mod ϕ(n))이므로 e⋅d = k⋅ϕ(n) + 1을 만족하는 자연수 k가 존재 → (m^ϕ(n))^km ≡ 1^k⋅m ≡ m (mod n)
- 오일러 파이 정리에 의해 m^ϕ(n) ≡ 1 (mod n) → c^d ≡ (m^e)^d ≡ m^(ed) (mod n)

암, 복호화 실습

getPrime → 원하는 비트 수의 임의의 소수를 찾음

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

PEM(Privacy Enhanced Mail) 서명 시스템
- PEM RSA
  - 키의 값들이 BASE64로 인코딩됨
  - 비밀키의 경우 n,e,d,p,q 외 아래 세 값을 저장 → RSA-CRT(복호화 방법)에 사용 (시간을 단축)
    - d_p = d mod (p − 1)
    - d_q = d mod (q − 1)
    - q_(inv) = q^(−1) mod p

// public.pem

// key.pem

RSA 공격 방법

common modulus attack → 같은 n과 서로 다른 e에 대해 여러 번 암호화하는 경우 사용
1. 같은 n과 서로 다른 e로 만들어진 두 암호문 c_1, c_2에 대해 두 공개 지수가 서로소이므로 확장 유클리드 알고리즘을 통해 다음 식을 만족하는 r, s를 구할 수 있음 → re_1 + se_2 = 1
2. 다음 수식을 통해 평문 m을 구할 수 있음 → c_1^r⋅c_2^s ≡ m^(e_1⋅r)⋅m^(e_2⋅s) ≡ m^(re_1 + se_2) ≡ m (mod n)

cube attack, Håstad’s broadcast attack → 빠른 암호화를 위해 작게 설정한 공개 지수 e를 공격 (특히 e = 3) → 큰 수인 65537을 이용하면 이러한 공격을 대부분 막을 수 있음
- cube attack
  1. 거듭제곱 이후에도 n보다 작을 수 있는데, 이러한 경우 m^e를 n으로 나눈 나머지와 m^e의 결과가 동일하게 됨
  2. n과 무관하게 c = m^e임을 알 수 있음
  3. c의 e거듭제곱근인 c^(1/e)를 구해 해결
    - 평문 m이 n^(1/e)보다 작은 경우, n이 2048비트의 자연수일 경우 m이 최대 682(2048/3)비트일 경우 사용 가능
- Håstad’s broadcast attack → 평문 m이 n^(1/e)보다 클 경우 사용 → 같은 평문을 다른 n에 대해 암호화한 결과들을 모아 중국인의 나머지 정리 사용
  1. 서로소인 n_1, n_2, n_3에 대해 아래 수식이 성립하므로 중국인의 나머지 정리를 이용해 m^3 ≡ c (mod n_1n_2n_3)임을 확인할 수 있음
    - m^3 ≡ c_1 (mod n_1)
    - m^3 ≡ c_2 (mod n_2)
    - m^3 ≡ c_3 (mod n_3)
  2. 각 n의 값이 모두 m보다 크므로 m^3 < n_1n_2n_3
  3. m^3 = c

RSA-CRT
- 암호문을 p, q로 각각 modulus를 통해 복호화한 결과, p, q에 대해 중국인의 나머지 정리를 적용한 결과를 이용하여 평문을 복구
- 방법
  - m = c^d mod n에 대하여 m을 p, q로 각각 나눈 나머지로 m_p, m_q를 구한 후, 중국인의 나머지 정리 사용
    - m_p = c^d mod p = c^(d mod p − 1) mod p = c^d_p mod p
    - m_q = c^d mod q = c^(d mod q − 1) mod q = c^d_q mod q
    - m_p = c^d_p mod p, m_q = c^d_q mod q
    - m_q + q⋅*q_(inv)*⋅(m_p − m_q)
- 속도 차
  - 기존 복호화는 pow(c, d, n)을 연산 (c, d, n 모두 2048 비트)
  - RSA-CRT 복호화는 pow(c_p, d_p, p)를 연산 (c_p, d_p, p는 모두 1024비트에 근접)
  - pow(x, y, z)연산 시간은 log(y), log(z)^1.5 ~ log(z)^2에 비례하므로 이론 상 2.8 ~ 4배 줄어듦

from Crypto.Util.number import getPrime
import random
import time

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

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

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

            if phi % self.e == 0:
                continue

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

            self.dp = self.d % (self.p - 1)
            self.dq = self.d % (self.q - 1)
            self.qinv = pow(self.q, -1, self.p)

            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

    def decrypt_crt(self, ct):
        pt_p = pow(ct, self.dp, self.p)
        pt_q = pow(ct, self.dq, self.q)

        h = (self.qinv * (pt_p - pt_q)) % self.p
        pt = pt_q + h * self.q

        return pt

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

    normal_time = 0.0
    crt_time = 0.0

    for _ in range(10):
        plaintext = random.randrange(0, rsa.n)
        ciphertext = rsa.encrypt(plaintext)

        st = time.time()
        assert plaintext == rsa.decrypt(ciphertext)
        en = time.time()
        normal_time += en - st

        st = time.time()
        assert plaintext == rsa.decrypt_crt(ciphertext)
        en = time.time()
        crt_time += en - st

    print(f"CRT decryption is {normal_time / crt_time} times faster than nomral decryption.")

CRT decryption is 3.5976546488711207 times faster than nomral decryption.

Common modulus attack 실습

prob.py → 암호문 두 개 (같은 n을 사용 / 서로 다른 서로소(e)를 이용해 암호화) → common modulus 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 = }")

exploit.py
- r⋅e_1 + s⋅e_2 = 1을 만족하는 r, s 찾기 → pow 함수나 PyCryptodome의 inverse 함수를 통해 확장 유클리드 알고리즘을 사용하여 구할 수 있음
  - 위 식에서 양변에 mod *e_*2를 취하면 다음과 같은 식을 구할 수 있음 → r⋅e_1 ≡ 1 (mod e_2) → pow(e1, -1, e2) 또는 inverse(e1, e2)를 사용하여 r을 구함 (s는 s = (1 − r⋅e_1) / e_2를 이용)
- c_1^r⋅c_2^s mod n을 통해 m을 얻음

# exploit.py

from Crypto.Util.number import GCD, long_to_bytes

N = 18564839028340970630632687927085732690660216946716888067188954046812800985732372062460700863888002343155902759133649880101140768419725781550847529242612574780286876355781415545270149267924318930484262298628091098398893193544538272524290190578306149953368594658823348775434109820836311754081667945186523509419274141640792179302149121645060758381445210342226062749581257840649008843072969882069745488933714383742625035916351887508696280553528500528993974650390749489910938646668966427281419193682964555099697539229141704274820381967489671915008271272572784624353477273387243166242973237904102218303978989538340075110803
e1 = 26107
e2 = 416
FLAG_enc1 = 7527079488835824550176589432384780921138078216741164078317178088512020484637815911814449926944662371885728405467621509470317993615175662631245614263206465411761405248665475018014955011387536383732578999002193581953127201730485926821982569309896641811322758517611730555795173063573946211306084429097792646498732335587337634527626172754334153175582669944053431474970826408358022316126279869698898223075336790046723458233152991869045783807109865365096509043487724858636091575421769914060998644878330883643511254289263960487281213979614256506109469224245020612145584918823245558025971100167133602718304130194072814312710
FLAG_enc2 = 5553467916392779302319650321161682360291392077019602231908379041584499902773710723619110301005008094731504431902945888409491392723061165695579512443486392024940348967751410819758344508288749930005375895909393752897849038447778016747963886132791102187462287312608282729773341145901349954559564077909026595969034706754208713806020071917600988186991043342705750598606533751031166628502148837344385933277599437539183985932955644653119376571815604213229278422645273875273059325957488817516922134037588666169092554553063254879269416996367056713107865228810125004163068707218820011235988174311427569510212386257879728088984

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())

출력

// output.txt

N = 19056595815498938937827313400202784370682628273677184912106930216682597940790026113920523685958454732397180061608578640387495289806553136749250142493447897815574199279026363034632158551515947220239346700850298104009063341490764277841739252473024697498767093178268657420955688730709955275788673968551749260709498821096149881183335674118051463729635997604036412822135631306732784704554530238631555025300512731538889158646866755424007127252668776979528555327038953597006552404025499393029745762618251704562738377655672239325746581488880969849239208915768367237828456048777888128529465833041509210429322080724954471457153 e1 = 503 e2 = 24481 FLAG_enc1 = 15896332265563107536793725214641004012044541498086069027232457164210978705696376794418360548872381808005979059594776781553653502155796558117578844062415477118690865158937855324681584444366125141102224100497084116450867706328701378629720727449381986197338927319932165899713788723965165510407564001376878368675915066246617448050027816417255770117007664058853768967150883457632806452298667439886745091165169619245176807951475217420331832731265868311307243431297695614210233974271599886745673023800241608064858693276447516768233561572578888328471389745636837580905902298829385536368165011019027171030082808286431520522434 FLAG_enc2 = 6130128594160805343608855270424561730864865369181458323913473396899157421567780132846367830064249025339182818204241920192656051715499345401674348466747285155444249347832139613547811757101868681756691144856628716297302732235799355821039535562725970512162241508932949918530692560927152674551181294351899265911497464112927409526075647151874911303930869337696512426729194319509543105477301517354030525836177279870012841834074535124900843754479127845242159807263250416034132847689110597355576391365469378447495649562929633735165835020154538067462998115597940302989355032828190044598225091985640932052655681842361499359710

저작자표시

'24-여름 SISS > 암호학' 카테고리의 다른 글

[SISS/암호학 스터디] 여름 9주차 스터디 - 전자 서명 (0)	2024.08.24
[SISS/암호학 스터디] 여름 8주차 스터디 - 해시 (0)	2024.08.19
[SISS/암호학 스터디] 여름 7주차 스터디 - 디피헬만 키 교환 (0)	2024.08.16

ABOUT ME

블로그 블로그

공개키 암호 - RSA

RSA, RSA-CRT

RSA 공격 방법

Common modulus attack 실습

'24-여름 SISS > 암호학' 카테고리의 다른 글

티스토리툴바

ABOUT ME

공개키 암호 - RSA

RSA, RSA-CRT

RSA 공격 방법

Common modulus attack 실습

'24-여름 SISS > 암호학' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바