2021년 1월 21일 목요일

Vaishali Bhatia et al, "An Efficient Quantum Computing technique for cracking RSA using Shor’s Algorithm" 번역

작성중인 글입니다.

이 글은 2020년 IEEE ICCCA 에서 공개된 Vaishali Bhatia 씨 등의 "An Efficient Quantum Computing technique for cracking RSA using Shor’s Algorithm" 논문[1]을 번역한 글입니다. 번역기를 사용하지 않으므로, 제 이해와 필요에 따라 원문과 차이가 날 수 있습니다. 논문에 포함된 표와 그림은 재도식하거나 생략합니다. 

ABSTRACT

양자 컴퓨팅은 계산을 빠르게 수행할 수 있는 유망한 단어이다. 양자 컴퓨팅을 사용하는 동기는 전통적인 컴퓨터로는 어려웠던 많은 문제들을 빠르게 해결할 수 있다는 것이다. 전통적인 방법은 0과 1로 구성된 비트를 사용하는 반면 양자 컴퓨팅은 큐비트로 동작한다. 전통적인 컴퓨터는 계산이 병렬적으로 수행되더라도 저장 공간과 계산에서 중요한 문제를 갖는다. 양자 병렬성의 개념은 전통적인 컴퓨터와 비교하여 기하급수적으로 짧은(low time) 시간에 계산이 수행될 수 있도록 한다. 이 논문은 양자 컴퓨팅 알고리즘과, 어떻게 쇼어 알고리즘이 RSA 알고리즘을 깨뜨릴 수 있는 지에 대해 논한다. 큐비트의 얽힘과 중첩은 빠른 계산을 돕는다. 적용 가능성의 시현은 계산 시간, 저장 공간, 정확도, 기밀성, 효율성, 무결성과 가용성을 기반으로 평가되었다. 다양한 알고리즘 중 쇼어의 기법은 전통적인 계산 방식보다 더 우월하게 다양한 암호 알고리즘을 깨뜨릴 수 있다. 간단히 말해서, 논문은 다양한 양자 알고리즘에 대해 논의하고, 어떻게 쇼어 알고리즘이 RSA을 깨뜨릴 수 있는 지를 설명한다.

Ⅰ. INTRODUCTION

양자 컴퓨팅은 1980년대에 시작되었으며, 얽힘과 중첩 같은 기법과 함께 양자 역학 현상을 기반으로 한다. 컴퓨터를 사용하여 수행하는 계산을 양자 컴퓨터로 수행한 것은 1994년에 존재한 것으로 알려져 있다. 양자 컴퓨팅에 의해 해결된 첫 번째 문제는 16큐비트를 사용하여 해결된 스도쿠 게임이었다. 전통적인 컴퓨터 시스템에서는 0과 1의 두 가지 가능한 상태가 있지만, 양자 컴퓨팅은 각 비트가 두 가지 가능한 상태로 구성된 큐비트로 이루어진다. 2018년에 가능한 가장 큰 양자 컴퓨터는 72큐비트로 구성된다.

양자 컴퓨팅의 발전을 이끄는 아이디어는 사용자가 가용한 많은 양의 데이터를 처리할 때 계산 속도를 높이기 위한 병렬화 작업이 많은 수의 코어에서도 계산 시간이 길다는 점이다.  양자 컴퓨팅의 얽힘, 간섭, 중첩의 원리를 사용하면 대량의 데이터를 병렬로 처리하고 실행할 수 있다. 이 장점은 동적인 문제를 처리하는 데 도움이 될 뿐만 아니라 어렵고 복잡한 문제의 해결책을 매우 빠른 시간 안에 제공한다.

양자 역학에 깊이 들어가는 동안에 명확히 해야하는 기본 용어들이 있다. 원자나 입자가 자기장에 들어갈 때마다 위쪽 또는 아래쪽으로 편향되는 것을 스핀이라고 한다. 그림 1은 상하 운동으로 구성된 양자 컴퓨터의 스핀 운동을 보이는 반면, 전통적인 컴퓨터의 경우에는 상하좌우로 구성된다. 그러면 전통적적인 컴퓨터가 더 경우의 수가 많은 건가....

그림1. 양자 컴퓨터의 스핀 운동

중첩의 원리는 두 상태가 결합된 때 역시 유효한 상태가 된다는 것을 기반으로 한다. 이 입자는 00, 01, 10과 11과 같은 상태로 구성된 큐비트로 표시된다. 여기에서 0은 업스핀을, 1은 다운스핀을 나타낸다. 여기에서 |10> 의 표현은 하나는 다운스핀, 하나는 업스핀을 표현한다. 

그림2. 전통적인 컴퓨터의 스핀 운동

그림2는 전통적인 컴퓨터의 스핀 운동을 나타낸다. 가장 좋은 결과를 얻기 위해 진폭의 모든 가능성을 시도한다는 점에서 전통적인 컴퓨팅과 다르다. 

φ[2] = α|0> + β|1>

위 식에서 φ 는 양자 상태를 나타내고, α|0> + β|1> 는 중첩 상태를 나타낸다. |01> 의 행렬 곱셈은 0이고, |11> 은 1이다. 비슷하게, 아래의 식과 같이 다른 중첩 결과를 표현한다.

|+> = |0> + |1> / 2

|-> = |0> - |1> / 2

양자 컴퓨팅 분야의 다음 관련 용어는 양자 게이트이다. 전통적인 컴퓨터가 연산에서 AND, OR, NOR과 같은 논리 게이트를 사용하는 것과 유사하게 양자 컴퓨터는 연산을 수행하기 위해 파울리(Pauli)-X, 파울리-Y, 파울리-Z, 하다마드 게이트 등을 사용한다. 다음 연산은 0과 1의 중첩에 적용될 수 있는 하다마드 행렬을 나타낸다. 



파장의 간섭은 원하는 결과를 얻기 위한 규비트 중첩의 부차적인 결과에 의해 수행된다. 

얽힘은 둘 이상의 상태의 상관관계 또는 다른 상태에 대한 참조로 알려진 과정이다. 전통적인 컴퓨터의 경우 입자 간의 상관관계를 찾기가 매우 어렵기 때문에 가장 유망하게(prominent) 여겨진다.

그림3은 1970년대에 시작된 양자 컴퓨팅의 발전을 도식하며 현재까지 상업적 붐으로 확장되었다.

그림3. 양자 컴퓨팅 분야의 발전

