面向代理重加密算法的程序設計語言研究

蘇铓，俞研，吳檳，付安民

（1. 南京理工大學計算機科學與工程學院，江蘇 南京 210094；2. 中國科學院信息工程研究所信息安全國家重點實驗室，北京 100093；3. 中國科學院大學網絡空間安全學院，北京 100049）

1 引言

云計算等復雜網絡環境的發展，推動了數據共享和互聯等相關技術的進步，越來越多的用戶開始通過網絡進行數據的傳輸和分發，其中，包含了大量隱私數據、機密數據的不可信的云存儲環境增大了用戶共享的難度，各類外包計算和云應用需求給人們帶來了隱私泄露的風險[1]。為了確保該類數據的安全使用，保障用戶和服務提供商雙方的權益，數據加密和簽名的相關技術被廣泛應用。代理重加密是眾多的密碼技術之一，其依托于公鑰密碼加密的思想，采用公私鑰對的形式進行秘密數據的發布和使用，基于其技術特點，密鑰的產生可以由代理服務器進行處理，在實現共享的同時，減輕數據分享者的計算量[2]，這對于云這類用戶眾多、密鑰計算量巨大的系統來說至關重要，因此，受到眾多云計算安全研究人員的青睞。

代理重加密技術的研究涉及密碼算法的設計和實現這2個方面，密碼算法的研究和設計者多為密碼學家或數學領域工作者，其描述的算法從數學理論方面進行分析和證明，在理論層面對其進行安全性分析，依托線性對、有限域等數學理論。算法一般采用形式化的方式進行描述，安全性證明則通過隨機語言、標準等模型，基于“挑戰—應答”的機制。算法在實現與具體應用時，需要針對具體系統進行程序代碼編寫，該方面的研究人員多為計算機專業，依托于程序設計理論，對于算法的描述通常采用流程圖、偽代碼等形式進行，最終編寫具體程序語言代碼。這個過程中除了關注數學理論外，更加注重數據定義、程序邏輯結構等方面，例如，數學語言使用無符號字符數組定義明文數據，而不是使用假設變量進行描述。

針對密碼算法的實現問題，主流研究思想是通過開發開源密碼算法代碼庫，為廣大算法研究人員提供支持。目前，對于對稱密碼、非對稱密碼等傳統密碼算法均有對應的開源代碼庫，例如，crypto++[3]提供了 C++版本的多種傳統密碼算法的實現接口，包含 AES、RC6、MARS、Twofish、RSA、ECC等，同時兼顧密鑰分發、散列函數等多個方面。結合SSL協議的特點，OPENSSL開源代碼庫為用戶提供了對稱加解密、數字簽名等相關傳統密碼的應用接口。上述代碼庫提供了針對傳統密碼學算法的實現，對于目前的屬性基加密、雙線性對理論并未提供支持。為此，文獻[4]設計并實現了針對雙線性對的C語言代碼庫PBC Library，提供了雙線性對相關的定義、計算等數學運算的計算機代碼。PBC為用戶提供了基本的群、有限域等運算，同時實現了線性對相關的運算，為廣大密碼研究人員的算法實現提供了重要程序基礎[5]。隨著各類計算機編程語言的發展，PBC不再局限于C語言，出現了針對Java的JPBC、針對Python的版本，將PBC的C語言接口進行了進一步封裝，使用起來更加便利，面向的操作系統也涉及Windows、Linux等。更進一步，針對代理重加密，文獻[6]提出了開源代碼庫PRL，通過C++或C語言進行代理重加密的基本核心代碼，并且在不斷擴充算法。PBC、PRL等的出現在很大程度上方便了研究人員的算法實現與測試，但是PBC具體程序的編寫過程中仍然需要熟悉具體程序語言、進行數組定義、明確內存空間分配原則等，這些對于密碼算法設計人員仍然是一項不小的挑戰。

