Logo
Published on

What is Modular Arithmetic

Authors

보안

보안을 위해 보통 세 가지 목표를 잡는다고 한다 이 세 가지 요소의 앞 글자를 따서 CIA라고 이야기하기도 합니다.

  1. 기밀성 (Confidentality) : 인가된 사람들만 정보를 조회 및 접근할 수 있습니다.

⤷ 기밀성을 위협하는 공격 : Snooping, 트래픽 분석 등 외부에서 비인가 데이터에 접근 혹은 탈취하는 공격들

  1. 무결성 (Integrity) : 정보들은 무단으로 상태가 변경되지 않도록 해야 합니다.

⤷ 위협하는 공격 : Spoofing 등 다른 사람으로 위장하여 정보를 조작하거나 탈취 후 다른 시점에 재사용하는 공격들

  1. 가용성 (Availability) : 인가된 사람들이 정보를 이용함에 문제가 없어야 합니다.

⤷ 위협하는 공격 : DoS(Denial of Service) 종류의 서비스를 느리게 하거나 완전히 차단할 수 있는 공격들

Modular Arithmetic(모듈러 연산)

모듈러 연산이란 정수와 정수를 나눗셈 연산을 하여 나온 나머지를 계산하는 연산이라고 볼 수 있습니다.

표기법

9를 2로 나누었을때 나머지

9 % 2

X = 9 mod 2

특성

  • a ≡ b mod n = b ≡ a mod n
  • a ≡ b mod n && b ≡ c mod n => a = c
  • (a + b) mod n = ((a mod n) + (b mod n)) mod n
  • (a - b) mod n = ((a mod n) - (b mod n)) mod n
  • (a * b) mod n = ((a mod n) * (b mod n)) mod n

Equivalence Classes

같은 수로 모듈러 계산을 할 때 나오는 값이 같으면 동치류라고도 하며 이 동치류 원소들은 해당 모듈러 연산 기준으로는 동일한 값으로 취급된다

예시

1 ≡ 3 mod 2

1 ≡ 5 mod 2

1 ≡ 19 mod 2

1 ≡ 231123 mod 2

위처럼 3, 5, 19, 231123은 mod 2 안에서는 같은 값으로 취급된다.

Identity & Inverse

Identity (항등원) : 어떤 수에 어떠한 연산을 했을 때 처음과 동일한 수가 나오는 수

  • 덧셈에 대한 항등원 : 0

    a + 0 = a x + 0 = x

  • 곱셈에 대한 항등원 : 1

    a * 1 = a x * 1 = x

Inverse (역원) : 어떤 수에 어떠한 연산을 했을 때 항등원이 나오는 수

  • 덧셈에 대한 역원

    a + -a = 0 x + -x = 0

  • 곱셈에 대한 역원

    a * a^-1 = 1 x * x^-1 = 1

Mondular 연산에서 항등원과 등원

  • 덧셈에 대한 항등원

    (a + 0) mod n = a mod n > (x + 0) mod n = x mod n

  • 곱셈에 대한 항등원

    (a * 1) mod n = a mod n > (x * 1) mod n = x mod n

  • 덧셈에 대한 역원

    (a + -a) mod n = 0 mod n > (x + -x) mod n = 0 mod n

  • 곱셈에 대한 역원 모듈러 연산은 정수를 사용하므로 a = x mod n 에서 a와 n의 최대공약수가 1인 경우에만 역원이 존재하고, 그렇지 않은 경우에는 역원이 존재하지 않는다.

    ( 1 * x ) mod 3 = 1 ⇨ x = 1

    ( 2 * x ) mod 3 = 1 ⇨ x = 2

    ( 3 * x ) mod 3 = 1 ⇨ x는 존재하지 않는다

Reference