PHP Classes

File: dot.vs.gfmul128.php

Recommend this page to a friend!
  Classes of Jose Luis Lucas  >  PHP AES GCM Encryption SIV  >  dot.vs.gfmul128.php  >  Download  
File: dot.vs.gfmul128.php
Role: Auxiliary script
Content type: text/plain
Description: Auxiliary script
Class: PHP AES GCM Encryption SIV
Encrypt data with pure PHP code for Rijndael AES
Author: By
Last change: Update dot.vs.gfmul128.php
Date: 3 years ago
Size: 13,150 bytes
 

Contents

Class file image Download
<?
/**

COMPUTING ON GALOIS 128-FIELDS

Functions coded:

as defined in https://www.intel.cn/content/dam/www/public/us/en/documents/white-papers/carry-less-multiplication-instruction-in-gcm-mode-paper.pdf	

	- PCLMULQDQ 	
	- GFMUL     

and as defined in https://www.ietf.org/id/draft-irtf-cfrg-gcmsiv-09.txt
	
	- mulX_POLYVAL 	
	- mulX_GHASH 	
	
	- dot_siv_ghash
	- dot_siv_polyval (in binary mode, fastest)
	
	- dot_big_math (using longs longs mode 1)
	- dot2         (using longs longs mode 2, faster)



from draft https://tools.ietf.org/id/draft-irtf-cfrg-gcmsiv-09.html

Polynomials in this document will be written as 16-byte values. 
For example, the sixteen bytes 01000000000000000000000000000492 
would represent the polynomial x^127 + x^124 + x^121 + x^114 + 1, 
which is also the value of x^-128 in this field.

10010010000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

(1's are in positions 127,124,121,114 and 0)

$packed="";
foreach (str_split("10010010000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001",8) as $z) $packed.=chr(bindec($z));
$hex=bin2hex(strrev($packed));

$Ri=$hex=01000000000000000000000000000492

irreducible polynomial: POLYVAL works modulo x^128 + x^127 + x^126 + x^121 + 1

11000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

$R=$hex=010000000000000000000000000000C2


Then, dot makes 2 gf128 operations

- first 
	$ab = gf128_dot($a , $b, $R); 		mul a,b and reduce 		modulo 010000000000000000000000000000C2
-second
	Ri = 01000000000000000000000000000492
	$r = gf128_dot($ab, $Ri, $R);		mul ab,Ri(=x^-128) and reduce 	modulo 010000000000000000000000000000C2
	

function convert
	
		    ''' Polynomials in this field are converted to and from 128-bit strings
		    by taking the least-significant bit of the first byte to be the
		    coefficient of x^0, the most-significant bit of the first byte to the
		    the coefficient of x^7 and so on, until the most-significant bit of
		    the last byte is the coefficient of x^127.
		    '''	

so convert transform to an element of the binary galois field 2^128	


   
If a = 66e94bd4ef8a2c3b884cfa59ca342b2e and b =
   ff000000000000000000000000000000 then a+b =
   99e94bd4ef8a2c3b884cfa59ca342b2e, a*b =
   37856175e9dc9df26ebc6d6171aa0ae9 and 
   
   dot(a, b) = ebe563401e7e91ea3ad6426b8140c394.
   
   then dot(a,b) = gf128(a,b)
   
Also dot can be simplified

				    		 		    
		R	= e1000000000000000000000000000000;
		
		no need to convert 
		
		1- a=strrev a
		2- H 	= 40000000000000000000000000000000;
		   b=mul b,H mod e1000000000000000000000000000000
		3- r=strrev(mul a,b mod e1000000000000000000000000000000)	    
*/
		    
class Galois128
{	
	function __construct()
		{
		$this->hbin	= $this->h2bin = array();
		for ($k=0;$k<16;$k++) 
			{
			$this->hbin[$k]=sprintf("%04b",$k);
			$this->h2bin[$this->hbin[$k]]=dechex($k);
			}			
		}		    
	function convert($x) 
		{ 		
		$poly = 0;
		    for ($b=0;$b<16;$b++)
		    	{
		        $byte_val = 0;
		        for ($i=7; $i>-1; $i--)
			    {
		            $index = 127 - (8 * $b) - $i;				
		            $t_byte_val = bcmul(gmp_and(bcdiv($x,bcpow('2',$index)) , 1),bcpow('2',$i));
			    $byte_val = bcadd($t_byte_val,$byte_val) ;
			    }			
		        $poly = bcadd(bcmul($poly,256) , $byte_val) ;
			}
		    return $poly;
		}
		
