ibe_dec.cpp

miracl-大数运算库,大家使用有什么问题请多多提意见

/*
   Boneh & Franklin's Identity Based Encryption

   Decryption phase

   Decrypts a file <filename>.ibe
   Finds the session key by IBE decrypting the file <filename>.key
   Uses this session key to AES decrypt the file.

   Outputs to the console

   NOTE: Uses Tate Pairing only
   NOTE: New fast Tate pairing algorithm

   Compile as 
   cl /O2 /GX /DZZNS=16 ibe_dec.cpp zzn2.cpp big.cpp zzn.cpp ecn.cpp miracl.lib
   where miracl is built using the Comba method.

*/

#include <iostream>
#include <fstream>
#include <cstring>
#include "ecn.h"
#include "zzn.h"
#include "ebrick.h"
#include "zzn2.h"

using namespace std;

#define PBITS 512
#define QBITS 160

// Using SHA-1 as basic hash algorithm

#define HASH_LEN 20

//
// 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 if group order q is "simple" = 2^159+2^17+1
#define SIMPLE

//
// Tate Pairing Code
//
// Extract ECn point in internal ZZn format
//

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,ZZn& Qy)
{ 
    ZZn2 n=Qx;
    ZZn x,y,z,t,w=Qy;
#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;
}

//
// 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;
}

//
// Add A=A+B  (or A=A+A) or
// Sub A=A-B
// 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
//

#define ADD 1
#define SUB 2

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

    if (as==ADD)
    { // Evaluate line from A, and then evaluate vertical through destination
        ptr=A.add(B);

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

 //       u*=conj(d);
 //       d=1;

    }
    else // as==SUB
    { // Evaluate Vertical at A, and then line from A to destination
      // (Note swap num and denom, Qy=-Qy, process lines "backwards")
        u=vertical(A,Qx);
        ptr=A.sub(B);

        if (A.iszero())   { d=u;  } 
        else
        {
            mQy=-Qy;
            if (ptr==NULL) d=1;
            else 
            {
                lam=ptr;
                d=line(P,A,lam,Qx,mQy);
            }
        }
    }

    if (first) {num= u; denom= d; }
    else       {num*=u; denom*=d; }   // 6 ZZn muls  
}

//
// Tate Pairing - note ha -> numerator, had -> denominator
// Trying to minimize number of modular inversions
//
// Special optimized and deterministic version of Tate Pairing algorithm 
// Requires that the point (0,1) is on the curve AND
// P and Q(x,y) linearly independent, that is P!=r.Q for any r, and odd order q.
// If P & Q are linearly dependent it might fail, but this will be detected.
//
// Sketch of proof:-
// Consider S=(0,1) - a point of order 3 - as the random contribution in the 
// "normal" Tate algorithm i.e. Q <- (Q+S)-(S). Note that the coordinates of P
// are both in Fp. Under these circumstances the contribution of S to the 
// numerator and denominator of the cumulative multiplicative total will always
// be in Fp. All such contributions will be "wiped out" by the final raising 
// to the power of (p-1). Therefore S can be ommitted altogether, and all 
// calculations involving it removed.
//
// Furthermore the calculation will not fail. The numerator and denominator 
// will never evaluate to 0, as a consequence of linear independence. The point 
// Q cannot be both on the curve and on a line joining two point in the 
// calculation of r.P
//
// P & Q(x,y) are both points of order q. 
// Note that P is a point on the curve over Fp, Q(x,y) a point on the 
// quadratic extension field Fp^2
//

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

#ifndef SIMPLE
    Big q3;
    ECn P2,t[11];
    ZZn2 hc,hcd,z2n,z2d,zn[11],zd[11];
#endif

    ha=had=1;  

