양자 암호 - 쇼어 (Shor) 알고리즘, 그로버(Grover) 알고리즘

[개념] 

양자내성암호는 이런 양자 컴퓨팅 환경에서도 안전한 공개키 암호 시스템을 의미

 

[유형]

양자내성암호에는 암·복호화 알고리즘, 키 캡슐화 방식, 전자서명 세 가지가 있으며, 격자, 다변수, 코드, 해시 등 다양한 난제에 기반하고 있다.

 

[배경]

양자 컴퓨터는 기존 고전 컴퓨터보다 빠른 계산 속도를 제공하여 양자 컴퓨팅 환경에서 는 양자 기반 알고리즘인 쇼어(Shor) 알고리즘과 그로버(Grover) 알고리즘이 현대에서 많이 사용되는 공개키 암호 시스템에 큰 변화를 가져오게 된다. 그로버(Grover) 알고리즘 은 정렬되지 않은 데이터베이스의 원소를 검색하는 속도를 향상시켜 대칭키 암호와 해시 함수에 영향을 준다. 쇼어(Shor) 알고리즘은 인수분해 문제 해결 시간을 감소시켜 RSA 암·복호화, RSA 서명, 디피-헬만(Diffie-Hellman) 키 교환 등 여러 공개키 암호 알고리즘 을 사용할 수 없게 만든다.

 

 

• 쇼어 알고리즘 (Shor's Algorithm):
  • 목적: 큰 수의 소인수분해를 빠르게 수행하는 것입니다. 전통적인 컴퓨터에서는 이 작업이 매우 어렵고 시간이 많이 걸리는 반면, 쇼어 알고리즘은 양자 컴퓨터를 사용하여 이 문제를 훨씬 더 효율적으로 해결할 수 있습니다.
  • 중요성: 이 알고리즘은 현재 많은 암호 시스템의 안전성이 큰 수의 소인수분해의 어려움에 기반하고 있다는 점에서 매우 중요합니다. 예를 들어, RSA 암호화는 소인수분해가 어려운 것에 의존하고 있기 때문에, 쇼어 알고리즘은 이론적으로 RSA와 같은 암호 시스템을 깰 수 있는 가능성을 가지고 있습니다.
  • 작동 원리: 쇼어 알고리즘은 양자 푸리에 변환을 이용해 주기를 찾아내며, 이를 통해 소인수분해할 수 있는 핵심 정보를 얻습니다.
  • 장점
    1. 암호 해독 능력: 현재 널리 사용되는 공개 키 암호 시스템(예: RSA)의 보안이 소인수분해의 어려움에 기반하고 있기 때문에, 쇼어 알고리즘은 이론적으로 이러한 암호를 해독할 수 있습니다.
    2. 양자 우위 증명: 이 알고리즘은 양자 컴퓨터가 특정 작업에서 전통적인 컴퓨터보다 월등한 성능을 낼 수 있음을 보여줍니다.
  • 단점
    1. 실용성: 현재 사용 가능한 양자 컴퓨터는 아직 쇼어 알고리즘을 큰 수에 대해 실행하기에 충분히 강력하지 않습니다.
    2. 암호 위협: 이 알고리즘은 현재 암호 시스템에 심각한 위협이 될 수 있어, 양자 내성 암호로의 전환 필요성을 촉진시킵니다.
• 그로버 알고리즘 (Grover's Algorithm):
  • 목적: 비정렬 데이터베이스에서 특정 항목을 찾는 데 사용됩니다. 전통적인 컴퓨터에서는 이 작업이 데이터베이스의 크기에 비례하는 시간이 걸리지만, 그로버 알고리즘은 루트 N의 시간 복잡도를 가지며, 이는 상당한 속도 향상을 의미합니다.
  • 중요성: 이 알고리즘은 대규모 데이터베이스 검색, 이미지 인식, 머신 러닝 문제 등 다양한 분야에서의 응용 가능성을 제시합니다.
  • 작동 원리: 그로버 알고리즘은 양자 상태의 중첩과 간섭을 이용하여, 원하는 항목을 효율적으로 찾아냅니다. 이는 양자 비트가 동시에 여러 상태를 표현할 수 있는 양자 컴퓨터의 특성을 활용하는 것입니다.
  • 장점
    1. 검색 효율성: 데이터베이스 크기에 비례하는 시간 대신, 루트 N의 시간 복잡도로 검색할 수 있습니다. 이는 큰 데이터베이스에서 상당한 속도 향상을 의미합니다.
    2. 다양한 응용: 이미지 처리, 기계 학습, 패턴 인식 등 다양한 분야에서 활용될 수 있습니다.
    단점
    1. 제한된 속도 향상: 속도 향상이 폴리노미얼(다항식) 수준으로, 쇼어 알고리즘처럼 지수적인 향상은 아닙니다.
    2. 특정 문제에 한정: 그로버 알고리즘은 검색 문제에 특화되어 있어, 이 외의 문제에는 직접 적용하기 어렵습니다.

 

 

 

쇼어 알고리즘은 암호학에 중대한 영향을 미칠 잠재력을 가지고 있으며, 그로버 알고리즘은 검색과 데이터 처리 분야에서 중요한 역할을 할 수 있습니다.

 

쇼어(Shor) 알고리즘

 

- 양자 푸리에 변환 기반

- 인수분해

- Factorial 함수보다 지수적 빠름

-  항식 시간 (polynomial time) 에서 이산 대수 문제와 정수 분해 문제

 

이 가능하다.

 

113회 정보관리 기술사 기출풀이

 

그로버 (Grover) 알고리즘

 

- 진폭 증폭 기반

- 구조화되지 않은 데이터베이스 또는 정렬되지 않은 목록을 검색

- 동일한 작업에 대해 2배 빠름

 

113회 정보관리 기술사 기출풀이

 

113회 정보관리 기술사 기출풀이

 

출처: TTA,  http://www.tta.or.kr/data/ttas_view.jsp?rn=1&pk_num=TTAK.KO-12.0349-Part1