암호학 정리(for CTF)

2018. 4. 5. 11:36



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


+ Recent posts