[양자 컴퓨팅과 보안] 수학적 배경 지식

수학적 배경지식

RSA 암호 알고리즘

• 공개키 알고리즘
• 암호화 : 공개키 / 복호화 : 개인키
• 소인수분해 기반
  • 소인수분해를 통해 공개 키를 알아내는게 어렵다
  • 모두에게 공개되어있다
  • a^2 - b^2이 N의 배수가 되는 정수 a, b를 찾으면 풀림
• 쇼어 알고리즘이 개발되면 쉽게 풀리게 됨

최대공약수 GCD (Greatest Common Divisor)

• GCD(a, b) = n
• 만약 a와 b 중 하나라도 0이면, 0이 아닌 다른 수가 n
• 유클리디언 알고리즘 : GCD(a, b) = GCD(b, a%b)
  • GCD(72,30) = GCD(30,12) = GCD(12,6) = GCD(6,0) = 6
  • 72%30 = 12 / 30%12 = 6

모드 연산

• 나눗셈을 해서 나머지를 구하는 연산
• ex) 27 mod 12 = 3
  • 27을 12로 나눈 나머지 = 3
  • mod 12에서는 0부터 11(mod-1)까지의 수 존재
• 모드 덧셈
  • (7 mod 12) + (6 mod 12) = (7 + 6) mod 12 = 13 mod 12 = 1
  • 같은 모드 상에서 연산 가능
  • 7+6 = 13인데, 13이라는 수는 mod12 상에서는 존재하지 않음
  • 결과는 13%12인 1
• 모드 뺄셈
  • (3 mod 12) - (7 mod 12) = (3 - 7) mod 12 = -4 mod 12
  • -4는 mod 12상에서 존재하지 않음 (0~11까지 존재)
  • 12 - 4를 진행
  • 결과는 8 mod 12
• 모드 곱셈
  • 곱셉 = 덧셈의 반복
  • (7 mod 12) * 4 = (7 * 4) mod 12 = 28 mod 12 = 4
• 모드 나눗셈
  • 일반적 나눗셈 X (mod 상에서 분수 존재 X)
  • 곱셈의 역원 계산 가능
• 곱셈의 역원
  • 곱했을 때 1이 되는 수
  • 하나하나 대입 후 계산 필요 (노가다)
  • ex) 49 % 12 = 1
  • 모든 수가 곱셈의 역원을 갖지는 않음
  • 서로소인 수가 가질 수 있다
    • 서로소 : 최대공약수가 1인 두 수 (ex. mod 12에서는 1, 5, 6, 11)
• 모드 거듭제곱
  • 계산 도중 mod를 취해도 결과가 같다!
  • $7^4 mod 12 = (7 * 7 mod 12) * (7 7 mod 12) = (49 mod 12) (49 mod 12) = 1*1 mod 12 = 1$
    • $7^2 mod 12 = 1$
    • 49 % 12 = 1

페르마 소정리

• p가 소수 (prime)이고 a와 p가 서로소이면 모두 만족

주기

• 쇼어의 알고리즘 : $f(x) = a^x mod N$
• 위 식에서 a와 N이 서로소일 때 값은 1 (gcd(a, N) = 1)
• $a^r mod N$ 에서 1을 만족하는 r 중 가장 작은 값을 “주기” 라고 한다
• 주기는 0이 될 수 없다
• a = 7 , N = 15 (→ a, N이 서로소일 때 주기는 4)

 

소인수분해 문제

• 1단계가 주기 찾기
• p * q = N
  • p와 q를 알면 N을 쉽게 구한다
  • N만 아는 상태에서는 p와 q를 구하기 어렵다 (256bit)
  • ⇒ 일방향 함수

이산 대수 문제

• 모드 상에서 제곱근을 구하는 문제
  • $7^x mod 13 = 8 -> x = ?$
• 모드 상이 아니면 제곱근 구하기 쉬움
• $7^x mod 13 = 8$
  • x를 알면 구하기 쉽다
  • 모를때는 어렵다
  • ⇒ 일방향 함수
• 모드로 사용되는 숫자가 매우 크면 매우 어렵고 시간이 많이 걸림
• 이산 대수를 구하는 고속 알고리즘이 없음

주기를 찾는 문제

• 주기 찾기가 되면 소인수분해가 된다
• $f(x) = a^x mod N$ 이면⁍$a^x+r = a^x mod N$
• 과정
  • 랜덤한 정수 a 선택
  • 유클리디언 알고리즘을 통해 gcd(a, N) 계산
  • 결과가 서로소이면 “주기 찾기 기계” 돌림 (가상의 기계)
  • 주기 r이 짝수가 나올 때까지 반복
  ⇒ “주기 찾기 기계” 만 현재의 컴퓨터로 불가능 → 양자 컴퓨터 “쇼어의 알고리즘”을 통해 개발해내고자 함
• (Fast) Fourier Transform (FFT) : 기존 컴퓨터에서 그나마 빠르게 주기 찾는 법