3 C code for MQQ160-SIGN suitable for 8-bit smart cards
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"
10 Danilo Gligoroski and Rune Jensen and Daniel Otte
13 Verified by Danilo Gligoroski
20 #include <avr/pgmspace.h>
22 #include "mqq160-sign.h"
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,
33 static void memxor_idx(void* dest, const void* src, uint16_t length, uint8_t dist){
35 *((uint8_t*)dest) ^= *((uint8_t*)src);
36 dest = (uint8_t*)dest + 1;
37 src = (uint8_t*)src + dist;
41 This is just for testing purposes.
42 It should be programmed in a more flexible way
43 in the MQQ160-SIGN C Library.
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;
53 /* Initialize H1 and H2 = 0 */
55 memset(result, 0, 20);
58 Fill H1 with bits of InputBytes accordingly to RP1 permutation
59 and fill H2 with bits of InputBytes accordingly to RP5 permutation
70 bitindex = 0x80 >> (rp1&0x07);
71 if (input_bytes[byteindex] & bitindex){
72 h1[byteindex_d] ^= bitindex_d;
76 bitindex = 0x80 >> (rp5&0x07);
77 if (input_bytes[byteindex] & bitindex){
78 result[byteindex_d] ^= bitindex_d;
86 // cli_putstr_P(PSTR("\r\nDBG (ref): "));
87 // cli_hexdump(h1, 20);
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)];
95 static uint16_t MaskShort[8] = {0x8000, 0x4000, 0x2000, 0x1000, 0x0800, 0x0400, 0x0200, 0x0100};
97 static uint8_t mqq_q(uint8_t i, uint8_t b1, uint8_t b2, const mqq160_sign_key_t* key){
100 uint8_t result, column, row, k;
103 uint8_t *tmp_ptr=key->a;
105 memcpy(e, key->cc1, 9);
108 memxor_idx((uint8_t*)e, tmp_ptr, 9, 9);
114 memcpy(e, key->cc2, 9);
117 memxor((uint8_t*)e, tmp_ptr, 9);
123 /* So we finished with obtaining e0 .. e7 and e8 */
125 /* We XOR e[8] with b2 and that will be initial value to transform in order to solve a linear system of equations */
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].
136 row |= (e[k]&0x80)>>(k);
139 a[j]=(((uint16_t)row)<<8) | (result>>7);
143 /* Now we finally realize Gausian elimination */
145 /* First we apply upper triangular transformation */
146 for(column=0; column<8; column++)
149 while ((a[row] & MaskShort[column]) == 0){
158 for (j=column+1; j<8; j++)
159 if ((a[j]&MaskShort[column]) !=0){
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){
172 /* The result is in the Least Significant Bits of a[0] ... a[7] */
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];
186 r1[i] = mqq_q(i, r1[i-1], ((uint8_t*)dest)[i], key);
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[].
193 for (i=0; i<20; i++){
194 r1[i] ^= (uint8_t)((key->rp5[byteindex])<<4)
195 | (uint8_t)(key->rp5[byteindex+1]&0x0F);
198 mqq_inv_affine_transformation(r1, (uint8_t*)dest, key);