浏览器环境下的双线性映射运算实现
1.      背景
双线性映射是现代密码学中的常⽤数学⼯具，经常被⽤来构造包括基于⾝份加密在内的各种密码算法。笔者近⽇开发的⼀款B/S架构⽀持基于⾝份加密和关键字可搜索加密的邮件系统就使⽤到了双线性映射，⽽通过搜索，发现浏览器中的常⽤前端语⾔JavaScript并没有提供⽂档与功能齐全的⽀持双线性映射的代码库可供使⽤。为了使开发⼯作可以正常进⾏，笔者另寻他路解决了这个问题，最终可以在Chrome 浏览器实现需要的加密算法，本⽂就记录了问题的解决过程。但是这个解决⽅案并不通⽤，⽬前仅能在FireFox和Chrome浏览器中使⽤，在IE和Edge浏览器中则需要使⽤另外的技术。
1.1.  双线性映射
双线性映射的定义⼗分抽象，这⾥仅对其做简单介绍。
1.1.1.  定义
设G1、G2、G T都是阶p为素数的循环，如果映射e:G1xG2→G T满⾜如下性质：
1、双线性：对于任意的g1∈G1，g1∈G1，a,b∈Z p，均有e(g1a,g2b)=e(g1,g2)ab成⽴；
2、⾮退化性：∃g1∈G1和g2∈G2，满⾜e(g1,g2)≠1GT；
3、可计算性：存在有效的算法，对于∀g1∈G1，g2∈G2，均可计算e(g1,g2)。
如果G1和G2相同，就称双线性映射e是对称的，否则称其为⾮对称的。
另外，上述双线性映射中各是素数阶的，其实在2005年boneh也实现了合数阶的双线性映射，具体可以参考⽂献[1]。
1.1.
2.  使⽤场景
双线性映射在现代密码学中应⽤⼴泛，⽐如基于⾝份加密[2]、基于属性加密[3]、组密钥分配协议[4]、基于属性签名[5]和公钥可搜索加
密[6]。可以看到双线性映射对于现代密码学是多么重要。
1.1.3.  常⽤的函数库
⽬前有⾮常多的函数库提供了双线性映射的计算功能，如笔者最常⽤的PBC Library[7]，这是⼀个开源
的C语⾔项⽬。此外还有C语⾔的Miracl[8]、Relic[9]，Java的jPBC[10]等。这些函数库都可以从互联⽹上进⾏下载并使⽤。
1.2.  浏览器
浏览器的编程环境⽐较单⼀，不像客户端或服务器开发中那样可以使⽤多种开源软件以及系统调⽤，因此其中的编程⽅式选择也很匮乏。
1.2.1.  编程环境及不⾜
浏览器中的编程环境，主要是前端语⾔HTML和JavaScript，对于FireFox和Chrome来说，还可以使⽤C++开发Native Client，对于IE来说可以使⽤C#或者C++开发ActiveX空间。其中Native Client中的代码主要是平台⽆关代码，其作⽤更多的是优化⽹页中特定组件的运⾏速度，如实时3D动画等。
对于HTML来说，其主要作⽤是绘制⽹页内容，并不具备执⾏复杂内容的能⼒；对JavaScript来说，存在⾯向JavaScript的双线性映射运算库jspairing[11]，但是其已多年⽆⼈维护，并且缺乏⽂档和教程，缺少实⽤性；对Native Client来说，其更多的是⾯向代码的可移植性，对于已有代码的兼容性以及系统中动态库的调⽤流程没有过多考虑；⽽ActiveX技术则⾮常古⽼，其只对Windows平台中的IE浏览器兼容，并且缺乏⾜够的⽂档和教程。因此这些技术都被⼀⼀否定。
1.2.2.  其他选项
直接编写浏览器可⽤的功能代码是⾏不通的，那么就只能考虑其他选项了。这⾥我的选择是使⽤由FireFox和Chrome兼容的Native Messaging[12]技术。这项技术允许浏览器中的JavaScript代码与操作系统中的应⽤程序进⾏通信，从⽽实现调⽤操作系统中程序功能的⽬的。如果使⽤这项技术，就可以在应⽤程序中提供基于双线性映射的密码算法的底层功能，并由JavaScript实现上层接⼝，从⽽在浏览器中实现双线性映射的功能。
2.      ⽅案实现
虽然Native Messaging可以帮助我们实现想要的功能，但是其本⾝的编程规范较为复杂，并且编程过程中需要注意的地⽅也很多，因此整个⽅案实现起来⽐较⿇烦。这⾥使⽤Chrome浏览器的Native Messaging技术来进⾏实现，理论上Firefox也是兼容这套技术的，但是有些细节部分需要修改，这其中的细节笔者没有去求证。
2.1.  架构
Chrome的Native Messaging技术是依托于浏览器扩展的，也就是说与本地应⽤程序直接进⾏通信的是浏览器中的扩展程序，⽽⽹页中的JavaScript代码通过与扩展程序通讯，来对本地应⽤程序进⾏间接调⽤。其整个通信框架如图 1所⽰。
图 1 Native Messaging的通信框架[13]
从图中，可以看到，⽹页⾸先向浏览器扩展发送请求，接着扩展向本地应⽤程序发送请求，当本地应⽤程序将请求数据返回给扩展后，扩展再将请求结果返回给⽹页。因此在整个⽅案实现中，需要进⾏三个部分的开发：本地应⽤程序、浏览器扩展和⽹页代码。
2.2.  通信⽅式
在开始开发⼯作之前，⾸先要确定浏览器扩展与本地应⽤之间的通信⽅式，以确定通信的具体数据结构以及封装形式，并及早确定所选编程语⾔，避免后⾯遇到问题。
根据Native Messaging的官⽅⽂档，浏览器扩展和本地应⽤程序之间使⽤标准输⼊输出进⾏通信，通信的数据必须是JSON格式，并且本地应⽤程序在读取数据的时候，会先从标准输⼊中读取⼀个4字节的⼆
进制数据，其代表后续JSON数据的长度；同样地，本地应⽤程序在向浏览器扩展返回结果时，也会先向标准输出中写⼊返回的数据的总长度，再将整个数据写⼊到标准输出中。同时，因为JSON数据格式不⽀持⼆进制字符，因此需要对通信过程中的⼆进制数据进⾏Base64编码。
2.3.  底层库编译
因为⾮常熟悉PBC的⽤法和⽂档，以及我⼿头上还有⽐较多的PBC代码，因此这⾥我选择PBC作为底层的函数库来使⽤。PBC的官⽅下载地址为，可以看到官⽅提供了源代码以及编译好的win32平台⼆进制dll⽂件。但是由于官⽅没有提供该⼆进制⽂件对应的符号⽂件，因此没有办法直接使⽤它来进⾏编程，因此需要⾃⼰动⼿进⾏编译。
在编译时使⽤MinGW32环境，这⾥说明⼀下，即使平台是64位Windows，也要使⽤32位的MinGW来进⾏编译，否则编译好的PBC库的数据输⼊输出会存在问题。
⾸先从中科⼤的开源软件站下载最新的msys2安装包，接着⼀路点击下⼀步进⾏安装，安装完毕后，启动⽂件，并在弹出的shell窗⼝中输⼊以下命令，安装解压和编译gmp⼤数运算库所需的软件：
pacman –S mingw-w64-i686-gcc make  mingw-w64-i686-gdb xzip
接着从下载最新的gmp⼤数运算库。解压后从MinGW32 Shell进⼊其解压的⽬录。依次执⾏命令
./configure --enable-shared --disable-static
make
make install
来将gmp库编译为动态链接库dll，并将其安装到MinGW32的相关⽬录中。
编译完gmp后，执⾏命令
pacman –S flex bison
来安装编译pbc所需的软件，pbc的源码及依赖⽂件准备就绪后，就可以像gmp库⼀样依次执⾏命令
./configure --enable-shared --disable-static
make
make install
来将其编译为动态链接库并安装到MinGw32的相关⽬录中了。
2.4.  本地应⽤程序底层代码
本地应⽤程序分为两个部分：底层函数库和Python接⼝层。其中底层函数库使⽤C语⾔编写，Python接⼝层使⽤Python语⾔编写。这⾥就有两种实现⽅式：
1. 将底层函数库编译为DLL动态连接库，通过Python的ctypes进⾏调⽤；
2. 将底层函数库编译为Python模块，直接由Python来进⾏调⽤。
这两种⽅法中，第⼆种⽅法更加便捷，但是实现起来问题⽐较多，这⾥我将重点介绍第⼀种⽅法，第⼆种⽅法我会介绍⼀下要注意的地⽅。
2.4.1.  使⽤ctypes
ctypes是python内置的⾮常有⽤的模块，它能够赋予Python直接调⽤外部动态链接库的能⼒，并且提供了多种C语⾔数据类型，是利⽤Python兼容调⽤已有代码的⾮常好的⼯具。
这⾥挑选⼀个典型的函数来进⾏举例讲解。
设有⼀个C语⾔结构体和⼀个函数
typedef struct IBECipher_
{
unsigned char *cip1, *cip2;
int cip1_len, cip2_len;
} IBECipher;
int generate_ibe_cipher(char *receiver, IBECipher *cip, unsigned char *aes_key, int *aes_key_len);
其中结构体IBECipher中的cip1和cip2以及aes_key都是⽤于输出的，其所指空间在函数调⽤前就已经分配完毕，并且全部都是⼆进制数据。⽽receiver是传⼊的以NULL结尾的ASCII字符串，aes_key_len是指向⼀个整数的指针，⽤来表明aes_key的字节长度。
⾸先，要将包含函数generate_ibe_cipher的C语⾔实现⽂件编译为动态链接库。假设其⽂件名为foo.c，那么使⽤gcc来将其编译为动态链接库的命令为
gcc -shared foo.c -o foo.dll
这个命令会产⽣名为foo.dll的动态链接库，供其他程序调⽤了。
那么为了在Python中利⽤ctypes调⽤这个函数，还需要需要模拟4种数据结构：整数指针、以NULL结尾的C语⾔字符串、⼆进制缓冲区和C语⾔结构体。这⾥要说明的是，在C语⾔中，以NULL结尾的字符串与⼆进制缓冲区的表达都是字节数组，但是在python中两者是不⼀样的，因为⼆进制缓冲区中的数据是可能存在NULL字符的，此时如果将其看做以NULL结尾的字符串，就会导致数据的截断，从⽽造成错误。这四种C语⾔数据结构在Python中的表⽰为：
1、整数指针
整数指针⾮常简单，就是指向整数的指针，使⽤ctypes来表达的话，就是这样的
from ctypes import POINTER, c_int32
p_int = POINTER(c_int32)
其中p_int是⼀个整数指针的类型，如果要使⽤这个类型，需要⽤⼀个c_int32型的变量来对它进⾏初始化，也就是这样的
p_some_int = p_int(c_int32())
这样，p_some_int就是⼀个指向某个整数的指针了。
2、以NULL结尾的C语⾔字符串
以NULL结尾的C语⾔字符串⾮常简单，它在ctypes中的类型是c_char_p，如果将某个已有的Python字符串转换为以NULL结尾的C语⾔字符串，代码也⾮常简单
from ctypes import c_char_p
some_str = 'This is som string'
p_some_ptr = c_char_p(some_str)
3、⼆进制缓冲区
前⾯说过，在C语⾔中⼆进制缓冲区和字符串没有本质上的区别，但是在Python中，这两者是有区别的，因为C语⾔字符串会被从NULL 处截断。因此，为了与动态链接库交换任意⼆进制数据，就不能使⽤c_char_p来直接从Python中的字节数据来构造，⽽要使⽤另⼀个数据类型——字节数组。在ctypes中，定义⼀个数组类型⾮常简单，⽐如要定义⼀个有64个字节的整形数组，代码如下
from ctypes import c_int32
arr_64 = c_int32*64
这⾥的arr_64是⼀个数组类型，其中有64个整形元素。如果要定义⼀个此类型的变量，就直接使⽤代码
arr = arr_64()
这会将arr中所有的元素初始化为0，当然也可以提供部分初始化值，⽐如
arr = arr_64(1,2,3,4,5)
这会将arr中的前5个元素分别初始化为1,2,3,4,5.并且字节数组中的元素在Python中⽀持按下标读写，特别⽅便。那么定义字节数组的⽅式与定义整形数组的⽅式也是⼀样的
from ctypes import c_ubyte
arr_byte = c_ubyte*128
这个代码定义了长度为128字节的字节数组类型，如果要使⽤它就直接像使⽤整形数组那样就好
4、C语⾔结构体
ctypes也提供了定义C语⾔结构体的功能，以上⾯的IBECipher为例，在Python中，它的定义为
from ctypes import Structure, POINTER, c_ubyte, c_int32
class IBECipher(Structure):
_fields_ = [
("cip1", POINTER(c_ubyte)),
("cip2", POINTER(c_ubyte)),
("cip1_len", c_int32),
("cip2_len", c_int32)
]
p_IBECipher = POINTER(IBECipher)
就是说，结构体在ctypes中的定义是ctypes中Structure类的⼦类，并且⾃⼰按需填充其_feilds_字段就可以了。
chrome浏览器最新版
接下来，就是要⽤ctype调⽤编译好的foo.dll中的函数了，代码如下
from ctypes import CDLL, PONTER, c_ubyte, c_int32, c_char_p, Structure
dll_lib = CDLL('foo.dll')
receiver = c_char_p('receiver')
ibe_cipher = IBECipher()
ibe_cipher.cip1 = arr_byte()
ibe_cipher.cip2 = arr_byte()
aes_key = arr_byte()
aes_key_len = PONTER(c_int32)(c_int32())
ate_ibe_cipher(receiver, PONTER(IBECihper)(ibe_cipher), aes_key, aes_key_len)
执⾏完毕后就可以从ibe_cipher和aes_key中获取输出结果了。
这个⽅法的缺点是要对dll_lib中的函数进⾏封装，优点是可以直接使⽤现有的dll⽂件，⽽不需要专门为Python编写相应的版本。
如果要将编译好的dll模块拷贝出来，在MinGW32环使⽤，就需要将该dll以及它依赖的dll全部拷贝出来，这其中，出来gmp和pbc等编程库之外，还要拷贝libgcc_s_dw2-1.dll和libwinpthread-1.dll这两个MinGW32本⾝的依赖⽂件。
2.4.2.  编译为Python模块
将C语⾔代码编译为Python模块的⽅法，在⽹上有⾮常多的参考资料，基本上都是使⽤Python的模块，编写Setup⽂件来编译安装模块的，但是在Windows平台上，就会出现⼏个问题：
1、所⽤编译器版本与当前系统中编译器的版本不匹配，不到所需的lib导⼊库⽂件；
2、⽆法⾃动调⽤Visual Studio编译器；
3、没有安装Visual Studio编译器，⽆法编译。
也就是说，如果使⽤默认的⽅法，就需要安装对应版本的Visual Studio编译器或者对应版本的SDK，并且还要保证不出各种奇奇怪怪的错误。因此，这⾥介绍使⽤MinGW32中的gcc来编译模块的⽅法。
⾸先进⼊要使⽤的Python的安装⽬录，进⼊Lib/distutils⼦⽂件夹，到cygwinccompiler.py⽂件，到
if msc_ver == ‘1300’:
# MSVC 7.0
returen [‘msvcr70’]
这⼀⾏，然后在这个判断语句中添加缺少的版本的判断，⽐如1900，并且将列表中的字符串msvcr*替换为任意可在MinGW32中到的库，⽐如gmp。我这⾥的⽂件替换后的代码为
msc_pos = sys.version.find('MSC v.')
if msc_pos != -1:
msc_ver = sys.version[msc_pos+6:msc_pos+10]
if msc_ver == '1300':
# MSVC 7.0
return ['msvcr70']
elif msc_ver == '1310':
# MSVC 7.1
return ['msvcr71']
elif msc_ver == '1400':
# VS2005 / MSVC 8.0
return ['msvcr80']
elif msc_ver == '1500':
# VS2008 / MSVC 9.0
return ['msvcr90']
elif msc_ver == '1600':
# VS2010 / MSVC 10.0
return ['msvcr100']
elif msc_ver == '1900':
return ['gmp']
else:
raise ValueError("Unknown MS Compiler version %s " % msc_ver)
此时，再在MinGW32的shell中利⽤此Python来执⾏编译安装所⽤的setup⽂件，并传⼊参数--compiler=mingw32，即可完成编译，具体的命令⾏为
'/c/Program Files (x86)/' setup.py build --compiler=mingw32
此时可在⽣成的build⼦⽬录中的lib.w32-3.6⽬录中到编译好的pyd⽂件，将此pyd⽂件与其依赖的动态链接库⼀起拷贝到对应的Python根⽬录，就可以直接在Python中导⼊其中内容了。
2.5.  本地应⽤程序接⼝代码、浏览器扩展和⽹页JavaScript
关于本地应⽤程序接⼝代码、浏览器扩展和⽹页JavaScript的编写，可以参考⾕歌官⽅的教程，地址是，
这个教程中的本地应⽤程序也是Python编写的，因此与上⾯介绍的内容是很吻合的。这⾥只说⼏个很容易踩坑的地⽅：
1、启动本地应⽤程序的bat脚本，⼀定要在开头加上@echo off命令，因为脚本与浏览器扩展之间是通过标准输⼊与标准输出进⾏数据交换的，因此如果不关闭脚本的回显功能，那么脚本产⽣的输出就会被传递给本地应⽤程序，造成错误；
2、浏览器与本地应⽤程序之间交换的JSON数据必须是JSON的数组或者字典结构，不能单独传递数字或者字符串，并且具体的JSON内容与意义是由⾃⼰设计的；
3、在进⾏数据的读取和写⼊时，⼀定要先读写4个字节长度的数据长度整数值，这样好确定后续数据的长度，并能避免出错；
4、⽹页向浏览器扩展传递请求信息时，提供的JavaScript回调函数是⼀次性的，即最多只能使⽤⼀次，并且默认情况下，其⽣命周期是在浏览器扩展内的MessageExternal.addListener中注册的函数的内部，如果要想保留该回调函数，以等待处理结果产⽣后再返回数据，就要让函数返回true值，并且即使如此，该回调函数也只能调⽤⼀次；
5、为了让⽹页调⽤浏览器扩展，需要提供浏览器扩展的ID，这个ID是在chrome在Debug下安装该扩展后就⾃动分配的，在扩展页⾯可以看到。
这样⼀来就可以通过由浏览器扩展中转请求的⽅式来在浏览器环境下实现双线性映射运算了。
参考⽂献
[1] Boneh, Dan, Eu-Jin Goh, and Kobbi Nissim. "Evaluating 2-DNF formulas on ciphertexts." Theory of Cryptography Conference. Springer, Berlin, Heidelberg, 2005.
[2] Boneh, Dan, and Matt Franklin. "Identity-based encryption from the Weil pairing." Annual international cryptology conference. Springer, Berlin, Heidelberg, 2001.
[3] Goyal, Vipul, et al. "Attribute-based encryption for fine-grained access control of encrypted data." Proceedings of the 13th ACM conference on Computer and communications security. Acm, 2006.
[4] Lee, Sangwon, et al. "An efficient tree-based group key agreement using bilinear map." International Conference on Applied Cryptography and Network Security. Springer, Berlin, Heidelberg, 2003.
[5] Shanqing, Guo, and Zeng Yingpei. "Attribute-based signature scheme." Information Security and Assurance, 2008. ISA 2008. International Conference on. IEEE, 2008.
[6] Boneh, Dan, et al. "Public key encryption with keyword search." International conference on the theory and applications of cryptographic

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。