GCD, Euclid Algorithm gcd(a, b) = gcd(b, a%b) 를 기반으로 함. Modular Arthmetic a mod b = (a+kb) mod b, k는 임의의 정수 x*y mod b = (x mod b * y mod b) mod b Extended Euclid Algorithm 유클리드 알고리즘으로 나온 최대공약수로부터 역추적하며 gcd(a, b) = ax + by가 되는 x와 y를 찾음. int extended_gcd(int a, int b, int *x, int *y) { if (b == 0) { *x = 1; *y = 0; return a; } int x1 = *x; int y1 = *y; int gcd = extended_gcd(b, a % b, &x1, &y1); *..
암호학
symmetric key, 대칭키는 키를 하나만 사용하는 암호화에서 사용한다. 암호문을 보내는 사람과 푸는 사람 모두 같은 키를 가지고 있어야 하며, 전자서명이 안되기 때문에 메시지를 위조하거나 내가 안보냈는데 보냈다고 하는 등 문제가 발생할 수 있다. (유용하지 않다는 뜻이 아니다.) Public-Key Cryptography Asymmetric key => public key + private key 공개키 시스템은 공개키와 개인키가 있고, 공개키는 모두에게 보여져도 상관없고 개인키는 숨긴다. 공개키로 암호화했다면 개인키로 풀 수 있고, 개인키로 암호화했다면 공개키로 풀 수 있다. 장점으로는 다음과 같다. 1. 키 분배 문제를 해결할 수 있다. 상대방에게 공개키만 보내주면 되고, 대칭키 시스템의 키 ..
랜덤 넘버는 암호학에서 자주 쓰인다. - nonces는 한 번만 사용되는 일회용 값으로, 재생공격을 방지하는데 사용된다. - 세션 키는 각 세션마다 랜덤으로 생성된다. - 공개 키 생성에서 키 쌍을 생성할 때 랜덤으로 생성된다. 랜덤 넘버는 통계학적으로 무작위여야하고, 각 난수는 서로 독립적이고 예측 불가능해야한다. TRNG 실제 무작위 소스를 랜덤생성기의 입력으로 사용한다. 무작위 소스는 엔트로피 소스라고 부른다. 컴퓨터의 물리적 환경에서 얻을 수 있다. 예를 들어, 키보드 - 마우스 타이핑 패턴 및 속도, 디스크의 전기적 활동, 시스템 클럭의 순간 값과 환경 소음이나 온도 변동 등 물리적인, 아날로그 소스 값을 이진 출력으로 변환하여 사용한다. PRNG Pseudorandom Number Genera..
DES는 56비트의 키를 가지는 암호화 방법이다. 짧은 키로 인해 브루트포스 어택이 쉽다. Double-DES는 DES를 2번 적용하는 방법이다. 2^112일 것 같지만, 모든 가능한 키에 대하여 평문을 암호화하고, 각 결과를 저장한 다음 같은 암호문을 모든 가능한 키에 대해 복호화하고 암호화 결과와 복호화 결과가 일치하는 것을 찾는 meet in the middle attack을 사용하면 2^57밖에 되지 않는다. Triple-DES는 DES를 3번 적용하는 방법이다. 각 단계별로 다른 키에 대해 암호화-복호화-암호화 를 실행한다. 복호화-암호화-복호화도 가능하다. C = Ek1(Dk2(Ek3(P))) k1,k2,k3중에 같은게 있다면 single DES와 같아진다. 비교적 안전하지만 암호화와 복호화가..
GCD (Greatest Common Divisor) 최대 공약수란 두 개 이상의 정수 간의 가장 큰 공통된 약수를 뜻한다. relatively prime(서로소)란 최대 공약수가 1인 정수쌍이다. 만약 GCD(a,0)이라면 최대 공약수는 a이다. GCD(0,0)은 정의되지 않는다. gcd(a,b) = gcd(b, a%b) 라는 원리를 이용한 유클리드 알고리즘을 통해 GCD를 구할 수 있다. Euclid(a,b){ while (a != 0 && b != 0) { int n = a % b; a = b; b = n; } return a ? a : b; } 최대 공약수를 구하려는 a,b에 대해, a%b를 구한 값을 b로, a값을 b로 대입하는 과정을 두 정수 중 하나가 0이 될 때까지 반복한다. 만약 둘 중 ..
카이사르 암호 (Caesar Cipher) 모든 문자에 대해, 아스키코드 상에서 특정 수만큼 더해서 암호화 알파벳이 26개기 때문에, 26번만에 해독될 수 있다. (브루트포스) 모노알파벳 암호 (Monoalphabetic Cipher) 각각의 알파벳이 랜덤한 알파벳으로 변환되어 암호화 브루트포스 방식으로 해독하려면 26! 번으로 해독된다. 하지만 영어에서, 가장 많이 나오는 문자가 e이고, 다음이 t, 다음이 a ... 인 점, 그리고 2, 3개의 알파벳이 연속하여 나오는 빈도 테이블을 이용하여 암호화 문자열의 알파벳 빈도를 구하면 해독될 수 있다. 폴리알파벳 암호 (Polyalphabetic Cipher) 암호화하는 동안 여러 알파벳 대치 방식을 사용한다. 문자 빈도를 변조하기 때문에 해독하기 어렵다...
먼저 암호학에서 쓰이는 기본 용어부터 살펴보자. plaintext 평문 cipertext 암호문 cipher 알고리즘 key 비밀번호 encipher (encrypt) 암호화 decipher (decrypt) 복호화 cryptography 암호학 cryptanalysis key를 모르는 상태에서 key를 알아내는 것 cryptology cryptography + cryptanalysis 암호학이란, 암호화/복호화를 시키는 것 뿐만 아닌 key를 알아내는 것까지 포함한 cryptology를 알아가는 학문이 되겠다. 암호화와 복호화는 위와 같이 진행된다. 평문 X와 암호문 Y, 키값 K가 있을 때, 암호화 알고리즘 E에 K, X를 대입시키면 암호문 Y가 반환된다. 반대로 복호화 알고리즘 D에 Y와 K를 대입..
