본문 바로가기

CS118

이산수학 - 증명, 직접증명법, 수학적 귀납법, 간접증명법, 다양한 증명방법 기본사항  일반적으로 타당성을 입증하는 데는 증명이 사용된다. 증명은 주로 "P이면 Q이다"라는 형식을 따르게 되는데, 전제가 참일 때 결론이 참임을 논리적으로 보일 수 있다면 많은 사람이 Q가 타당하다고 받아들이게 될 것이다.  그렇다면 P가 참임은 어떻게 증명해야 할까? 수학적으로 참으로 알려진 많은 사실이 P가 될 수 있겠지만, 이들 역시 다른 전제의 동무을 받아 증명되어야 이용할 수 있을 것이다. 이렇게 계속 거슬러 올라가게 되면 더 이상 증명할 수 없는 사실을 만나게 되는데 이들을 공리라 한다.  공리 어떤 다른 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정으로, 별도의 증명없이 참으로 이용되는 명제를 공리라고 한다.   예시 1) 두 점이 주어졌을 때, 두 점을 통과하는 직선을 그.. 2024. 5. 13.
대칭키 공개키 관리, 디피-헬먼 키 교환 프로토콜, 공개키 기반 구조 PKI 0. 문제대칭키 암호에서 비밀키는 송수신자가 서로 나누어 가지기 어렵다는 문제가 있다. 그래서 공개키 암호를 이용해 비밀키를 암호화해서 분배할 수도 있지만, 공개키 암호 역시 공개키를 분배할 때 실제로는 다양한 위협요소가 존재한다.1. 대칭키 암호의 키 관리앨리스(Alice)와 밥(Bob)이 있다고 가정하자. 대칭키를 사용하는 암호 시스템에서 앨리스가 밥에게 메시지를 보내고 싶다면, 앨리스는 밥과 비밀키를 공유해야 한다. 두 사람이 직접 만난다면 제3자 모르게 비밀키를 정할 수 있을 것이다. 하지만 그렇지 않다면? 비밀키를 어떻게 공유할 것인가가 문제가 된다. 우리는 공개키 암호로 비밀키를 암호화하면 안전한 키 공윺가 가능하다는 것을 이미 알고 있다. 하지만 공개키 암호를 안전하게 사용하는 것도 간단하지.. 2024. 5. 6.
공개키 암호: 개념, 소인수분해 문제, 이산대수 문제, 타원곡선 문제, RSA, ElGamal 알고리즘 1. 공개기 암호의 개념공개키 암호는 암호화와 복호화에 두 개의 서로 다른 공개키와 개인키를 사용하는 암호 방식이다.C = Ek(P)P = Dk(C) 이때 E는 암호화 함수, D는 복호화 함수를 의미한다. 공개키와 개인키는 언제나 한쌍으로 존재한다. 공개키는 누구나 이용할 수 있도록 공개하고 개인키는 자신만 이용하도록 공개하지 않는다. 만약 A가 B에게 보낼 메시지를 암호화하려면 B의 공개키를 이용하는 것이고, 이 암호문을 받은 B는 자신의 개인키를 이용하여 복호화한다. 공개키 암호는 비대칭키라고도 한다.2. 기반 문제어떻게 키를 공개했는데도 암호화 메커니즘이 동작하는지 의문이 들 수 있다. 핵심은 공개키 암호 알고리즘이 수학적으로 어려운 문제들에 기반을 두고 있다는 것이다. 어려운 문제라는 것은 무.. 2024. 5. 6.
대칭키 암호: 개념, 블록 암호, 파이스텔, SPN, 스트림 암호, DES, AES 1. 대칭키 암호의 개념암호화와 복호화에 하나의 같은 비밀키를 사용하는 암호 방식C = Ek(P)P = Dk(P)이때 E는 암호화 함수, D는 복호화 함수를 의미한다.다양한 이름으로 불린다: 대칭키 암호, 비밀키 암호, 단일키 암호, 관용 암호대칭키 암호는 블록암호화 스트림 암호로 나눌 수 있다.먼저 블록 암호부터 살펴보자.2. 블록 암호개념평분을 고정된 크기의 블록으로 나누어 각 블록마다 암호화 과정을 수행하여 블록 단위로 암호문을 얻는 대칭키 암호 방식예를 들어 다음과 같이 하나의 평문을 4개의 블록으로 나눈뒤, 각 블록을 대칭키 암호 방식으로 각각 암호화한다.여기서는 하나의 키를 이용하여 모든 블록을 암호화한다. 암호화된 각 블록을 다시 연결하면 원래 평문에 대한 암호문이 완성된다.블록 암호 알고리.. 2024. 5. 6.
이산수학 논리 - 명제, 논리 연산, 술어 논리, 추론 명제명제참과 거짓을 구별할 수 있는 문장이나 수학적 식을 명제라고 한다.명제의 진리값참 (True), T: 명제가 타당한 경우거짓 (False), F: 명제가 타당하지 않은 경우명제의 종류합성명제조건명제, 쌍조건명제항진명제, 모순명제명제의 예다음 문장이 명제인지 아닌지 구분해보자(1) 6은 2의 배수다. -> 명제이다(2) 철수는 공부를 잘한다 -> 명제가 아니다.(3) 2+3=7 -> 명제이다(진리값이 거짓임).(4) x +2 = 0 -> x의 값에 따라서 참일 수도 있고, 거짓일 수도 있다. 따라서 명제가 아니다.  다음 명제의 진리값을 구하라(1) 2,3,6는 소수이다. -> F(2) 소수의 개수는 무한하다. -> T(3) 126 = 2^6 -> F(4) 지구에서 가장 높은 산은 에베레스트이다. -.. 2024. 5. 2.

티스토리툴바