mqq-sign/mqq160-sign.c

   1 /* mqq160-sign.c */
   2 /*
   3    C code for MQQ160-SIGN suitable for 8-bit smart cards
   4
   5    It is supposed that the private key is "engraved" in
   6    the ROM of the smart card - thus it is here stored as
   7    predefined const arrays in "MQQ160-SIGN-PrivateKey.h"
   8
   9    Programmed by
  10    Danilo Gligoroski and Rune Jensen and Daniel Otte
  11    March 2010.
  12
  13    Verified by Danilo Gligoroski
  14    March 2010.
  15
  16 */
  17
  18 #include <string.h>
  19 #include <stdint.h>
  20 #include <avr/pgmspace.h>
  21 #include "memxor/memxor.h"
  22 #include "mqq160-sign.h"
  23
  24 #include "cli.h"
  25
  26 static uint8_t mod20_table[32] PROGMEM = {
  27                  4,  5,  6,  7,  8,  9, 10, 11,
  28                 12, 13, 14, 15, 16, 17, 18, 19,
  29                  0,  1,  2,  3,  4,  5,  6,  7,
  30                  8,  9, 10, 11, 12, 13, 14, 15,
  31 };
  32
  33 static void memxor_idx(void* dest, const void* src, uint16_t length, uint8_t dist){
  34         while(length--){
  35                 *((uint8_t*)dest) ^= *((uint8_t*)src);
  36                 dest = (uint8_t*)dest + 1;
  37                 src  = (uint8_t*)src  + dist;
  38         }
  39 }
  40 /*
  41 This is just for testing purposes.
  42 It should be programmed in a more flexible way
  43 in the MQQ160-SIGN C Library.
  44 */
  45
  46 static void mqq_inv_affine_transformation(const uint8_t* input_bytes, uint8_t* result, const mqq160_sign_key_t* key){
  47         /* The matrix SInv is given as two permutations of 160 elements. */
  48         uint8_t j, byteindex, bitindex, bitindex_d, byteindex_d, rp1, rp5;
  49         uint8_t *rp1_ptr, *rp5_ptr;
  50         uint8_t h1[20];
  51
  52
  53         /* Initialize H1 and H2 = 0 */
  54         memset(h1, 0, 20);
  55         memset(result, 0, 20);
  56
  57         /*
  58            Fill H1 with bits of InputBytes accordingly to RP1 permutation
  59            and fill H2 with bits of InputBytes accordingly to RP5 permutation
  60         */
  61         j=160;
  62         byteindex_d = 0;
  63         bitindex_d = 0x80;
  64         rp1_ptr = key->rp1;
  65         rp5_ptr = key->rp5;
  66         do{
  67                 rp1 = *rp1_ptr++;
  68                 rp5 = *rp5_ptr++;
  69                 byteindex = rp1>>3;
  70                 bitindex = 0x80 >> (rp1&0x07);
  71                 if (input_bytes[byteindex] & bitindex){
  72                         h1[byteindex_d] ^= bitindex_d;
  73                 }
  74
  75                 byteindex = rp5>>3;
  76                 bitindex = 0x80 >> (rp5&0x07);
  77                 if (input_bytes[byteindex] & bitindex){
  78                         result[byteindex_d] ^= bitindex_d;
  79                 }
  80                 bitindex_d >>= 1;
  81                 if(bitindex_d==0){
  82                         ++byteindex_d;
  83                         bitindex_d = 0x80;
  84                 }
  85         }while(--j);
  86 //      cli_putstr_P(PSTR("\r\nDBG (ref): "));
  87 //      cli_hexdump(h1, 20);
  88         for (j=0; j<20; j++){
  89                 result[j] ^= h1[j] ^ h1[pgm_read_byte(j+mod20_table)]
  90                                    ^ h1[pgm_read_byte(8+j+mod20_table)]
  91                                    ^ h1[pgm_read_byte(12+j+mod20_table)];
  92         }
  93 }
  94
  95 static uint16_t MaskShort[8] = {0x8000, 0x4000, 0x2000, 0x1000, 0x0800, 0x0400, 0x0200, 0x0100};
  96
  97 static uint8_t mqq_q(uint8_t i, uint8_t b1, uint8_t b2, const mqq160_sign_key_t* key){
  98         uint8_t  e[9];
  99         uint16_t a[8];
 100         uint8_t result, column, row, k;
 101         int8_t j;
 102         uint16_t temp;
 103         uint8_t *tmp_ptr=key->a;
 104         if(i&1){
 105                 memcpy(e, key->cc1, 9);
 106                 while(b1){
 107                         if(b1&0x80){
 108                                 memxor_idx((uint8_t*)e, tmp_ptr, 9, 9);
 109                         }
 110                         tmp_ptr++;
 111                         b1 <<= 1;
 112                 }
 113         }else{
 114                 memcpy(e, key->cc2, 9);
 115                 while(b1){
 116                         if(b1&0x80){
 117                                 memxor((uint8_t*)e, tmp_ptr, 9);
 118                         }
 119                         tmp_ptr+=9;
 120                         b1 <<= 1;
 121                 }
 122         }
 123         /* So we finished with obtaining e0 .. e7 and e8 */
 124
 125         /* We XOR e[8] with b2 and that will be initial value to transform in order to solve a linear system of equations */
 126         result=b2 ^ e[8];
 127
 128         /*
 129            We can look at the bits of e0 .. e7 as a columns of a given matrix. We want to define 8 variables that have the rows
 130            of that matrix. The variables need to be 16-bit because we will put into the upper 8 bits the bits of e0 .. e7,
 131            and the bits of the variable result will be the Least Significant Bits of a[0] ... a[7].
 132    */
 133         for(j=0; j<8; ++j){
 134                 row = 0;
 135                 for(k=0; k<8; ++k){
 136                         row |= (e[k]&0x80)>>(k);
 137                         e[k]<<=1;
 138                 }
 139                 a[j]=(((uint16_t)row)<<8) | (result>>7);
 140                 result <<= 1;
 141         }
 142
 143         /* Now we finally realize Gausian elimination */
 144
 145         /* First we apply upper triangular transformation */
 146         for(column=0; column<8; column++)
 147         {
 148                 row=column;
 149                 while ((a[row] & MaskShort[column]) == 0){
 150                         row++;
 151                 }
 152                 if(row>column)
 153                 {
 154                         temp=a[column];
 155                         a[column]=a[row];
 156                         a[row]=temp;
 157                 }
 158                 for (j=column+1; j<8; j++)
 159                         if ((a[j]&MaskShort[column]) !=0){
 160                                 a[j] ^= a[column];
 161                         }
 162         }
 163
 164         /* Then we eliminate 1s above the main diagonal */
 165         for (column=7; column>0; column--){
 166                 for (j=column-1; j>=0; j--){
 167                         if ((a[j]&MaskShort[column]) !=0){
 168                                 a[j] ^= a[column];
 169                         }
 170                 }
 171         }
 172         /* The result is in the Least Significant Bits of a[0] ... a[7] */
 173         result = 0;
 174         for(j=0; j<8; ++j){
 175                 result <<=1;
 176                 result |= a[j]&1;
 177         }
 178         return(result);
 179 }
 180
 181 void mqq160_sign(void* dest, const void* hash, const mqq160_sign_key_t* key){
 182         uint8_t i, r1[20], byteindex;
 183         mqq_inv_affine_transformation((uint8_t*)hash, (uint8_t*)dest, key);
 184         r1[0]=((uint8_t*)dest)[0];
 185         for(i=1; i<20; ++i){
 186                 r1[i] = mqq_q(i, r1[i-1], ((uint8_t*)dest)[i], key);
 187         }
 188         /*
 189         Affine transformation is just for the second call. The constant is extracted
 190         from the 4 LSBs of the first 40 bytes of RP5[] and xor-ed to input_bytes[].
 191         */
 192         byteindex = 0;
 193         for (i=0; i<20; i++){
 194                 r1[i] ^=   (uint8_t)((key->rp5[byteindex])<<4)
 195                                  | (uint8_t)(key->rp5[byteindex+1]&0x0F);
 196                 byteindex += 2;
 197         }
 198         mqq_inv_affine_transformation(r1, (uint8_t*)dest, key);
 199 }