- 암호학 기초 : 다양한 암호화 기초 정리본2024년 10월 09일 17시 52분 37초에 업로드 된 글입니다.작성자: 방세연
모듈러 연산
A mod B = R
A를 B로 나누면 몫은 Q이고 나머지는 R이다. ( A= B * Q + R)
모듈러 합동
1 mod 5 6 mod 5 11 mod 5 16 mod 5 21 mod 5 다음의 나머지 R은 모두 1이기 때문에, 이들은 모듈러 입장에서 합동이다.
21과 1은 모듈 5에 대한 합동 관계다.
21 = 1(mod 5)
21 mod 5
헷갈릴 수 있으니까 주의..이때 모듈러 역원은,
이 값을 만족하는 b 값을 구하는거다.
이 말은 즉,
이걸 만족하는 값을 구하라는 것이다. 결국 이를 만족하는 b의 값은 3인거다.
왜 0이 아니라 x와 -2가 2에 대한 합동관계일까?
해당하는 답에 나머지 값을 더했을 때, (mod n)으로 나누어 떨어지는가?
나머지가 음수던 양수던, 부호를 바꿔서 해당하는 답에 넣고 (mod n)으로 나눠떨어지는지 확인한다.
여기에 나머지 0, 1, 2, 3, 4 로 나눠지는 각각의 조각을 읽어본다.
각각의 조각의 차를 구해보면, C (즉, 나누려는 수)의 배수라는 것을 알 수 있다.잉어류
: 나머지가 같은 숫자들의 집합
( 보통 bar을 붙여서 표시한다. )
완전 잉여계
Zn
Zn = { 0, 1, 2, 3, 4 ... n - 1 } 이 될 수밖에 없다.
즉, 소수 p는 특이한 기약 잉여계를 정의한다.
모든 숫자가 곱셈에 대해 역원을 가지는 매우 좋은 구조다. (유리수, 실수와 유사)
기약 잉여계
Z*n
Zn의 원소 중에서 곱셈에 대한 역원이 존재하는 수들의 집합
즉, Zn = {} 집합에서 n과 서로소인 숫자의 집합을 찾는다.
이들은 모두 같은 값이다.
( `|` 은, 나누기 또는 ()의 인수라는 뜻이다. )
예를들면 이런 문제가 있다고 치자.
이건 x가 11 (mod 8)에 대해 합동관계라는 뜻이다.
=> 그럼 x와 11은 8에 대해 합동관계다.
x mod 8 = 11 mod 8
이렇게 정의할 수 있다.
그리고 즉, 이들은 3이라는 나머지에 대한 합동관계일 것이다.
그러니 올바른 x의 값을 구할 때 3을 연산하고, 8로 나누어 떨어지는지 확인한다.
따라서 다음과 같은 모듈러 공식이 성립한다.
모듈러의 덧셈 성질
(A + B) mod C = (A mod C + B mod C) mod C
(A - B) mod C = (A mod C - B mod C) mod C
예를들면 A는 14, B는 17, C는 5라고 가정한다.
(31) mod 5도 (1) mod 5 이고,
(14 mod 5 + 17 mod 5) mod 5도 결국에는 ( 4 + 2 ) mod 5 => (1)mod 5이기 때문에,
둘은 온전히 같은 값이 된다.모듈러 곱셈 공식
(A * B) mod C = (A mod C * B mod C) mod C
모듈러에서의 거듭제곱
예를들어 이런 문제를 푸는 방법이다.
거듭제곱이 너무 큰 숫자라면, 위에서 증명했던 모듈러 공식을 활용해 다음을 금방 계산할 수 있다.
A² mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C
다음과 같은 성질이 성립한다.
다음과 같이 117=1110101로 이진수로 변환한다음, 각각의 숫자를 왼쪽으로 처리해가면 쉽게 값을 구할 수 있다.
이런 풀이가 나타난다.
모듈러 역원
A * B mod C = 1
즉, A * x ( mod C) = 1 (mod C)을 만족하는 x 값이 역원이 되는 것이다.
A (mod C)의 모듈러 역수를 구하는 단순한 방법은 다음과 같습니다.
1단계. 0에서 C-1까지의 B값에 대해 A * B mod C 를 계산합니다
2단계. A mod C의 모듈러 역수는 A * B mod C = 1을 만족하는 B값입니다
서로소 관계가 아닌 값 (어떤 인수를 공통으로 가지는 값)은 A * B mod C = 1 모듈러 역원을 만족하지 못한다.
유클리드 호제 알고리즘
: 두 정수의 최대공약수를 쉽게 알아내는 계산법
a가 1180이고, n이 482일 때.
GCD(1180, 482) : 1180와 482를 나누어떨어지게 하는 수 중 가장 큰 정수를 구해라.
- 최대공약수를 구해라.
원리에 의해서, 만약, gcd(a, n) = 1이 되면 역원이 존재한다고 할 수 있는 것이다.
(두 수가 서로 더이상 나눠떨어지지 않는다면, 그들의 최대 공약수는 1이다.)
gcd(5,7) 도 둘이 서로 나눠떨어지지를 않으니 1이다.
그러니까, GCD(1180, 482) = GCD(482, 216) = GCD(216, 50) = GCD(50, 16) = GCD(16, 2)가 되는 것이다.
이건 어떻게 도출되는걸까?
A가 B에 대해 나눠 떨어지고, 나머지가 등장하면 다음 GCD()의 끝부분이 된다.
이때 B는 GCD()의 첫 번째 부분이 된다.
해당 연산을 반복적으로 수행하다보면, 나머지가 0이 될 때가 나타나고, 앞 단계 결과를 반환하면 정답이 된다.
오일러 함수
Z*n의 원소의 수 = φ (n)
즉, n 이하의 자연수 중 n과 서로소인 자연수의 개수
(이때 소수 p는 Z*n 원소의 수와 전부 서로소이므로, φ (p) = p-1이 된다는 결론이 나온다.φ (n)을 계산하는 공식
정수 n>1이 소인수분해되어
이 되면,
해당 공식이 성립한다.
이걸 풀어서 설명하면, 먼저 pi는 다 전부 다른 소수이고 ki는 각자 소수들의 각각 다른 지수들이다.
만약 오일러 정리를 하고싶다면 정수 n을 소인수분해 해서 나온 값을 친절하게 적어주기만 하면 된다.
그 다음, 해당 값에서 (현재 지수 - 1)한 다음에 그 값을 기존 piki 값에 빼고, 이 과정을 각각의 소수에 반복해서 모두 곱하면
φ (n)의 값을 구할 수 있게 되는거다.
힐 암호화힐 암호화는 기본적으로 비즈네르의 다중치환 암호와 연계된다.
암호화와 복호화
비밀 키를 ' 행렬 '로 이용한다는 점에서 비즈네르 암호와 차이가 존재한다.
예를들면 "HI"라는 평문은 26개의 글자 중 7, 8번째에 해당하므로 P와 같이 표현할 수 있다.
암호화
K (비밀 키) * P (평문 행렬) mod (26) = C (암호문)
( J T ) 라는 평문이 ( t e )로 암호화되는 과정이다.
복호화
P (평문) = K-¹ (비밀 키의 역원) * C (암호문) mod (26)
암호화 키 행렬/ 암호화 키 행렬로 사용할 수 없는 경우
해당 행렬을 암호화로 사용하기 위해 다음과 같은 내용이 성립해야 한다.
det(K) 행렬식을 정의할 때, N mod 26에 대해 지켜져야하는 것:
- 행렬식이 0이 아니어야 한다.
- 행렬식과 mod의 최대공약수가 1이어야 한다. (즉, GCD()가 1이어야 한다.)
det(A)= ad− bc
중요한 것은, det(K)와 26의 GCD가 1이어야 한다는 것이다.
이전글이 없습니다.댓글