2018년 11월 23일

Shor, Grove 알고리즘

I. 양자 알고리즘이 현대 암호에 미치는 영향

중첩, 얽힘, 불확정성 양자특성 기반 Shor와 Grove 알고리즘이 현대 암호학에 큰 영향

II. Shor 알고리즘

절차도	절차 설명
	① 인수분해 대상 N 보다 작은 m 선택하여, m, N 최대공약수 계산
	② m⁶ mod n 의 주기 P 계산
	③ p가 홀수이면 ①로 이동 짝수이면 ④로 이동
	④ (m^p/2– 1)(m^p/2+ 1) = m^p– 1 = 0 mod N m^p/2 + 1 = 0 mod N 시 ①로
	⑤ m^p/2 – 1와 N 최대공약수

두 번째 단계 ②가 양자 푸리에 변환 사용 단계로, 인수분해 문제가 고전 컴퓨터와 달리 해결 가능

III. Grove 알고리즘

구 성 도
절 차	① Hadamard gate(H) 이용 시스템 동일 중첩 상태 만듦
	② Quantum oracle이라 불리는 부분 통과해 찾고자 하는 원소에 맞게 시스템 변화
	③ diffusion transform 통해 위상이 평균보다 큰 경우 평균보다 낮게 변화, 평균보다 낮은 경우 크게 변화
	④ classical measurement로 결과 평가하여 O(1)의 확률로 옳은 값 출력

Grover 알고리즘은 정렬되지 않은 데이터베이스 원소를 찾는 양자 알고리즘, 고전 컴퓨터로 N개의 원소 중 하나 찾으려면 O(N) 검색 필요, Grover 알고리즘은 O(N^1/2) 검색으로 찾음

Tags:양자암호, Shor, Grove

About The Author

도리

4 Comments

준수
궁금한게 있습니다
양자 암호인 shor, Grover가 필요한가요?
양자암호통신을 할때 도청의 위험은 양자의 특성인 중첩과 복제불가능 인데
양자 알고리즘을 만들 필요한가요?
2019년 8월 28일 응답

도리
Shor, Grover 알고리즘은 양자 암호 알고리즘이 아니고 양자의 특성을 이용하여 공개키와 대칭키로 대표되는 현대 암호 시스템이 더이상 안전하지 않다는것(키가 유출되지 않더라도 해킹이 가능하다는 것을 의미)을 증명한 내용입니다. 따라서 현대 암호학에서 의미가 있는 알고리즘입니다.

두번째 질문하신 의도는 잘 모르겠습니다만 판단하건데, 양자암호통신으로 안전한 통신이 가능한데 굳이 양자 알고리즘을 만들 필요성에 대해 질문하신것으로 이해했습니다.

양자암호통신은 키 자체의 안전성과는 무관하며, BB84, COW4 등의 프로토콜을 이용하여 대칭키가 유출(도청)되지 않게끔 상대편에 전달하기 위한 기술입니다. 현대 암호학에서 사용하는 공개키나 대칭키를 사용하는 시스템의 경우, 앞서 말씀드린 Shor, Grover 알고리즘을 이용하여 키 유출(도청)이 되지 않더라도 해킹이 가능하므로 양자 컴퓨팅을 이용한 보안 위협에 대응하기 위해 양자내성암호(PQC) 기술이 필요합니다.
양자 암호 기술과 양자내성암호(PQC) 알고리즘을 참고해주세요.
2019년 8월 28일 응답

준수
양자 암호는 양자의 특성인 중첩, 얽힘, 불확정성을 기반으로 양자암호통신의 보안을 높이기 위해서 나온건데 이걸 기반으로 기존에 사용하던 보안 체계에 적용은 불가능한건가요? 오직 양자암호통신에서만 가능한가요?
2019년 8월 28일 응답

도리
양자의 특성을 이용하여 RSA(공개키 기반) 암호 기술 등 기존 보안 체계에 적용하여 메시지 자체의 안전성을 향상시킬 수 있습니다.
양자 암호 기술과 양자내성암호(PQC) 알고리즘을 참고해주세요.
2019년 8월 28일 응답

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^응답 취소