이 논문은 단원 1에서 양자 컴퓨팅 소개와 위에서 논의된 다양한 용어에 대한 세부 정보가 포함되고, 단원 2는 양자 컴퓨팅의 다양한 알고리즘으로 구성되며, 단원 3은 이 분야의 다양한 연구자들이 수행한 작업을 보여주는 문헌 조사를 다루고, 단원 4는 쇼어 알고리즘이 RSA 알고리즘을 해독할 수 있는 방법을 보여주는 제안된 작업으로 구성되며, 단원 5는 결과 및 토론으로 구성되는 다양한 단원으로 나뉜다.

Ⅱ. QUANTUM ALGORITHMS

이 단원에서는 다양한 양자 알고리즘과 그 중요성에 대해 설명한다.

A. 도이치-조사 알고리즘(Deutsch-Jozsa algorithm)

이 알고리즘은 고전 컴퓨터와 경쟁하기 위해 1992년에 개발된 최초의 알고리즘이다. 입력을 0 또는 1로 취하고, 출력을 0 또는 1로 제공한다. 

f : {0, 1} → {0, 1}


이 알고리즘은 출력으로 동일한 수의 0과 1을 가지고 있으면 균형을 이룬다고 한다. N 자리 이진수를 입력으로 취하며, 결과를 0 또는 1로 제공한다. 최악의 경우 2n-1 + 1 의 시간 복잡도를 가진 전통적인 컴퓨팅에 비해 기하급수적으로 낮은 복잡도로 어려운 문제를 해결할 수 있었다. 입력에 하다마드 연산을 적용하고, 오라클 함수를 적용하기 위한 모든 구성을 준비한 다음 매핑과 함께 그룹화를 적용하여 결과를 0 또는 1로 제공하는 원리를 기반으로 동작한다. 오라클 함수는 f(x) = 0 인 경우 I-게이트를 적용하고, f(x) = 1 인 경우 X-게이트를 적용한다. 그림3은 입력 n = 3 비트 값에 대해 Qiskit 을 사용하여 구현한 도이치-조사 알고리즘의 구현을 보여준다. Qiskit 이 아니고 IBM 양자 컴포저입니다만...

그림4. 도이치-조사 알고리즘의 구현[3]