上述研究成果與開源庫為密碼算法實現提供了重要的編程工具，但是，這些開源工具一般基于指定的程序設計語言，要求使用者能夠熟練地進行計算機語言的使用，給密碼算法的設計者帶來使用上的困難，進而導致密碼算法的性能和安全性測試分析脫離具體系統環境，停留在數學理論層面；而計算機編程人員雖然熟知程序設計，但是對密碼算法設計中所包含的數學理論和描述較為陌生，在具體實現的過程中容易出現應為理解的偏差導致的實現與設計脫節的問題。上述問題是目前包含代理重加密算法等一系列密碼算法設計與測試面臨的主要困境。

領域專用語言（DSL, domain specific language）有別于通用程序設計語言，其針對具體的領域和問題，例如，HTML、SQL、YACC等，這類語言在使用過程中，不需要使用者關注過多的計算機實現細節，更加接近人類的自然語言或數學描述語言，為此DSL被引入密碼算法的描述和實現中[7]。Cryptol就是其中的代表之一，用于指定加密算法的特定域語言。其設計之初是用來表達各類加密算法，以便可以有效地應用到硬件電路上，后來不斷地被用于軟件設備上，可行度較高。Cryptol與平臺無關，側重算法的具體實現，其描述規則類似于算法的數學描述[8]。Cryptol在密碼算法描述和實現方面被廣泛應用于安全性和正確性的證明和測試[9-10]，但是該語言在直觀性上仍然有待提高。文獻[11]針對對稱密碼算法的特點，提出一種面向分組密碼算法的程序設計語言PLBCA，并針對DES算法進行了描述，該語言定義了變量、控制結構、置換函數等元素，對于對稱密碼算法能夠進行類數學語言的描述，并基于ANTLR（another tool for language recognition）進行了實現，通過ANTRL的解釋，最終對對稱密碼算法進行實現。PLBCA的思想即為密碼學家提供密碼算法正確性和安全性分析的具體實現途徑，描述簡明直觀。上述DSL語言在密碼算法實現方面的研究為代理重加密的算法實現提供了重要的理論支撐，若將DSL語言引入代理重加密的算法實現中，就為算法設計人員提供了一個類似數學語言的編程描述工具，搭建了一座算法設計與編程實現的橋梁。

本文針對上述代理重加密研究過程中面臨的問題，提出一種針對代理重加密算法的程序設計語言（PLPRE, programming language for proxy re-encryption），通過近乎數學語言的方式對代理重加密算法進行描述，并借助ANTLR工具[12]對描述程序進行解析，產生對應的計算機語言代碼，既能夠適用于密碼學家描述，又能夠與計算機編程語言無縫對接。這有利于算法研究人員的交流和算法實際性能的測試與分析，減輕算法研究人員的計算機編程難度，同時避免計算機編程人員由于數學理論陌生而導致的實現偏差，將推動代理重加密理論在各類系統的廣泛應用。

2 PLPRE相關介紹

PLPRE語言設計的初衷在于為密碼研究人員提供一種面向重加密算法的專業程序設計語言，使密碼學專家能夠以近乎自然語言或數學語言的方式和思維進行算法的描述，以表述算法思想和過程。在 PLPRE語言的研究過程中，一方面需要分析各類代理重加密算法的基本步驟，提取共性特點，并進行抽象的表達；另一方面，需要定義針對雙線性對等理論和重加密算法的專用符號和運算。另外，PLPRE的語法結構要盡量簡單、明確、易于表達，同時要兼容PBC等開源代碼庫，實現代理重加密算法設計與實現的無縫對接。

2.1 范式定義

PLPRE采用BNF范式的形式進行基本的語法規范描述，具體范式如下。

＜program＞::=＜definition_list＞＜program_block＞

＜definition_list＞::=“/def”＜definition_seq＞“def”

＜definition_seq＞::={＜definition＞}

＜definition＞::=＜var＞“(”＜expression＞“)”“；”|＜modular_dec＞“；”

＜modular_dec＞::=＜var＞“(”＜para_list＞“)”

