## Pairing Based Cryptography

1. Arithmetic in $Z_p$: 可以建構在 GMP library 上 (提供了 number theoretic functions 像是 inversion modulo a prime 和 Jacobi symbol 等)

2. Elliptic curve groups: 解 $y^2=x^3+ax+b over Zp$, point addition 和 multiplication (可參考前一份notebook)

3. Bilinear pairing: Miller’s algorithm

## Introduction to Charm

### Group Abstractions

1. Integergroups
2. ecgroups
3. pairinggroups

In [ ]:
from charm.toolbox.integergroup import IntegerGroup

In [ ]:
group1 = IntegerGroup()
group1.paramgen(1024)

g = group1.randomGen()
g, type(g)

In [ ]:
dir(g)

In [ ]:
from charm.toolbox.pairinggroup import PairingGroup,ZR,G1,G2,GT,pair

In [ ]:
group2 = PairingGroup('SS512')
g1 = group2.random(G1)
g2 = group2.random(G2)

In [ ]:
g1, g2, type(g1)

In [ ]:
help(g1)

In [ ]:
type(g2)


### Implement a Scheme

In [ ]:
from charm.toolbox.PKEnc import PKEnc
from charm.toolbox.ecgroup import ECGroup

class CS98(PKEnc):
def __init__(self, curve):
PKEnc.__init__(self)
global group
group = ECGroup(curve)


$\begin{array}{c} g_1, g_2 \in G \\ x_1, x_2, y_1, y_2, z \in Z_q \\ c = g_1^{x_1} \cdot g_2^{x_2}, d = g_1^{y_1} \cdot g_2^{y_2}, h = g_1^z \\ pk = (g_1, g_2, c, d, h, H) \\ sk = (x_1, x_2, y_1, y_2, z) \end{array}$

In [ ]:
def keygen(self, secparam): # Security parameter only
g1, g2 = group.random(G), group.random(G)
x1, x2, y1, y2, z = group.random(ZR), group.random(ZR), group.random(ZR), group.random(ZR), group.random(ZR)
c = (g1 ** x1) * (g2 ** x2)
d = (g1 ** y1) * (g2 ** y2)
h = (g1 ** z)

pk = { 'g1' : g1, 'g2' : g2, 'c' : c, 'd' : d, 'h' : h, 'H' : group.hash } #dict class
sk = { 'x1' : x1, 'x2' : x2, 'y1' : y1, 'y2' : y2, 'z' : z }
return (pk, sk)


encryption 在 paper中敘述如下，我們利用group的encode幫我們轉換message到運算domain

$\begin{array}{c} m \in G, r \in Z_q \\ u_1 = g_1^r, u_2 = g_2^r, e = h^r \cdot m , \alpha = H(u_1, u_2, e), v = c^r \cdot d^{r\alpha} \\ (u_1, u_2, e, v) \end{array}$

In [ ]:
def encrypt(self, pk, m):
r   = group.random(ZR)
u1  = pk['g1'] ** r
u2  = pk['g2'] ** r
e   = group.encode(m) * (pk['h'] ** r)
alpha = pk['H'](u1, u2, e)
v   = (pk['c'] ** r) * (pk['d'] ** (r * alpha))

return { 'u1' : u1, 'u2' : u2, 'e' : e, 'v' : v }


decryption 在 paper中敘述如下

$\begin{array}{c} \alpha = H(u_1, u_2, e) \\ v = u_1^{x_1+y_1\alpha} \cdot u_2^{x_2+y_2\alpha} \\ m = e/{u_1^z} \end{array}$

In [ ]:
def decrypt(self, pk, sk, c):
alpha = pk['H'](c['u1'], c['u2'], c['e'])

v_prime = (c['u1'] ** (sk['x1'] + (sk['y1'] * alpha))) * (c['u2'] ** (sk['x2'] + (sk['y2'] * alpha)))
if (c['v'] != v_prime):
return 'reject'
return group.decode(c['e'] / (c['u1'] ** sk['z']))


## Reuse Tools

### Test and Benchmark

• 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