B. 그로버 알고리즘(Grover's algorithm)

그로버 알고리즘은 1996년에 개발되었으며, 기존의 O(N)과 비교하여 O(√N)의 복잡도(complexity)를 가지는 병렬성의 원리를 기반으로 동작한다. 기본적으로 데이터베이스 검색에 사용되고, 비구조적 데이터에도 주로 동작한다. 예를 들어, 우리가 n 개의 아이템을 가지고 있고, 어떤 아이템을 찾아야 할 때 이 알고리즘이 사용될 수 있다.

f(x) : {0 for u = x and 1 for u != x}

그림 5는 입력 n = 4비트 인 그로버 알고리즘의 구현을 보여준다.

그림5. 그로버 알고리즘의 구현[4]

C. 사이먼 알고리즘(Simon's algorithm)

이 알고리즘은 1997년에 소개되었으며, 이 경우 양자 이산 푸리에 변환(Quantum discrete fourier transformation)으로 알려져 있는 이산 푸리에 변환을 기반으로 한다. 하나의 입력이 하나의 출력 또는 두개의 입력이 하나의 출력으로 구성되는 일대일 또는 이대일 매핑 방법에서 동작한다. 그림 6은 사이먼 알고리즘의 구현을 보여준다.

그림6. 사이먼 알고리즘의 구현[5]

D. 쇼어 알고리즘(Shor's algorithm)

쇼어 알고리즘은 1994년 피터 쇼어에 의해 개발되었으며, 양자 컴퓨터를 사용하여 다항 시간에 알고리즘의 소인수를 찾는 작업이다. 우리가 쇼어 알고리즘을 통해 소인수를 찾으려고 할 때 쇼어 알고리즘은 쇼어의 소인수 분해 알고리즘으로도 알려진다. 큰 수들의 소인수들은 매우 계산하기 어렵다는 개념을 기초로 하며, 객체의 주기성을 측정하는 기법을 사용한다.

큰 수의 소인수를 찾는 문제는 전통적인 컴퓨터에게 어려운 문제로 여겨진다. p 와 q 가 큰 수이고, N = p * q 인 N이 알려진 경우에 p 와 q 를 찾는 작업을 가정한다. Brute force 방법으로 찾을 수 있겠지만, 얼마나 많은 시간이 걸릴지는 알 수 없다. 전통적인 컴퓨터에서는 Brute force 방법보다 더 나은 다른 알고리즘이 없다. 쇼어 알고리즘은 소인수 분해 기법으로 주기 함수(periodic function)의 주기(period)를 찾는 작업을 목적으로 한다. 

쇼어 알고리즘에 사용되는 연산자는 양자 푸리에 변환이다. 이는 소인수 분해 알고리즘과 함께 잘 동작하고, 현재까지 21큐비트의 소인수를 찾을 수 있다. 구현을 위한 단계로 우선 레지스터들이 텐서 곱을 통해 Q 상태의 중첩으로 초기화된다. 이 상태를 사용하여 양자 함수 f(x)가 입력 레지스터들에 생성되어 역 양자 푸리에 변환(Inverse Quantum Fourier Transformation)이 적용된다. 그 다음 다른 축소 불가능한 작업이 수행된다. 이 작업들은 소인수 분해 문제를 축소하는 작업을 주로 수행한다.

[2] '프시' 또는 '프사이' 라고 읽는다.
[3] 논문의 그림과 IBM의 그림이 상이하여 IBM의 그림을 참고하여 도식하였다. 자세한 설명은 다음 링크 참고. 
https://quantum-computing.ibm.com/docs/iqx/guide/deutsch-jozsa-algorithm
[4] 그림 출처는 역시 논문이 아닌 IBM의 다음 링크.


2021년 1월 14일 목요일

A New Approach to Protect Your Smartphone from Evil Twin Access Points

이 글은 제가 석사과정 끝날 즈음 MobiCom 2014 에 투고했다가 떨어진 논문을 옮긴 글입니다. 여러모로 후속 연구는 없을 듯 하여 블로그에 공개합니다.


ABSTRACT

How can you trust a stranger? This study starts with this question. Your smartphone has various and important information about you. So, how can you assure that a Wi-Fi you've never connected is secure to use free internet access? The more prevalent smartphone becomes, the more important Wi-Fi security is. Evil twin access point tries to capture your information without your permission. This study is about an approach for smartphones to detect evil twin access point without any help. In this study, we analyze evil twin access point attack and survey related works. Finally, we propose relay sniffing based evil twin access point detection scheme. This scheme does not rely on any third party authentication, traffic characteristics, dual networks, statistics, and training. But, it takes traditional wireless network vulnerability which every packet is open to public and uses it as a clue for evil twin access point detection. Experimentally, our proposed scheme makes smartphones able to detect evil twin access point 99.9% and warn the user.


1. INTRODUCTION

How can you trust a stranger? If you don't have any information about someone you have met before, you cannot just be relaxed. But, at that time, if the stranger offers you a favor, what will you do? It's apparent that you can benefit from him when you trust that one. Nonetheless, you cannot assure whether the benefit is a pure favor or can be harmful to you. In this question, Most people may answer that it needs a reliable third party certificate to trust the stranger somehow. Showing public identification which contains reliable authentication can be an example. But, if not, would you believe that the stranger's favor is true?

Let's change the case of preamble question to your smartphone. How can you trust an access point (AP) you've never connected before? It's favorable for you to use Wi-Fi to access the internet instead of cell networks like 3G, LTE, LTE-A to avoid data rate. But, you cannot assure that the AP which supports your Wi-Fi connection is safe. If the AP you connected is evil twin AP, every data you transmitted and received through Wi-Fi can be captured by the attacker. If so, your personal information like credit card number, Facebook and e-mail password can be accessed by the attacker without your permission.

These days, smartphones have become very essential to our daily lives [1]. People can access the internet everywhere. We can also communicate, shop, study, do business using smartphones. Smartphones offer the internet connection based on cell or Wi-Fi networks. But, unlike cell networks which charge a data rate, Wi-Fi usually offers free internet access to authenticated users. Thanks to Wi-Fi's flexible extendibility, nowadays many public places like airport, university, hotel, and coffee shop offer a free internet access to smartphone users.

Current smartphone has various and important personal information about the user [1]. So, the more prevalent smartphone becomes, the more important Wi-Fi security is [2]. But, because smartphone users move and try to connect to various APs, unlike cell networks which can support a central uniform filtering system, it could not assure that it has a third party authentication system like remote authentication dial-in user service (RADIUS) server. Unfortunately, the information about new AP is limited to the user who wants to use first seen Wi-Fi securely.

This study is about an approach for a smartphone to detect evil twin AP which tries to sniff communication through Wi-Fi without any help. The rest of this paper consists of 5 chapters. Chapter 2 introduces backgrounds of evil twin AP attack. Chapter 3 surveys related works about evil twin AP detection schemes. In Chapter 4, we propose a new evil twin AP detection scheme. Our proposed scheme is evaluated in chapter 5. Finally, we give you the conclusion of this study and our answer to the preamble question in chapter 6.


2. BACKGROUNDS

2.1. Paradigm Shift of AP Attacks

AP attacks before the advent of smartphones were mainly rogue AP. Figure 1 shows rogue AP attack. Like backdoor, it emasculates security system using unauthorized AP installed by authorized person. At this time, because the information which should be protected is stored in servers mainly, unauthorized access to the server using rogue AP causes serious risks. So, this rouge AP attack can be categorized as insider attack. Also, it is regarded as social engineering issue.

Figure 1. Traditional AP attacks

On the other hand, paradigm of AP attacks was shifted after the advent of smartphone. Because the information which should be protected is stored in not only servers but also smartphones, the main target of AP attack is changed from servers to smartphones.

Figure 2. Evil twin AP attacks against a smartphone

The victim is not fixed anymore but it can move. Then, attacker should move too. So, this evil twin AP can be categorized as outsider attacks [4]. Picture 2 shows evil twin AP attack. In light of unauthorized AP's illegal action, evil twin AP attack can be seen as rogue AP. An important point is not the name of the attack, but Paradigm shift of AP attacks

2.2. Threat of Evil Twin AP to Smartphones

Aforementioned evil twin AP attack can spoof smartphone users easily. When a smartphone scans available AP and the user selects it, the AP which has strong signal strength is selected firstly [5]. The stronger signal strength is, the more stable the smartphone users can use the high speed internet access. Evil twin AP tries to be located closer to smartphone users and provides stronger signal than a legitimate AP to attract them. So, even though evil twin AP attack is an outsider attack, it’s not an indiscriminate attack but a targeting attack which selects a victim.

Service set identifier (SSID) is exposed to smartphone users like AP's name. If evil twin AP uses reliable SSID to the users, spoofing them is much easier [5]. For example, if evil twin AP uses 'Starbucks' in Starbucks coffee shop, they might not doubt evil twin AP.

Evil twin AP offers the internet access to the users too. If not, smartphone users do not connect evil twin AP. Therefore, it is difficult for a smartphone user to recognize that the AP they connected is evil twin AP and they have become the target. The attacker can capture and store packets while the victim accesses Wi-Fi without their permission. If packet is encrypted, it may be more secured. But, the packet stored once may be the target of offline brute force attack to be decrypted.


3. RELATED WORKS

3.1. Traffic Analysis Based Detection

Traditional rogue AP detection scheme is MAC address filtering applied by Cisco [3]. But, MAC address can be spoofed by attacker [2]. Also, detouring MAC address filtering scheme is already published [7]. On the other approach, filtering a packet which comes from wireless network through rogue AP and arrives in wired network was studied [3-4]. On the other hand, several network traffic analysis based schemes were published [8][13-14]. But, these schemes present somewhat false-positive ratio while rogue AP detection in real networks environment which has a lot of factors to affect the result [4]. Therefore, it cannot be assured that analyzing several packets or traffic characteristics can give a perfect clue for evil twin AP detection.

3.2. AP Nature Analysis Based Detection 

Suman Jana et al proposed clock skew based rogue AP detection scheme [6]. Clock skew is an AP's nature which every AP can be identified even they are same model and has same brand. They registered all the AP's nature and judged each AP in Wi-Fi network whether registered or not. If an AP which has unregistered clock skew nature, it is regarded as rogue AP. This kind of scheme needs training cost. In other words, every legitimate AP should be registered first before being regarded as rogue AP. But, real Wi-Fi network environment can be changed frequently. For example, current smartphone itself can be an AP and a supplicant.

3.3. User Side Detection

Somayeh et al proposed hop count based user side rogue AP detection scheme [5]. They suggested that sent packet has extra hop, there is evil twin AP due to Man-in-themiddle attack. Their scheme can be seen well but there are two drawbacks. Firstly, they should know previous hop count to know a hop count increment. That means the scheme needs training cost. If so, smartphone users should pay the cost every time when they go to unfamiliar places and try to access the internet through Wi-Fi you've never connected. Secondly, even in wired network, packet routing can be changed frequently to find optimal path. Needless to say, wireless network's routing can vary. That is, the hop count which the smartphone knows due to right before training can be meaningless. Consequently, hop count based evil twin AP detection is limited in real Wi-Fi network. Jaemin Lee et al proposed dual networks based user side evil twin AP detection scheme [9]. This scheme uses 3G and Wi-Fi networks. Their scheme compares undamaged certificate sent through 3G and certificate sent through WiFi to detect evil twin AP. But there are two drawbacks in their scheme. Firstly, their scheme relies on network infrastructure. If smartphone users cannot access dual networks simultaneously, their scheme cannot be implemented. Secondly, their scheme needs web server which receives packets smartphone users sent. That is, it is not pure and independent user side evil twin AP detection because it relies on the server. Chao Yang et al proposed statistical technique based user side evil twin AP detection scheme [10]. This scheme does not rely on training but it cannot eliminate whole false positive ratio.


4. PROPOSED SCHEME

In this study, we propose relay sniffing based evil twin access point detection scheme. This scheme does not rely on any third party authentication, traffic characteristics, statistics, dual networks, and training. Wireless networks are well known that it is more vulnerable than wired networks because it uses radio frequency as its medium and transmits data to every device in transmission range. But, our proposed scheme takes traditional wireless network vulnerability which every packet is open to public and uses it as a clue for evil twin AP detection. If a smartphone can sniff the packet which relayed by evil twin AP, it can detect existing evil twin AP without any help. In this scheme, the only thing the smartphone needs to detect evil twin AP is just one packet. To understand it better, let's compare the environments between existing evil twin AP and not under our proposed scheme. 

Figure 3. Proposed scheme testing legitimate AP

Figure 3 shows proposed scheme in normal Wi-Fi access. First of all, a smartphone starts monitoring its Wi-Fi network environment and sends test packet. Then, the smartphone can sniff all the packets including its test packet. If the AP in which the smartphone is connected is not evil twin AP, the smartphone can sniff that sender's MAC address of the test packet is its MAC address and receiver’s MAC address is the AP's MAC address.

Figure 4. Proposed scheme testing evil twin AP

On the other hand, Figure 4 shows how our proposed scheme works in Wi-Fi access through evil twin AP. First of all, a smartphone starts monitoring around Wi-Fi networks and sends a test packet. Then, evil twin AP relays the packet to offer the internet access to the smartphone. Because this relaying packet reaches to the smartphone too, the smartphone can recognize that there are two test packets in its monitoring interface. The second test packet which evil twin AP relayed and the smartphone captured says that sender is the AP in which the smartphone is connected. Using this packet, the smartphone can detect that it is connected to evil twin AP. Consequently, the smartphone disconnects current Wi-Fi access and warn the user. Figure 5 shows the procedure of our proposed scheme.

Figure 5. A flowchart of the proposed scheme

5. EVALUATION

We made an android smartphone application implementing our proposed scheme to evaluate in real Wi-Fi network environment. The source code of the application can be downloaded in http://www.(veiled until notification due to double-blind review).net. Even though it does not need in our scheme, we uploaded source code of server side program which makes us know if the smartphone sends a test packet or not. The procedure of making evil twin AP is published in [7].

We used Samsung Galaxy S3 which is identified as SHVE201S by the manufacturer and using Android 4.3, TG NXI-L7000 laptop as evil twin AP which uses Backtrack R5 Linux as its OS, two Next-201N mini USB type WLAN card using RealTek 8188CUS chipset, and one desktop with an IPtime N150UA_Solo USB type WLAN card using Ralink 3070 chipset as legitimate AP.

We wanted to evaluate our proposed scheme with only one smartphone, but we faced an obstacle during implementation. Configuring smartphone's Wi-Fi interface mode from managed to monitor was introduced in [11]. But, it needs root permission of the smartphone. In several countries including U.S., rooting or jail breaking of smartphones is illegal in some case [12]. Therefore, we used one more laptop to support monitoring Wi-Fi network which is needless originally in the scheme.

Figure 6. Starting scan

Figure 7. Stopping scan

Figure 6 shows the application implementing our proposed scheme. If you touch “WiFi Scan OFF” toggle button, the smartphone starts scanning candidate APs near the smart phone to access the internet repeatedly. When you touch “WiFi Scan On” toggle button again, you can hold updating candidate AP list like Figure 7. Then you can select the AP which will be tested when you touch “AP test” button which located in right side of SSID of the AP. Connection changing and sending test packet are performed by the application automatically like Figure 8. So, that test packet is captured by monitoring mode laptop. As mentioned above, the roll of monitoring can perform by the smartphone itself [11]. But, in this evaluation, we copied the packet captured (PCAP) file from monitoring mode laptop to smartphone manually to avoid smartphone rooting. So, the smartphone which has PCAP file can analyze monitoring result. When you touch bottom “Detect Evil Twin Access Points” button, like figure 9, the application shows whether the AP you touched its test button is evil twin AP or not using our proposed scheme.

Figure 8. Testing AP

Figure 9. Detecting result

We evaluated our proposed scheme using this application several hundred times and it missed detecting evil twin AP only one time. Usually, retransmission due to signal loss occurs in wireless network occasionally. So, monitor mode does not guarantee every packet is captured. But, our proposed scheme makes smartphones able to detect evil twin AP 99.9% and warn the user. Because, as mentioned, the attacker may try to be closer to victims to lure them with higher signal strength than legitimate AP, we think this evil twin AP detection scheme can work with almost perfect detecting ratio similarly in real attacking environment.


6. CONCLUSION

In the preamble of this paper, we ask that how can you trust a stranger. Our answer is never. But, if in the case we can benefit from him when we trust that one, we will change the question like how can you doubt a stranger? If so, our answer is simple. If someone shows a suspicious action then we cannot trust him.

So far, we surveyed already published related works to detect evil twin AP and analyzed their limitation. Finally, we proposed relay sniffing based evil twin AP detection scheme. As mentioned above, our proposed scheme is simple but powerful and does not rely on any third party authentication, traffic characteristics, dual networks, training and statistics. In our evaluation, our proposed scheme shows that it makes a smartphone able to detect evil twin AP 99.9% and warn the user. In our opinion, this scheme can work with almost perfect detecting ratio similarly in real attacking environment.

Last but not least, we address three limitation of our proposed scheme. Firstly, as aforementioned in chapter 5, our proposed scheme should be implemented by smartphone manufacturers or smartphone OS developer to avoid intellectual property conflicts. Our proposed scheme needs root permission to control Wi-Fi interface to monitor mode. Secondly, legitimate Wi-Fi repeater works similarly with evil twin AP. It relays a smartphone user's data to another AP, So, our proposed scheme may judge it as evil twin AP. Therefore, final selection should be leaved for the user. The ultimate goal of our proposed scheme is giving serious warnings to the user, not absolutely blocking all wireless relaying transmission. Lastly, if our proposed scheme is implemented without any more consideration, smartphones may not detect evil twin AP when there is security algorithm like IEEE 802.11i between evil twin AP and legitimate AP. Figure 10 shows this environment for easy understand.

Figure 10. Evil twin AP protected by legitimate AP

Like figure 10, if our proposed scheme is implemented simply, smartphone may not detect evil twin AP in some case because they cannot find test packet in communication between evil twin AP and legitimate AP. Actually, this limitation can be regarded as social engineering problem because evil twin AP is authorized one for legitimate AP.

But, in our opinion, if those communication packets captured and stored in the smartphone once, it could be decrypted using tools like Aircrack-ng, Cowpatty through offline dictionary attack [7] or trying known plain text attack. The more things the smartphone needs to exploit our proposed scheme are enough volume of dictionary data and computational power. So, we suggest that it can be regarded by smartphone manufacturers and its OS developers in the light of proactive and offensive wireless security.


7. REFERENCES

[1] Minwoo Park et al, "Dangerous Wi-Fi access point: attacks to benign smartphone applications", Personal and Ubiquitous Computing, Oct. 2013
[2] Sungmin Lee et al, "A mitigation scheme of DoS attacks against IEEE 802.11i using dynamic MAC address", International Conference on Electrical Engineering & Computer Science, Dec. 2013
[3] Lanier Watkins et al, "A Passive Approach to Rogue Access Point Detection", IEEE GLOBECOM 2007
[4] Raheem Beyah el al, "Rogue-Access-Point Detection Challenges, Solutions, and Future Directions", IEEE Security and Privacy, Volume 9 Issue 5, Sept. 2011, Pages 56-61
[5] Somayeh Nikbakhsh et al, "A Novel Approach for Rogue Access Point Detection on the Client-Side", International Conference on Advanced Information Networking and Applications Workshops, 2012 [6] Suman Jana et al, "On Fast and Accurate Detection of Unauthorized Wireless Access Points Using Clock Skews", IEEE Transactions on Mobile Computing, Vol.9, No.3, Mar. 2010, Pages 449-462 
[7] Vivek Ramachandran, "BackTrack 5 Wireless Penetration Testing Beginner's Guide", PACKT Publishing, 2011
[8] Kevin Benton, "The Evolution of 802.11 Wireless Security", UNLV Informatics, Apr. 2010
[9] Jaemin et al, "Man-in-the-middle Attacks Detection Scheme on Smartphone using 3G network”, IARIA, 2012
[10] Chao Yang et al, "Active User-Side Evil Twin Access Point Detection Using Statistical Techniques", IEEE Transactions on Information Forensics and Security, Vol. 7, No. 5, Oct. 2012
[11] Omri Ildis et al, http://bcmon.blogspot.kr 
[12] Richi Jennings, "Jailbreak or unlock hacks of iPhone to be ILLEGAL under Obama's TPP treaty", Computerworld, Nov. 19. 2013
[13] Raheem Beyah el al, “Rogue Access Point Detection using Temporal Traffic Characteristics”, IEEE GLOBECOM, Nov. 2004
[14] Hao Han et al, “A measurement Based Rogue AP Detection Scheme”, IEEE INFOCOM, Apr. 2009

2021년 1월 12일 화요일

양자 컴퓨터 클라우딩 서비스 기반 쇼어 알고리즘의 RSA 알고리즘 공격 실증 및 공간 복잡도 최적화 가능성 연구

이 글은 제가 2020년 12월 14일 작성해서 제출다가 떨어졌..ㅠ던 과제 제안서 중 학술적인 부분만 추린 글입니다.


1. 과제의 필요성

1.1. 국내ㆍ외 연구의 주요 이정표

1.1.1. 양자 컴퓨팅 연구의 주요 이정표

1985년, 미국의 물리학자 리처드 파인만은 전통적인 컴퓨터에서 양자 시스템을 시뮬레이션하는 작업은 기하급수적으로 비용이 많이 들며, 미래의 양자 컴퓨터가 물리학과 화학의 문제를 해결할 수 있는 효과적인 도구가 될 것이라고 예언[1-1]하였다. 이는 양자 물리학을 기반으로 하는 새로운 컴퓨팅 모델 이었으나, 과학자 대부분은 물리적으로 실현하기가 매우 어려워 전통적인 컴퓨터의 발전에 비해 많은 관심을 받지 못하고, 순수 이론으로 간주하였다. 

  1994년, AT&T Bell 연구소의 컴퓨터과학자인 피터 쇼어는 양자 컴퓨터를 이용하여 다항 시간에 소인수 분해와 이산 로그 문제를 해결하는 알고리즘을 발표[1-2, 3]하였다. 이는 전통적인 컴퓨터에서 기하급수적인 시간 복잡도를 가지는 것과 비교하여 더 효율적인 계산 방식이다. 또한, 1995년, 오류 없는 양자 컴퓨터를 개발하기가 어려운 현실을 다소 보완할 수 있는 양자 오류 정정 알고리즘[1-4]을 발표하였다. 현재 비대칭키 표준 암호 알고리즘인 RSA가 소인수 분해 문제의 어려움을 기반하므로, 쇼어 알고리즘은 일반적으로 양자 컴퓨터의 첫 번째 킬러 어플리케이션으로 알려져 있다.  

  1996년, AT&T Bell 연구소의 컴퓨터과학자인 로브 그로버는 양자 컴퓨터를 이용하여 정렬되지 않은 데이터베이스의 검색 속도를 루트 시간에 수행할 수 있는 알고리즘을 발표하였다. 이는 전통적인 컴퓨터에서 다항 시간 복잡도를 가지는 것과 비교하여 더 효율적인 계산 방식이며, 양자 컴퓨터의 두 번째 킬러 어플리케이션으로 알려져 있다. 

  2001년, IBM 알마덴 연구소의 리븐 벤더시펜은 7-큐비트의 핵자기공명 기반 양자 컴퓨터로 쇼어 알고리즘을 최초로 실현[1-6]하였다. 

  2016년, IBM은 양자 컴퓨터 클라우딩 서비스인 Quantum Experience를 출시하였다. 초기에는 5-큐비트 연산을 지원하였으나, 2017년에는 16-큐비트, 2020년 12월 현재는 53-큐비트까지 활용할 수 있다.

그림1. https://quantumcomputing.stackexchange.com/questions/tagged/ibm-q-experience

  2018년, 미국의 물리학자 존 프레스킬은 50-큐비트 이상 규모의 양자 컴퓨터를 개발할 수 있다면, 오류 정정 알고리즘을 활용하여 양자 계산을 상용화할 수 있는 새로운 시대(NISQ era, Noisy Intermediate-Scale Quantum era)가 열릴 것으로 예상[1-7]하였다.

  2019년, Google의 프랭크 알럿은 53-큐비트의 초전도체 기반 양자 컴퓨터를 이용하여 전통적인 슈 퍼컴퓨터에서 약 1만 년이 소요되는 연산을 200초에 수행했다고 발표하며, NISQ 시대의 시작과 양자 우월성(Quantum Supremacy)의 달성을 주장[1-8]하였다.

  같은 해, IBM의 에드윈 페드널트는 Google에서 실험한 연산이 전통적인 슈퍼컴퓨터에서 2.5일이면 수행될 수 있으며, 2012년 프레스킬이 정의한 양자 우월성은 “양자 컴퓨터는 할 수 있으나, 전통적인 컴퓨터는 할 수 없는 일”이므로, Google의 양자 우월성의 달성을 부정[1-9]하였다.

1.1.2. 쇼어 알고리즘 관련 연구 현황

2001년, IBM에서 쇼어 알고리즘을 최초로 실현한 후, 이 알고리즘의 실현과 응용에 관한 다양한 연구가 진행되었다. 2005년, 에드워드 게르주이 등은 쇼어 알고리즘이 현재 인터넷에서 사용되는 보안 알고리즘에 영향을 주기 위해서는 키 길이의 두 배 크기의 큐비트 연산이 필요하다고 주장[1-10]하였다. 이는 쇼어 알고리즘의 위협을 축소하는 것으로 간주할 수 있다. 그러나, 2016년, 토마스 몬즈 등 은 이온 트랩 기반 13-큐비트 양자 컴퓨터에서 7개의 제어 큐비트와 4개의 캐시 큐비트를 활용하는 기법으로 쇼어 알고리즘을 실현[1-11]하며, 쇼어 알고리즘의 양적 확장성을 주장하였다. 다시 쇼어 알고리즘이 현대 암호에 위협이 될 수 있다는 의미로 해석할 수 있다. 반대로, 2019년, Google의 크레 이그 기드니 등은 양자 게이트의 오류율을 10-3 , 코드 순환 시간을 1마이크로초, 그리고 반응 시간을 10마이크로초로 가정하고, 잡음 등의 다른 요소들을 배제하였을 때 현재 권장되는 RSA 암호의 키 길 이인 2048bit 암호를 8시간 안에 깨는 데는 2천만 개의 큐비트가 필요하다고 주장[1-12]하였다. 이는 현대 사이버 보안에서 쇼어 알고리즘이 미치는 영향을 부정하는 것으로 이해할 수 있다. 이처럼, 쇼어 알고리즘이 현대 사이버 보안에 미치는 영향을 바라보는 관점은 낙관론과 부정론의 이견이 공존한다.

1.2. 연구 개발의 중요성

2016년, 미국 NIST는 대규모 양자 컴퓨터가 존재하면 쇼어 알고리즘으로 인해 RSA는 더는 안전하 지 않다는 내부 보고서[1-13]를 공개하였다. 이 보고서에서 NIST는, 양자 컴퓨터의 두 번째 킬러 애플 리케이션인 그로버 알고리즘의 이차원 시간 성능 향상(quadratic speedup)은 단순히 AES와 같은 대 칭 키 암호 알고리즘의 키 길이를 두 배로 늘리고, SHA-2와 같은 해시 함수는 출력 길이를 두 배로 늘려서 대응할 수 있다고 말한다. 하지만, 쇼어 알고리즘의 급수적 성능 향상(exponential speedup)으 로 현재 비대칭키 표준인 RSA는 안전하지 않으며, 양자 컴퓨팅에 대한 더 많은 연구가 긴급하게 필요 하고, 향후 비대칭키 암호 알고리즘의 표준 전환을 대비하여 암호화 민첩성(crypto agility)를 강조하였다.

  2020년 7월, NIST는 69종류의 차기 양자 후 비대칭키 암호 알고리즘 표준 후보 중 3차 심사를 통과한 4개의 알고리즘을 발표하였다. 하지만, 상기 NIST의 보고서[1-13]에서도 언급된 바와 같이, 지난 30여 년간 발전하여 오늘날 널리 사용되고 있는 TLS, PKI, IKE 등 다양한 통신 보안 체계가 RSA에 의존하고 있으며, 양자 후 비대칭키 암호 표준으로 손쉽게 교체(drop-in replacement)되는 것은 불가능 하다. 따라서 NIST에서 강조한 암호화 민첩성에는 상당한 저항이 예상된다.

  과거에는 양자 컴퓨팅에 대한 접근이 어려웠으나, 최근에는 빠르게 상용화되고 있다. 상기 기술한 IBM에 이어, Microsoft20201, 양자 컴퓨터 클라우딩 서비스인 애저 퀀텀(Azure Quantum)을 발표[1-14]했다. 이어서, 20208, Amazon도 초전도체 기반 양자 컴퓨터 회사인 Rigetti, 이온 트랩 방식의 양자 컴퓨터 회사인 IONQ, 양자 어닐링 기반 양자 컴퓨터 회사인 DWave 사의 기술을 제공하는 클라우딩 서비스인 아마존 브라켓(Braket)을 발표하였다.

  쇼어 알고리즘의 위협성 평가는 이견이 공존하고, 양자 컴퓨터는 빠르게 발전하고 있으며, 클라우딩 서비스를 통해 점점 보편화하고 있다. 하지만, NIST는 추가 연구와 암호화 민첩성을 강조할 뿐 명확한 위협 수준과 현대 사이버 보안 체계가 양자 후 암호(Post Quantum Cryptography) 체계로 전환하는 타임라인을 제시하지 못한다. 이 연구는 현대 양자 컴퓨팅을 기반으로 쇼어 알고리즘이 현대 사이버 보안에 미치는 실질적인 영향을 분석하고, NIST에서 요구하는 암호화 민첩성에 관한 판단의 기준을 제시할 것이다.

* 참고

[1-1] Richard P. Feynman, “Simulating physics with computers”, Int. J. Theor. Phys, 1982
[1-2] Peter W. Shor, “Algorithms for Quantum Computation : Discrete Logarithms and Factoring”, IEEE, 1994
[1-3] Peter W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM, 1997
[1-4] Peter W. Shor, “Scheme for reducing decoherence in quantum computer memory”, SIAM, 1997
[1-5] Lov K. Grover, “A fast quantum mechanical algorithm for database search”, IEEE, 1994
[1-6] Lieven M. K. Vandersypen et al, “Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance”, Nature, 2001
[1-7] John Preskill, “Quantum Computing in the NISQ era and beyond”, Quantum J., 2018
[1-8] Frank Arute et al, “Quantum supremacy using a programmable superconducting processor”, 2019
[1-9] Edwin Pednault et al, “Quantum Computing On Quantum Supremacy”, IBM Research Blog, 2019, https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/
[1-10] Edward Gerjuoy , “Shor’s factoring algorithm and modern cryptography. An illustration of the capabilities inherent in quantum computers”, American J. of Phy., 2005
[1-11] Thomas Monz et al, "Realization of a scalable Shor algorithm", Science, 2016
[1-12] Craig Gidney, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”, 2019
[1-13] NIST, “Report on Post-Quantum Cryptography”, NISTIR 8105, 2016
[1-14] ZDNet Korea, https://zdnet.co.kr/view/?no=20200130140036


2. 과제의 목표 및 내용

2.1. 최종 목표

양자 컴퓨터 클라우딩 서비스를 이용한 쇼어 알고리즘의 RSA 알고리즘 공격 실증 및 최적화 가능성 연구

2.2. 연구 범위

최종 목표 달성을 위해 아래와 같은 연구 주제를 목표로 한다.

  1. 양자 컴퓨터 클라우딩 서비스의 활용 방법 분석 및 쇼어 알고리즘의 구현
  2. 양자 컴퓨팅과 전통적인 컴퓨팅에서 쇼어 알고리즘 동작 비교 분석
  3. 양자 컴퓨팅의 쇼어 알고리즘을 통한 RSA 알고리즘 공격 실증 및 최적화 가능성 연구

2.3. 연구 내용

2.3.1. 양자 컴퓨터 클라우딩 서비스의 활용 방법 분석 및 쇼어 알고리즘의 구현

대표적인 양자 컴퓨터 클라우딩 서비스인 IBM QX(Quantum eXperience)에서 양자 컴퓨팅을 구현하는 방법은 크게 세 가지로 나뉜다. 후발 주자인 MS와 Amazon도 유사한 인터페이스를 지원할 것으로 예상한다.

2.3.1.1. 양자 컴포저(Quantum Composer) 활용

양자 컴포저는 드래그 엔 드롭 방식의 GUI를 제공하는 양자 컴퓨팅 인터페이스이다. 상단에는 연산에서 사용할 수 있는 게이트들이 나열되어 있다. 아래 그림2는 두 개의 큐비트를 초기화하고, 하다마드 게이트와 CNOT 게이트적용한 , 고전 레지스터에 각 큐비트의 측정값을 기록하는 예제이다.

그림2. 양자 컴포저(https://quantum-computing.ibm.com/composer/)

2.3.1.2. OpenQASM(Quantum Assembly Language) 활용

양자 컴포저는 GUI를 지원하여 직관적이기는 하지만 긴 프로그램을 작성하기에는 적합하지 않을 수 있다. 이를 위해 OpenQASM을 활용할 수 있으며, IBM QX에서 양자 컴포저와 호환할 수 있다. 그림2의 양자 컴포저 구현을 표1과 같이 OpenQASM을 활용하여 코딩할 수 있다.

표1. 그림2의 양자 컴퓨저를 OpenCASM으로 구현


2.3.1.3. Qiskit(Quantum Information Software Kit) 활용

QiskitIBM QX를 활용할 수 있는 Python 라이브러리이다. Python 이 설치된 환경에서 pip 툴을 이용하여 Qiskit을 설치하고, 버전을 확인할 수 있다. 아래 표2Windows 10의 콘솔에서 수행하였다.

표2. Qiskit 설치 및 버전 확인

  Qiskit 라이브러리를 사용하기 위해서는 IBM QX 계정에서 API 토큰을 받아 활성화해야 한다. IBM QX 사이트에 회원 가입 후 account 페이지에서 Copy token을 누르면 API 토큰이 클립보드에 복사된다.

그림3. API토큰(https://quantum-computing.ibm.com/account)

이 후, 다음 표3과 같은 python 코드를 실행할 수 있다.

표3. Qiskit 을 활용한 양자 프로그래밍

2.3.2. 양자 컴퓨팅과 전통적인 컴퓨팅에서 쇼어 알고리즘 동작 비교 분석

RSA 암호 알고리즘은 소인수 분해 문제의 어려움을 기반으로 한다. 소수 1723을 곱하는 데 필요한 시간은 몇 초에 불과하지만, 두 수의 곱인 391을 소인수 분해하기 위해서는 훨씬 더 많은 시간이 필요하다. 가능한 수를 모두 시도해보는 시행착오 방법을 이용했을 때, 자릿수를 4개에서 8개로 늘리면 계산 과정의 수는 대략 70번에서 5,000번으로 늘어나며, 5,000번의 계산을 4시간으로 가정할 때 16자리 수로 늘어나는 경우, 계산 시간은 약 2년이 된다. 최근 전통적인 컴퓨터는 1초 동안 1조 번의 계산을 수행하는 테라플롭스(Teraflops)의 성능을 가지고 있지만, 130자리 수를 갖는 소인수 분해는 약 42일이 소요되며, 자릿수가 2배가 되면 대략 100만 년 정도의 시간이 걸리고, 자릿수가 몇 개 더 늘어나면 계산 시간은 우주의 나이보다 길어질 수 있다[2-1].

  소인수 분해 문제는 시행착오 방법이 아닌 푸리에 변환(Fourier transform)문제로 변형하여 접근할 수 있다. 푸리에 변환은 함수가 가진 주기성을 이용한다. 예를 들어, 다음과 같은 수열이 있는 경우,

1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, ...

  숫자 4 다음에는 1이 될 것을 알 수 있는 데, 이는 수열의 주기가 4이기 때문이다. 소수 7의 지수로부터 유도되는 수열은 다음과 같다.

71 = 7, 72 = 49, 73 = 343, 74 = 2401, 75 = 16807, ...

  위 수열에 각각 modulo 15를 적용하면 7, 4, 13, 1가 반복되며, 주기가 4 임을 알 수 있다. , an 제곱 형태의 n에 따라 커지는 수열을 어떤 수 N으로 modulo 연산을 하면 수열 an mod N은 주기 r을 가지며, r이 짝수인 경우, N의 소인수는 ar/2 + 1 N의 최대공약수와, ar/2 - 1 N의 최대공약수이다. 위 식에 대입하면, 15의 소인수는 74/2 + 1 = 50 N의 최대공약수, 74/2 1 = 48N의 최대공약수이고, N15를 대입하여 GCD(50, 15)GCD(48, 15)를 계산하면, 15의 소수는 53임을 알 수 있다.

  두 소수 pq의 곱으로 생성된 N을 소인수 분해하는 쇼어 알고리즘은 다음의 단계들로 요약할 수 있다[2-2].

Step1) 1보다 크고, N보다 작은 임의의 정수 a를 선택한다. 만일, GCD(N, a) 1 이면p = GCD(N, a)이고, q = N / q 이다.

Step2) 함수 f(x)ax mod N 의 주기 r을 구한다. 주기가 짝수가 아니면 Step1 부터 다시 시작한다.

Step3) 주기 r로 두 개의 최대공약수 GCD(N, ar/2 + 1) GCD(N, ar/2 1)을 구한다.

Step4) 두 최대공약수가 1N이라면, Step1부터 다시 시작한다.

  쇼어의 알고리즘을 표4와 같이 Python으로 전통적인 컴퓨터에서도 구현[2-3]할 수 있다. 4의 코드를 실행하면 라인 25의 결과는 출력되지만, 라인 28의 결과는 다소 시간이 소요된다. 12번 라인에서 선택된 난수와 컴퓨팅 환경에 따라 상당히 긴 시간이 걸릴 수 있다. 코드에서 가장 많은 계산 시간을 차지하는 부분은 라인 6의 주기를 찾는 부분으로, 양자 컴퓨터에서 양자 푸리에 변환(QFT, Quantum Fourier Transform)을 이용하여 최적화할 수 있다. 일반적으로, 전통적인 컴퓨터에서 고속 푸리에 변환(FFT, Fast Fourier Transform)O(n log n)의 시간 복잡도[2-4]를 가지지만, 양자 푸리에 변환은 O(log n)의 시간 복잡도[2-5]를 가진다.

2.3.3. 양자 컴퓨팅에서 쇼어 알고리즘을 이용한 RSA 알고리즘 공격 실증 및 최적화 가능성 연구

쇼어 알고리즘은 QFT를 이용한 소인수 분해의 최적화 기법이지만, 이는 시간 복잡도(Time complexity)에 집중되어 있어서, 실질적인 RSA 알고리즘의 위협이 되기 위해서는 최소 세 가지 추가적인 관점이 고려되어야 한다. 첫 번째는 공간 복잡도이다. 양자 컴퓨터가 빠르게 발전하고, 클라우딩 서비스를 통해 진입장벽이 낮아지고 점차 보편화하여 가고 있지만, 양자 계산에 사용할 수 있는 큐비트의 수는 제한되어 있다. 두 번째 필수적인 고려 사항은 결잃음 시간(Decoherence time)이다. 양자 컴퓨팅과 전통적인 컴퓨팅의 대표적인 차이는 큐비트들의 중첩(Superposition)을 통한 병렬 연산이지만, 양자 컴퓨터의 큐비트들이 중첩을 유지하는 시간은 제한되어 있다. 마지막으로, 양자 컴퓨팅의 오류 보정이 고려되어야 한다. 큐비트는 일반적인 비트의 비트 플립에 추가하여 위상 플립(phase flip)의 오류도 영향을 받으며, 이는 양자 계산의 신뢰도를 위협할 수 있다. 일반적으로, 전통적인 컴퓨팅 수준의 신뢰할 수 있는 큐비트와 양자 연산을 가리켜 충실도(fidelity)라는 표현[2-6]을 사용한다.

  결잃음 시간과 오류 보정이 필요하지 않다고 가정했을 때, RSA 알고리즘을 공격하기 위해 몇 개의 큐비트가 필요한지에 대한 정보는 이견이 공존한다. 유명 개발자 커뮤니티 중 하나인 StackOverflow 에서는 4N + 2개의 큐비트가 필요하다는 답변[2-7]이 있다. 반면에, StackExchange 에서는 2N + 2개의 큐비트가 필요하다는 답변[2-8]을 찾을 수 있다.

그림4. 쇼어 쇼어 알고리즘 구현에 필요한 큐비트의 수에 대한 StackOverflow의 답변(4n + 2)

그림5. 쇼어 알고리즘에 필요한 큐비트의 수 답변 StackExchange의 답변(2n + 2)

  양자 컴퓨팅 환경에서 쇼어 알고리즘을 기반으로 RSA 알고리즘을 효과적으로 공격하는 다수의 연구가 최근까지 발표[2-9, 10, 11, 12]되고 있다. 따라서 이 연구는 현재 발표된 쇼어 알고리즘 최적화 연구들의 이론적 분석 및 양자 클라우딩 서비스를 이용한 실증과 추가적인 최적화 기법의 발견 가능성 연구를 목표로 한다.

* 참고

[2-1] Oliver Morch, “양자 비트와 양자 암호(김말진 등 옮김)”, 북스힐, 2010
[2-2] 배준현, “소인수 분해를 위한 쇼어의 양자 알고리즘”, 
[2-3] 배준현, “쇼어의 소인수 분해 알고리즘 구현”, 
[2-4] 위키백과, “고속 푸리에 변환”, https://ko.wikipedia.org/wiki/고속_푸리에_변환
[2-5] Christin Corbett Moran, “Quantum Computing with IBM QX(황진호 옮김)”, 2020, 225p
[2-6] 김기환 등, “이온 포획장치를 이용한 양자 컴퓨터”, 물리학과 첨단기술 3월호, 2019
[2-9] Vaishali Bhatia et al, "An Efficient Quantum Computing technique for cracking RSA using Shor’s Algorithm", IEEE ICCCA, 2020
[2-10] Yahui Wang et al, “Quantum Polynomial-Time Fixed-Point Attack for RSA”, IEEE China Communications, 2018 
[2-11] Kapil Kumar Soni et al, “Cryptographic Attack Possibilities over RSA Algorithm through Classical and Quantum Computation” IEEE ICSSIT, 2018
[2-12] Martin Ekerå et al, “Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers”, PQCrypto, 2017