새벽의 블로그

RSA란?RSA는 1977 MIT에서 Rivest / Shamir / Adleman이 만들어낸 암호화 구조입니다.1. 가장 많이 알려지고, 쓰이는 공개키 암호화 방식2. 모듈로 연산을 포함한 정수론을 기반으로 한 지수 연산을 사용 (GF에서의 지수연산)3. 2048 비트와 같은 매우 큰 정수 사용으로 느린 속도 (AES보다 느림)4. 매우 큰 정수의 곱을 사용하기 때문에 소인수분해의 어려움을 가지고, 이를 기반으로 보안을 유지 RSA 암호화 / 복호화암호화암호화하여 보낼 송신자는, 암호문을 받을 수신자의 공개키 PU = {e,n} 이용 암호문 C 복호화암호문을 받은 수신자는, 본인의 개인키 PR = {d,n} 이용 복호화 결과 메세지 M* 이때 mod n을 적용하기 때문에 구분 가능하도록,메세지 M을 0..

Fetmat's Theorem  페르마의 이론Fetmat's Little Theorem으로도 알려져있다.소수 p에 대하여, p와 서로소인 a에 대하여 다음 식이 성립한다.  단, 다음 두 조건을 잘 확인해야 한다. 1. p는 소수이다.2. 1을 만족하고 a 이다.      = gcd(a,p) = 1, a는 p와 서로소와 같은 의미이다.         p가 소수라면, p보다 작은 약수는 1과 p뿐이기 때문이다. 이 이론은 암호학의 공유키 활용, 소수 검증에서 많이 사용한다.증명은 하지 않고 활용에 초점을 둔다 ..  이와 같은 매우 큰 지수승 계산을 쉽게 만들 수 있습니다.그 이유는 9와 11이 조건을 만족하여 페르마의 이론이 성립하기 때문입니다.Euler Totient Function φ(n)  오일러..

군 (Group) 이란?군은 특정 연산을 만족하는 집합과 그 집합에서 정의된 이항 연산(binary operation)으로 이루어진 대수 구조를 군이라고 합니다.군을 만족하기 위해서는 집합의 모든 원소가 다음 조건을 만족해야 합니다. * 대수 구조(Algebraic Structure)란, 집합과 그 위에 정의된 연산들이 특정 규칙(공리)을 만족하는 수학적 구조를 의미함. 군의 조건1. Closure 닫힘a, b ∈ G, then a · b ∈ Ga와 b가 집합에 속하면, a와 b를 연산한 결과도 그 집합에 속해야 합니다. 2. Associative 결합법칙a, b, c ∈ G,then (a·b)·c = a·(b·c)a와 b를 연산하고 c를 연산한 결과가, b와 c를 연산하고 a를 연산한 결과와 같아야합니..

확장 유클리드 알고리즘이란?두 수의 최대공약수를 구하는 과정에서 , 베주 항등식(Bézout's Identity) 계수인 x와 y를 찾는 알고리즘입니다. 즉, 기본 유클리드 알고리즘에서 나머지 연산을 반복하면서, 동시에 계수 x와 y를 추적하여 베주 항등식을 만족하는 값을 찾고,이를 모듈로 역원을 구하는 데 사용합니다.  베주 항등식두 정수와 그 최대공약수 사이의 관계를 보여주는 항등식입니다.GCD(a,b) = ax + by = d위 방정식은 다음과 같은 의미를 가집니다.적어도 둘 중 하나는 0이 아닌 정수 a,b가 있고 그 최대공약수를 d라 합니다. 이때 다음 세 명제가 성립합니다.1. d = ax + by를 만족하는 정수 x,y가 반드시 존재한다.2. d는 정수 x,y에 대하여 ax+by 형태로 표현..

설명유클리드 알고리즘은 두 정수 사이의 최대공약수를 구하는 방식이다. 두 정수 사이의 아래와 같은 특성을 이용한다.큰 수(a)와 작은 수(b) 사이의 최대 공약수 = 큰 수를 작은 수로 나눈 나머지(a mod b)와 작은 수(b) 사이의 최대 공약수  a,b의 최대공약수를 구하기 위해 GCD(a,b)를 반복적으로 사용하는데, 만약 b가 0이라면, a값을 리턴하고b가 0이 아니라면, Euclid(b, a mod b) 를 재귀호출 (또는 while loop 사용) 한다. 앞의 파라미터를 계속 뒤의 파라미터로 나눈 나머지로 줄게 만들면서,어느 순간 뒤 파라미터가 0 (나머지가 0)이 될 때 그 앞 파라미터가 두 수의 최대공약수이다. 3개 정수의 최대공약수를 구할 때는, 두 개씩 먼저 적용하면 된다.gcd(a,..

AES란? Advanced Encryption Standard (AES)DES의 대체 암호화 방식의 필요성이 대두되고, US NIST 공모로 1997년에 정해진 새로운 블록 암호화 방식 data는 128 bit,key는 128 / 192 bit / 256 bit를 사용입출력 데이터를 모두 128비트 (16바이트)의 블록으로 처리 Iterative AES DES는 Feistel cipher* Feistel 암호는 데이터를 왼쪽과 오른쪽으로 나눈 후, 반복적으로 교환하면서 변환을 수행하는 구조 * 하지만 AES는 Feistel 구조를 사용하지 않고, 모든 라운드에서 전체 데이터 블록을 사용하는 반복적 구조(iterative cipher)* 라운드(round) - 데이터를 점점 복잡하게 변환하는 반복적인 처리..