＜para_list＞::=＜var＞*(“,”＜var＞)|empty

＜program_block＞::=“/start”＜function_list＞“end”

＜function_list＞::={＜function＞}

＜function＞::=“/method”＜function_name＞“(”＜para_list＞“)”“＜function_block＞”“method”

＜function_name＞::=“Setup”|“KeyGen”|“Enc”|“ReKeyGen”|“ReEnc”|“Dec”|“main”

＜function_block＞::={＜statement＞}|empty

＜statement＞::=＜expressions＞|＜modulars＞|

＜loops＞|＜selections＞|＜sub_fun＞

＜expressions＞::=＜expression＞“；”

＜modulars＞::=＜modular_dec＞“；”

＜loops＞::=“/loop”“(”＜expression＞“；”“step=”

＜simple_expression＞“；”“until=”＜expression＞“)”

＜statement＞“loop”＜selections＞::=“/if ”“(”＜expression＞“)”“then” ＜statement＞“if ”|“/if ”“(”＜expression＞“)”“then” ＜statement＞“else”＜statement＞“if ”

＜sub_fun＞::=＜sfun_name＞“(”＜para_list＞“)”

＜sfun_name＞::=“Prime”|“Group”|“Generator”|“e”|“random”

＜expression＞::=＜var＞“=” ＜expression＞|＜simple_expression＞

＜simple_expression＞::=＜var＞＜op＞＜var＞|＜modular_dec＞

＜op＞::=^|@|“xor”|==|!=

＜var＞::=＜ALPHA＞*(＜ALPHA＞|＜DIGIT＞|“_”)

＜ALPHA＞::=%x41-5A|%x61-7A

＜DIGIT＞::=%x30-39s

2.2 PLPRE語法

2.2.1 程序結構

PLPRE的程序主要包含定義、主體、注釋3個部分。

定義部分用于對算法描述過程中涉及的變量或常量進行定義、對變量進行初始賦值等。定義以“/def”表示開始定義，以“def”表示結束定義，該部分等同于其他程序語言中的聲明、變量定義的部分，對于代理重加密算法描述，定義的內容包含群、域、生成元、大素數等數學相關變量定義以及明文、密文等內容的定義，是必選部分。

主體部分以“/start”關鍵字標識主體描述開始，以“end”關鍵字標識主體描述結束，主要用于代理重加密的算法描述，包含初始化、加密、重加密、密鑰生成、重加密密鑰生成、解密等主要函數過程，算法的描述可以使用普通的文本編輯進行，采用純文本格式，算法描述以“行”為單位，以“；”標識“行”的結束。

注釋部分是對定義、主體部分內容的附件說明，與現有程序設計語言的注釋功能類似，單行以“//”標識開始，內容不能跨行；多行則以“/*”標識開始，“*/”標識截止，可以跨行。

2.2.2 關鍵字

PLPRE需要關鍵字實現具體描述，關鍵字包括描述類、控制類和函數類，其中，描述類包含def、method、sfun、bits、start、end 等，分別用于表示變量或常量定義、函數描述起始、子函數調用、數據位數定義、描述主體開始、描述主體結束；函數類包含 Setup、KeyGen、Enc、ReKeyGen、ReEnc、Dec、main等關鍵字分別表示初始化、密鑰生成、加密、重加密、重加密密鑰生成、解密函數和主函數的定義；控制類包含 if、then、else、loop、step、until，分別針對選擇和循環類的操作。

2.2.3 變量及常量類型

變量定義以關鍵字“/def”為起始，以“def”為終止。代理重加密的算法描述中涉及循環群、雙線性對、生成元、大素數等變量類型的定義，涉及的運算包含散列、按位邏輯運算等，多針對整數、比特串等進行描述。因此，PLPRE所提供的變量類型如下。

整型：采用十進制表示。

邏輯型：僅包含true和false這2種類型，使用1和0與之對應。

比特串：用于明文、密文、密鑰、大素數等相關數據的定義，使用二進制比特串表示。

