# 量子密碼
## 量子CTF種類
* 量子計算

主要是逆向工程、加解密
這次主講加解密比較基礎
## 量子相關知識
* 薛丁格的貓
* 一種思想實驗
* 如果不看月亮，月亮還存在嗎?

* 量子(quantum)
* 定義
* 物理量最小單位(離散存在)
* 事物以頻率機率狀態存在
* 物體小到有量子效應都能當作量子位元，使其當作資訊的仔仔，如光子或代電粒子
* 狀態
* 疊加態 (Superposition)
* 糾纏態 (Entanglement)
* 密集傳輸 (Dense coding)
* 瞬間傳輸 (Teleportation)

* 疊加態
* 消相干(?
* 越靠近哪一軸，哪一軸的機率越高 (絕對值平方)
* 每次測量都會改變量子態
* 

* 糾纏態
* 超距效應
* EPR糾纏
* 糾纏態一定是疊加態

* 密集傳輸
* 傳統傳輸只能傳1 bit，量子通過疊加態可以傳多個bits

* 瞬間傳輸
* 超光速？
* 無法超光速
* 瞬間傳輸是一種複製嗎？
* https://www.youtube.com/watch?v=_Fc_XmWiS0c&themeRefresh=1
* ！！注意X高的影片不可當知識頻道！！
* 未知的量子態無法被複製，因此瞬間傳輸無法超光速
* 做特定運算 -> 狀態改變 -> 修復 -> 還原
* Alice 做特定運算後，狀態改變
* Bob 那邊的狀態未知，需要從 Alice 那邊傳遞訊息過來修復

## 密碼學基礎概念
* 凱薩密碼
* 每個字母 shift n 個字母
* ABCDED -> DEFGHI (shift 3)
* ~~現代基本沒用了~~
* 此加密方式在 WW2 的時候被改良且做到極致
* 電影:
* 攔截密碼戰 EniGMA
* 獵殺 U-571
* 模仿遊戲
* Enigma = 「謎」
* 二戰德國使用的加密解密機器
* 密碼本如同金鑰
* 定期更新密碼本

* 密碼學基礎
* **明文** *-加密->* **密文** *-傳輸->* **密文** *-解密->* **明文**
* 雙方 key 為同一把
* **==金鑰配置問題==**
* 公開資訊需要加密才安全，那一開始要怎麼知道金鑰？

* 1976 Diffie, Hellman 兩人研究出公開交換金鑰的方法
* 公開色、Alice 秘密色、Bob 秘密色
* 雙方將自己的秘密色與公開色混合後傳輸
* 拿到對方的混合色後再加入自己的秘密色

* 1978 RSA 公開金鑰算法
* 基於兩個質數相乘後難以分解
* 一個 user 會有兩把鑰匙：公鑰、私鑰
* Alice 和 Bob 各有各的私鑰，公鑰任意散播，私鑰不能公開
* 公鑰加密，私鑰解密
* 假設 Alice 要傳給 Bob，需要用 Bob 的公鑰加密
* 因為 Bob 的公鑰任何人都可知道，所以拿 Bob 的公鑰就可以傳訊息給他
* Bob 可以用自己的私鑰來解開用 Bob 公鑰加密的資訊
* 反過來， Bob 要傳訊息給 Alice 的話，可以用 Alice 的公鑰來加密訊息

* 1994 Shor's algorithm 破解 RSA
* 量子演算法演示了找循環的能力
* 需要研究出即使是量子電腦也無法破解的非對稱加密方法

* 後量子密碼 (抗量子密碼)：
* 用既有的傳統算法抵抗量子計算
* 比RSA慢
* USA 目前主要在推後量子密碼

* 量子密碼
* 比較複雜
* 量子演算法 *(必須運行在量子電腦上)*
* 成本高

## 量子密碼學基礎 (BB84)
- BB84 就像 RSA 一樣，是一個基礎的積木，到處都會用到
- 金鑰配置協定

* 1984年的量子金鑰配置問題

* 量子如何解決金鑰配置問題
* 無法得知未知量子態
* 量子位元無法被複製
* 基底轉換可以使用量子位元配置金鑰

* 成功達成了什麼事情？
* 達成金鑰配置
* 無限長度的金鑰(絕對安全)
* 可以檢測出通道有沒有監聽者

* 一次性密碼 (One-Time Pad)
* 把明文和金鑰做XOR

* 相同的基底連續重複測會得到相同結果
* 使用基底之後會影響結果
* 再用之前的基底測一次結果會不一樣

|0>
├Z基底─ |0>
│       ├Z基底─ |0>
│       └X基底─ |+>,|->
└X基底─ |+>
        ├Z基底─ |0>,|1>
        └X基底─ |+>,|->

* Alice 傳送 qubit、Bob 隨機選擇測量的基底

Alice -----> Bob
|0>   --Z--> |0> 保留
|->   --Z--> |1>
|+>   --X--> |+> 保留
|1>   --X--> |+>

sequenceDiagram
Alice ->> Eve: 1. 產生亂數位元 2. 產生亂數基底

Eve in the middle

公布基底的時候狀態不一可以找到eve
有機率抓不到
如何最大化抓到Eve的機率?

## 環境安裝
* Python
* Xampp
* 放置index.php至C:\xampp\htdocs
* Linux: `/opt/lampp/htdocs`
* 開apache server
* 開cmd執行qkd.py
* https://reurl.cc/677gYO
* https://ctftime.org/writeup/18212
## 例題
- Google CTF(2019 QKD)
1.自己隨機產生bit和basis string
2.透過這兩者產生qubit序列
3.將qubit序列和basis string 傳給google
4.
python會傳量子態與基底給apache，php會選出相同的基底然後用金鑰加密

## 練習題正解
1. qkd_ais3.py :

key = ""
for i in range(len(Alice_bases)):
    if Alice_bases[i] == Bob_bases[i]:
        key += Alice_bit_string[i]

flag = ""
for i in range(len(ciphertext_bin)):
    if ciphertext_bin[i] != key[i]:
        flag += '1'
    else:
        flag += '0'

print(dec2utf8(flag))

2. qkd_b92.py :

key = ""
for i in range(0, qubit_num-1):
    if data["reserved"][i] == '1':
        key += Alice_bit_string[i]

## Q&A
> dense encode 可以讀出兩個 bits 的原因是因為糾纏態嗎？
>

> 量子密碼學與後量子密碼學有什麼不一樣？
> 量子密碼學：用量子特性開發的加密演算法
> 後量子密碼學：對抗量子電腦的加密演算法

> 是透過比對狀態來確定有沒有一樣基底嗎？
> 要先比對基底

> 所以用不同的基底看同一個 qubit，會讓它的狀態變來變去嗎?但是它在向量表示上不是始終是同一個嗎?
> 會，狀態會改變；

> 如果比對基底後，一樣的很少，金鑰很短不是很不安全嗎？
> 一個便當吃不飽，那就吃兩個，可以多傳一點
> p.66 的最後的+ -是怎麼決定他是1還是0
> |0> -> 0
> |1> -> 1
> |+> -> 0
> |-> -> 1

> 推薦書籍：https://www.sciencedirect.com/book/9780123838742/classical-and-quantum-information