컴퓨터 보안 - [Public Key]

RSA

RSA는 공개 키 암호화 방식중 하나로, 데이터의 안전한 전송을 위해 널리 사용됩니다. RSA는 공개 키와 개인 키를 사용하여 데이터를 암호화 하고 복호화 합니다.

RSA 키 생성

• Public Key : e,n // Private Key : d
• 두개의 큰 소수 p와 q를 선택합니다. 이 소수들은 비밀로 유지됩니다.
• n = p*q, (n은 공개합니다.)
• e는 $\phi$(n) = (p-1)(q-1)과 서로인 값을 랜덤으로 정한다.
• d는 d*e = 1 mod $\phi$(n)인 d를 계산합니다. 이는 e의 모듈러 역수입니다. (확장된 유클리드 알고리즘)

encryption, decryption

• Message M을 정수로 바꿈
• 암호화 : E(M) = M^e mod n = C
• 복호화 : D(C) = C^d mod n = M -> 페르마,오일러 정리

El Gamal

공개키 방식 중 하나로 이산대수의 어려움을 이용했다.
A = B^C, C를 찾는 것

• RSA보다 더 안정적이다.

El Gamal 키 생성

• 큰 소수 p, p보다 작은 임의의 g,x 선택
• Y = g^x mod P를 계산
• 공개 키: Y, P, g
• 비밀 키: x

encryption, decryption

• Message(평문) M을 정수로 바꿈
• 암호화: p-1과 서로소인 임의의 k (1<k<p-1)
  a = g^k mod p, b = Y^k *M mod p
• k를 임의로 선택하기 때문에 동일한 M에 대해서 매번 다르게 암호화
• 암호문은 원래 M 길이의 2배가 된다(a,b)
• 복호화 : b/a^x mod p = (Y^k * M / a^x) mod p = M

ECC

암호화보다 전자서명, 키교환에서 주로 사용된다.
이산대수 문제를 기반으로 한다.
A = B^C, C찾기 문제

• RSA보다 작은 키를 사용하지만 수학적 계산량이 많다

원리

• 타원 곡선의 덧셈: y^2 = x^3 + ax + b (mod p)
• 점의 덧셈 : 타원 곡선 위에 두 점을 더하여 새로운 점을 생성합니다. -> 원래의 점을 알 수 없습니다.
• 스칼라 곱 : 특정 점을 정수와 곱하는 연산으로 이는 점을 반복적으로 더하는 방식으로 정의됩니다. 예를들어 kp는 점 p를 k번 더한 결과