In [ ]:
from charm.toolbox.ecgroup import ECGroup,ZR,G
from charm.toolbox.eccurve import prime192v1

trials = 10
group = ECGroup(prime192v1)
g = group.random(G)
h = group.random(G)
i = group.random(G)

assert group.InitBenchmark(), "failed to initialize benchmark"
group.StartBenchmark(["Mul", "Div", "Exp", "Granular"])
for a in range(trials):
j = g * h
k = h ** group.random(ZR)
t = (j ** group.random(ZR)) / k
group.EndBenchmark()

msmtDict = group.GetGeneralBenchmarks()
print ("<=== General Benchmarks ===>")
print ("Mul := ", msmtDict["Mul"])
print ("Div := ", msmtDict["Div"])
print ("Exp := ", msmtDict["Exp"])
granDict = group.GetGranularBenchmarks()
print ("<=== Granular Benchmarks ===>")
print ("G mul   := ", granDict["Mul"][G])
print ("G exp   := ", granDict["Exp"][G])


In [ ]:
from charm.toolbox.pairinggroup import PairingGroup,ZR,G1,G2,GT,pair

trials = 10
group = PairingGroup("SS1024")
g = group.random(G1)
h = group.random(G1)
i = group.random(G2)

assert group.InitBenchmark(), "failed to initialize benchmark"
group.StartBenchmark(["Mul", "Exp", "Pair", "Granular"])
for a in range(trials):
j = g * h
k = i ** group.random(ZR)
t = (j ** group.random(ZR)) / h
n = pair(h, i)
group.EndBenchmark()

msmtDict = group.GetGeneralBenchmarks()
granDict = group.GetGranularBenchmarks()
print("<=== General Benchmarks ===>")
print("Results  := ", msmtDict)
print("<=== Granular Benchmarks ===>")
print("G1 mul   := ", granDict["Mul"][G1])
print("G2 exp   := ", granDict["Exp"][G2])


In [ ]:
from charm.core.math.integer import *
trials = 10
a = integer(1234)

assert InitBenchmark(), "failed to initialize benchmark"
StartBenchmark(["RealTime", "Exp", "Mul"])
for k in range(trials):
r = randomPrime(512)
s = r * (r ** a)
j = r * (r ** a)
EndBenchmark()

msmtDict1 = GetGeneralBenchmarks()
print ("General Benchmarks: ", msmtDict1)


## Optimization

In [ ]:
from charm.toolbox.pairinggroup import PairingGroup,ZR,G1,G2,GT,pair

count = 10
group = PairingGroup("MNT224")
g = group.random(GT)
assert g.initPP(), "failed to init pre-computation table"
h = group.random(GT)
a, b = group.random(ZR, 2)

assert group.InitBenchmark(), "failed to initialize benchmark"
group.StartBenchmark(["RealTime"])
for i in range(count):
A = g ** a
group.EndBenchmark()
print ("With PP: ", group.GetBenchmark("RealTime"))

assert group.InitBenchmark(), "failed to initialize benchmark"
group.StartBenchmark(["RealTime"])
for i in range(count):
B = h ** b
group.EndBenchmark()
print ("Without: ", group.GetBenchmark("RealTime"))


## Implement Application

In [ ]:
from charm.schemes.pkenc.pkenc_cs98 import CS98
from charm.toolbox.eccurve import prime192v1
from charm.toolbox.ecgroup import ECGroup

groupObj = ECGroup(prime192v1)
pkenc = CS98(groupObj)

(pk, sk) = pkenc.keygen()

M = b'Hello World!'
ciphertext = pkenc.encrypt(pk, M)

message = pkenc.decrypt(pk, sk, ciphertext)
(ciphertext, message)


### Serial API

from charm.core.engine.util import objectToBytes,bytesToObject

pk_bytes = objectToBytes(pk, group)
orig_pk = bytesToObject(pk_bytes, group)


from charm.core.math.integer import integer,serialize,deserialize

class mySerializeAPI:
def __init__(self)
...

def serialize(self, charm_object):
assert type(charm_object) == integer, "required type is integer, not: ", type(charm_object)
return serialize(charm_object)

