암호학 정리(for CTF)

CTF 를 위한 기초 암호학 개념들을 간단히 정리했다. (아주 간단히...)

1.기본 개념

RSA 용어 

- 인증서 종류 : .pem(base64 로 저장), .der(바이너리로 저장)

o() = euler's totient function, 오일러 파이 함수

o(6) = 3

=> 1,2,3,4,5,6 중 나눠지는 2,3 은 제외하고 서로소인 1,4,5 인 3개

p = 315274063651866931016337573625089033553

q = 311155972145869391293781528370734636009

e = 12405943493775545863

n = p * q

공개키 :  n, e 

개인키 : d

암호문 : c (실제론 큰 정수)

복호화 : m (실제론 큰 정수)

- 암호화 과정

1) 소수 p 와 q 를 정한다.    

        p = 123123123

        q = 590129113

2) n = p*q 를 구한다.

        n = p * q

3) o(n) = (p-1)*(q-1) 을 구한다.

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

4) 1 < e < o(n) 이고 o(n) 과 서로소인 e 를 구한다.

5) (d * e) mod o(n)=1 이고 o <= d <= N 인 d 를 구한다.

   d = gmpy.invert(e, phi)

- 암호연산 : c = m^e mod n  ( m ** e % n )

- 복호연산 : m = c^d mod n  ( c ** d % n )

key = RSA.construct(n,e,d)

2. 점검툴

- yafu (인수분해 등) 

> factor(0x192873aba29290cbade10) => p, q 로 분해

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

- rsatool

- rsactftool

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

- sympy  :  수학기호 사용 모듈 ( x = symbol(x); x+y 등)

http://docs.sympy.org/latest/tutorial/solvers.html#a-note-about-equations 

3. 문제유형

1. RSA 

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

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

- lsb oracle attack

2. DES/AES

- padding oracle attack

## ETC ##

RSA 곱셈의 성질

- 암호문 cipher2, cipher5 가 있다.

- (c2 * c5) %n) 을 복호화 한 것은 m2 * m5 와 같다.

=> ((c2 * c5) % n)^d mod n == m2 * m5 

 

(2 암호문 * flag %n) ^d mod n == 2 * flag 평문