	function gf128_dot($x, $y, $R)
		{
		    /*''' Multiplication in GF(2^128). 
		    The caller specifies the irreducible polynomial.
		    '''*/
		    $z = 0;
		    for ($i=127;$i>-1;$i--)
		        {
		        $z = $z ^ ($x * gmp_and(bcdiv($y,bcpow('2',$i)),1));      # if MSB is 0, XOR with 0, else XOR with x
		        $x = bcdiv($x,2) ^ (gmp_and($x , 1) * $R);     		  # shift and also reduce by R if overflow detected
			}
		
		    return $z;
		}			
	 function u128_dec($hex)
	 	{
	     	$dec = 0;
	     	$len = strlen($hex);
	     	for ($i = 1; $i <= $len; $i++)
	         	$dec = bcadd($dec, bcmul(strval(hexdec($hex[$i - 1])), bcpow('16', strval($len - $i))));	
	     	return $dec;
	 	}
	 
	function dot_big_math($a,$b)
		{ 
		/*
		Working with long long elements
		
		mod R=0x010000000000000000000000000000C2
		
		convert elements
		
		1- ab=mul a,b
		2- r=mul ab,Ri=0x01000000000000000000000000000492 		
		*/
	
		    $Ri	= $this->convert($this->u128_dec("01000000000000000000000000000492"));		 		    
		    $R 	= $this->convert($this->u128_dec("010000000000000000000000000000C2"));		    				    
		  		    
		    $b	= $this->convert($this->u128_dec($b));
		    $X	= str_split($a,32);
		    
                    $i	= 0;$r = str_repeat("\0",16);	
		
		    while($i<sizeof($X))
			{
			$a	= $this->convert($this->u128_dec(bin2hex(pack("H*",$X[$i])^$r)));		    		    
		    	$ab	= $this->gf128_dot($a , $b, $R);		    
			$r	= gmp_Export($this->convert($this->gf128_dot($ab, $Ri, $R)));
		    	++$i;
		    	}

		    return bin2hex($r);
		}
	function dot2($a,$b)
		{   
		/*
		simplified dot
		
		no need to convert 
		
		mod R=0xe1000000000000000000000000000000
		
		1- a=strrev a
		2- b=mul b,H
		3- r=mul a,b 		
		*/
		 
		    $H 	= $this->u128_dec("40000000000000000000000000000000");		    		 		    
		    $R	= $this->u128_dec("e1000000000000000000000000000000");			    
		    
		    $b	= $this->gf128_dot($this->u128_dec($this->reverse($b)) , $H, $R);		    		    		    
		    $X	= str_split($a,32);
		    
                    $i	= 0;$r = str_repeat("\0",16);	
		
		    while($i<sizeof($X))
			{
			$a	= $this->u128_dec(bin2hex(strrev(pack("H*",$X[$i]))^$r));		    		    		    
			$r	= gmp_Export($this->gf128_dot($a, $b, $R));
		    	++$i;
		    	}

		    return bin2hex(strrev($r));
		}
/*********************************************************************************************************/
	function reverse($hex)
		{
		return implode(array_reverse(str_split($hex,2)));
		}
	function bstr($hex)
		{
		// from hex to binary string
		return str_replace($this->h2bin,$this->hbin,$hex);
		}
	function to128($bin)
		{
		$result="";foreach (str_split(bin2hex($bin),2) as $z) $result.=$z[1];
		return $result;
		}
	function bstrtohex($bin)
		{
		$hex="";foreach (str_split($this->to128($bin),4) as $bin) $hex.=dechex(bindec($bin));
		return $hex;
		}
	function mul($binX)
		{
		$mask0 	= str_repeat(sprintf("%08b",1),16);
		$mask1 	= str_repeat("01111111",16);
		// polynomial reduction
		$R 	= $this->bstr("000000000000000000000000000000e1");
		
		$xLSB 	= $binX[7];				
		$binX 	= "0".substr($binX,0,-1)&$mask1|substr($binX&$mask0,15);				
		if ($xLSB)
			$binX = $this->to128($binX^$R);
			
		return $binX;		
		}
				