def deserialize(self, object):
assert type(object) == bytes, "required type is bytes, not: ", type(object)
return deserialize(object)

from charm.core.engine.util import objectToBytes,bytesToObject

serObject = mySerializeAPI()
pk_bytes = objectToBytes(pk, serObject)
orig_pk = bytesToObject(pk_bytes, serObject)


## ABE example

In [6]:
from charm.schemes.abenc.abenc_bsw07 import CPabe_BSW07
from charm.toolbox.pairinggroup import PairingGroup,GT

debug = True
groupObj = PairingGroup('SS512')

cpabe = CPabe_BSW07(groupObj)
attrs = ['THREE', 'ONE', 'TWO']
access_policy = '((ONE or THREE) and (ONE or FOUR))'
if debug:
print("Attributes =>", attrs); print("Policy =>", access_policy)

(pk, mk) = cpabe.setup()

sk = cpabe.keygen(pk, mk, attrs)
print("sk :=>", sk)

rand_msg = groupObj.random(GT)
if debug: print("msg =>", rand_msg)
ct = cpabe.encrypt(pk, rand_msg, access_policy)

if debug: print("\n\nCiphertext...\n")
groupObj.debug(ct)

rec_msg = cpabe.decrypt(pk, sk, ct)
if debug: print("\n\nDecrypt...\n")
if debug: print("Rec msg =>", rec_msg)

assert rand_msg == rec_msg, "FAILED Decryption: message is incorrect"
if debug: print("Successful Decryption!!!")

Attributes => ['THREE', 'ONE', 'TWO'] Policy => ((ONE or THREE) and (ONE or FOUR)) sk :=> {'Djp': {'THREE': [6276122109109426287397553513575914468341027484366298497746300064132749253539980029132700773775447955442676300956836137281382181372546499724557459973369490, 1795476119287768441013887569705620933962494299668997391846792068958141096175304165244965706342723260232250086876889100253742624870810067037151552353031807], 'TWO': [6924124382980575830781490840630960273794342008751116574070665252364212195636192550742824655262852541846254965051425217574882536637642592616612155973395808, 8108426394656279258614966091821611038675838157480563425712989481381530945904325372340963087983567673593458303309907998087951849442207502323531761728168001], 'ONE': [6214922806147845959328072463238677155640067392726266903682243783876099942600904104773748970444727984510062636495191147198345655765522974854475074699791359, 4630962608250885034549832054036011242006941950537077468772236052050884033803703912105524225739004590799163049382175163833868849228617070716457437315420126]}, 'S': ['THREE', 'ONE', 'TWO'], 'D': [7687491133591300392489925937356671817531456966061948916229208833518845082633339153261975594982026586415308356033055153604299653858595474432396275243773000, 4318950466636556312032265562625647492326724869289831129174893034346195323582587562433111119245156322042479243840555644418535798917990151942743847383780563], 'Dj': {'THREE': [7994613409051727137522865580015029574772996843380828301599887126273613132844122913337590146469959657539996722785678494558443433149046454112274017506093854, 3905999273369170389289588280376602134461333515823066665811835708384759635246475375865644058077196138036701150784678481263701897912740609436813254212907645], 'TWO': [5035495247163564172284577618592484581014067962687230501105497707767536697578968095496011419373642480182091229748882502794990229017892287271693747171642159, 7768591754299435361319796433922437420175007293702926461217826123671734856797194686197706260013527009051827951196910300017586416653757940260645394794756086], 'ONE': [6805189749535456001264102735047759589342626779139275815700412176233753702347101696333559080054586606548573296648525732185009932900151431864903264736086416, 6695605871674387402119430197165256691216959425906221313196935410770986832136369820089136314801454730884042011993618575113141067457071896178035126718084789]}} msg => [5499530206739178687329483066235619442931659699977981155680587241526012324791607903651765803548056374589854867322721271855880337977684419674241327412344022, 1586884519471378212390281522967903086724330382922390165640139288304416399438221420818991375092282769535787961108438238586764989210068394126794331160644798] Ciphertext... Decrypt... Rec msg => [5499530206739178687329483066235619442931659699977981155680587241526012324791607903651765803548056374589854867322721271855880337977684419674241327412344022, 1586884519471378212390281522967903086724330382922390165640139288304416399438221420818991375092282769535787961108438238586764989210068394126794331160644798] Successful Decryption!!!
In [2]:
from charm.toolbox.pairinggroup import PairingGroup,ZR,G1,G2,GT,pair
from charm.toolbox.secretutil import SecretUtil
from charm.toolbox.ABEnc import ABEnc

