[보안] 0316

목차

• 모듈러 연산
• 모듈러 연산의 정의
• 최소 잉여 집합과 모듈러 합동
• 잉여류와 모듈러 연산의 성질
• 모듈러 역원

모듈러 연산

모듈러 연산 : 나머지 연산의 두 결과 값 중 나머지 r (≥ 0)만 출력하는 연산

• 나눗셈은 관계식이다.
• 모듈러 연산에서는 나머지만 출력하므로 연산자다.

최소 잉여 집합(set of least residues modulo)

• 모듈러 n을 이용하는 모듈러 연산의 결과는 0 ~ n-1 사이의 값을 갖는다.
• 이 때, 정수 n에 대한 모듈러 연산 결과는 하나의 집합을 생성하는데, 이 집합을 "모듈러 n의 최소 잉여 집합 Z$_n$"이라고 한다.

Z$_n$ = { 0, 1, 2, ... , (n-1) }

모듈러 합동(Modular congruent)

• 모듈러 연산 "mod 10"을 2, 12, 22, 52에 대해 수행하면, 모두 같은 결과 값(r=2)을 가진다.
• 이 때, 2와 12, 22 그리고 22는 "mod 10"에 대하여 합동(congruence)이다.
• 합동 연산자 "≡"
  • a ≡ b (mod x) : 두 정수 a와 b는 "mod x"에 대하여 서로 합동이다.
  • 즉, a와 b는 x로 나누었을 때, 서로 같은 나머지를 갖는다.

잉여류 (Residue classes)

• 정의 : n으로 합동인 정수의 집합
• [a] 또는 [a]n으로 표기
  • [a]n은 n으로 나누었을 때, 나머지가 a가 되는 모든 정수들의 집합

Z$_n$에서의 연산

• 최소 잉여 집합 Z$_n$에 대해서 덧셈, 뺄셈, 곱셈 연산 수행 가능
• 임의의 두 정수 a, b ∈ Z or Z$_n$에 대한 덧셈, 뺄셈, 곱셈 연산
  
  • 입력 값 : a, b ∈ Z or Z$_n$
  • 출력 값 : c ∈ Z$_n$

최소 잉여 집합 Z$_n$에 대해서 '덧셈, 뺄셈, 곱셈 연산' 후 mod n 연산을 수행해주어야 한다!!

모듈러 연산의 성질

Property 1. (a + b) mod n = [(a mod n) + (b mod n)] mod n

Property 2. (a - b) mod n = [(a mod n) - (b mod n)] mod n

Property 3. (a * b) mod n = [(a mod m) * (b mod n)] mod n

Property 4. 10$^n$ mod x = (10 mod x)$^n$ mod x

최종 결과에 항상 mod n을 해주어야 함

상기 모듈러 연산의 성질을 왜 이해해야 하는가?
: 암호 알고리즘에 모듈러 연산 적용 시 a와 b의 값은 일반적으로 매우 큰 수 → 오버플로우 발생 위험!
: 따라서, 계산 시 발생하는 오버헤드를 완화할 수 있다.

모듈러 역원

덧셈에 대한 역원

• 모듈러 연산에서 각각의 정수는 덧셈에 대한 역원을 갖는다.
• "어떤 정수 a"와 "그 정수의 덧셈에 대한 역원 b"의 합은 "모듈러 n에 대하여 0과 합동"이다.
• 즉, Z$_n$에서 두 수 a와 b는 다음과 같이 서로 덧셈에 대한 역원이 된다.

a + b ≡ 0 mod n

• 따라서, Z$_n$에서 a의 덧셈에 대한 역원은 b = n - a

곱셈에 대한 역원

• 즉, Z$_n$에서 두 정수 a와 b가 아래의 성질을 만족하면 이들은 서로 곱셈에 대한 역원이 된다.

a × b ≡ 1 mod n

• 모듈러 연산에서 정수는 곱셈에 대한 역원이 있을 수도 있고, 없을 수도 있다.
• 만약 곱셈에 대한 역원이 있다면, 그 정수와 해당하는 곱셈에 대한 역원의 곱은 모듈러 n에서 1과 합동이다.
• a가 Z$_n$에서 곱셈에 대한 역원을 갖기 위한 필요충분조건

gcd(n, a) = 1

• 이 경우 n과 a는 서로소이다.

예제

• 예제 1. Z$_10$에서 8의 곱셈에 대한 역원을 계산하시오.
  • gcd(10, 8) = 2 ≠ 1 이므로 곱셈에 대한 역원 존재하지 않음.
  • 즉, 8을 곱하여 그 결과가 1과 합동이 되는 수를 0부터 9사이에서 찾을 수 없다.
• 예제 2. Z$_10$에서 곱셈에 대한 모든 역원을 계산하시오.
  • Z$_10$에서 세 쌍의 역원 (1,1), (3,7), (9,9)가 존재한다.
    • (1 * 1) mod 10 = 1
    • (3 * 7) mod 10 = 1
    • (9 * 9) mod 10 = 1

 

곱셈에 대한 역원과 확장 유클리드 알고리즘

• 확장 유클리드 알고리즘에서 n과 b가 주어지고 역원이 존재할 때, Z$_n$에서 b의 곱셈에 대한 역원을 구할 수 있다.

① 첫 번째 정수 b를 모듈러 n으로 대체한다.

② 확장 유클리드 알고리즘을 이용하여 sn + bt = gcd(n, b)를 만족하는 s와 t 값을 구한다.

③ b의 곱셈에 대한 역원이 존재한다면 gcd(n, b) = 1이어야 한다. 따라서, (sn + bt) = 1을 만족해야 한다.

④ 양변에 대한 모듈러 연산을 적용한다. 즉, 좌변과 우변을 Z$_n$에 대응시키면 다음과 같다.

(sn + bt) mod n = 1 mod n

[ ( s × n ) mod n ] + [ (b × t) mod n ] = 1 mod n

0 + [ ( b × t ) mod n ] = 1 mod n

( b × t ) mod n = 1

이는 Z$_n$에서 t가 b의 곱셈에 대한 역원임을 의미한다.

즉, b의 곱셈에 대한 역원은 t를 Z$_n$에 대응시킨 값이다.

예제 1 : Z$_26$에서 11의 곱셈에 대한 역원을 구하시오.

• gcd(26, 11) = 1 이다. 이는 11의 곱셈에 대한 역원이 존재함을 의미한다.
• 확장 유클리드 알고리즘을 이용하여 t = -7을 얻는다.
• 곱셈에 대한 역원은 (-7) mod 26 = 19이다. 즉, 11과 19는 Z$_26$에서 곱셈에 대한 역원이다.
• 따라서 (11 × 19) mod 26 = 209 mod 26 = 1이다.