枚舉型：用于循環群等相關類型的表示和定義。

在使用過程中，變量的定義僅說明位數，類型的定義則通過具體描述中子函數和運算規則進行表示。例如，定義循環群G1的語句為“/def G1def”，循環群的表示則在具體函數描述中通過語句“G1=Group(q)”進行說明，其中，q為群G1的階，Group為系統子函數，子函數說明見2.2.5節。

PLPRE變量名的命名規則如下。

變量名不得與關鍵字、運算符重復。

變量名需要區分大小寫，即變量g與G為不同的變量。

變量名不超過20個字符，超出則忽略20個字符之外的內容。

變量名必須以字母開頭，可以包含字母、數字、下劃線，其他字符則不能包含在變量名中。

對于數組類數據的定義，則以“數組名[數據長度]”的形式進行定義，數組名的定義需要符合變量名的定義約束，數據長度采用整型定義。

2.2.4 函數

函數的描述規則是PLPRE中的重要組成部分，依托的數據理論、面向的具體環境的不同可能導致代理重加密算法描述各異，但是通常的算法描述中包含初始化、密鑰對生成、加密、解密、重加密密鑰生成、重加密等函數步驟，因此針對不同的代理重加密算法中可以抽象出共性的函數步驟進行描述語言的定義，PLPRE的函數描述均以“/method”關鍵字為起始，形式為“/method”函數名（參數表），以“method”表示函數描述結束；參數表中參數數量為0～N，N為自然數，參數數量由描述用戶需求來確定。

具體函數的定義形式和描述說明如表1所示。

2.2.5 運算規則

PLPRE的運算規則定義包含子函數描述和運算符描述。其中，子函數描述以sfun 表示，子函數是指數學算法設計過程中相關的通用數學函數，由現有的通用程序源碼庫支撐。

子函數描述包括大素數生成子函數Prime()、循環群生成子函數 Group()、整數循環群生成子函數GroupZ()、生成元獲取子函數Generator()、雙線性對生成子函數 e()、隨機選取群中元素子函數random()、散列函數構造函數 Hash()，運算符包含冪運算^、連接運算@、有限域乘*，具體說明如表2所示。

2.2.6 控制結構

PLPRE中包含了條件選擇和循環 2類控制結構，條件判定以“/if”開始，結構如下所示。

/if（邏輯判定條件）

表1 PLPRE函數定義說明

表2 PLPRE子函數及運算符說明

then 程序語句1

else 程序語句2

條件判定多用于加密、解密過程描述中的先決條件判定的描述。

循環以“/loop”和“loop”分別表示開始和結束，“step =”表示起始變量變化步長，“until =”表示循環結束條件。具體描述示例如下。

/loop (a=0; step =1; until = 10 )

…//程序語句，即循環內容

loop

該示例中a為實變量，步長為1，10為截止條件，每執行一次程序語句，a加1，直至a=10，進行 11次循環。循環語句多用于明文數據輸入、密文數據輸出、密鑰數據產生等描述。

3 PLPRE的描述示例

基于上述PLPRE語法描述，現以文獻[12]中描述的代理重加密算法為實例，給出該 PRE算法的PLPRE描述程序。

3.1 定義部分

/def /*參數定義*/

q (bits=128) ;

/*定義長度128 bit的變量q，用于大素數生成，大素數具體位數有初始化函數參數k確定*/

g ;

G1;//定義變量g用于循環群生成元，G1表示循環群

…//此處定義其他生成元、循環群以及其他中間變量，方法同上

plaintxt(bits=128) ;

ciphertxt(bits=128) ;

/*定義明文數據plaintxt、密文數據ciphertxt，長度均為128 bit，重加密基于公鑰密碼體制，明文、密文不需要估計按照長度分組，此處定義 128 bit旨在便于數據讀取*/

Input (plaintxt, “plaintxt.txt”);

Output (ciphertxt, “ciphertxt.txt”);/*描述明文和密文的輸入和輸出文件*/