class CPabe09(ABEnc):
"""
>>> from charm.toolbox.pairinggroup import PairingGroup,GT
>>> group = PairingGroup('SS512')
>>> cpabe = CPabe09(group)
>>> msg = group.random(GT)
>>> (master_secret_key, master_public_key) = cpabe.setup()
>>> policy = '((ONE or THREE) and (TWO or FOUR))'
>>> attr_list = ['THREE', 'ONE', 'TWO']
>>> secret_key = cpabe.keygen(master_public_key, master_secret_key, attr_list)
>>> cipher_text = cpabe.encrypt(master_public_key, msg, policy)
>>> decrypted_msg = cpabe.decrypt(master_public_key, secret_key, cipher_text)
>>> decrypted_msg == msg
True
"""

def __init__(self, groupObj):
ABEnc.__init__(self)
global util, group
util = SecretUtil(groupObj, debug)
group = groupObj

def setup(self):
g1, g2 = group.random(G1), group.random(G2)
alpha, a = group.random(), group.random()
e_gg_alpha = pair(g1,g2) ** alpha
msk = {'g1^alpha':g1 ** alpha, 'g2^alpha':g2 ** alpha}
pk = {'g1':g1, 'g2':g2, 'e(gg)^alpha':e_gg_alpha, 'g1^a':g1 ** a, 'g2^a':g2 ** a}
return (msk, pk)

def keygen(self, pk, msk, attributes):
t = group.random()
K = msk['g2^alpha'] * (pk['g2^a'] ** t)
L = pk['g2'] ** t
k_x = [group.hash(s, G1) ** t for s in attributes]

K_x = {}
for i in range(0, len(k_x)):
K_x[ attributes[i] ] = k_x[i]

key = { 'K':K, 'L':L, 'K_x':K_x, 'attributes':attributes }
return key

def encrypt(self, pk, M, policy_str):
# Extract the attributes as a list
policy = util.createPolicy(policy_str)
p_list = util.getAttributeList(policy)
s = group.random()
C_tilde = (pk['e(gg)^alpha'] ** s) * M
C_0 = pk['g1'] ** s
C, D = {}, {}
secret = s
shares = util.calculateSharesList(secret, policy)

# ciphertext
for i in range(len(p_list)):
r = group.random()
if shares[i][0] == p_list[i]:
attr = shares[i][0].getAttribute()
C[ p_list[i] ] = ((pk['g1^a'] ** shares[i][1]) * (group.hash(attr, G1) ** -r))
D[ p_list[i] ] = (pk['g2'] ** r)

if debug: print("SessionKey: %s" % C_tilde)
return { 'C0':C_0, 'C':C, 'D':D , 'C_tilde':C_tilde, 'policy':policy_str, 'attribute':p_list }

def decrypt(self, pk, sk, ct):
policy = util.createPolicy(ct['policy'])
pruned = util.prune(policy, sk['attributes'])
if pruned == False:
return False
coeffs = util.getCoefficients(policy)
numerator = pair(ct['C0'], sk['K'])

# create list for attributes in order...
k_x, w_i = {}, {}
for i in pruned:
j = i.getAttributeAndIndex()
k = i.getAttribute()
k_x[ j ] = sk['K_x'][k]
w_i[ j ] = coeffs[j]
#print('Attribute %s: coeff=%s, k_x=%s' % (j, w_i[j], k_x[j]))

C, D = ct['C'], ct['D']
denominator = 1
for i in pruned:
j = i.getAttributeAndIndex()
denominator *= ( pair(C[j] ** w_i[j], sk['L']) * pair(k_x[j] ** w_i[j], D[j]) )
return ct['C_tilde'] / (numerator / denominator)

