Opened 12 years ago

Closed 12 years ago

#5791 closed enhancement (fixed)

[cla][patch]Blowfish Optimisations

Reported by: Peter W A Wood Owned by: Tom Trenka
Priority: high Milestone:
Component: Dojox Version: 1.0
Keywords: crypto blowfish encoding Cc:
Blocked By: Blocking:

Description

I did some work using Dojo Blowfish.js as a base and made a number of performance improvements that resulted in processing small blocks of data in less than half the previous time. I submitted a CLA via fax on 13 Jun 2006.

I haven't posted the complete function I wrote as I reduced the input and output encoding options only to a hex string. I also only provided CBC chaining. I can provide the whole class in you'd like.

The unchanged lines of code end with the comment DJ.

The main improvements were replacing the add and xor functions. I took the add function from Paul Johnston's sha1.js (BSD licence)

Qcrypt.add = function (x,y)
{                                                            
  var lsw = (x & 0xFFFF) + (y & 0xFFFF);                                        //PJ
  var msw = (x >> 16) + (y >> 16) + (lsw >> 16);                                //PJ
  return (msw << 16) | (lsw & 0xFFFF);                                          //PJ
};
/** @private */
Qcrypt.xor = function (x,y)
{                                                    
    var lsw = (x & 0xFFFF) ^ (y & 0xFFFF);
    var msw = (x >> 16) ^ (y >> 16);
    return (msw << 16) | (lsw & 0xFFFF);
};

and inlining some functions calls in $:

/** @private */
Qcrypt.$ =	function (v, box)
{
		var d=v&0xff; v>>=8;                                                        //DJ
		var c=v&0xff; v>>=8;                                                        //DJ
		var b=v&0xff; v>>=8;                                                        //DJ
		var a=v&0xff;                                                               //DJ
    //var r=Qcrypt.add(box.s0[a],box.s1[b]); -- inlined for speed
    var x = box.s0[a];
    var y = box.s1[b];
    var lsw = (x & 0xFFFF) + (y & 0xFFFF);
    var msw = (x >> 16) + (y >> 16) + (lsw >> 16);
    r = (msw << 16) | (lsw & 0xFFFF);
    
    //r=Qcrypt.xor(r,box.s2[c]);  -- inlined for speed
    y = box.s2[c];
    lsw = (r & 0xFFFF) ^ (y & 0xFFFF);
    msw = (r >> 16) ^ (y >> 16);
    r = (msw << 16) | (lsw & 0xFFFF);
    
    //return Qcrypt.add(r,box.s3[d]); -- inlined for speed
    y = box.s3[d];
    lsw = (r & 0xFFFF) + (y & 0xFFFF);
    msw = (r >> 16) + (y >> 16) + (lsw >> 16);
    return (msw << 16) | (lsw & 0xFFFF);
		
};

I also made a few changes to the init function

Qcrypt.init =	function(key)
{                                                                               //DJ
    var k=key;                                                                  //DJ
    var kl = k.length;
    var a=[];                                                                   //DJ 	    for(var i=0; i<kl; i++)
      {a.push(k.charCodeAt(i)&0xff);}                                           //DJ
    k=a;                                                                        //DJ
    kl = k.length;
    //	init the boxes                                                          //DJ
    var box = { p:[], s0:[], s1:[], s2:[], s3:[] };                             //DJ
    var qbp = Qcrypt.boxes.p;
    var qbs0 = Qcrypt.boxes.s0;
    var qbs1 = Qcrypt.boxes.s1;
    var qbs2 = Qcrypt.boxes.s2;
    var qbs3 = Qcrypt.boxes.s3;
    var pl = qbp.length;
    var s0l = qbs0.length;
    var s1l = qbs1.length;
    var s2l = qbs2.length;
    var s3l = qbs3.length;
    
    for(i=0; i<pl; i++) {box.p.push(qbp[i]);}
    for(i=0; i<s0l; i++) {box.s0.push(qbs0[i]);}
    for(i=0; i<s1l; i++) {box.s1.push(qbs1[i]);}
    for(i=0; i<s2l; i++) {box.s2.push(qbs2[i]);}
    for(i=0; i<s3l; i++) {box.s3.push(qbs3[i]);}
    
    //	init p with the key                                                     //DJ
    var pos=0;                                                                  //DJ
    var data=0;                                                                 //DJ
    var pl = box.p.length;
    for(i=0; i < pl; i++)
    {                                                                           //DJ
      for (var j=0; j<4; j++)                                                   //DJ
      {                                                                         //DJ
	data = (data*Qcrypt.POW8) | k[pos];                                     //DJ
	if(++pos==kl) {pos=0;}
      }                                                                         //DJ
      box.p[i] = Qcrypt.xor(box.p[i], data);                                    //DJ
    }                                                                           //DJ 	//	encrypt p and the s boxes                                               //DJ
    var res={ left:0, right:0 };                                                //DJ
    for(i=0; i<pl;){
      Qcrypt.eb(res, box);                                                      //DJ
      box.p[i++]=res.left;                                                      //DJ
      box.p[i++]=res.right;                                                     //DJ
    }                                                                           //DJ
		
    for(j=0; j<box.s0.length;)
    {
      Qcrypt.eb(res, box);
      box.s0[j++]=res.left;
      box.s0[j++]=res.right;
    }
    
    for(j=0; j<box.s1.length;)
    {
      Qcrypt.eb(res, box);
      box.s1[j++]=res.left;
      box.s1[j++]=res.right;
    }
      
    for(j=0; j<box.s2.length;)
    {
      Qcrypt.eb(res, box);
      box.s2[j++]=res.left;
      box.s2[j++]=res.right;
    }
    
    for(j=0; j<box.s3.length;)
    {
      Qcrypt.eb(res, box);
      box.s3[j++]=res.left;
      box.s3[j++]=res.right;
    }
      
    return box;                                                                 //DJ
};                                                                              //DJ


I have a few unit tests written using JSAssert but they only cover hex strings and cbc mode. (I generated the test data using Marcus Hahn's Java implementation.

Let me know if you think I can help

Regards

Peter W A Wood

Change History (2)

comment:1 Changed 12 years ago by Adam Peller

Owner: changed from Adam Peller to Tom Trenka
Reporter: changed from guest to Peter W A Wood
Summary: Blowfish Optimisations[cla][patch]Blowfish Optimisations

comment:2 Changed 12 years ago by Tom Trenka

Resolution: fixed
Status: newclosed

(In [12337]) Fixes #5791 (!strict); applied part of Peter Wood's patch to increase performance of Blowfish. Will continue to revisit based on Firebug profiling and the patch to refine and speed up perf.

Note: See TracTickets for help on using tickets.