def

3.2 主體部分

參考文獻[13]的算法，本節選取ACC-PRE的初始化、加密、重加密部分進行描述。

1) 初始化函數Setup

該函數輸入參數k，定義大素數長度，生成k長度的大素數p，q階循環群，構造散列函數映射關系，具體算法及描述語言對應關系實例如表 3所示。

2) 第一次加密函數Enc

該函數輸入明文及用戶i的公鑰pki，產生第一加密的密文C1。算法及程序設計語言對應關系實例如表4所示。

3)重加密函數Re-Enc

該函數輸入第一次加密密文 C1與重加密密鑰rk，產生可由用戶j解密的重加密密文C2。具體算法及描述語言對應關系實例如表5所示。

由于篇幅關系，密鑰生成、重加密生成函數以及解密函數將不再贅述，具體描述方法與上述算法描述相同。

4 PLPRE系統實現

ANTLR是一種語言識別工具，前身為PCCTS，該工具可以為包括Java、C++、C#在內的語言提供了一個通過語法描述來自動構造自定義語言的識別器（recognizer）、編譯器（parser）和解釋器（translator）的框架，涉及詞法分析器、語法分析器、語法分析樹等內容。本文基于 ANTRL工具，對PLPRE語言及其解析程序進行了實現和測試，具體實現流程如圖1所示。

表3 ACC-PRE Setup算法PLPRE描述

表4 ACC-PRE 第一次加密算法PLPRE描述

表5 ACC-PRE 重加密算法PLPRE描述

圖1 PLPRE實現流程

用戶依據自身需求，描述重加密算法，產生描述文本文件ReEnc.pre，具體解析過程說明如下。

1) 對重加密描述文件ReEnc.pre進行詞法分析。

步驟 1 預處理，去除無效的空格、制表符、換行這些字符。

步驟2 識別專用運算符，如“^”“xor”“==”“!=”“@”，專用運算符識別為相應的TOKEN碼。

步驟3 識別關鍵字，為其指定相應的屬性值，并將其對應為TOKEN碼，為語法分析程序準備。

步驟 4 識別字符串、數字、字符常量，保存并將其對應為TOKEN碼，為語法分析程序準備。

步驟5 識別main函數描述結束符，并交給語法分析程序處理。

2) 接下來，對代理重加密描述文件進行語法分析，根據前面類數學描述語言的語法規則，把詞法分析的結果分解為各個語法單元，并進行進行語法錯誤的檢查與識別。

語法分析主要依托的是詞法分析中產生的TOKEN碼表，識別各類語法成分，分別包含關鍵字、變量、常量、函數、運算子函數和運算符，并進行關鍵字單詞撰寫錯誤、括號不匹配錯誤的識別。

3) 對代理重加密描述文件進行語義分析，并對描述語言具體語義含義進行識別和分析、靜態語義檢查，例如，指定變量是否定義、類型是否匹配、代理重加密步驟函數是否描述完整、齊全，為代碼生成階段搜集相關的語義信息。

經過語義分析將構造以下信息：全局變量、常量信息表；步驟函數信息表；步驟函數聲明信息表；子函數調用信息表；產生中間代碼。

4) 此時生成的中間代碼已經類似于用戶指定的計算機編程語言對應的代碼，但是具體子函數的實施還未進行處理。

5) 依據用戶的目標代碼需求，選擇對應計算機編程語言的代碼底層庫，生成目標代碼。目前程序實現代碼庫依托于 PBC庫。在現有的PBC底層支持庫中進行選擇，調用不同的子函數實現程序及相關代碼，并產生對應的頭文件函數生成列表。

6) 將產生的子函數代碼與頭文件信息進行整合，生成輸出文件ReEnc.c和ReEnc.h文件，此處以C語言為例，若用戶選擇其他編程語言，則后綴名與文件格式會發生相應的變化。

