16ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org/* 26ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * gf2_8.c 36ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 46ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * GF(256) finite field implementation, with the representation used 56ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * in the AES cipher. 66ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 76ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * David A. McGrew 86ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * Cisco Systems, Inc. 96ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org */ 106ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 116ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org/* 126ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 136ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * Copyright (c) 2001-2006, Cisco Systems, Inc. 146ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * All rights reserved. 156ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 166ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * Redistribution and use in source and binary forms, with or without 176ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * modification, are permitted provided that the following conditions 186ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * are met: 196ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 206ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * Redistributions of source code must retain the above copyright 216ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * notice, this list of conditions and the following disclaimer. 226ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 236ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * Redistributions in binary form must reproduce the above 246ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * copyright notice, this list of conditions and the following 256ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * disclaimer in the documentation and/or other materials provided 266ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * with the distribution. 276ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 286ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * Neither the name of the Cisco Systems, Inc. nor the names of its 296ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * contributors may be used to endorse or promote products derived 306ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * from this software without specific prior written permission. 316ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 326ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 336ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 346ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 356ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 366ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 376ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 386ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 396ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 406ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 416ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 426ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 436ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * OF THE POSSIBILITY OF SUCH DAMAGE. 446ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org * 456ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org */ 466ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 476ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 486ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org#include "datatypes.h" 496ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org#include "gf2_8.h" 506ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 516ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org/* gf2_8_shift() moved to gf2_8.h as an inline function */ 526ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 53be690507ced395dc006cd05cb810700b7c91a83emallinath@google.comgf2_8 546ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.orggf2_8_multiply(gf2_8 x, gf2_8 y) { 556ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org gf2_8 z = 0; 566ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 576ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (y & 1) z ^= x; x = gf2_8_shift(x); 586ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (y & 2) z ^= x; x = gf2_8_shift(x); 596ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (y & 4) z ^= x; x = gf2_8_shift(x); 606ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (y & 8) z ^= x; x = gf2_8_shift(x); 616ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (y & 16) z ^= x; x = gf2_8_shift(x); 626ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (y & 32) z ^= x; x = gf2_8_shift(x); 636ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (y & 64) z ^= x; x = gf2_8_shift(x); 646ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (y & 128) z ^= x; 656ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 666ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org return z; 676ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org} 686ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 696ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 706ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org/* this should use the euclidean algorithm */ 716ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 726ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.orggf2_8 736ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.orggf2_8_compute_inverse(gf2_8 x) { 746ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org unsigned int i; 756ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 766ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (x == 0) return 0; /* zero is a special case */ 776ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org for (i=0; i < 256; i++) 786ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org if (gf2_8_multiply((gf2_8) i, x) == 1) 796ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org return (gf2_8) i; 806ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 816ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org return 0; 826ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org} 836ed0ee98e1c3d29a0ef79996f7d1abf174f39besergeyu@chromium.org 84