	function PCLMULQDQ($X,$Y) 
		{
		// as defined in https://www.intel.cn/content/dam/www/public/us/en/documents/white-papers/carry-less-multiplication-instruction-in-gcm-mode-paper.pdf		
		/*
		a = 			7b5b54657374566563746f725d53475d
		b = 			48692853686179295b477565726f6e5d
		PCLMULQDQ (a, b) = 	040229a09a5ed12e7e4e10da323506d2 
		
		little endian
		
		rbits =  Reflecting Bits 
		
		PCLMULQDQ (a, b) = rbits(GFMUL (rbits(a),rbits(b))) 
		
		with reduction
		*/

		$p     = str_repeat("0",128);						
		
		$binY  = strrev($this->bstr($Y));				
		$binX  = strrev($this->bstr($this->reverse($X)));
		
		for($i = 0; $i < 128; $i++) 
			{							 
			if ($binY[$i]) 						
				$p^=$binX;
			
			$binX = $this->mul($binX);				 			
			}
	
		return $this->reverse($this->bstrtohex(strrev($p)));				
		}	 
	function GFMUL($X,$Y) 
		{
		// as defined in https://www.intel.cn/content/dam/www/public/us/en/documents/white-papers/carry-less-multiplication-instruction-in-gcm-mode-paper.pdf
		/*
		Counter mode
		Data: 			952b2a56a5604ac0b32b6656a05b40b6
		Hash Key: 		dfa6bf4ded81db03ffcaff95f830f061
		Multiplication Result: 	da53eb0ad2c55bb64fc4802cc3feda60		
		*/

		$p     = str_repeat("0",128);						
		
		$binY  = $this->bstr($this->reverse($Y));
		$binY  = implode(array_reverse(str_split($binY,8)));			
		$binX  = $this->bstr($this->reverse($X));
		
		for($i = 0; $i < 128; $i++) 
			{							 
			if ($binY[$i]) 										
				$p^=$binX;
							
			$binX = $this->mul($binX);				 			
			}
	
		return $this->reverse($this->bstrtohex($p));			
		}

	function mulX_POLYVAL($X)
		{
		/*			   		   		
		multiplies X by bigendian(010000000000000000000000000000c2) 
		        and reduce modulo 000000000000000000000000000000e1 
			
		let H = 25629347589242761d31f826ba4b757b
		If we wished to calculate this
		   given only an implementation of POLYVAL then we would first calculate
		   the key for POLYVAL, 
		   mulX_POLYVAL(ByteReverse(H)) = f6ea96744df0633aec8424b18e26c54a
		*/
		
		$Ri = $this->reverse("010000000000000000000000000000c2");
		return $this->reverse($this->gfmul($X,$Ri));	
		}
				
	function mulX_GHASH($X)
		{
		/* 
		multiplies X by bigendian(40000000000000000000000000000000)
		        and reduce modulo 000000000000000000000000000000e1
			
		let H = 25629347589242761d31f826ba4b757b
		If we wished to calculate this
		   given only an implementation of GHASH then the key for GHASH would be
		   
		   mulX_GHASH(ByteReverse(H)) = dcbaa5dd137c188ebb21492c23c9b112
		*/
								
		$binX  = $this->mul($this->bstr($X));
		return $this->reverse($this->bstrtohex($binX));		
		}

	function dot_siv_ghash($X,$Y)
		{
		// as defined in https://www.ietf.org/id/draft-irtf-cfrg-gcmsiv-09.txt
		/*
		   GHASH(H, X_1, ..., X_n) =
		   ByteReverse(POLYVAL(mulX_POLYVAL(ByteReverse(H)), ByteReverse(X_1),
		   ..., ByteReverse(X_n)))
		   		
		let H = 25629347589242761d31f826ba4b757b
		  X_1 = 4f4f95668c83dfb6401762bb2d01a262  
		  X_2 = d1a24ddd2721d006bbe45f20d3c9f362
		  
		GHASH(H, X_1, X_2)= bd9b3997046731fb96251b91f9c99d7a		
		*/
		$X	=str_split($X,32);
		$H	=$Y;
		$GHASH	=str_repeat("\0",16);
		
		$i	=0;			
		while($i<sizeof($X))
			{
			$GHASH=pack("H*",$this->gfmul(bin2hex($GHASH^pack("H*",$X[$i])),$H));			
			++$i;
			}
			
		return bin2hex($GHASH);					
		}
				
