1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple Hex Multiplication question from AES Algorithm

  1. May 16, 2009 #1
    I searched around a while on the site to see if I could find a thread that could answer this question and was unable to find one. If this has already been asked before, I apologize.

    I'm having a problem with something in the AES crypto algorithm.
    http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf" [Broken]
    In Section 4.2.1 (page 11), they talk about Multiplication by X. I completely understand what they are doing and how. My problem is that they dont ever explain the inverse function of this. Clearly there must be a way to reverse the multiplication. In there example, {57} · {13} = {fe}. I understand how they come to that, but I dont understand how would would take the result of {fe} with the known value of {13} and be able to derive {57}.
    Ive been trying to figure it out for hours. I'm sure its something simple that I'm missing, but for whatever reason it escapes me.

    If you dont want to view the PDF, here is the information they provide.
    4.2.1 Multiplication by x
    Multiplying the binary polynomial defined in equation (3.1) with the polynomial x results in
    b7x^8 + b6x^7 + b5x^6 + b4x^5 + b3x^4 + b2x^3 + b1x^2 + b0x^1 + 0. (4.4)
    The result x · b(x) is obtained by reducing the above result modulo m(x), as defined in equation 4.1 [ m(x) = x^8 + x^4 + x^3 + x + 1 ]. If b7 = 0, the result is already in reduced form. If b7 = 1, the reduction is accomplished by subtracting (i.e., XORing) the polynomial m(x). It follows that multiplication by x (i.e., {00000010} or {02}) can be implemented at the byte level as a left shift and a subsequent conditional bitwise XOR with {1b}. This operation on bytes is denoted by xtime(). Multiplication by higher powers of x can be implemented by repeated application of xtime(). By adding intermediate results, multiplication by any constant can be implemented.
    For example, {57} · {13} = {fe} because
    {57} · {02} = xtime({57}) = {ae}
    {57} · {04} = xtime({ae}) = {47}
    {57} · {08} = xtime({47}) = {8e}
    {57} · {10} = xtime({8e}) = {07},
    {57} · {13} = {57} · ({01} XOR {02} XOR {10})
    = {57} XOR {ae} XOR {07}
    = {fe}.
    Last edited by a moderator: May 4, 2017
  2. jcsd
  3. May 18, 2009 #2
    It says right above where your quote that:

    For any non-zero binary polynomial b(x) of degree less than 8, the multiplicative
    inverse of b(x), denoted b-1(x), can be found as follows: the extended Euclidean algorithm [7] is
    used to compute polynomials a(x) and c(x) such that
    b(x)a(x) + m(x)c(x) = 1. (4.2)
    Hence, a(x) · b(x) mod m(x) = 1, which means
    b-1 (x) = a(x) mod m(x) .

    Unless you're asking about something else?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook