Difference between r1.28 and the current
@@ -14,12 +14,19 @@
* p.25
* 임의의 정수 a가 있을 때 이 수는 다음과 같이 소수의 곱으로 유일하게 표시할 수 있다.
* 모든 수는 소수의 곱으로 이루어짐을 a=p1^(e1)*p2^(e2)*...*pr^(er)와 같이 수식으로 나타냈구나 - [창민규]
* [a] ={x|(a,x) ∈ R}
* 이 때, 원소의 개수 ϕ(m)을 Euler의 ϕ함수 (ϕ-function) 혹은 Euler의 토션 함수(totient function)라고 한다.
* 파이 함수를 토션 함수라고도 부르는 구나 - [창민규]
* 만약 소수 p가 있고 정수 a가 p로 나누어지지 않는 수라면 다음과 같은 방법으로 a의 역수를 구할 수 있다
* a^(p-1)을 a^(-1)*a^(p-2)로 나눠서 a^(-1)을 구하려는 거구나 - [창민규]
* 임의의 정수 a가 있을 때 이 수는 다음과 같이 소수의 곱으로 유일하게 표시할 수 있다.
* 모든 수는 소수의 곱으로 이루어짐을 a=p1^(e1)*p2^(e2)*...*pr^(er)와 같이 수식으로 나타냈구나 - [창민규]
* 합동식 a=b mod m에 대한 정수 집합 Z상의 동치류를 표현할 때, 법 m에 댛나 잉여류라고 하며 다음과 같이 표현한다.
* 합동식 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)을 구하려는 거구나 - [창민규]
@@ -27,15 +34,19 @@
* p.28
* 따라서 덧셈군일 때는 항등원은 '0'(영원)으로 표시하고 승산군일 때의 항등원은 '1'(단위원)으로 표시한다.
* 승산원은 곱셈군을 의미하는건가?... - [창민규]
* 특히, 곱셈에 대한 단위원이 존재하고 영이 아닌 원소가 승산에 대하여 역원을 갖는 가환환을 체(field) F라고 정의한다.
* 그러면 결국 "체" F 정의는 {{①닫힘 ②결합 법칙 ③항등원 ④역원} 성질을 가지는 ⑤가환군이면서 ⑥곱셈에 대한 닫힘 ⑦곱셈에 대한 결합법칙 ⑧분배법칙} 성질과 ⑨곱셈의 역원을 가지는 ⑩가환환 이라고 할 수 있는게 맞나? - [김도엽]
* 유클리드 알고리즘을 이용한 최대 공약수를 구하는 방법은 어떠한 음이 아닌 정수 a와 그보다 작은 정수 b가 있을 때 다음 등식에 기반한다. {{{
gcd(a, b)=gcd(b, a mod b)
}}}
* C-style로 한 줄 코딩할 수 있음. 이걸로 gcd는 물론 lcm 구해야 할 때도 유용하게 써먹음. - [김도엽]{{{
* p.34
* 그런데 유클리드 알고리즘을 확장한 확장 유클리드 알고리즘은 두 개의 정수가 서로 소인 경우에 한 수에 대한 다른 수의 곱셈에 대한 역원을 계산하는데 사용된다
* 따라서 덧셈군일 때는 항등원은 '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 ? a : gcd(b, a%b); }
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
}}}* p.34
* 그런데 유클리드 알고리즘을 확장한 확장 유클리드 알고리즘은 두 개의 정수가 서로 소인 경우에 한 수에 대한 다른 수의 곱셈에 대한 역원을 계산하는데 사용된다
@@ -43,15 +54,104 @@
* p.35
* 만약 두 정수 f와 f보다 작은 정수 d가 서로 소이면, 즉 gcd(f, d)=1이라면, 그때 d는 모듈러 f상에서 곱셈에 대한 역원을 갖는다. 즉, d·d^-1=1 mod f인 d^-1<f가 존재한다.
* RSA 키 만드는 과정중 비밀키 d를 만들때, ϕ(N)상에서 e의 곱셈에 대한 역원으로 d를 결정해야 함. 마침 ed≡1(mod ϕ(N))에서 이미 e를 ϕ(N)와 서로소인 정수로 결정했기 때문에 e의 곱셈에 대한 역원이 존재하므로 d를 구할 수 있는 것임. - [김도엽]
* p.36
* 최대공약수 구하기(Euclid 알고리즘){{{
* VS에서 만든 코드인 듯? - [김도엽]
* p.38
* 역수 구하기(확장 Euclid 알고리즘){{{
1. int Extended_Euclid(int a, int p);
* 함수를 위에서 정의만 해놓고 코드 작성은 밑에서 하는 경우가 꽤 있네. 가독성이 좋아서 그런건가 - [이효근]
* 만약 두 정수 f와 f보다 작은 정수 d가 서로 소이면, 즉 gcd(f, d)=1이라면, 그때 d는 모듈러 f상에서 곱셈에 대한 역원을 갖는다. 즉, d·d^-1=1 mod f인 d^-1<f가 존재한다.
* RSA 키 만드는 과정중 비밀키 d를 만들때, ϕ(N)상에서 e의 곱셈에 대한 역원으로 d를 결정해야 함. 마침 ed≡1(mod ϕ(N))에서 이미 e를 ϕ(N)와 서로소인 정수로 결정했기 때문에 e의 곱셈에 대한 역원이 존재하므로 d를 구할 수 있는 것임. - [김도엽]
* 확장 유클리드 알고리즘을 이용한 역원을 계산하는 과정을 나타낸 것은 밑의 그림으로 확인할 수 있다. 포인트: 밑에 그림
*https://www.youtube.com/watch?v=PmwLXveLtqc (이미 카톡방에서 한번 공유한적 있지만), 유클리드 알고리즘을 어떤 방법으로 활용했느지 잘 설명해준 내용인듯..? - [이승화]
=== 2.3 최대공약수 및 역수 구하기 S/W ===* p.36
* 최대공약수 구하기(Euclid 알고리즘){{{
1. #define _CRT_SECURE_NO_WARNINGS
1. #define _CRT_SECURE_NO_WARNINGS
}}}* VS에서 만든 코드인 듯? - [김도엽]
* p.38
* 역수 구하기(확장 Euclid 알고리즘){{{
3. int Extended_Euclid(int a, int p);
}}}* 함수를 위에서 정의만 해놓고 코드 작성은 밑에서 하는 경우가 꽤 있네. 가독성이 좋아서 그런건가 - [이효근]
* 가독성 맞음. main()함수를 맨 위에 올려놓고, 다른 함수들을 밑으로 내릴려면 위에서 정의를 해 놔야돼서 - [김도엽]
= Part 2 비밀 키 암호 시스템 =
== Chapter 03 고전 암호 알고리즘 ==
=== 3.1 대치 암호 ===
* p.44
* 가장 오래된 암호로서 로마의 유명한 군인이자 정치가였던 쥴리어스 시저(Julius Caesar, B.C. 100~44)가 사용하여 그 이름이 유래되었다.
* 시저 암호를 어떤 곳에서는 카이사르 암호라고 부르는 것도 봤음 - [김도엽]
* 고전암호에서 송신자와 수신자가 동일한 암호 키를 이용해 평문을 암호화하고, 암호문을 복호화나는 대칭 키 암호 혹은 관용 암호 알고리즘이라고 한다. 키의 안전성에 따라 대치암호와 전치암호로 구분할 수 있다.
* 컴활 시험공부중에서 나왔던 얘기들이여서 두 개의 차이에 좀 주목해서 내용 읽어야할듯. - [이승화]
* 시저 암호는 영어 문자에 번호를 0부터 25까지 붙여 비밀키와 조합해 법(module)연산을 하는 것이 특징이다.
* 쉽게 말해, 영어 알파벳에 순서를 붙여 그대로 key값만큼 오른쪽이나 왼쪽으로 옮기는 방법인듯. 만약 알파벳을 대문자와 소문자를 따로따로 키를 작용시키는 방법이라면 시저암호도 어려운 암호가 아닐지라는 생각이 들었다. - [이승화]
* p.45
* 그러나 시저 암호는 암호 키로 25개의 문자만 사용할 수 있어 전수 조사 공격(brute force attack)에 취약한 특성을 가진 고전암호이다.
* 암호 키로 매우 큰 숫자도 쓸 수 있지만 암호 키가 1이나 27이나 53이나 같은 결과가 나오니 25개의 키밖에 없는게 맞음 - [김도엽]
* brute force는 가능한 경우를 전부 조사하는 알고리즘 이름으로도 쓰임 - [김도엽]
* https://hcr3066.tistory.com/26 도엽님이 얘기한것을 조사해봤는데, 요약해보자면 모든 경우의수를 대입하는 방법이지만 그 알고리즘을 잘 설명해준 내용인 것 같아서 공유합니다. - [이승화]
* 당시에는 이러한 암호 방식이 먹혔는지가 궁금하다. - [창민규]
* p.46
* {{{
23. if( (str[i] + key) < 0)
24. str[i] += 26;
}}}
* 26을 더해도 법 연산에서 걸러지기 때문에 굳이 조건 확인할 필요는 없음 - [김도엽]
* p.48
* 단일 대치 암호는 하나의 평문 문자를 다른 하나의 암호문 문자로 대치하는 방식이다.
*시저 암호와 큰 차이점을 말하면, 시저 암호는 한 개의 키 값에 전체 문장의 알파벳을 다 옮기는 방법을 사용한 것이라면, 단일 대치암호를 요약하면 한 개의 문자마다 옮길 알파벳을 찾는 방법이라고 생각하면 될 것 같음. - [이승화]
* p.49
* 단일 대치 암호는 암호에서 키 공간의 크기는 26!(약 4*10^26개)로서 전수 조사 공격(brute force attack)에는 비교적 강인한 특성을 가지지만 암호문에 나타난 문자의 출현 빈도수를 보고 이를 통계학적인 방법으로 분석하여 비밀 키를 찾아낼 수 있다.
* 보통 알고리즘 문제 풀 때 1억번 연산할 때마다 1초가 걸린다고 생각하는데, 이걸로 단순계산해보면 약 1,268,391,679,350년이 걸림 - [김도엽]
* 비즈네르도 빈도분석법에 완전히 강한 것은 아님 [https://m.blog.naver.com/sepaper/221801111654 다중문자 암호와 비즈네르 암호] - [김도엽]
* p.49
* 대표적인 다준 대체 암호 방식으로 프랑스 암호학자 B. Vigenere가 고안한 Vigenere 암호가 있다.
* 이 암호는 비교적 빈도분석법에 강하지만 카지스키 테스트가 프리드먼 테스트를 통해 충분히 복호화가 가능하다고 한다. [https://kevin0960.tistory.com/116] - [창민규]
=== 3.2 전치 암호 ===
== Chapter 04 DES(Data Encryption Standard) ==
=== 4.1 Feistel 암호 구조 ===
* p.60
* 이 Feistel 구조는 암호화 과정과 복호화 과정을 키 순서만 바꾸어 똑같이 적용할 수 있는 간편한 형태이면서 안전성이 높아 현대 비밀 키 암호를 설계하는데 많이 이용되고 있다.
* ASNI X9.17 유사 난수 생성기의 과정에서도 3DES가 사용됨. 6번 암호화, 3번 복호화가 진행되어 혼돈, 확산 기능이 높다고 함. - [김도엽]
=== 4.2 DES 구조 ===
* p.69
* 4.2.1 DES 전체 구조
* [https://developer-mac.tistory.com/52 기초 암호학(1) - DES] 이번에 DES 공부하면서 많이 참고한 블로그 - [김도엽]
* DES는 기본적으로 16라운드로 구성되며, 각 라운드는 서로 동일한 과정을 반복적으로 수행하다.
* ~~마지막에 "수행하다"는 오타인가?~~ 16라운드씩이나 전치와 대치가 일어나는데 어찌 혼돈과 확산이 안일어나리오 - [김도엽]
* p.71
* {{{
1. void IP(BYTE *in, BYTE *out)
}}}
* BYTE는 p.86에서 unsigned char로 정의되어 있음. 마찬가지로 UINT는 unsigned int. - [김도엽]
* {{{
6. for(i=0;i<64;i++)
7. {
8. index = (ip[i]-1) / 8;
9. bit = (ip[i]-1) % 8;
10.
11. if(in[index] & (mask >> 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 구현 ===
Contents
1.1.1. 2.1 정수론 ¶
- p.24
- 암호학에서는 정수론과 유한체 이론이 많이 사용되고 있다.
- 정수론이 쓰이는건 알았는데, 유한체를 여기서 볼 줄은 몰랐네 - 김도엽
- 정수론이 쓰이는건 알았는데, 유한체를 여기서 볼 줄은 몰랐네 - 김도엽
- 이와 같이 b는 a로 나누어 떨어진다고 말하는 관계를 다음과 같이 표시한다.
a|b
- a|b를 외울 때 "a can divide b"라고 외우면 될 듯 (밑에 링크는 "a divides b"라고 설명하고 있긴 함) - 김도엽
- Meaning of a|b or a pipe b
- a|b를 외울 때 "a can divide b"라고 외우면 될 듯 (밑에 링크는 "a divides b"라고 설명하고 있긴 함) - 김도엽
- 암호학에서는 정수론과 유한체 이론이 많이 사용되고 있다.
- p.25
- 임의의 정수 a가 있을 때 이 수는 다음과 같이 소수의 곱으로 유일하게 표시할 수 있다.
- 모든 수는 소수의 곱으로 이루어짐을 a=p1^(e1)*p2^(e2)*...*pr^(er)와 같이 수식으로 나타냈구나 - 창민규
- 모든 수는 소수의 곱으로 이루어짐을 a=p1^(e1)*p2^(e2)*...*pr^(er)와 같이 수식으로 나타냈구나 - 창민규
- 합동식 a=b mod m에 대한 정수 집합 Z상의 동치류를 표현할 때, 법 m에 대한 잉여류라고 하며 다음과 같이 표현한다.
- 정수 집합 Z상에는 무한히 많은 소수가 분포되어 있으나 어떠한 규칙을 가지고 분포하는지는 밝혀진 바 없다.
- 훗날 이 소수의 규칙이 발견된다면 양자역학이 중요한 역할을 할 수 있다고 들어본 것 같다. - 박석진
- 훗날 이 소수의 규칙이 발견된다면 양자역학이 중요한 역할을 할 수 있다고 들어본 것 같다. - 박석진
- 즉, a = b mod m은 a-b= km 이라는 뜻이다. 여기서 = 는 합동식을 나타내는 합동기호이다.
- 밑에는 반사적,, 대칭적, 추이적 성질만 적혀있지만 합동식도 이항해서 하는계산이 가능하나는 것을 활용할 수 있다. - 이승화
- 밑에는 반사적,, 대칭적, 추이적 성질만 적혀있지만 합동식도 이항해서 하는계산이 가능하나는 것을 활용할 수 있다. - 이승화
- 임의의 정수 a가 있을 때 이 수는 다음과 같이 소수의 곱으로 유일하게 표시할 수 있다.
- p.26
- 이 때, 원소의 개수 ϕ(m)을 Euler의 ϕ함수 (ϕ-function) 혹은 Euler의 토션 함수(totient function)라고 한다.
- 이 때, 원소의 개수 ϕ(m)을 Euler의 ϕ함수 (ϕ-function) 혹은 Euler의 토션 함수(totient function)라고 한다.
- p.27
- 만약 소수 p가 있고 정수 a가 p로 나누어지지 않는 수라면 다음과 같은 방법으로 a의 역수를 구할 수 있다
- a^(p-1)을 a^(-1)*a^(p-2)로 나눠서 a^(-1)을 구하려는 거구나 - 창민규
- a^(p-1)을 a^(-1)*a^(p-2)로 나눠서 a^(-1)을 구하려는 거구나 - 창민규
- 만약 소수 p가 있고 정수 a가 p로 나누어지지 않는 수라면 다음과 같은 방법으로 a의 역수를 구할 수 있다
1.1.2. 2.2 유한체 ¶
- p.28
- p.29
- 특히, 곱셈에 대한 단위원이 존재하고 영이 아닌 원소가 승산에 대하여 역원을 갖는 가환환을 체(field) F라고 정의한다.
- 그러면 결국 "체" F 정의는 {{①닫힘 ②결합 법칙 ③항등원 ④역원} 성질을 가지는 ⑤가환군이면서 ⑥곱셈에 대한 닫힘 ⑦곱셈에 대한 결합법칙 ⑧분배법칙} 성질과 ⑨곱셈의 역원을 가지는 ⑩가환환 이라고 할 수 있는게 맞나? - 김도엽
- 그러면 결국 "체" F 정의는 {{①닫힘 ②결합 법칙 ③항등원 ④역원} 성질을 가지는 ⑤가환군이면서 ⑥곱셈에 대한 닫힘 ⑦곱셈에 대한 결합법칙 ⑧분배법칙} 성질과 ⑨곱셈의 역원을 가지는 ⑩가환환 이라고 할 수 있는게 맞나? - 김도엽
- 특히, 곱셈에 대한 단위원이 존재하고 영이 아닌 원소가 승산에 대하여 역원을 갖는 가환환을 체(field) F라고 정의한다.
- p.30
- a^b = 1 mod m에서 법 m에 관한 정수 a의 위수가 ϕ(m)일 때, a를 법 m에 대한 원시근(primitive root) 또는 원시원소라고 한다.
- 이 말이 어떤 정수를 계속 제곱해도 잉여계가 1이 되는 자연수가 있는데, 이 수에 위수가 존재하고, 그 모든 위수가 ϕ(m)의 약수가 될때, 그 위수가 원시근이라는 내 이해가 맞나? -이승화
- 이 말이 어떤 정수를 계속 제곱해도 잉여계가 1이 되는 자연수가 있는데, 이 수에 위수가 존재하고, 그 모든 위수가 ϕ(m)의 약수가 될때, 그 위수가 원시근이라는 내 이해가 맞나? -이승화
- a^b = 1 mod m에서 법 m에 관한 정수 a의 위수가 ϕ(m)일 때, a를 법 m에 대한 원시근(primitive root) 또는 원시원소라고 한다.
- 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; }
- C-style로 한 줄 코딩할 수 있음. 이걸로 gcd는 물론 lcm 구해야 할 때도 유용하게 써먹음. - 김도엽
- 유클리드 알고리즘을 이용한 최대 공약수를 구하는 방법은 어떠한 음이 아닌 정수 a와 그보다 작은 정수 b가 있을 때 다음 등식에 기반한다.
- p.34
- 그런데 유클리드 알고리즘을 확장한 확장 유클리드 알고리즘은 두 개의 정수가 서로 소인 경우에 한 수에 대한 다른 수의 곱셈에 대한 역원을 계산하는데 사용된다
- 유클리드 알고리즘에서의 ax+by=gcd(a,b)와 모듈러를 이용하여 역원을 구하겠구나 - 창민규
- 유클리드 알고리즘에서의 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를 구할 수 있는 것임. - 김도엽
- RSA 키 만드는 과정중 비밀키 d를 만들때, ϕ(N)상에서 e의 곱셈에 대한 역원으로 d를 결정해야 함. 마침 ed≡1(mod ϕ(N))에서 이미 e를 ϕ(N)와 서로소인 정수로 결정했기 때문에 e의 곱셈에 대한 역원이 존재하므로 d를 구할 수 있는 것임. - 김도엽
- 확장 유클리드 알고리즘을 이용한 역원을 계산하는 과정을 나타낸 것은 밑의 그림으로 확인할 수 있다. 포인트: 밑에 그림
- https://www.youtube.com/watch?v=PmwLXveLtqc (이미 카톡방에서 한번 공유한적 있지만), 유클리드 알고리즘을 어떤 방법으로 활용했느지 잘 설명해준 내용인듯..? - 이승화
- https://www.youtube.com/watch?v=PmwLXveLtqc (이미 카톡방에서 한번 공유한적 있지만), 유클리드 알고리즘을 어떤 방법으로 활용했느지 잘 설명해준 내용인듯..? - 이승화
- 만약 두 정수 f와 f보다 작은 정수 d가 서로 소이면, 즉 gcd(f, d)=1이라면, 그때 d는 모듈러 f상에서 곱셈에 대한 역원을 갖는다. 즉, d·d^-1=1 mod f인 d^-1
2.1.1. 3.1 대치 암호 ¶
- p.44
- 가장 오래된 암호로서 로마의 유명한 군인이자 정치가였던 쥴리어스 시저(Julius Caesar, B.C. 100~44)가 사용하여 그 이름이 유래되었다.
- 시저 암호를 어떤 곳에서는 카이사르 암호라고 부르는 것도 봤음 - 김도엽
- 시저 암호를 어떤 곳에서는 카이사르 암호라고 부르는 것도 봤음 - 김도엽
- 고전암호에서 송신자와 수신자가 동일한 암호 키를 이용해 평문을 암호화하고, 암호문을 복호화나는 대칭 키 암호 혹은 관용 암호 알고리즘이라고 한다. 키의 안전성에 따라 대치암호와 전치암호로 구분할 수 있다.
- 컴활 시험공부중에서 나왔던 얘기들이여서 두 개의 차이에 좀 주목해서 내용 읽어야할듯. - 이승화
- 컴활 시험공부중에서 나왔던 얘기들이여서 두 개의 차이에 좀 주목해서 내용 읽어야할듯. - 이승화
- 시저 암호는 영어 문자에 번호를 0부터 25까지 붙여 비밀키와 조합해 법(module)연산을 하는 것이 특징이다.
- 쉽게 말해, 영어 알파벳에 순서를 붙여 그대로 key값만큼 오른쪽이나 왼쪽으로 옮기는 방법인듯. 만약 알파벳을 대문자와 소문자를 따로따로 키를 작용시키는 방법이라면 시저암호도 어려운 암호가 아닐지라는 생각이 들었다. - 이승화
- 쉽게 말해, 영어 알파벳에 순서를 붙여 그대로 key값만큼 오른쪽이나 왼쪽으로 옮기는 방법인듯. 만약 알파벳을 대문자와 소문자를 따로따로 키를 작용시키는 방법이라면 시저암호도 어려운 암호가 아닐지라는 생각이 들었다. - 이승화
- 가장 오래된 암호로서 로마의 유명한 군인이자 정치가였던 쥴리어스 시저(Julius Caesar, B.C. 100~44)가 사용하여 그 이름이 유래되었다.
- p.45
- 그러나 시저 암호는 암호 키로 25개의 문자만 사용할 수 있어 전수 조사 공격(brute force attack)에 취약한 특성을 가진 고전암호이다.
- 암호 키로 매우 큰 숫자도 쓸 수 있지만 암호 키가 1이나 27이나 53이나 같은 결과가 나오니 25개의 키밖에 없는게 맞음 - 김도엽
- brute force는 가능한 경우를 전부 조사하는 알고리즘 이름으로도 쓰임 - 김도엽
- https://hcr3066.tistory.com/26 도엽님이 얘기한것을 조사해봤는데, 요약해보자면 모든 경우의수를 대입하는 방법이지만 그 알고리즘을 잘 설명해준 내용인 것 같아서 공유합니다. - 이승화
- 당시에는 이러한 암호 방식이 먹혔는지가 궁금하다. - 창민규
- 암호 키로 매우 큰 숫자도 쓸 수 있지만 암호 키가 1이나 27이나 53이나 같은 결과가 나오니 25개의 키밖에 없는게 맞음 - 김도엽
- 그러나 시저 암호는 암호 키로 25개의 문자만 사용할 수 있어 전수 조사 공격(brute force attack)에 취약한 특성을 가진 고전암호이다.
- p.46
23. if( (str[i] + key) < 0) 24. str[i] += 26;
- 26을 더해도 법 연산에서 걸러지기 때문에 굳이 조건 확인할 필요는 없음 - 김도엽
- 26을 더해도 법 연산에서 걸러지기 때문에 굳이 조건 확인할 필요는 없음 - 김도엽
- p.48
- 단일 대치 암호는 하나의 평문 문자를 다른 하나의 암호문 문자로 대치하는 방식이다.
- 시저 암호와 큰 차이점을 말하면, 시저 암호는 한 개의 키 값에 전체 문장의 알파벳을 다 옮기는 방법을 사용한 것이라면, 단일 대치암호를 요약하면 한 개의 문자마다 옮길 알파벳을 찾는 방법이라고 생각하면 될 것 같음. - 이승화
- 시저 암호와 큰 차이점을 말하면, 시저 암호는 한 개의 키 값에 전체 문장의 알파벳을 다 옮기는 방법을 사용한 것이라면, 단일 대치암호를 요약하면 한 개의 문자마다 옮길 알파벳을 찾는 방법이라고 생각하면 될 것 같음. - 이승화
- 단일 대치 암호는 하나의 평문 문자를 다른 하나의 암호문 문자로 대치하는 방식이다.
- p.49
- 단일 대치 암호는 암호에서 키 공간의 크기는 26!(약 4*10^26개)로서 전수 조사 공격(brute force attack)에는 비교적 강인한 특성을 가지지만 암호문에 나타난 문자의 출현 빈도수를 보고 이를 통계학적인 방법으로 분석하여 비밀 키를 찾아낼 수 있다.
- 보통 알고리즘 문제 풀 때 1억번 연산할 때마다 1초가 걸린다고 생각하는데, 이걸로 단순계산해보면 약 1,268,391,679,350년이 걸림 - 김도엽
- 비즈네르도 빈도분석법에 완전히 강한 것은 아님 다중문자 암호와 비즈네르 암호 - 김도엽
- 보통 알고리즘 문제 풀 때 1억번 연산할 때마다 1초가 걸린다고 생각하는데, 이걸로 단순계산해보면 약 1,268,391,679,350년이 걸림 - 김도엽
- 단일 대치 암호는 암호에서 키 공간의 크기는 26!(약 4*10^26개)로서 전수 조사 공격(brute force attack)에는 비교적 강인한 특성을 가지지만 암호문에 나타난 문자의 출현 빈도수를 보고 이를 통계학적인 방법으로 분석하여 비밀 키를 찾아낼 수 있다.
- p.49
- 대표적인 다준 대체 암호 방식으로 프랑스 암호학자 B. Vigenere가 고안한 Vigenere 암호가 있다.
- 이 암호는 비교적 빈도분석법에 강하지만 카지스키 테스트가 프리드먼 테스트를 통해 충분히 복호화가 가능하다고 한다. https://kevin0960.tistory.com/116 - 창민규
- 이 암호는 비교적 빈도분석법에 강하지만 카지스키 테스트가 프리드먼 테스트를 통해 충분히 복호화가 가능하다고 한다. https://kevin0960.tistory.com/116 - 창민규
- 대표적인 다준 대체 암호 방식으로 프랑스 암호학자 B. Vigenere가 고안한 Vigenere 암호가 있다.
2.2.1. 4.1 Feistel 암호 구조 ¶
- p.60
- 이 Feistel 구조는 암호화 과정과 복호화 과정을 키 순서만 바꾸어 똑같이 적용할 수 있는 간편한 형태이면서 안전성이 높아 현대 비밀 키 암호를 설계하는데 많이 이용되고 있다.
- ASNI X9.17 유사 난수 생성기의 과정에서도 3DES가 사용됨. 6번 암호화, 3번 복호화가 진행되어 혼돈, 확산 기능이 높다고 함. - 김도엽
- ASNI X9.17 유사 난수 생성기의 과정에서도 3DES가 사용됨. 6번 암호화, 3번 복호화가 진행되어 혼돈, 확산 기능이 높다고 함. - 김도엽
- 이 Feistel 구조는 암호화 과정과 복호화 과정을 키 순서만 바꾸어 똑같이 적용할 수 있는 간편한 형태이면서 안전성이 높아 현대 비밀 키 암호를 설계하는데 많이 이용되고 있다.
2.2.2. 4.2 DES 구조 ¶
- p.69
- 4.2.1 DES 전체 구조
- 기초 암호학(1) - DES 이번에 DES 공부하면서 많이 참고한 블로그 - 김도엽
- 기초 암호학(1) - DES 이번에 DES 공부하면서 많이 참고한 블로그 - 김도엽
- DES는 기본적으로 16라운드로 구성되며, 각 라운드는 서로 동일한 과정을 반복적으로 수행하다.
마지막에 "수행하다"는 오타인가?16라운드씩이나 전치와 대치가 일어나는데 어찌 혼돈과 확산이 안일어나리오 - 김도엽
- 4.2.1 DES 전체 구조
- p.71
- p.74
- f함수는 먼저 입력된 32비트를 48비트로 확장하게 되며 다음의 확장 테이블을 이용하게 된다.
- 그냥 간단하게 원래 비트를 4개씩 쪼개서 가운데에 넣은 다음에, 처음과 마지막에 이웃한 4개묶음에서 끄트머리 비트들을 가져와 붙인거다 - 김도엽
- 그냥 간단하게 원래 비트를 4개씩 쪼개서 가운데에 넣은 다음에, 처음과 마지막에 이웃한 4개묶음에서 끄트머리 비트들을 가져와 붙인거다 - 김도엽
- f함수는 먼저 입력된 32비트를 48비트로 확장하게 되며 다음의 확장 테이블을 이용하게 된다.
- p.75
- F함수의 두 번째 과정은 S-BOX로서 총 8개의 S-BOX가 있으며, S-BOX 테이블에 의해 각각 6비트를 입력으로 받아들여서 4비트로 출력한다.
- 이 때, S-BOX가 이미 정해져있는데, 한때는 NBS(현 NIST)가 백도어를 심은거 아니냐는 여론이 있었다고 한다. 지금은 그딴거 없다고 밝혀지긴 했지만 - 김도엽
- 이 때, S-BOX가 이미 정해져있는데, 한때는 NBS(현 NIST)가 백도어를 심은거 아니냐는 여론이 있었다고 한다. 지금은 그딴거 없다고 밝혀지긴 했지만 - 김도엽
- F함수의 두 번째 과정은 S-BOX로서 총 8개의 S-BOX가 있으며, S-BOX 테이블에 의해 각각 6비트를 입력으로 받아들여서 4비트로 출력한다.
- p.82
- 입력된 64비트의 키는 순열 선택표(Permuted Choice 1, PC-1)에 의해 축소되어 재배치되는데 좌우로 28비트씩 2개로 나누어져 각각 C_0와 D_0가 된다.
- 8의 배수의 인덱스에 있는 비트가 사라진다. - 김도엽
- 8의 배수의 인덱스에 있는 비트가 사라진다. - 김도엽
- 입력된 64비트의 키는 순열 선택표(Permuted Choice 1, PC-1)에 의해 축소되어 재배치되는데 좌우로 28비트씩 2개로 나누어져 각각 C_0와 D_0가 된다.
- p.83
- 순열 선택 1을 거쳐 나온 출력 값 56비트의 키를 다음의 라운드별 좌측 쉬프트 테이블에 의해 왼쪽 방향으로 순환 쉬프트를 수행한다.
- 이 페이지에 나온 표를 보면 좌측 순환 쉬프트 수의 합이 28이 나오는 걸 볼 수 있다. - 김도엽
- 이 페이지에 나온 표를 보면 좌측 순환 쉬프트 수의 합이 28이 나오는 걸 볼 수 있다. - 김도엽
- 순열 선택 1을 거쳐 나온 출력 값 56비트의 키를 다음의 라운드별 좌측 쉬프트 테이블에 의해 왼쪽 방향으로 순환 쉬프트를 수행한다.
