Pairing Based Cryptography
要implement此類crypto至少需要以下計算:
Arithmetic in : 可以建構在 GMP library 上 (提供了 number theoretic functions 像是 inversion modulo a prime 和 Jacobi symbol 等)
Elliptic curve groups: 解 , point addition 和 multiplication (可參考前一份notebook)
Bilinear pairing: Miller’s algorithm
上述可以實現出 Type A and B (and A1) pairings- 快速但是elements 需要很多空間來表示,如果要實現起他 pairing 就必須實現 Field extensions
另外還要尋找 pairing-friendly curves。 像是 MNT curve construction method 需要 finding roots modulo a given prime, testing polynomial irreducibility, computing Hilbert polynomials. 這些都需要 high precision complex floating point arithmetic 和解 Pell-type equation
另外我們要隨機在 elliptic curve 上產生點,常見做法是隨機選擇 x-coordinate 然後解上述的 quadratic equation 來得到 y. (若無解, 則再換下一個x座標)。對於 odd characteristics, 如果我們可以找到 square roots of elements這可以一次達成。 在 finite field of prime order 中 square roots 可以藉由解 Tonelli-Shanks algorithm來得到。 至於其他field 則要參考其他新的文獻。(一個解法是去解 用 Cantor-Zassenhaus method (Legendre’s method))。
對於特定情況有更簡潔的方式可以產生隨機點。 例如若 p 是質數且 則 x 的三次方根(Fq中) 為 . 故若方程式中 a=0,我們可以選擇先挑y然後解x。
Introduction to Charm
Group Abstractions
實做scheme的第一步是去選擇適當的 group。 Modern cryptographic algorithms 通常建構在提供特定數學難題性質的group上。
在charm中提供了三種cryptographic settings:
Integergroups
ecgroups
pairinggroups
要 initialize a group in the elliptic curve (EC) setting, 請參考 toolbox.eccurve 中實做的成員和方法以及了解提供相關的 NIST approved curves (e.g., prime192v1).
對 EC with billinear maps (or pairings)來說,提供了 symmetric 和 asymmetric 的 curves。 例如: 'SS512' 是一個 symmetric curve with a 512-bit base field 而'MNT159' 代表了 asymmetric curve with 159-bit base field.
注意這些 curves 是 prime order。
最後,對於 Integer groups, 通常定義大質數 p and q 就足以產生一個 RSA group. 若要用其他像 schnorr groups, 可能會需要一些時間來產生相關參數,因為 他們要求safe primes (例如: p = 2q + 1). 接下來我們呈現 integer 和 pairing groups:
Implement a Scheme
通常採用OOP的實作方法來增進可重複利用以及延伸性。 事實上內建了許多 base classes 對許多 cryptographic primitives 含有 standard interfaces 像是 PKEnc(public-key encryption), PKSig(public-key signatures), ABEnc(attribute-based encryption) 等等。第一步是去繼承這些class (下面我們說明如何用 Charm 實現 Cramer-Shoup PKEnc scheme。)
在 charm toolbox 中每種 cryptographic setting 有一個對應的 group abstraction 像是前面提到的 elliptic curve group , pairing group, 和 integer groups。 這些 abstractions 提供了 convenient 且 simple 的界面來選擇 group parameters, 運算 group operations, 和 benchmarking.
接下來,針對所要實現的 cryptographic scheme 要 import 我們要實現相關的 group setting。
在 class initialization時,會呼叫 init, 在這個例子中會定義PKEnc基本的 security properties: 把 NIST standard elliptic curve identifier當成input。另外, 在這例子中,我們將 group object 定義為 global variable.
另一種方法是定義 group 為class member,例如: self.group = ECGroup(curve).
接下來看 Keygen, 他只接受一個 security parameter,然後產生 public 和 private keys 給 user, 注意這邊我們需要選一個 hash function H
encryption 在 paper中敘述如下,我們利用group的encode幫我們轉換message到運算domain
decryption 在 paper中敘述如下
這類scheme會將 messages 定義為 group element,故我們利用charm內建的 encode/decode methods 來將message轉換進入 G。 然而目前沒有支援直接轉進pairing group的 encode/decode。 因此將用別種方式來替代直接轉換
Reuse Tools
先在這邊找找看有沒有可用的工具吧! https://jhuisi.github.io/charm/toolbox.html#toolbox
Test and Benchmark
設計好shceme之後需要做驗證和量測performance。 charm提供了兩個 approaches:
Define a test routine that executes the algorithms in your scheme via test vectors if they exist a
embedding the test routine as a docstring in your scheme’s class definition.
Docstrings 可用下列方法直接執行!
python -m doctest myScheme.py
另外有下列benchmark flag可以使用: RealTime, CpuTime, Add, Sub, Mul, Div, and Exp. 以下是對 EC setting 使用 Charm 的 benchmark interface
以上的 benchmark function 也可以用在其他的 group settings。 pairing base module同樣支援 **granular level (operation count per group)**的 benchmark。 如下:
另外針對 integer module, 我們可以 benchmarking without a group object:
Optimization
針對 pairing base module, charm提供了 pre-computation tables 來加速 group exponentiation。 要使用的話,先呼叫 initPP()
method 在 pairing object in G1, G2, or GT 上。 initPP()
會儲存 pre-computed values。 見以下比較10次 exponential 有用和沒有用的差別
Implement Application
拉高一個 abstraction level 來看,我們可以在應用中拿內建的sheme(https://jhuisi.github.io/charm/schemes.html#schemes)。 每一個內建scheme都有example的main function吃 default的test。 因此我們可以看main來了解如何使用它, 底下為在application中使用 Cramer-Shoup scheme:
Serial API
為了支援 key或 ciphertext的 serialization,charm toolbox 中提供了兩個 high-level API 來 serialize charm objects (和 python structures (e.g., lists, tuples, or dictionaries, etc)做轉換) 亦即charm.core.engine.util
packag 中的 objectToBytes()
和 bytesToObject()
。 這些function可以將 keys 和 ciphertexts 轉換成 base 64 encoded strings。
以下說明如何使用 upported group objects (integergroup, pairinggroup or ecgroup)的這個 API:
若想要加入 custom serialization routine,以下說明 schemes based on the integergroup 如何在不需要 group object下達成: