[[TableOfContents]] = Part 1 정보보호 시스템 = == Chapter 02 수학적 배경 == === 2.1 정수론 === * p.24 * 암호학에서는 정수론과 유한체 이론이 많이 사용되고 있다. * 정수론이 쓰이는건 알았는데, 유한체를 여기서 볼 줄은 몰랐네 - [김도엽] * 이와 같이 b는 a로 나누어 떨어진다고 말하는 관계를 다음과 같이 표시한다. {{{ a|b }}} * a|b를 외울 때 "a can divide b"라고 외우면 될 듯 (밑에 링크는 "a divides b"라고 설명하고 있긴 함) - [김도엽] * [https://www.chilimath.com/lessons/introduction-to-number-theory/meaning-of-ab-or-a-pipe-b/ Meaning of a|b or a pipe b] * p.25 * 임의의 정수 a가 있을 때 이 수는 다음과 같이 소수의 곱으로 유일하게 표시할 수 있다. * 모든 수는 소수의 곱으로 이루어짐을 a=p1^(e1)*p2^(e2)*...*pr^(er)와 같이 수식으로 나타냈구나 - [창민규] * 합동식 a=b mod m에 대한 정수 집합 Z상의 동치류를 표현할 때, 법 m에 대한 잉여류라고 하며 다음과 같이 표현한다. * 여기서 동치류란 집합 A에 대한 R이 동치 관계일 때, 집합 A의 각 원소 a와 순서쌍을 이루는 원소들의 집합이다. - [이효근] * [a] ={x|(a,x) ∈ R} * 정수 집합 Z상에는 무한히 많은 소수가 분포되어 있으나 어떠한 규칙을 가지고 분포하는지는 밝혀진 바 없다. * 훗날 이 소수의 규칙이 발견된다면 양자역학이 중요한 역할을 할 수 있다고 들어본 것 같다. - [박석진] * 즉, a = b mod m은 a-b= km 이라는 뜻이다. 여기서 = 는 합동식을 나타내는 합동기호이다. * 밑에는 반사적,, 대칭적, 추이적 성질만 적혀있지만 합동식도 이항해서 하는계산이 가능하나는 것을 활용할 수 있다. - [이승화] * p.26 * 이 때, 원소의 개수 ϕ(m)을 Euler의 ϕ함수 (ϕ-function) 혹은 Euler의 토션 함수(totient function)라고 한다. * 파이 함수를 토션 함수라고도 부르는 구나 - [창민규] * ϕ(m)에서 m이 소수일 때는 ϕ(m) = m -1이니까 페르마의 소정리를 일반화한 것이 오일러의 정리라고 말할 수 있을 것 같다. -[박석진] * 집합 Z={0,1,2,...}상의 원소 중 m과 서로소인 원소 개수를 ϕ(m)이라고 표현하고 오일러 함수라고 한다. * 오일러정의에서 gcd(a,p)=1을 활용해서 정리를 시작하는게 페르마 정리이므로, 둘의 정리들이 서로 밀접하게 연관되있는 것 같다. - [이승화] * p.27 * 만약 소수 p가 있고 정수 a가 p로 나누어지지 않는 수라면 다음과 같은 방법으로 a의 역수를 구할 수 있다 * a^(p-1)을 a^(-1)*a^(p-2)로 나눠서 a^(-1)을 구하려는 거구나 - [창민규] === 2.2 유한체 === * p.28 * 따라서 덧셈군일 때는 항등원은 '0'(영원)으로 표시하고 승산군일 때의 항등원은 '1'(단위원)으로 표시한다. * 승산원은 곱셈군을 의미하는건가?... - [창민규] * 자연수는 덧셈에 대한 항등원이 존재하지 않는다 -[박석진] * p.29 * 특히, 곱셈에 대한 단위원이 존재하고 영이 아닌 원소가 승산에 대하여 역원을 갖는 가환환을 체(field) F라고 정의한다. * 그러면 결국 "체" F 정의는 {{①닫힘 ②결합 법칙 ③항등원 ④역원} 성질을 가지는 ⑤가환군이면서 ⑥곱셈에 대한 닫힘 ⑦곱셈에 대한 결합법칙 ⑧분배법칙} 성질과 ⑨곱셈의 역원을 가지는 ⑩가환환 이라고 할 수 있는게 맞나? - [김도엽] * p.30 * a^b = 1 mod m에서 법 m에 관한 정수 a의 위수가 ϕ(m)일 때, a를 법 m에 대한 원시근(primitive root) 또는 원시원소라고 한다. * 이 말이 어떤 정수를 계속 제곱해도 잉여계가 1이 되는 자연수가 있는데, 이 수에 위수가 존재하고, 그 모든 위수가 ϕ(m)의 약수가 될때, 그 위수가 원시근이라는 내 이해가 맞나? -[이승화] * p.34 * 유클리드 알고리즘을 이용한 최대 공약수를 구하는 방법은 어떠한 음이 아닌 정수 a와 그보다 작은 정수 b가 있을 때 다음 등식에 기반한다. {{{ gcd(a, b)=gcd(b, a mod b) }}} * C-style로 한 줄 코딩할 수 있음. 이걸로 gcd는 물론 lcm 구해야 할 때도 유용하게 써먹음. - [김도엽]{{{ int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } }}} * p.34 * 그런데 유클리드 알고리즘을 확장한 확장 유클리드 알고리즘은 두 개의 정수가 서로 소인 경우에 한 수에 대한 다른 수의 곱셈에 대한 역원을 계산하는데 사용된다 * 유클리드 알고리즘에서의 ax+by=gcd(a,b)와 모듈러를 이용하여 역원을 구하겠구나 - [창민규] * p.35 * 만약 두 정수 f와 f보다 작은 정수 d가 서로 소이면, 즉 gcd(f, d)=1이라면, 그때 d는 모듈러 f상에서 곱셈에 대한 역원을 갖는다. 즉, d·d^-1=1 mod f인 d^-1> bit)) 12. out[i/8] |= mask >> (i%8); 13. } }}} * 이 부분은 다음에 다시 찬찬히 무슨 원리인지 디버깅해보자 - [김도엽] * p.74 * f함수는 먼저 입력된 32비트를 48비트로 확장하게 되며 다음의 확장 테이블을 이용하게 된다. * 그냥 간단하게 원래 비트를 4개씩 쪼개서 가운데에 넣은 다음에, 처음과 마지막에 이웃한 4개묶음에서 끄트머리 비트들을 가져와 붙인거다 - [김도엽] * p.75 * F함수의 두 번째 과정은 S-BOX로서 총 8개의 S-BOX가 있으며, S-BOX 테이블에 의해 각각 6비트를 입력으로 받아들여서 4비트로 출력한다. * 이 때, S-BOX가 이미 정해져있는데, 한때는 NBS(현 NIST)가 백도어를 심은거 아니냐는 여론이 있었다고 한다. 지금은 그딴거 없다고 밝혀지긴 했지만 - [김도엽] * p.82 * 입력된 64비트의 키는 순열 선택표(Permuted Choice 1, PC-1)에 의해 축소되어 재배치되는데 좌우로 28비트씩 2개로 나누어져 각각 C_0와 D_0가 된다. * 8의 배수의 인덱스에 있는 비트가 사라진다. - [김도엽] * p.83 * 순열 선택 1을 거쳐 나온 출력 값 56비트의 키를 다음의 라운드별 좌측 쉬프트 테이블에 의해 왼쪽 방향으로 순환 쉬프트를 수행한다. * 이 페이지에 나온 표를 보면 좌측 순환 쉬프트 수의 합이 28이 나오는 걸 볼 수 있다. - [김도엽] === 4.3 DES의 S/W 구현 === * p.87 * {{{ 31. /* 전역 변수 */ 32. // 초기 순열 테이블 33. BYTE ip[64] = {58, 50, 42, ... }}} * 전역 변수로 테이블들이 너무 많아서 구현할 의욕이 사라진다... - [김도엽] == Chapter 05 AES(Advanced Encryption Standard) == === 5.1 AES의 소개 === === 5.2 AES 구조 === === 5.3 각 라운드 함수 === === 5.4 키 확장 === === 5.5 AES의 S/W 구현 ===