	function dot_siv_polyval($X,$Y)
		{
		// as defined in https://www.ietf.org/id/draft-irtf-cfrg-gcmsiv-09.txt
		/*
		POLYVAL(H, X_1, ..., X_n) =
		   ByteReverse(GHASH(mulX_GHASH(ByteReverse(H)), ByteReverse(X_1), ...,
		   ByteReverse(X_n)))
		   
		
		let H = 25629347589242761d31f826ba4b757b
		  X_1 = 4f4f95668c83dfb6401762bb2d01a262  
		  X_2 = d1a24ddd2721d006bbe45f20d3c9f362
		  
		POLYVAL(H, X_1, X_2)= f7a3b47b846119fae5b7866cf5e5b77e			
		*/
		$X 	= str_split($X,32);
		$H 	= $this->mulX_GHASH($Y);
		$GHASH	= str_repeat("\0",16);	
		
		$i 	= 0;		
		while($i<sizeof($X))
			{
			$GHASH=pack("H*",$this->gfmul(bin2hex($GHASH^pack("H*",$this->reverse($X[$i]))),$H));
			++$i;
			}			
		return $this->reverse(bin2hex($GHASH));					
		}
}

$gf128=new Galois128;

echo " PCLMULQDQ 		".$gf128->PCLMULQDQ("7b5b54657374566563746f725d53475d","48692853686179295b477565726f6e5d")."\n";
echo " GFMUL     		".$gf128->GFMUL("952b2a56a5604ac0b32b6656a05b40b6","dfa6bf4ded81db03ffcaff95f830f061")."\n";
echo " mulX_POLYVAL 	".$gf128->mulX_POLYVAL(("25629347589242761d31f826ba4b757b"))."\n";
echo " mulX_GHASH 	".$gf128->mulX_GHASH(("25629347589242761d31f826ba4b757b"))."\n";
echo " GHASH   		".$gf128->dot_siv_ghash("4f4f95668c83dfb6401762bb2d01a262d1a24ddd2721d006bbe45f20d3c9f362","25629347589242761d31f826ba4b757b")."\n";
/*
from https://www.ietf.org/id/draft-irtf-cfrg-gcmsiv-09.txt page 10

The latter halves of the ciphertext blocks are discarded and the
   remaining bytes are concatenated to form the per-message keys.  Thus
   the 
   
   message-authentication key is 310728d9911f1f3837b24316c3fab9a0
   
   and the message-encryption key is a4c5ae6249963279c100be4d7e2c6edd.

   The length block contains the encoding of the bit-lengths of the
   additional data and plaintext, respectively.  The string "example" is
   seven characters, thus 56 bits (or 0x38 in hex).  The string "Hello
   world" is 11 characters, or 88 = 0x58 bits.  Thus the length block is
   38000000000000005800000000000000.

   The input to POLYVAL is the padded additional data, padded plaintext
   and then the length block.  This is 
   
   6578616d706c6500000000000000000048656c6c6f20776f726c64000000000038000000000000005800000000000000
   
   based on the ASCII encoding of "example" (6578616d706c65) and of
   "Hello world" (48656c6c6f20776f726c64).

   Calling POLYVAL with the message-authentication key and the input
   above results in S_s = ad7fcf0b5169851662672f3c5f95138f.
*/

echo "\nComputing POLYVAL\n\n";
$input  ="6578616d706c6500000000000000000048656c6c6f20776f726c64000000000038000000000000005800000000000000";
$authkey="310728d9911f1f3837b24316c3fab9a0";

echo " Valid result   ad7fcf0b5169851662672f3c5f95138f\n";
$t=hrtime(true);
echo " POLYVAL 		".$gf128->dot_siv_polyval($input,$authkey)." ";
echo ((hrtime(true)-$t)/1000000)." ms (in binary mode)\n";
$t=hrtime(true);
echo " dot_big_math 	".$gf128->dot_big_math($input,$authkey)." ";
echo ((hrtime(true)-$t)/1000000)." ms (long long mode 1)\n";
$t=hrtime(true);
echo " dot_big_math2 	".$gf128->dot2($input,$authkey)." ";
echo ((hrtime(true)-$t)/1000000)." ms (long long mode 2)\n";

For more information send a message to info at phpclasses dot org.