Theory/Cryptology27 메세지 인증 코드 (MAC) 1. 메세지 인증 코드(Message Authentication Code) 1) 메시지에 붙여지는 작은 블록을 생성하기 위해 비밀키를 이용한다. 2) 메시지 변경과 거짓행세[위조]를 확인한다. 3) 복호화가 불가하고 해시와 거의 비슷하다. 4) 사용 목적은 무결성 검증과 인증에 목적이 있다.(부인방지 및 기밀성유지는 불가) 5) 기밀성유지[메세지를 전송해서]도 안되고, 부인방지[비밀키 사용해서]도 안 된다. 2. 메세지 인증 코드를 이용한 인증순서 1) 송신자와 수신자는 사전에 키를 공유한다 2) 송신자는 메시지를 기초로 해서 MAC값을 계산한다. (사전 공유 키 이용) 3) 송신자는 수신자에게 메시지와 MAC값을 보낸다 4) 수신자는 메시지를 기초로 해서 MAC값을 계산한다. (사전 공유 키 이용) 5.. 2018. 8. 12. 해시함수 1. 해시함수 - Message Digest Algorithm - Hash - 전자지문 - 암호학적 체크섬 - 손도장 2. 해시함수의 특성 1) 해시함수는 계산효율이 양호하다. 2) 일방향성(약) - 해시함수로 얻은 해시값(H)으로 부터 서명문 (M)을 찾기는 계산상 불가능하다 [h(M) = H] 3) 일방향성(강) - 서명문 M과 해시값 H가 주어졌을 때 해시값이 같아지는 서로 다른 서명문을 찾는 것이 계산상 불가능하다. 4) 충돌회피성 = 강한충돌방지 - 해시값이 같아지는 서로 다른 서명문을 찾는 것이 계산상 불가능하다. 예제) - 약한충돌방지는 생일이 1월 1일인(서명문고정) 사람 찾기 - 강한충돌방지는 생일이 같은(해시값이 같은) 사람 찾기 - 즉, 약한충돌방지의 경우가 정해져 있기 때문에 찾기가.. 2018. 8. 12. RSA 전자서명 1. RSA 전자서명(메세지에 서명) [ e=공개키 -> 서명 검증키 / d=개인키 -> 서명 작성키 ] 1) 두 소수 p와 q를 찾는다 [p와 q는 비밀] 2) 두 소수 n = p x q 로 만든다 [n은 공개] 3) Ø(n) = (p - 1) x (q - 1) [Ø(n)는 비밀] 4) gcd (e, Ø(n)) = 1 인 e를 선택 5) e와 d 키 쌍을 제작 -> e x d = 1 mod Ø(n) 6) 서명 S = M의 d승 mod n, M과 S를 전송 7) 검증 M' = S의 e승 mod n, M과 M'을 비교 2. RSA 전자서명(해시값에 서명) 1) 두 소수 p와 q를 찾는다 [p와 q는 비밀] 2) 두 소수 n = p x q 로 만든다 [n은 공개] 3) Ø(n) = (p - 1) x (q -.. 2018. 8. 12. 전자서명 1. 전자서명 (= 디지털서명) - 사용자인증 [거짓행세] - 무결성 [변조] - 부인방지 [비밀키로 불가, 구지 하려면 중재자가 필요] 2. 전자서명의 조건 - 위조 불가 : 합법적인 서명자만이 전자서명 생성 - 서명자확인 : 전자서명의 서명자를 불특정다수가 검증가능 - 부인방지 : 서명자는 서명행위 이후에 서명한 사실에 대해 부인 불가 - 변경불가 : 서명한 문서의 내용을 변경 불가 - 재사용불가: 전자문서의 서명을 다른 전자문서의 서명으로 사용 불가 3. 전자서명의 흐름 - 서명자가 서명자의 개인키로 서명을 작성한다. - 검증자가 서명자의 공개키로 서명을 인증한다. 4. 중재서명방식 - 중재자가 전자서명에 과정에 개입하여 서명자의 서명을 검증자에게 확인시켜주며 서명자와 검증자의 부정행위 방지 => .. 2018. 8. 12. 공개키 암호의 문제점과 하이브리드 암호 1. 공개키 암호의 문제점 - 비밀키 암호에 비해 속도가 느리다. - 중간자공격에 약하다. 2. 중간자공격 - 송신자와 수신자 사이에서 송신자에게는 수신자처럼, 수신자에게는 송신자처럼 행세하는 공격을 말한다. 3. 하이브리드 암호 1) 평문을 비밀키 방식으로 암호화한다. 2) 비밀키는 의사(가짜)난수생성기로 생성한다. 3) 비밀키는 공개키 방식으로 암호화한다. 2018. 8. 12. 공개키 - Rabin암호, Knapsack암호, 초증가수열, 타원곡선암호(ECC) 1. Rabin 암호 1) 소인수 분해의 어려움을 이용한다. 2) 암호화 과정이 RSA 암호 시스템보다 빠르다. 3) 소인수 분해가 어렵다면 선택 평문 공격에 대하여 계산적으로 안전하다.[ 몇 천년 ] 2. Knapsack 암호 - 전체의 무게를 알 때 어떠한 무게의 물건이 몇 개 들었는지는 알기 어려운 것을 이용한 암호이다. 3. 초증가 수열 - 수열의 각 항이 이전 항들 모두의 합계보다 더 큰 수열 이다. - ex) 1, 3, 5, 10, 20, 40 ... 4. 타원곡선암호 (ECC) - 키의 길이가 짧고 안전성이 높으며, 서명할 때의 계산을 고속으로 처리한다. - 스마트카드나 휴대폰 등 키의 길이가 제한적인 무선환경에 적합하다. - 하드웨어 소프트웨어 구현이 용이하다. 2018. 8. 12. 공개키 - Elgamal 암호 1. Elgamal 암호 - 같은 평문이라도 암호화가 이루어질 때마다 암호문이 달라짐 - 다른 공개키 암호 알고리즘에 비해 길이가 2배로 늘어남 - 이산대수(로그) 문제에 바탕을 둔 공개키 알고리즘 - RSA 암호에 비해 안전하지만 속도가 느림 y = g의 x승 mod p --> g는 원시원소, p는 소수 g와 x를 아는 사람이 y를 계산하는 것은 간단하나, g와 y를 아는 사람이 x를 계산하는 것은 어렵다. Bob은 1) 큰 소수 p, 원시원소 g -->공개 2) x 선정, y = g의 x승 mod p [ x는 비밀, y는 공개] Alice는 3) 난수 r을 선정 -> K = y의 r승 mod p 4) C1 = g의 r승 mod p, C2는 KM mod p Bob은 5) C = ( C1, C2 ) 6).. 2018. 8. 12. 공개키 - 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 2018. 8. 12. 공개키암호의 기초지식 1. 공개키 암호의 기초지식 1) 공개키 암호로 암호화 할 때 수신자의 공개키가 필요하다. 2) 공개키 암호로 암호화된 암호문을 복호화하기 위해서는 공개키 암호와 쌍을 이루고 있는 개인키가 필요하다. 3) 공개키 암호의 개인키는 암호화한 메시지와 함께 수신자에게 송신할 필요가 있다. 4) 일반적으로 공개키 암호보다 비밀키 암호가 빠르다. 5) 소인수분해를 고속으로 푸는 방법이 발견되면 RSA도 고속으로 풀 수 있다. 6) 부인방지는 비밀키알고리즘만으로 구현될 수 없다. 7) RSA 알고리즘에서 e와 d를 곱한 값을 Ø(n)로 나누면 나머지가 1이다. 8) 공개키 암호화 기법은 키분배가 비밀키보다 쉽다. 9) Diffie-Hellman은 암호화나 전자서명에 이용되지 않고 키 분배에 이용된다. 10) RSA.. 2018. 8. 12. 공개키 - 오일러함수, 소인수분해, 거듭제곱 1. 오일러 함수[ Ø(n) ] - 어떤 자연수 n에 n이하의 자연수 중 n과 서로소인 수를 대응시키는 함수. - 소수의 경우 Ø(n)는 n-1개 이다. ex) Ø(7) = 6개 (7과 서로소인 1, 2, 3, 4, 5, 6) 2. 소인수분해의 특징 p x q => n p와 q를 알고 n을 구하는 것[암호화]은 쉬우나, n => p x q n을 알고 p와 q를 구하는 것[복호화]는 어렵다. 3. 거듭제곱 5¹ mod 23 = 5 5² mod 23 = 2 5³ mod 23 = (5¹ mod 23) x (5² mod 23) = 10 5⁴ mod 23 = (5² mod 23) x (5² mod 23) = 4 2018. 8. 12. 공개키 - 모듈러 연산, 모듈러 인버스 1. 모듈러 연산 - A(피제수) ÷ B(제수) = Q(몫) ... R(나머지) - 나머지가 될 수 있는 수의 개수 = 제수 ex) [ 9 mod 12 = 9 ] 와 [ 7 mod 12 + 2 mod 12 = 9 ] 는 같다. ex) [ -5 mod 3 = 1 ] 피제수가 음수인 경우는 제수를 양수가 될 때까지 더해준다. 2. 모듈러 인버스 (= 모듈러 역원) - ▣ x ◉ mod ★ = 1 , ▣ x ▣ mod ★(=12) = 1 , - 같은 수를 곱한 것을 12로 나누었을 때 1이 나오는 것은 1, 5, 7 ,11 이 있다. 2018. 8. 12. 공개키 암호를 사용한 흐름 1. 공개키 암호를 사용한 흐름 - 공개키와 개인키는 같은 사람이 만든 한 쌍의 키를 사용한다. [1] 밥은 공개키/개인키 로 이루어진 한 쌍의 키를 만든다. [2] 밥은 자신의 공개키를 앨리스에게 보낸다. [3] 앨리스는 밥의 공개키를 사용하여 메시지를 암호화 한다. [4] 앨리스는 암호문을 밥에게 보낸다. [5] 밥은 자신의 개인키를 사용하여 암호문을 복호화 한다. - 암호화 시 수신자(=상대방)의 공개키 사용, 복호화 시 수신자(=자신)의 개인키 사용 2018. 8. 12. 이전 1 2 3 다음
