时控性加密原理

要想实现一个加密算法首先先清楚它的原理，时控性加密算法以其独特的时间敏感而广泛应用。

初始化

首先时控性加密规定了几个域：

$G_1\text{为素数} q\text{的循环加法群}\quad G_2\text{为素数}q\text{的循环乘法群}\\ \text{双线性映射}e:G_1 \times G_1 \rightarrow G_2\\ H_1:\{0,1\}^* \rightarrow G_1\qquad H_2:G_2 \rightarrow \{0,1\}^n,\ n\text{为明文长度}\\ \text{选取}G_1\text{群中的生成元}P\in G_1$

以我的理解来说，H1是将01字符串映射到椭圆曲线，H2是将椭圆曲线上的点重新映射回有限域。

加密和解密

首先时间服务器选取随机数 $s$ 作为私钥 $ts_{priv}$ ，并且计算 $s\cdot P$ 作为其公钥 $ts_{pub}$
类似的，接收方选取随机数 $u\in Z_q^*$ ，作为其私钥 $usk$ ，以 $uP$ 作为其公钥 $upk$
给定消息 $M$ 、接收方公钥 $upk$ 、时间服务器公钥 $ts_{pub}$ 以及发布时间 $T\in \{0,1\}^*$ ，发送方进行如下操作：

(1)随机选取数 $r\in Z_q^*$ ，计算 $U=r*P$

(2)计算 $K=e(rH_1(T),uP+sP)=e(H_1(T),P)^{r(u+s)}$

(3)得到密文 $C=<U,V>=<rP,M\oplus H_2(K)>$
在指定解密时间 $T\in\{0,1\}^*$ ，时间服务器使用私钥 $ts_{priv}$ ，计算时间陷门 $S_T=ts_{priv}\cdot H_1(T)=sH_1(T)$
在指定解密时间 $T\in\{0,1\}^*$ ，接收方使用私钥 $usk$ 计算自己的时间陷门 $U_T=usk\cdot H_1(T)=uH_1(T)$
给定密文 $C=<U,V>$ ，接收方在指定解密时间 $T\in \{0,1\}^*$ ，使用自己计算得到的时间陷门 $U_T$ 和时间服务器的时间陷门 $S_T$ ，完成如下解密操作：

(1)计算 $K'=e(U,S_T+U_T)$

