[보안] 암호 관련 수학 간단 정리

✅ 기본

• 수의 범위가 좁을 경우 연산(+,-,*,/)들을 자유롭게하기 어려움
  • ex) 자연수는 덧셈을 자유롭게 가능 = 자연수는 덧셈에 대해서 닫혀있다
  • ex) 자연수는 뺄셈에 대해서 닫혀있지 않다 3-5=-2
  • ex) 자연수는 곱셈에 대해서 닫혀있다
  • ex) 자연수는 나눗셈에 대해서 닫혀있지 않다.
  • 자유롭다 : 자연수 + 자연수 = 연산결과가 다시 집합안으로 포함되는 것 = 닫혀있다.
• 역원
  • 덧셈의 역원 : 더해서 0 ex) +2, -2
  • 곱셈의 역원 : 곱해서 1 ex) 2, 1/2
  • +) 뺄셈을 수행하는 것: 덧셈의 역원을 구해서 덧셈을 수행하는 것 3 + (-2)=1
    • 정수에대해서는 덧셈에 대한 역원이 존재하기 때문에 덧셈뺼셈 수행 가능
  • +) 나눗셈을 수행하는 것 : 곱셈의 역원을 구해서 곱셈을 수행하는 것 7/4 = 7*1/7
    • 모든 원소들에 대해서 역원이 존재하면 곱셈이 가능하다. (0제외)
      → 자연수, 정수 불가 유리수 가능

🔐 암호학에서는?

• 유한하고 불연속인 수가 필요 + 자유로운 연산 → finite field
• 모듈러 연산(Modular arithmetic)

	의미	예(modulus = 7)
Modular reduction	modulus로 나눈 나머지만 취함	13 mod 7 = 6, -2 mod 7 = 5
Modular addition	addition + modular reduction	5 + 6 mod 7 = 4, 2 - 5 mod 7 = 2 + (-5) , 5 = 2 (mod 7) = 2+ 2 = 4
Modular multiplication	multiplication + modular reduction	5 × 6 mod 7 = 2, 2 / 5 mod 7 = 2* 3= 6

대수 구조

• set < group < Abelian group < Field
• • Abelian : 대수 구조에서 교환 법칙이 허용되면 앞에 Abelian 붙임
    • 그룹 조건에서 교환 법칙이 허용되면 Abelian 그룹
• set
  • 연산이 하나
• Group
  • 연산이 하나
  • Group 조건: 닫힘, 결합 법칙, 항등원 존재, 역원 존재
  • Abelian Group : Group 조건에 교환 법칙이 추가 된것
  • Additive group <𝑆,+> : + 역원 존재 ➔ +, − 가능
  • Multiplicative group <𝑆,×>: × 역원 존재 ➔ ×,÷ 가능
• Ring
  • 연산이 2개
  • 연산이 +에 대해서 힘, 결합 법칙, 항등원 존재, 역원, 교환 법칙 존재
  • 연산이 x에 대해서 닫혀있고, 교환 법칙만 존재
  • <𝑆, +,×> + 역원 존재, × 역원 존재 X ➔ +, −, × 가능
• Field
  • 두 연산에 대해 모두 Abelian Group + 분배 법칙
  • <𝑆, +,×>: +,× 역원 ➔ +, −,×,÷ 가능
  • 암호 단골 손님
  • 모든 원소의 10(=11-1)승: 항등원 → 9(=11-2)승한 값: 역원
    • a∈Zp 이면 a^(p-1) = 1
      ㄴ⇒ a * a^(p-2) = 1 , a와 a^(p-2)는 역원관계

Finite Field (유한체) = 갈로아 체(Galois Field)

• 말 그대로 유한 범위의 Field -> 갈로아 체
  • 무한이면 컴터서 못씀ㅋㅋ
• 유한 필드 범위를 늘리는 방법
  • 1. <𝑍𝑝, +, ×>에서 큰 p 사용
  • 2. field 확장(Extension field): GF(𝑝^𝑛)
    • 𝑎 ∈ 𝑍𝑝 = {0, 1, 2, … , 𝑝 − 1}인 집합 𝑎에 다른 수 섞기