In [3]:
from charm.toolbox.pairinggroup import PairingGroup,GT
debug = True
group = PairingGroup('SS512')
cpabe = CPabe09(group)
msg = group.random(GT)
(master_secret_key, master_public_key) = cpabe.setup()
policy = '((ONE or THREE) and (TWO or FOUR))'
attr_list = ['THREE', 'ONE', 'TWO']
secret_key = cpabe.keygen(master_public_key, master_secret_key, attr_list)
cipher_text = cpabe.encrypt(master_public_key, msg, policy)
decrypted_msg = cpabe.decrypt(master_public_key, secret_key, cipher_text)
decrypted_msg == msg

SessionKey: [4897898898501355351683453535780272251374740691648870523298963161176459049718631704623165917580790112782364738858654913088188127564635790942994867351641166, 5594148607004606790445539725307269743280460162251313297488780598171706543996991704109849456242130630540511011310380099671661836103996130031750688538585740]
True

## Appendix - CryptoBase

In [7]:
from charm.toolbox.paddingschemes import PKCS7Padding
from charm.toolbox.securerandom import OpenSSLRand
from charm.core.crypto.cryptobase import MODE_CBC,AES,selectPRP
import json
from base64 import b64encode,b64decode

class SymmetricCryptoAbstraction(object):
"""
Abstraction for symmetric encryption and decryption of data.
Ideally provide an INDCCA2 secure symmetric container for arbitrary data.
Currently only supports primitives that JSON can encode and decode.

A large number of the schemes can only encrypt group elements
and do not provide an efficient mechanism for encoding byte in
those elements. As such we don't pick a symmetric key and encrypt
it asymmetrically. Rather, we hash a random group element to get the
symmetric key.
>>> from charm.toolbox.pairinggroup import PairingGroup,GT
>>> groupObj = PairingGroup('SS512')
>>> from charm.core.math.pairing import hashPair as extractor
>>> a = SymmetricCryptoAbstraction(extractor(groupObj.random(GT)))
>>> ct = a.encrypt(b"Friendly Fire Isn't")
>>> a.decrypt(ct)
b"Friendly Fire Isn't"
"""

def __init__(self,key, alg = AES, mode = MODE_CBC):
self._alg = alg
self.key_len = 16
self._block_size = 16
self._mode = mode
self._key = key[0:self.key_len]

def _initCipher(self,IV = None):
if IV == None :
IV =  OpenSSLRand().getRandomBytes(self._block_size)
self._IV = IV
return selectPRP(self._alg,(self._key,self._mode,self._IV))

def __encode_decode(self,data,func):
data['IV'] = func(data['IV'])
data['CipherText'] = func(data['CipherText'])
return data

#This code should be factored out into  another class
#Because json is only defined over strings, we need to base64 encode the encrypted data
# and convert the base 64 byte array into a utf8 string
def _encode(self,data):
return self.__encode_decode(data,lambda x:b64encode(x).decode('utf-8'))

def _decode(self,data):
return self.__encode_decode(data,lambda x:b64decode(bytes(x,'utf-8')))

def encrypt(self, message):
#This should be removed when all crypto functions deal with bytes"
if type(message) != bytes :
message = bytes(message,"utf-8")
ct = self._encrypt(message)
#JSON strings cannot have binary data in them, so we must base64 encode  cipher
cte = json.dumps(self._encode(ct))
return cte

def _encrypt(self,message):
#Because the IV cannot be set after instantiation, decrypt and encrypt
# must operate on their own instances of the cipher
cipher = self._initCipher()
ct= {'ALG':self._alg,
'MODE':self._mode,
'IV':self._IV,
}
return ct

def decrypt(self,cipherText):
return self._decrypt(self._decode(f)) #.decode("utf-8")

def _decrypt(self,cipherText):
cipher = self._initCipher(cipherText['IV'])
msg = cipher.decrypt(cipherText['CipherText'])

from charm.toolbox.pairinggroup import PairingGroup,GT