C로배우는암호학프로그래밍/밑줄긋기 (rev. 1.27)
- p.24
- 암호학에서는 정수론과 유한체 이론이 많이 사용되고 있다.
- 정수론이 쓰이는건 알았는데, 유한체를 여기서 볼 줄은 몰랐네 - 김도엽
- 이와 같이 b는 a로 나누어 떨어진다고 말하는 관계를 다음과 같이 표시한다.
a|b
- p.25
- 임의의 정수 a가 있을 때 이 수는 다음과 같이 소수의 곱으로 유일하게 표시할 수 있다.
- 모든 수는 소수의 곱으로 이루어짐을 a=p1^(e1)*p2^(e2)*...*pr^(er)와 같이 수식으로 나타냈구나 - 창민규
- 합동식 a=b mod m에 대한 정수 집합 Z상의 동치류를 표현할 때, 법 m에 댛나 잉여류라고 하며 다음과 같이 표현한다.
- 여기서 동치류란 집합 A에 대한 R이 동치 관계일 때, 집합 A의 각 원소 a와 순서쌍을 이루는 원소들의 집합
- p.26
- 이 때, 원소의 개수 ϕ(m)을 Euler의 ϕ함수 (ϕ-function) 혹은 Euler의 토션 함수(totient function)라고 한다.
- 파이 함수를 토션 함수라고도 부르는 구나 - 창민규
- p.27
- 만약 소수 p가 있고 정수 a가 p로 나누어지지 않는 수라면 다음과 같은 방법으로 a의 역수를 구할 수 있다
- a^(p-1)을 a^(-1)*a^(p-2)로 나눠서 a^(-1)을 구하려는 거구나 - 창민규
- p.28
- 따라서 덧셈군일 때는 항등원은 '0'(영원)으로 표시하고 승산군일 때의 항등원은 '1'(단위원)으로 표시한다.
- 승산원은 곱셈군을 의미하는건가?... - 창민규
- p.29
- 특히, 곱셈에 대한 단위원이 존재하고 영이 아닌 원소가 승산에 대하여 역원을 갖는 가환환을 체(field) F라고 정의한다.
- 그러면 결국 "체" F 정의는 {{①닫힘 ②결합 법칙 ③항등원 ④역원} 성질을 가지는 ⑤가환군이면서 ⑥곱셈에 대한 닫힘 ⑦곱셈에 대한 결합법칙 ⑧분배법칙} 성질과 ⑨곱셈의 역원을 가지는 ⑩가환환 이라고 할 수 있는게 맞나? - 김도엽
- p.34
- 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
- RSA 키 만드는 과정중 비밀키 d를 만들때, ϕ(N)상에서 e의 곱셈에 대한 역원으로 d를 결정해야 함. 마침 ed≡1(mod ϕ(N))에서 이미 e를 ϕ(N)와 서로소인 정수로 결정했기 때문에 e의 곱셈에 대한 역원이 존재하므로 d를 구할 수 있는 것임. - 김도엽
