Subversion Repositories tiny_tate_bilinear_pairing

/*
 * Copyright 2012, Homer Hsing <homer.hsing@gmail.com>
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
 
`define M     593         // M is the degree of the irreducible polynomial
`define WIDTH (2*`M-1)    // width for a GF(3^M) element
`define WIDTH_D0 1187
 
/* PE: processing element */
module PE(clk, reset, ctrl, d0, d1, d2, out);
    input clk;
    input reset;
    input [10:0] ctrl;
    input [`WIDTH_D0:0] d0;
    input [`WIDTH:0] d1, d2;
    output [`WIDTH:0] out;
 
    reg [`WIDTH_D0:0] R0;
    reg [`WIDTH:0] R1, R2, R3;
    wire [1:0] e0, e1, e2; /* part of R0 */
    wire [`WIDTH:0] ppg0, ppg1, ppg2, /* output of PPG */
                    mx0, mx1, mx2, mx3, mx4, mx5, mx6, /* output of MUX */
                    ad0, ad1, ad2, /* output of GF(3^m) adder */
                    cu0, cu1, cu2, /* output of cubic */
                    mo0, mo1, mo2, /* output of mod_p */
                    t0, t1, t2;
    wire c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10;
 
    assign {c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10} = ctrl;
    assign mx0 = c0 ? d1 : ad2;
    assign mx1 = c2 ? d2 : ad2;
    always @ (posedge clk)
        if(reset) R1 <= 0;
        else if (c1) R1 <= mx0;
    always @ (posedge clk)
        if(reset) R2 <= 0;
        else if (c3) R2 <= mx1;
    always @ (posedge clk)
        if(reset) R0 <= 0;
        else if (c4) R0 <= d0;
        else if (c5) R0 <= R0 << 6;
    assign {e2,e1,e0} = R0[`WIDTH_D0:(`WIDTH_D0-5)];
    PPG
        ppg_0 (e0, R1, ppg0),
        ppg_1 (e1, R2, ppg1),
        ppg_2 (e2, R1, ppg2);
    v0  v0_ (ppg0, cu0);
    v1  v1_ (ppg1, cu1);
    v2  v2_ (ppg2, cu2);
    assign mx2 = c6 ? ppg0 : cu0;
    assign mx3 = c6 ? ppg1 : cu1;
    assign mx4 = c6 ? mo1 : cu2;
    assign mx5 = c7 ? mo2 : R3;
    mod_p
        mod_p_0 (mx3, mo0),
        mod_p_1 (ppg2, t0),
        mod_p_2 (t0, mo1),
        mod_p_3 (R3, t1),
        mod_p_4 (t1, t2),
        mod_p_5 (t2, mo2);
    assign mx6 = c9 ? mo0 : mx3;
    f3m_add
        f3m_add_0 (mx2, mx6, ad0),
        f3m_add_1 (mx4, c8 ? mx5 : 0, ad1),
        f3m_add_2 (ad0, ad1, ad2);
    always @ (posedge clk)
        if (reset) R3 <= 0;
        else if (c10) R3 <= ad2;
        else R3 <= 0; /* change */
    assign out = R3;
endmodule
 
// C = (x*B mod p(x))
module mod_p(B, C);
    input [`WIDTH:0] B;
    output [`WIDTH:0] C;
    wire [`WIDTH+2:0] A;
    assign A = {B[`WIDTH:0], 2'd0}; // A == B*x
    wire [1:0] w0;
    f3_mult m0 (A[1187:1186], 2'd2, w0);
    f3_sub s0 (A[1:0], w0, C[1:0]);
    assign C[223:2] = A[223:2];
    wire [1:0] w112;
    f3_mult m112 (A[1187:1186], 2'd1, w112);
    f3_sub s112 (A[225:224], w112, C[225:224]);
    assign C[1185:226] = A[1185:226];
endmodule
 
// PPG: partial product generator, C == A*d in GF(3^m)
module PPG(d, A, C);
    input [1:0] d;
    input [`WIDTH:0] A;
    output [`WIDTH:0] C;
    genvar i;
    generate
        for (i=0; i < `M; i=i+1) 
        begin: ppg0
            f3_mult f3_mult_0 (d, A[2*i+1:2*i], C[2*i+1:2*i]);
        end
    endgenerate
endmodule
 
// f3m_add: C = A + B, in field F_{3^M}
module f3m_add(A, B, C);
    input [`WIDTH : 0] A, B;
    output [`WIDTH : 0] C;
    genvar i;
    generate
        for(i=0; i<`M; i=i+1) begin: aa
            f3_add aa(A[(2*i+1) : 2*i], B[(2*i+1) : 2*i], C[(2*i+1) : 2*i]);
        end
    endgenerate
endmodule
 
// f3_add: C == A+B (mod 3)
module f3_add(A, B, C);
    input [1:0] A, B;
    output [1:0] C;
    wire a0, a1, b0, b1, c0, c1;
    assign {a1, a0} = A;
    assign {b1, b0} = B;
    assign C = {c1, c0};
    assign c0 = ( a0 & ~a1 & ~b0 & ~b1) |
                (~a0 & ~a1 &  b0 & ~b1) |
                (~a0 &  a1 & ~b0 &  b1) ;
    assign c1 = (~a0 &  a1 & ~b0 & ~b1) |
                ( a0 & ~a1 &  b0 & ~b1) |
                (~a0 & ~a1 & ~b0 &  b1) ;
endmodule
 
// f3_sub: C == A-B (mod 3)
module f3_sub(A, B, C);
    input [1:0] A, B;
    output [1:0] C;
    f3_add a0(A, {B[0],B[1]}, C);
endmodule
 
// f3_mult: C = A*B (mod 3)
module f3_mult(A, B, C); 
    input [1:0] A;
    input [1:0] B; 
    output [1:0] C;
    wire a0, a1, b0, b1;
    assign {a1, a0} = A;
    assign {b1, b0} = B;
    assign C[0] = (~a1 & a0 & ~b1 & b0) | (a1 & ~a0 & b1 & ~b0);
    assign C[1] = (~a1 & a0 & b1 & ~b0) | (a1 & ~a0 & ~b1 & b0);
endmodule