열공하는베짱이

Theory57

공개키 - 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. 공개키 암호를 사용하게 된 이유 - 공개키 암호를 사용하게 된 이유는 비밀키 암호의 문제점과 같다. 1) 비밀키 사용 시 해독하려면 키가 필요한데 키를 전달하기가 힘들다. 2) 키를 보내지 않으면 안 되는데 키를 보낼 수 없다. - 모순 + n명이 통신할 때? 비밀 키 개수 = n(n - 1) / 2 , 공개 키 개수 = 2n 3) 이 문제를 해결하려면 - 열쇠의 사전공유 - 열쇠 배포센터(KDC) 이용 - Diffie-Hellman의 열쇠교환 - 공개키 암호사용 2018. 8. 12.
공개키 암호 1. 공개키암호 1) 송신자에게 필요한 것은 암호화 키(=공개키)이다. 2) 수신자에게 필요한 것은 복호화 키(=개인키)이다. 3) 도청자에게 알려지면 곤란한 것은 복호화 키(=개인키)이다. 4) 암호화 키(=공개키)는 도청자에게 알려져도 괜찮다. 2. 공개 키 암호의 종류 1) 소인수분해 - RSA, Rabin 2) 이산대수 - Elgamal 3) Knapsack 문제 - Knapsack 암호 4) 타원곡선 상의 이산대수 - 타원곡선암호 (ECC) 2018. 8. 12.
공개키 - 수학적 기본용어 1. 수학적 기본용어정리 1) 항등원 [덧셈 = 0, 곱셈 = 1] - 연산의 결과가 자기 자신이 되는 수 2) 역원(inverse) [덧셈 = a의 역원은 -a, 곱셈 = a의 역원은 1/a (단 a≠0, 즉 0은 곱셈역원이 없다.) ] - 연산의 결과가 항등원이 되는 수 3) 약수 - 어떤 수를 나누어 떨어지게 하는 수 4) 소수(prime number) ↔ 합성수 - 약수가 1과 자기 자신 밖에 없는 수 - 소수는 무한집합이며, 알고리즘이 없다. - 소수를 구하기 위해서는 일일이 나누어보아야 한다. - 갈수록 간격이 벌어져 구하기 힘들어진다. - 그래서 공개키 암호에 사용된다. 5) 공약수 - 공통된 약수 6) 서로소 - 1 이외에 공약수를 갖지 않는 둘 이상의 약수 7) 소인수분해 [24 = ( .. 2018. 8. 12.
블록암호의 운용모드 1. ECB(Electric Code Book) 모드(전자 부호 책) [1] 동일한 평문 블록은 동일한 암호문 블록으로 출력되어 해독가능성이 높다. [2] 초기 벡터가 필요없다. [3] 짧은 평문이나 키를 암호화 시 사용한다. [4] 암호문 간의 연관관계가 없어서 개별적으로 암호화되고 개별적으로 복호화된다. [5] 그러나 해독이 빠르고, 손 안대고 공격[블록을 통째로 변경]가능, 짧은 키나 평문 암호화시 좋다. [6] 5가지 운영방식 중 가장 간단하지만, 평문과 암호문이 1:1로 대응관계이며 기밀성이 낮다. ex) A가 B에게 1억원 입금 // 이것을 B가 A에게 1억원 입금 /// 암호를 몰라도 블록을 변경 2. CBC(Cipher Block Chaining mode) 모드(암호 블록 연결) [1] 초.. 2018. 8. 12.
DES암호의 특징 1. DES(Data Encryption Standard)의 특성 - [1] 컴퓨터의 성능이 좋아지면서 전수공격에 패했다. 대비하려면 키의 크기를 크게 해야한다. [2] 페이스텔 네트워크[Feistel Network]는 원하는 만큼 라운드 수를 늘릴 수 있다. [3] 각각의 출력비트는 모든 입력비트에 의존한다. ->암호의 안전성 [4] 쇄도효과, 눈사태효과, 산사태 효과라고 부른다. -> 1bit(평문 or 키) 변경 시 암호문 전체가 바뀐다. [5] 블록의 크기와 키의 크기가 항상 같지 않다. [6] DES는 전치가 매우 많다. (치환은 S-BOX에서만) [7] XOR연산이 많다. [8] 키의 길이가 길다고 무조건 좋은 것은 아니다. - 시간이 오래 걸림 2. 취약키 - 키가 모두 0 또는 1이면 키 .. 2018. 8. 12.
DES 암호 1. DES[Data Encryption Standard] 암호 - 평문 64비트를 암호문 64비트로 변환시키는 암호방식으로 64비트의 키를 사용한다. - 키는 8비트마다 패리티비트 하나씩을 포함하고 있어 암호화 과정에는 56비트만 적용된다. 2. DES암호의 암호화과정 [1] 64bit의 평문블록[A]을 초기전치(Initial Permutation)[IP(A)] 된다. [2] 초기전치[Initial Permutation]한 것 [IP(A)]을 L0와 R0로 32bit씩 나누어진다. [3] K1(48bit)의 서브키와 R0가 F함수에 입력되면 32bit가 출력된다. [4] F[R0(32bit), K1(48bit)]에서 출력된 값과 L0를 XOR 연산을 한 후 R1에 들어간다. [5] L1에는 R0의 값을.. 2018. 8. 12.

티스토리툴바