mqq-sign/mqq160-sign_P.c

   1 /* mqq160-sign.c */
   2 /*
   3     This file is part of the AVR-Crypto-Lib.
   4     Copyright (C) 2010 Danilo Gligoroski, Daniel Otte (daniel.otte@rub.de)
   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 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_P(void* dest, const void* src, uint16_t length){
  45         while(length--){
  46                 *((uint8_t*)dest) ^= pgm_read_byte(src);
  47                 dest = (uint8_t*)dest +1;
  48                 src  = (uint8_t*)src  +1;
  49         }
  50 }
  51
  52 static void memxor_idx_P(uint8_t* dest, const uint8_t* src, uint16_t length, uint8_t dist){
  53         while(length--){
  54                  *((uint8_t*)dest) ^= pgm_read_byte((uint8_t*)src);
  55                 dest = (uint8_t*)dest + 1;
  56                 src  = (uint8_t*)src  + dist;
  57         }
  58 }
  59 /*
  60 This is just for testing purposes.
  61 It should be programmed in a more flexible way
  62 in the MQQ160-SIGN C Library.
  63 */
  64
  65 static void mqq_inv_affine_transformation(uint8_t* input_bytes, uint8_t* result, const mqq160_sign_key_t* key){
  66         /* The matrix SInv is given as two permutations of 160 elements. */
  67         uint8_t j, byteindex, bitindex, bitindex_d, byteindex_d, rp1, rp5;
  68         uint8_t *r1_ptr, *r5_ptr;
  69         uint8_t h1[20];
  70
  71         /* Initialize H1 and H2 = 0 */
  72         memset(h1, 0, 20);
  73         memset(result, 0, 20);
  74
  75         /*
  76            Fill H1 with bits of InputBytes accordingly to RP1 permutation
  77            and fill H2 with bits of InputBytes accordingly to RP5 permutation
  78         */
  79         bitindex_d = 0x80;
  80         byteindex_d = 0;
  81         j=160;
  82         r1_ptr = key->rp1;
  83         r5_ptr = key->rp5;
  84         do{
  85                 rp1 = pgm_read_byte(r1_ptr++);
  86                 rp5 = pgm_read_byte(r5_ptr++);
  87                 byteindex = rp1>>3;
  88                 bitindex = 0x80 >> (rp1&0x07);
  89                 if (input_bytes[byteindex] & bitindex){
  90                         h1[byteindex_d] ^= bitindex_d;
  91                 }
  92
  93                 byteindex = rp5>>3;
  94                 bitindex = 0x80 >> (rp5&0x07);
  95                 if (input_bytes[byteindex] & bitindex){
  96                         result[byteindex_d] ^= bitindex_d;
  97                 }
  98                 bitindex_d >>= 1;
  99                 if(bitindex_d==0){
 100                         ++byteindex_d;
 101                         bitindex_d = 0x80;
 102                 }
 103         }while(--j);
 104
 105         for (j=0; j<20; j++){
 106                 result[j] ^= h1[j] ^ h1[pgm_read_byte(j+mod20_table)]
 107                                    ^ h1[pgm_read_byte(8+j+mod20_table)]
 108                                    ^ h1[pgm_read_byte(12+j+mod20_table)];
 109         }
 110 }
 111
 112 static uint16_t MaskShort[8] = {0x8000, 0x4000, 0x2000, 0x1000, 0x0800, 0x0400, 0x0200, 0x0100};
 113
 114 static uint8_t mqq_q(uint8_t i, uint8_t b1, uint8_t b2, const mqq160_sign_key_t* key){
 115         uint8_t  e[9];
 116         uint16_t a[8];
 117         uint8_t result, column, row, k;
 118         int8_t j;
 119         uint16_t temp;
 120         uint8_t *tmp_ptr=key->a;
 121         if(i&1){
 122                 memcpy_P(e, key->cc1, 9);
 123                 while(b1){
 124                         if(b1&0x80){
 125                                 memxor_idx_P((uint8_t*)e, tmp_ptr, 9, 9);
 126                         }
 127                         tmp_ptr++;
 128                         b1 <<= 1;
 129                 }
 130         }else{
 131                 memcpy_P(e, key->cc2, 9);
 132                 while(b1){
 133                         if(b1&0x80){
 134                                 memxor_P((uint8_t*)e, tmp_ptr, 9);
 135                         }
 136                         tmp_ptr+=9;
 137                         b1 <<= 1;
 138                 }
 139         }
 140         /* So we finished with obtaining e0 .. e7 and e8 */
 141
 142         /* We XOR e[8] with b2 and that will be initial value to transform in order to solve a linear system of equations */
 143         result=b2 ^ e[8];
 144
 145         /*
 146            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
 147            of that matrix. The variables need to be 16-bit because we will put into the upper 8 bits the bits of e0 .. e7,
 148            and the bits of the variable result will be the Least Significant Bits of a[0] ... a[7].
 149    */
 150         for(j=0; j<8; ++j){
 151                 row = 0;
 152                 for(k=0; k<8; ++k){
 153                         row |= (e[k]&0x80)>>(k);
 154                         e[k]<<=1;
 155                 }
 156                 a[j]=(((uint16_t)row)<<8) | (result>>7);
 157                 result <<= 1;
 158         }
 159
 160         /* Now we finally realize Gausian elimination */
 161
 162         /* First we apply upper triangular transformation */
 163         for(column=0; column<8; column++)
 164         {
 165                 row=column;
 166                 while ((a[row] & MaskShort[column]) == 0){
 167                         row++;
 168                 }
 169                 if(row>column)
 170                 {
 171                         temp=a[column];
 172                         a[column]=a[row];
 173                         a[row]=temp;
 174                 }
 175                 for (j=column+1; j<8; j++)
 176                         if ((a[j]&MaskShort[column]) !=0)
 177                                 a[j] ^= a[column];
 178         }
 179
 180         /* Then we eliminate 1s above the main diagonal */
 181         for (column=7; column>0; column--){
 182                 for (j=column-1; j>=0; j--){
 183                         if ((a[j]&MaskShort[column]) !=0){
 184                                 a[j] ^= a[column];
 185                         }
 186                 }
 187         }
 188         /* The result is in the Least Significant Bits of a[0] ... a[7] */
 189         result = 0;
 190         for(j=0; j<8; ++j){
 191                 result <<=1;
 192                 result |= a[j]&1;
 193         }
 194         return(result);
 195 }
 196
 197 void mqq160_sign_P(void* dest, const void* hash, const mqq160_sign_key_t* key_P){
 198         uint8_t i, r1[20], byteindex;
 199         mqq160_sign_key_t key;
 200         memcpy_P(&key, key_P, sizeof(mqq160_sign_key_t));
 201         mqq_inv_affine_transformation((uint8_t*)hash, (uint8_t*)dest, &key);
 202         r1[0]=((uint8_t*)dest)[0];
 203         for(i=1; i<20; ++i){
 204                 r1[i] = mqq_q(i, r1[i-1], ((uint8_t*)dest)[i], &key);
 205         }
 206         /*
 207         Affine transformation is just for the second call. The constant is extracted
 208         from the 4 LSBs of the first 40 bytes of RP5[] and xor-ed to input_bytes[].
 209         */
 210         byteindex = 0;
 211         for (i=0; i<20; i++){
 212                 r1[i] ^=   (uint8_t)(pgm_read_byte(key.rp5+byteindex)<<4)
 213                                  | (uint8_t)(pgm_read_byte(key.rp5+byteindex+1)&0x0F);
 214                 byteindex += 2;
 215         }
 216         mqq_inv_affine_transformation(r1, (uint8_t*)dest, &key);
 217 }