공개키 - RSA암호방식, RSA에 대한 공격

1. RSA 암호방식

 1) 매우 큰 두 소수 p와 q [ p와 q는 비밀 ]

 2) n = p x q [ n은 공개 ]

 3) Ø(n) = (p - 1) x (q - 1) [ Ø(n)은 비밀, 이유는 Ø(n)를 알면 키를 만들 수 있으므로]

 4) gcd(e, Ø(n)) = 1 --> e를 선정 [ e는 공개 ]

  = 최대공약수가 1이면 서로소이다.

 5) e x d = 1 mod Ø(n) --> d를 계산 [ d는 비밀 ]

 6) C = M의 e승 mod n [ Ø(n)은 나만 계산 가능하고, n은 누구나 계산 가능 ]

 7) M = C의 d승 mod n

 

예제)

 

2. RSA에 대한 공격

 1) 암호문으로부터 평문구하기

 2) C = M의 e승 mod n <-- M을 구하려면 이산대수[로그]를 구해야 함

 3) Brute force 공격

  = d는 1024 비트 이상 사용 <-- 1024비트 이상의 Brute force 공격을 해야 함

 4) e와 n으로부터 d를 구하기

  = d를 알기 위해서는 q와 p를 알아야 함

 5) 중간자(man in the middle) 공격

  = 막기 위해서는 인증서가 필요 함