(2)计算 $V\oplus H_2(K')$ 恢复消息 $M$

正确性证明

$K'=e(U,S_T+U_T)=e(rP,(u+s)H_1(T))=e(P,H_1(T))^{r(u+s)}=K$

$V\oplus H_2(K')=V\oplus H_2(K)=M\oplus H_2(K)\oplus H_2(K)=M$

Miracl库

MIRACL(Multiprecision Integer and Rational Arithmetic C/c++ Library)是一套由Shamus Software Ltd.所开发的一套关于大数运算函数库，用来设计与大数运算相关的密码学之应用，包含了RSA 公开密码学、Diffie-Hellman密钥交换(Key Exchange)、AES、DSA数字签名，还包含了较新的椭圆曲线密码学(Elliptic Curve Cryptography)等等。

Miracl库需要手动下载调用才能使用。

Visual Studio中使用Miracl库

可以参考这个教程：https://www.bilibili.com/read/cv7663799

测试代码：

extern "C"
{
	#include "miracl.h"
	#include "mirdef.h"
}
#pragma comment(lib,"miracl.lib")
int main()
{
	miracl *mip = mirsys(500, 16); //初始化miracl系统
	big n = mirvar(8); //初始化n,必须有
	cotnum(n, stdout); //打印n
	cinnum(n, stdin); //输入n
	cotnum(n, stdout); //再次打印n
	return 0;
}

能成功运行这个测试代码表示静态资源库编译完成并且成功导入。

结构体说明

ECn：代表椭圆曲线上的点
Big：代表一个大整数
ZZn：表示大整数（大数）的数据类型。ZZn 提供了一个可以处理大数的抽象接口，使得在进行椭圆曲线密码学等计算时更加方便和高效。
ZZn2：二次扩展有限域上的元素，包含两个 ZZn元素，分别表示二次扩域中的实部和虚部。二次扩展域可看作加上虚数的椭圆曲线有限域。

函数说明

map_to_point：对应公式中的H1
H1：将字符串哈希为一个大整数
H2：对应公式中的H2
ecap：双线性对运算，计算椭圆曲线上两个点 P 和 Q 的配对运算结果。

代码示例

具体实现方案

/*
   Boneh & Franklin's Identity Based Encryption
   
   Set-up phase

   After this program has run the file common.ibe contains

   <Size of prime modulus in bits>
   <Prime p>
   <Prime q (divides p+1) >
   <Point P - x coordinate>
   <Point P - y coordinate>
   <Point Ppub - x coordinate>
   <Point Ppub - y coordinate>
   <Cube root of unity in Fp2 - x component >
   <Cube root of unity in Fp2 - y component >

   The file master.ibe contains

   <The master secret s>

   Requires: zzn2.cpp big.cpp zzn.cpp ecn.cpp

 */
#include <time.h>
#include <iostream>
#include <fstream>
#include <cstring>
#include<ctime>
using namespace std;

#include "ecn.h"
#include "zzn.h"
#include "zzn2.h"
extern "C"
{
   #include"miracl.h"
   #include"mirdef.h"
}

//2015版更新
FILE* __cdecl __iob_func(unsigned i) {
    return __acrt_iob_func(i);
}

#ifdef __cplusplus
extern "C"
#endif
//extern "C" { FILE __iob_func[3] = { *stdin,*stdout,*stderr }; }
FILE _iob[3] = { __iob_func(0)[0], __iob_func(1)[1], __iob_func(2)[2] };


#pragma comment(linker, "/NODEFAULTLIB:libc.lib")


#define renum 2500

#define HASH_LEN 32
#define HASH_LEN1 20   //用于求H2，因为本程序中q是160位的二进制数，而160/8=20
//H2中采用sha256要求HASH_LEN1 必须是32的倍数，因此，自己将H2内部函数其改为sha-1


#define PBITS 512
#define QBITS 160

// Using SHA-256 as basic hash algorithm

//
// Define one or the other of these
//
// Which is faster depends on the I/M ratio - See imratio.c
// Roughly if I/M ratio > 16 use PROJECTIVE, otherwise use AFFINE
//

// #define AFFINE
#define PROJECTIVE

// Define this to use this idea ftp://ftp.computing.dcu.ie/pub/resources/crypto/short.pdf
// which enables denominator elimination
#define SCOTT

Miracl precision(16, 0);  // increase if PBITS increases. (32,0) for 1024 bit p

/*----------------------------------------------------------------------------Tate Paring 计算所需要的函数-----------------------------------------------------*/
void extract(ECn& A, ZZn& x, ZZn& y)
{
    x = (A.get_point())->X;
    y = (A.get_point())->Y;
}

void extract(ECn& A, ZZn& x, ZZn& y, ZZn& z)
{
    big t;
    x = (A.get_point())->X;
    y = (A.get_point())->Y;
    t = (A.get_point())->Z;
    if (A.get_status() != MR_EPOINT_GENERAL)
        z = 1;
    else
        z = t;
}

//
// Line from A to destination C. Let A=(x,y)
// Line Y-slope.X-c=0, through A, so intercept c=y-slope.x
// Line Y-slope.X-y+slope.x = (Y-y)-slope.(X-x) = 0
// Now evaluate at Q -> return (Qy-y)-slope.(Qx-x)
//

ZZn2 line(ECn& A, ECn& C, ZZn& slope, ZZn2& Qx, ZZn2& Qy)
{
    ZZn2 n = Qx, w = Qy;
    ZZn x, y, z, t;
#ifdef AFFINE
    extract(A, x, y);
    n -= x; n *= slope;            // 2 ZZn muls
    w -= y; n -= w;
#endif
#ifdef PROJECTIVE
    extract(A, x, y, z);
    x *= z; t = z; z *= z; z *= t;
    n *= z; n -= x;                // 9 ZZn muls
    w *= z; w -= y;
    extract(C, x, y, z);
    w *= z; n *= slope; n -= w;
#endif
    return n;
}

#ifndef SCOTT

//
// Vertical line through point A
//

ZZn2 vertical(ECn& A, ZZn2& Qx)
{
    ZZn2 n = Qx;
    ZZn x, y, z;
#ifdef AFFINE
    extract(A, x, y);
    n -= x;
#endif
#ifdef PROJECTIVE
    extract(A, x, y, z);
    z *= z;
    n *= z; n -= x;                // 3 ZZn muls
#endif
    return n;
}

#endif

//
// Add A=A+B  (or A=A+A) 
// Bump up num and denom
//
// AFFINE doubling     - 12 ZZn muls, plus 1 inversion
// AFFINE adding       - 11 ZZn muls, plus 1 inversion
//
// PROJECTIVE doubling - 26 ZZn muls
// PROJECTIVE adding   - 34 ZZn muls
//


void g(ECn& A, ECn& B, ZZn2& Qx, ZZn2& Qy, ZZn2& num)
{
    ZZn  lam, mQy;
    ZZn2 d, u;
    big ptr;
    ECn P = A;

    // Evaluate line from A
    ptr = A.add(B);

#ifndef SCOTT
    if (A.iszero()) { u = vertical(P, Qx); d = 1; }
    else
    {
#endif
        if (ptr == NULL)
            u = 1;
        else
        {
            lam = ptr;
            u = line(P, A, lam, Qx, Qy);
        }
#ifndef SCOTT
        d = vertical(A, Qx);
    }

    num *= (u * conj(d));    // 6 ZZn muls  
#else
        // denominator elimination!
        num *= u;
#endif
}

    //
    // Tate Pairing 
    //

BOOL fast_tate_pairing(ECn& P, ZZn2& Qx, ZZn2& Qy, Big& q, ZZn2& res)
{
    int i, nb;
    Big n, p;
    ECn A;


    // q.P = 2^17*(2^142.P +P) + P

    res = 1;
    A = P;    // reset A

#ifdef SCOTT
    // we can avoid last iteration..
    n = q - 1;
#else
    n = q;
#endif
    nb = bits(n);

    for (i = nb - 2; i >= 0; i--)
    {
        res *= res;
        g(A, A, Qx, Qy, res);
        if (bit(n, i))
            g(A, P, Qx, Qy, res);
    }
    bool bb = (A != -P);
    bool bbb = res.iszero();


    p = get_modulus();         // get p
    res = pow(res, (p + 1) / q);   // raise to power of (p^2-1)/q
    res = conj(res) / res;
    if (res.isunity()) return FALSE;
    return TRUE;
}
BOOL ecap(ECn& P, ECn& Q, Big& order, ZZn2& cube, ZZn2& res)
{
    ZZn2 Qx, Qy;
    Big xx, yy;
#ifdef SCOTT
    ZZn a, b, x, y, ib, w, t1, y2, ib2;
#else
    ZZn2 lambda, ox;
#endif
    Q.get(xx, yy);
    Qx = (ZZn)xx * cube;
    Qy = (ZZn)yy;

#ifndef SCOTT
    // point doubling
    lambda = (3 * Qx * Qx) / (Qy + Qy);
    ox = Qx;
    Qx = lambda * lambda - (Qx + Qx);
    Qy = lambda * (ox - Qx) - Qy;
#else
    //explicit point subtraction
    Qx.get(a, b);
    y = yy;
    ib = (ZZn)1 / b;

    t1 = a * b * b;
    y2 = y * y;
    ib2 = ib * ib;
    w = y2 + 2 * t1;
    x = -w * ib2;
    y = -y * (w + t1) * (ib2 * ib);
    Qx.set(x);
    Qy.set((ZZn)0, y);

#endif

    if (fast_tate_pairing(P, Qx, Qy, order, res)) return TRUE;
    return FALSE;
}


//
// ecap(.) function - apply distortion map
//
// Qx is in ZZn if SCOTT is defined. Qy is in ZZn if SCOTT is not defined. 
// This can be exploited for some further optimisations. 
/*----------------------------------------------------------------------------Tate Paring 计算所需要的函数-----------------------------------------------------*/


/*----------------------------------------------------------------------------相关Hash函数所需的函数-----------------------------------------------------*/
Big H1(char* string)
{ // Hash a zero-terminated string to a number < modulus
    Big h, p;
    char s[HASH_LEN];
    int i, j;
    sha256 sh;

    shs256_init(&sh);

    for (i = 0;; i++)
    {
        if (string[i] == 0) break;
        shs256_process(&sh, string[i]);
    }
    shs256_hash(&sh, s);
    p = get_modulus();
    h = 1; j = 0; i = 1;
    forever
    {
        h *= 256;
        if (j == HASH_LEN) { h += i++; j = 0; }
        else         h += s[j++];
        if (h >= p) break;
    }
    h %= p;
    return h;
}

int H2(ZZn2 x, char* s)
{ // Hash an Fp2 to an n-byte string s[.]. Return n
    sha sh;
    Big a, b;
    int m;

    shs_init(&sh);
    x.get(a, b);

    while (a > 0)
    {
        m = a % 160;
        shs_process(&sh, m);
        a /= 160;
    }
    while (b > 0)
    {
        m = b % 160;
        shs_process(&sh, m);
        b /= 160;
    }
    shs_hash(&sh, s);

    return HASH_LEN1;

}
Big H3(char* string, Big qm)
{ // Hash a zero-terminated string to a number < modulus q
    Big h;
    char s[HASH_LEN1];
    int i, j;
    sha sh;

    shs_init(&sh);

    for (i = 0;; i++)
    {
        if (string[i] == 0) break;
        shs_process(&sh, string[i]);
    }
    shs_hash(&sh, s);
    //q=get_modulus();
    //cout<<"modulus"<<p<<endl;//自己加的查看p值的语句，通过p值可知get_modulus()得到了椭圆曲线所在有限域的素数P
    h = 1; j = 0; i = 1;
    forever
    {
        h *= 160;
        if (j == HASH_LEN1)
        {
h += i++; j = 0;
}
else
h += s[j++];
if (h >= qm) break;
    }
    h %= qm;
    return h;
}

//
// Given y, get x=(y^2-1)^(1/3) mod p (from curve equation)
//

Big getx(Big y)
{
    Big p = get_modulus();
    Big t = modmult(y + 1, y - 1, p);   // avoids overflow
    return pow(t, (2 * p - 1) / 3, p);
}
 
//
// MapToPoint
//

ECn map_to_point(char *ID,Big cof)
{
    ECn Q;
    Big x0, y0 = H1(ID);
    x0 = getx(y0);
    Q.set(x0, y0);
    Q *= cof;
    return Q;
}

void xorStrings(char* str1, char* str2, char* result, int len) {


    for (int i = 0; i < len; i++) {

        char c1 = str1[i];
        char c2 = str2[i];

        result[i] = c1 ^ c2;
    }
}

int main()
{
    ofstream common("common.ibe");
    ofstream master("master.ibe");
    //ECn P,Ppub;
    ECn P, Q;
    //ZZn px,py;//自加，定义的是点的x,y坐标
    ZZn2 cube, w;//自加
   // ZZn2 cube;
   // Big s,p,q,t,n,cof,x,y;
    Big a, b, c, d1, d2, p, q, t, n, cof;
    long seed;
    char pad[HASH_LEN1];//自加
    //char pad[20]={0};
    miracl* mip = &precision;

    cout << "Enter 9 digit random number seed  = ";
    cin >> seed;
    irand(seed);

    // SET-UP
    /*-------------------------------------------------------------产生素数阶q-------------------------------------------------------------------------*/
    q = pow((Big)2, 159) + pow((Big)2, 17) + 1;
    //    q=pow((Big)2,160)-pow((Big)2,76)-1;

    cout << "q= " << q << endl;
    //int logq=bits(q);//计算q的二进制位数，这里是160
//	cout << "log q= " << logq << endl;

/*--------------------------------------------------------------产生素数p-------------------------------------------------------------------------*/
//generate p
    t = (pow((Big)2, PBITS) - 1) / (2 * q);
    a = (pow((Big)2, PBITS - 1) - 1) / (2 * q);
    forever
    {
        n = rand(t);
        if (n < a) continue;
        p = 2 * n * q - 1;
        if (p % 24 != 11) continue;  // must be 2 mod 3, also 3 mod 8
        if (prime(p)) break;
    }
    cout << "p= " << p << endl;

    cof = 2 * n;

    ecurve(0, 1, p, MR_PROJECTIVE);    // elliptic curve y^2=x^3+1 mod p
//
// Find suitable cube root of unity (solution in Fp2 of x^3=1 mod p)
//    
    forever
    {
        //    cube=pow(randn2(),(p+1)*(p-1)/3);
            cube = pow(randn2(),(p + 1) / 3);
            cube = pow(cube,p - 1);
            if (!cube.isunity()) break;
    }

    cout << "Cube root of unity= " << cube << endl;

    if (!(cube * cube * cube).isunity())
    {
        cout << "sanity check failed" << endl;
        exit(0);
    }
    //
    // Choosing an arbitrary P ....
    /*-------------------------------------------------------------产生椭圆曲线上任意点P（生成元）-------------------------------------------------------------------------*/
    forever
    {
        while (!P.set(randn()));
        P *= cof;
        if (!P.iszero()) break;
    }

        // cout << "Point P= " << P << endl; //
    cout << "生成元P=" << P << endl;

    /*-------------------------------------------------------------产生椭圆曲线上任意点Q-------------------------------------------------------------------------*/
    forever
    {
        while (!Q.set(randn()));
        Q *= cof;
        if (!Q.iszero()) break;
    }

    cout << "Point Q= " << Q << endl; //
    
    //时间服务器计算公钥
    Big s = rand(q);
    ECn ts_pub = s * P;
    cout << "ts_pub=" << ts_pub << endl;
    //接收方计算公钥私钥
    Big u = rand(q);
    Big usk = u;
    cout << "usk=" << usk << endl;
    ECn upk = u * P;
    //发送方计算密文
    Big r = rand(q);
    ECn U = r * P;

    char T[100] = "2023-09-21-21-13";
    //计算k
    ECn RT = r * map_to_point(T, cof);
    ECn u_t = upk + ts_pub;
    ZZn2 k;
    ecap(RT, u_t, q, cube, k);
    cout << "k=" << k << endl;
    //计算V
    char M[20] = "abcdefghijklmn"; //明文
    cout << "M:" << M << endl;
    char c2[81] = "\0";
    char V[81] = "\0";
    int len = H2(k, c2);
    cout << "c2=" << c2 << endl;
    xorStrings(c2, M, V, 20);
    cout << "V=" << V << endl;

    //时间服务器计算时间陷门SH1(T)
    ECn ST = s * map_to_point(T, cof);
    //接收方计算UT,K'，计算M
    ECn UT = usk * map_to_point(T, cof);
    ZZn2 k_;
    ECn SU = ST + UT;
    ecap(SU, U, q, cube, k_);
    cout << "k'=" << k_ << endl;

    char m1[31] = "\0";
    len = H2(k_, m1);
    cout << len << endl;
    cout << m1 << endl;
    char m[21] = "\0";
    xorStrings(V, m1, m, 20);
    cout << "M=" << m;
    return 0;
}

关于main函数的具体分析

相关运算函数都已经写好，只需要按步骤执行即可

初始化

首先生成素数阶 $q$ ，随后生成 $p$ ，确定椭圆曲线域，随后产生椭圆曲线生成元 $P$

加密解密过程

随后时间服务器部分根据步骤产生随机数 $s$ 做为私钥， $s\cdot P$ 作为公钥

//时间服务器计算公钥
Big s = rand(q);
ECn ts_pub = s * P;
cout << "ts_pub=" << ts_pub << endl;

接收方选取随机数 $u$ 作为私钥，计算 $u\cdot P$ 作为公钥

 //接收方计算公钥私钥
Big u = rand(q);
Big usk = u;
cout << "usk=" << usk << endl;
ECn upk = u * P;

发送方发送的消息为 $M$ ，选取随机数 $r$ 计算 $U=r*P$
1
2
3
//发送方计算
Big r = rand(q);
ECn U = r * P;

计算 $K=e(rH_1(T),uP+sP)=e(H_1(T),P)^{r(u+s)}$ ，其中 $e()$ 为双线性对运算，也就是函数ecap

//选定时间T
char T[100] = "2023-09-21-21-13";
//计算k
//计算rH1(T)
ECn RT = r * map_to_point(T, cof);
//计算uP+sP
ECn u_t = upk + ts_pub;
ZZn2 k;
ecap(RT, u_t, q, cube, k);
cout << "k=" << k << endl;

密文 $C=<U,V>=<rP,M\oplus H_2(K)>$

//计算V
char M[20] = "abcdefghijklmn";
cout << "M:" << M << endl;
char c2[81] = "\0",V[81] = "\0";
//c2为H2(K)
int len = H2(k, c2);
cout << "c2=" << c2 << endl;
//异或
xorStrings(c2, M, V, 20);
cout << "V=" << V << endl;

在解密时间 $T$ 时时间服务器计算 $S_T=ts_{priv}\cdot H_1(T)=sH_1(T)$ ，其中 $H_1()$ 为函数map_to_point，并将此消息广播
1
2
//时间服务器计算时间陷门SH1(T)
ECn ST = s * map_to_point(T, cof);
接收方收到广播 $S_T$ 并计算 $U_T=usk\cdot H_1(T)=uH_1(T)$
1
2
//接收方计算UT,K'，计算M
ECn UT = usk * map_to_point(T, cof);
接收方计算