#ifdef SIMPLE

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

    A=P;    // reset A
    for (i=0;i<142;i++)
    {
        ha*=ha; had*=had;          
        g(A,A,Qx,Qy,ha,had,ADD,FALSE);      // 16 ZZn muls + 1 inverse 
        if (ha==0 || had==0) return FALSE;
    }                                       // 30 ZZn muls (Projective)
    g(A,P,Qx,Qy,ha,had,ADD,FALSE);          // 11 ZZn muls + 1 inverse 
    if (ha==0 || had==0) return FALSE;
                                            // 34 ZZn muls (Projective)
    for (i=0;i<17;i++)                      
    {
        ha*=ha; had*=had;          
        g(A,A,Qx,Qy,ha,had,ADD,FALSE);      // 16 ZZn muls + 1 inverse 
        if (ha==0 || had==0) return FALSE;
    }                                       // 30 ZZn muls (Projective)
    g(A,P,Qx,Qy,ha,had,ADD,FALSE);          // 11 ZZn muls + 1 inverse 
    if (ha==0 || had==0) return FALSE;
                                            // 34 ZZn muls (Projective)
#else

    q3=q*3;
    zn[0]=zd[0]=1;
    t[0]=P2=A=P;
    g(P2,P2,Qx,Qy,z2n,z2d,ADD,TRUE);     // P2=P+P
//
// Build NAF windowing table
//
    for (i=1;i<11;i++)
    {                                    // 17 ZZn muls + 1 inverse (Affine)
        g(A,P2,Qx,Qy,hc,hcd,ADD,TRUE);   // 40 ZZn muls (Projective)    
        t[i]=A;                          // precalculate t[i] = (2i+1).P
        zn[i]=z2n*zn[i-1]*hc;
        zd[i]=z2d*zd[i-1]*hcd;
    }
    A=P;    // reset A

/* Left to right method  */
    nb=bits(q3);
    for (i=nb-2;i>=1;i-=(nbw+nzs))
    {
        n=naf_window(q,q3,i,&nbw,&nzs);  // standard MIRACL NAF windowing
        for (j=0;j<nbw;j++)
        {
            ha*=ha; had*=had;          
            g(A,A,Qx,Qy,ha,had,ADD,FALSE);      // 16 ZZn muls + 1 inverse 
        }                                       // 30 ZZn muls (Projective) 
        if (n>0)
        {
            ha*= zn[n/2]; had*=zd[n/2];    
            g(A,t[n/2],Qx,Qy,ha,had,ADD,FALSE); // 17 ZZn muls + 1 inverse 
        }                                       // 40 ZZn muls (Projective)
        if (n<0)
        {
            n=(-n);
            ha*=zd[n/2]; had*=zn[n/2];
            g(A,t[n/2],Qx,Qy,ha,had,SUB,FALSE); // 17 ZZn muls + 1 inverse
        }                                       // 40 ZZn muls (Projective)
        for (j=0;j<nzs;j++) 
        {
            ha*=ha; had*=had;
            g(A,A,Qx,Qy,ha,had,ADD,FALSE);      // 16 ZZn muls + 1 inversion
        }                                       // 30 ZZn muls (Projective) 
        if (ha==0 || had==0) return FALSE;
    }

#endif

    if (!A.iszero()) return FALSE;

    res=(ha/had);

    p=get_modulus();         // get p
    res=conj(res)/res;    
    res= pow(res,(p+1)/q);   // raise to power of (p^2-1)/q

    if (res.isunity()) return FALSE;

    return TRUE;            
}

//
// ecap(.) function
//

BOOL ecap(ECn& P,ECn& Q,Big& order,ZZn2& cube,ZZn2& res)
{
    ZZn2 Qx;
    ZZn  Qy,iy;
    Big xx,yy;
    BOOL Ok;

    Q.get(xx,yy);
    Qx=(ZZn)xx*cube;
    Qy=(ZZn)yy;

    iy=(ZZn)1/(Qy+1);
    Qx=-2*Qx*iy;
    Qy=(Qy-3)*iy;        // Q+=(0,1)

    Ok=fast_tate_pairing(P,Qx,Qy,order,res);

    if (Ok) return TRUE;
    return FALSE;
}

//
// 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);
}
 
//
// Hash functions
// 

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%256;
        shs_process(&sh,m);
        a/=256;
    }
    while (b>0)
    {
        m=b%256;
        shs_process(&sh,m);
        b/=256;
    }
    shs_hash(&sh,s);

    return HASH_LEN;
}

