mqq-sign/mqq160-sign_P.c

   1 /* mqq160-sign.c */
   2 /*
   3     This file is part of the AVR-Crypto-Lib.
   4     Copyright (C) 2006-2015 Daniel Otte (bg@nerilex.org)
   5
   6     This program is free software: you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation, either version 3 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19 /*
  20    C code for MQQ160-SIGN suitable for 8-bit smart cards
  21
  22    It is supposed that the private key is "engraved" in
  23    the ROM of the smart card - thus it is here stored as
  24    predefined const arrays in "MQQ160-SIGN-PrivateKey.h"
  25
  26    Programmed by Danilo Gligoroski, 18 Mar 2010.
  27 */
  28
  29 #include <stdio.h>
  30 #include <stdlib.h>
  31 #include <string.h>
  32 #include <stdint.h>
  33 #include <avr/pgmspace.h>
  34 #include "memxor.h"
  35 #include "mqq160-sign.h"
  36
  37 static const uint8_t mod20_table[32] PROGMEM = {
  38                  4,  5,  6,  7,  8,  9, 10, 11,
  39                 12, 13, 14, 15, 16, 17, 18, 19,
  40                  0,  1,  2,  3,  4,  5,  6,  7,
  41                  8,  9, 10, 11, 12, 13, 14, 15,
  42 };
  43
  44 static void memxor_idx_P(uint8_t *dest, const uint8_t *src, uint16_t length, uint8_t dist){
  45         while(length--){
  46                  *((uint8_t*)dest) ^= pgm_read_byte((uint8_t*)src);
  47                 dest = (uint8_t*)dest + 1;
  48                 src  = (uint8_t*)src  + dist;
  49         }
  50 }
  51 /*
  52 This is just for testing purposes.
  53 It should be programmed in a more flexible way
  54 in the MQQ160-SIGN C Library.
  55 */
  56
  57 static void mqq_inv_affine_transformation(uint8_t *input_bytes, uint8_t *result, const mqq160_sign_key_t *key){
  58         /* The matrix SInv is given as two permutations of 160 elements. */
  59         uint8_t j, byteindex, bitindex, bitindex_d, byteindex_d, rp1, rp5;
  60         const uint8_t *r1_ptr, *r5_ptr;
  61         uint8_t h1[20];
  62
  63         /* Initialize H1 and H2 = 0 */
  64         memset(h1, 0, 20);
  65         memset(result, 0, 20);
  66
  67         /*
  68            Fill H1 with bits of InputBytes accordingly to RP1 permutation
  69            and fill H2 with bits of InputBytes accordingly to RP5 permutation
  70         */
  71         bitindex_d = 0x80;
  72         byteindex_d = 0;
  73         j=160;
  74         r1_ptr = key->rp1;
  75         r5_ptr = key->rp5;
  76         do{
  77                 rp1 = pgm_read_byte(r1_ptr++);
  78                 rp5 = pgm_read_byte(r5_ptr++);
  79                 byteindex = rp1>>3;
  80                 bitindex = 0x80 >> (rp1&0x07);
  81                 if (input_bytes[byteindex] & bitindex){
  82                         h1[byteindex_d] ^= bitindex_d;
  83                 }
  84
  85                 byteindex = rp5>>3;
  86                 bitindex = 0x80 >> (rp5&0x07);
  87                 if (input_bytes[byteindex] & bitindex){
  88                         result[byteindex_d] ^= bitindex_d;
  89                 }
  90                 bitindex_d >>= 1;
  91                 if(bitindex_d==0){
  92                         ++byteindex_d;
  93                         bitindex_d = 0x80;
  94                 }
  95         }while(--j);
  96
  97         for (j=0; j<20; j++){
  98                 result[j] ^= h1[j] ^ h1[pgm_read_byte(j+mod20_table)]
  99                                    ^ h1[pgm_read_byte(8+j+mod20_table)]
 100                                    ^ h1[pgm_read_byte(12+j+mod20_table)];
 101         }
 102 }
 103
 104 static uint16_t MaskShort[8] = {0x8000, 0x4000, 0x2000, 0x1000, 0x0800, 0x0400, 0x0200, 0x0100};
 105
 106 static uint8_t mqq_q(uint8_t i, uint8_t b1, uint8_t b2, const mqq160_sign_key_t *key){
 107         uint8_t  e[9];
 108         uint16_t a[8];
 109         uint8_t result, column, row, k;
 110         int8_t j;
 111         uint16_t temp;
 112         const uint8_t *tmp_ptr=key->a;
 113         if(i&1){
 114                 memcpy_P(e, key->cc1, 9);
 115                 while(b1){
 116                         if(b1&0x80){
 117                                 memxor_idx_P((uint8_t*)e, tmp_ptr, 9, 9);
 118                         }
 119                         tmp_ptr++;
 120                         b1 <<= 1;
 121                 }
 122         }else{
 123                 memcpy_P(e, key->cc2, 9);
 124                 while(b1){
 125                         if(b1&0x80){
 126                                 memxor_P((uint8_t*)e, tmp_ptr, 9);
 127                         }
 128                         tmp_ptr+=9;
 129                         b1 <<= 1;
 130                 }
 131         }
 132         /* So we finished with obtaining e0 .. e7 and e8 */
 133
 134         /* We XOR e[8] with b2 and that will be initial value to transform in order to solve a linear system of equations */
 135         result=b2 ^ e[8];
 136
 137         /*
 138            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
 139            of that matrix. The variables need to be 16-bit because we will put into the upper 8 bits the bits of e0 .. e7,
 140            and the bits of the variable result will be the Least Significant Bits of a[0] ... a[7].
 141    */
 142         for(j=0; j<8; ++j){
 143                 row = 0;
 144                 for(k=0; k<8; ++k){
 145                         row |= (e[k]&0x80)>>(k);
 146                         e[k]<<=1;
 147                 }
 148                 a[j]=(((uint16_t)row)<<8) | (result>>7);
 149                 result <<= 1;
 150         }
 151
 152         /* Now we finally realize Gausian elimination */
 153
 154         /* First we apply upper triangular transformation */
 155         for(column=0; column<8; column++)
 156         {
 157                 row=column;
 158                 while ((a[row] & MaskShort[column]) == 0){
 159                         row++;
 160                 }
 161                 if(row>column)
 162                 {
 163                         temp=a[column];
 164                         a[column]=a[row];
 165                         a[row]=temp;
 166                 }
 167                 for (j=column+1; j<8; j++)
 168                         if ((a[j]&MaskShort[column]) !=0)
 169                                 a[j] ^= a[column];
 170         }
 171
 172         /* Then we eliminate 1s above the main diagonal */
 173         for (column=7; column>0; column--){
 174                 for (j=column-1; j>=0; j--){
 175                         if ((a[j]&MaskShort[column]) !=0){
 176                                 a[j] ^= a[column];
 177                         }
 178                 }
 179         }
 180         /* The result is in the Least Significant Bits of a[0] ... a[7] */
 181         result = 0;
 182         for(j=0; j<8; ++j){
 183                 result <<=1;
 184                 result |= a[j]&1;
 185         }
 186         return(result);
 187 }
 188
 189 void mqq160_sign_P(void *dest, const void *hash, const mqq160_sign_key_t *key_P){
 190         uint8_t i, r1[20], byteindex;
 191         mqq160_sign_key_t key;
 192         memcpy_P(&key, key_P, sizeof(mqq160_sign_key_t));
 193         mqq_inv_affine_transformation((uint8_t*)hash, (uint8_t*)dest, &key);
 194         r1[0]=((uint8_t*)dest)[0];
 195         for(i=1; i<20; ++i){
 196                 r1[i] = mqq_q(i, r1[i-1], ((uint8_t*)dest)[i], &key);
 197         }
 198         /*
 199         Affine transformation is just for the second call. The constant is extracted
 200         from the 4 LSBs of the first 40 bytes of RP5[] and xor-ed to input_bytes[].
 201         */
 202         byteindex = 0;
 203         for (i=0; i<20; i++){
 204                 r1[i] ^=   (uint8_t)(pgm_read_byte(key.rp5+byteindex)<<4)
 205                                  | (uint8_t)(pgm_read_byte(key.rp5+byteindex+1)&0x0F);
 206                 byteindex += 2;
 207         }
 208         mqq_inv_affine_transformation(r1, (uint8_t*)dest, &key);
 209 }