量子密碼

量子CTF種類

  • 量子計算

主要是逆向工程、加解密
這次主講加解密比較基礎

量子相關知識

  • 薛丁格的貓

    • 一種思想實驗
    • 如果不看月亮，月亮還存在嗎?

  • 量子(quantum)

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

  • 疊加態

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

  • 糾纏態

    • 超距效應
    • 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的機率?

環境安裝

例題

  • 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))
  1. 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

Select a repo