Big H3(char *x1,char *x2)
{
    sha sh;
    char h[HASH_LEN];
    Big a;
    int i;

    shs_init(&sh);
    for (i=0;i<HASH_LEN;i++)
        shs_process(&sh,x1[i]);
    for (i=0;i<HASH_LEN;i++)
        shs_process(&sh,x2[i]);
    shs_hash(&sh,h);
    a=from_binary(HASH_LEN,h);
    return a;
}

void H4(char *x,char *y)
{ // hashes y=h(x)
    int i;
    sha sh;
    shs_init(&sh);
    for (i=0;i<HASH_LEN;i++)
        shs_process(&sh,x[i]);
    shs_hash(&sh,y);
}

void strip(char *name)
{ /* strip extension off filename */
    int i;
    for (i=0;name[i]!='\0';i++)
    {
        if (name[i]!='.') continue;
        name[i]='\0';
        break;
    }
}

int main()
{
    miracl *mip=mirsys(18,0);    // thread-safe ready.  (36,0) for 1024 bit p
    ifstream common("common.ibe");
    ifstream private_key("private.ibe");
    ifstream key_file,ciphertext;
    ECn U,P,rP,Ppub,Qid,Did,infinity;
    char key[HASH_LEN],pad[HASH_LEN],rho[HASH_LEN],V[HASH_LEN],W[HASH_LEN];
    char ifname[100],ch,iv[16];
    ZZn2 gid,cube,w;
    Big s,p,q,r,cof,x,y;
    int i,Bits;
    aes a;

// DECRYPT

    common >> Bits;
    mip->IOBASE=16;
    common >> p >> q;

    cof=(p+1)/q;

    common >> x >> y;
    EBrick B(x,y,(Big)0,(Big)1,p,QBITS);   // precomputation based on fixed P

#ifdef AFFINE
    ecurve(0,1,p,MR_AFFINE);
#endif
#ifdef PROJECTIVE
    ecurve(0,1,p,MR_PROJECTIVE);
#endif

    P.set(x,y);

    common >> x >> y;
    Ppub.set(x,y);

    common >> x >> y;
    cube.set(x,y);

// get private key

    private_key >> y;
    x=getx(y);              // get unique x from y

    Did.set(x,y);

// figure out where input is coming from

    cout << "file to be decoded = ";
    cin >> ifname;

    strip(ifname);          // open key file
    strcat(ifname,".key");
    key_file.open(ifname,ios::in);
    if (!key_file)
    {
        cout << "Key file " << ifname << " not found\n";
        return 0;
    }

    strip(ifname);          // open ciphertext
    strcat(ifname,".ibe");
    ciphertext.open(ifname,ios::binary|ios::in);
    if (!ciphertext)
    {
        cout << "Unable to open file " << ifname << "\n";
        return 0;
    }

    mip->IOBASE=16;

// get file info

    key_file >> y;
    x=getx(y);      // get unique x from y

    U.set(x,y);   

    key_file >> x;

    to_binary(x,HASH_LEN,V,TRUE);
    key_file >> x;
    to_binary(x,HASH_LEN,W,TRUE);

    mip->IOBASE=10;

// DECRYPT - extract session key


// No need for this as ecap calculates q*U implicitly
//
//    if (q*U!=infinity) 
//    {
//        cout << "Ciphertext rejected" << endl;
//        exit(0);
//    }

    cout << "Decrypting message" << endl;    

    if (!ecap(U,Did,q,cube,w))
    {
        cout << "Ciphertext rejected" << endl;
        exit(0);
    }


    H2(w,pad);    
    for (i=0;i<HASH_LEN;i++) rho[i]=V[i]^pad[i];

    H4(rho,pad);
    for (i=0;i<HASH_LEN;i++) key[i]=W[i]^pad[i];

    r=H3(rho,key);
    
    B.mul(r,x,y);        // r*P
    rP.set(x,y);

    if (U!=rP)
    {
        cout << "Ciphertext rejected" << endl;
        exit(0);
    }
    
//
// Use session key to decrypt file
//

    for (i=0;i<16;i++) iv[i]=i;  // Set CFB IV
    aes_init(&a,MR_CFB1,16,key,iv);

    forever
    { // decrypt input ..
        ciphertext.get(ch);
        if (ciphertext.eof()) break;
        aes_decrypt(&a,&ch);
        cout << ch;
    }
    aes_end(&a);

    return 0;
}