3 This file is part of the AVR-Crypto-Lib.
4 Copyright (C) 2010 Danilo Gligoroski, Daniel Otte (daniel.otte@rub.de)
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.
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.
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/>.
20 C code for MQQ160-SIGN suitable for 8-bit smart cards
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"
26 Programmed by Danilo Gligoroski, 18 Mar 2010.
33 #include <avr/pgmspace.h>
35 #include "mqq160-sign.h"
38 This is just for testing purposes.
39 It should be programmed in a more flexible way
40 in the MQQ160-SIGN C Library.
44 void mqq_inv_affine_transformation(uint8_t* input_bytes, uint8_t* result, const mqq160_sign_key_t* key);
45 uint8_t mqq_q(uint8_t i, uint8_t b1, uint8_t b2, const mqq160_sign_key_t* key);
49 static uint16_t MaskShort[8] = {0x8000, 0x4000, 0x2000, 0x1000, 0x0800, 0x0400, 0x0200, 0x0100};
51 static uint8_t mqq_q(uint8_t i, uint8_t b1, uint8_t b2, const mqq160_sign_key_t* key){
54 uint8_t result, column, row, k;
57 uint8_t *tmp_ptr=key->a;
59 memcpy_P(e, key->cc1, 9);
62 memxor_idx_P((uint8_t*)e, tmp_ptr, 9, 9);
68 memcpy_P(e, key->cc2, 9);
71 memxor_P((uint8_t*)e, tmp_ptr, 9);
77 /* So we finished with obtaining e0 .. e7 and e8 */
79 /* We XOR e[8] with b2 and that will be initial value to transform in order to solve a linear system of equations */
83 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
84 of that matrix. The variables need to be 16-bit because we will put into the upper 8 bits the bits of e0 .. e7,
85 and the bits of the variable result will be the Least Significant Bits of a[0] ... a[7].
90 row |= (e[k]&0x80)>>(k);
93 a[j]=(((uint16_t)row)<<8) | (result>>7);
97 /* Now we finally realize Gausian elimination */
99 /* First we apply upper triangular transformation */
100 for(column=0; column<8; column++)
103 while ((a[row] & MaskShort[column]) == 0){
112 for (j=column+1; j<8; j++)
113 if ((a[j]&MaskShort[column]) !=0)
117 /* Then we eliminate 1s above the main diagonal */
118 for (column=7; column>0; column--){
119 for (j=column-1; j>=0; j--){
120 if ((a[j]&MaskShort[column]) !=0){
125 /* The result is in the Least Significant Bits of a[0] ... a[7] */
136 void mqq160_sign_P(void* dest, const void* hash, const mqq160_sign_key_t* key_P){
137 uint8_t i, r1[20], byteindex;
138 mqq160_sign_key_t key;
140 memcpy_P(&key, key_P, sizeof(mqq160_sign_key_t));
142 mqq_inv_affine_transformation((uint8_t*)hash, (uint8_t*)dest, &key);
143 r1[0]=((uint8_t*)dest)[0];
145 r1[i] = mqq_q(i, r1[i-1], ((uint8_t*)dest)[i], &key);
148 Affine transformation is just for the second call. The constant is extracted
149 from the 4 LSBs of the first 40 bytes of RP5[] and xor-ed to input_bytes[].
152 for (i=0; i<20; i++){
153 r1[i] ^= (uint8_t)(pgm_read_byte(key.rp5+byteindex)<<4)
154 | (uint8_t)(pgm_read_byte(key.rp5+byteindex+1)&0x0F);
157 mqq_inv_affine_transformation(r1, (uint8_t*)dest, &key);