上述6個步驟是依托于ANTRL工具產生的編譯程序，ANTRL工具則以 PLPRE.g文件中描述的文法規則進行編譯框架程序的生成，依據文獻[12]，對第 3節中定義的規則進行描述，針對變量描述的文法描述示例如下。

grammar PLPRE;

options {

language = C;}

@header {

#include ＜pbc.h＞

#include ＜gmp.h＞}

expr: multExpr ((CON| EXP| XOR) multExpr)*;

CON: '@';

EXP: '^';

XOR:'xor';

multExpr : atom*

atom: INT

| ID

| '('! expr ')'!;

stmt: expr NEWLINE -＞ expr| ID ASSIGN expr NEWLINE -＞ ^(ASSIGN ID expr)| NEWLINE -＞;

ASSIGN: '=';

ID: ('a'..'z'|'A'..'Z')+ ;

INT: '～'? '0'..'9'+ ;

NEWLINE: ' '? ' ' ;

結合3.1節中的范式描述，進一步描述關鍵字、函數、子函數以及程序邏輯的文法描述，最終產生PLPRE.g文件。該文件通過ANTRL工具編譯，產生 PLPRE對應的詞法、語法和語義分析器，用于算法源文件的編譯。

5 PLPRE特征分析

PLPRE語言針對PRE的基本特征，提取功能步驟，給出了 PRE算法描述的基本框架和語法結構，描述語言類似數學語言，對于密碼算法研究人員和數學專家來說簡單明了，本節將從知識背景、適用范圍、跨平臺等方面對PBC、PRL、Cryptol、PLPRE等進行對比，如表6所示。

1) 知識背景

PBC與PRL基于C++、C、Java等語言，需要用戶熟知計算機編程語言，明確數據的定義類型、長度，還需要用戶在實現過程中進行數據結構、內存分配等方面的設計與分析；Cryptol與PLPRE則僅僅關注數據的長度，不需要過度關注類型，更不用考慮如何分類內存和定義何種數據結構。對于非計算機從業的密碼研究人員更為便捷。

2) 適用范圍

Cryptol主要針對傳統密碼算法，如DES、AES，同時包含 MD5等散列函數的描述方法，不適用于代理重加密算法的描述；PBC則針對大量密碼算法中至關重要的雙線性對進行了C語言的實現，提供循環群產生、生成元提取、有限域運算等編程接口；PRL更進一步針對PRE給出C++程序接口，但是PBC與PRL需要在調用接口前，用戶自行定義數據結構，設計程序邏輯；PLPRE是針對PRE的專用DSL，更加適合代理重加密算法的設計人員使用。

3) 跨平臺

PRL基于PBC進行了部分線性對重加密算法的 C++接口實現，需要運行平臺具備 C++代碼編譯的能力；PBC兼顧了 C++、Java等多種高級語言，提供了具體的線性對相關的算法實現接口，但是仍然需要考慮具體選擇語言適用的平臺；Cryptol和PLPRE則具備了其特有的語法描述體系，并產生出具體編程平臺需要的算法代碼。

表6 相關技術對比

6 結束語

代理重加密以其特有的技術特點，被廣泛應用于云安全、隱私保護等領域。通常從事代理重加密算法研究的多為熟知數學理論的非計算機專業人員，使算法設計僅通過數學分析進行安全性的證明，性能的分析則依托于理論計算；算法在具體應用時，系統編程人員由于不熟悉數學理論，往往出現理解的偏差，從而產生實現過程中的漏洞。這一現狀導致了代理重加密算法的設計與實際應用脫節。本文針對這一問題，提出一種面向代理重加密算法的程序設計語言PLPRE，該語言能夠通過類似數學語言的方式對代理重加密算法進行描述。描述過程中不需要關注代碼設計細節，適用于非計算機專業的密碼算法設計者，從而避免代理重加密算法的設計與實現的偏差。這有利于算法研究人員的理論交流，減輕算法研究人員的計算機編程難度，進而推動代理重加密技術在各類系統的廣泛應用。