컴퓨터보안#9
LeeMir, 28 April 2021
공개키 암호화
공개키 암호화
- 암호학 전체의 역사에서 최대 혁명적 발견
- 평문에 수신자의 공개키로 암호화 후 암호문을 수신자의 개인키로 복호화해서 볼 수 있음
Knapsack Problem
- 암호화 절차
- Superincrease knapsack인 S 설정
- S의 모든 원소의 합보다 큰 n 설정
- n보다 작은 수 중, n과 서로소인 수 w 설정
- S의 모든 원소를 w와 곱한 후 mod n 연산을 해 H를 구함
- plaintext에서 1인 부분에 해당하는 H 원소의 합이 ciphertext
- 복호화 절차
- 수신자는 w와 n, H를 알고 있음(H,n이 공개키 w^(-1), S가 개인키)
- w와 n과 H를 이용해 S를 구함
- w의 곱셈에 대한 역원을 구함
- w^(-1)과 ciphertext를 곱해 T를 구함
- T를 가지고 S에 대해 Super Increase Knapsack 형태로
- 쓰이고 있지는 않음
RSA
- 페르마의 정리
- p는 소수이고, a는 p로 나눠지지 않는 양의 정수일 때
a^(p-1) = 1 mod pa^(p-1) mod p = 1
- 오일러의 정리
- Totient Function
- n보다 작은 값 중에서 n과 서로소인 양의 정수가 몇 개인지 세는 함수 Φ(n)
Φ(1) = 1- 1도 세는 것으로 함
Φ(p) = p - 1- 1을 세고, p는 소수이기 때문
Φ(pq) = Φ(p) Φ(q) = (p-1) (q-1)- 소수가 아닐 때에는 소수의 곱으로 나타내고, 그 소수에 대한 Φ(n)을 곱해 계산
- p와 q가 다른 수일때에만 성립, p=q인 제곱수에서는 성립하지 않음
- 페르마의 정리에서 굳이 p가 소수가 아니어도 성립할 수 있음을 보여줌
a^(Φ(n)) = 1 mod n
- Totient Function
- 공개키
- n = pq
- e
- GCD(e, Φ(n)) = 1을 만족하는 e
- 암호키(개인키)
- d
- ed = 1 mod Φ(n)을 만족하는 d
- d
- 암호화(m : 메시지)
c = m^(e) mod n
- 복호화
m = c^(d) mod nc^(d) = m^(ed) = m^(kΦ(n)+1) = m mod n