Simple Hex Multiplication question from AES Algorithm

Click For Summary
The discussion centers on understanding the inverse function of multiplication in the AES algorithm, specifically regarding the operation described in Section 4.2.1 of the FIPS 197 document. The user is confused about how to derive the original value, {57}, from the result {fe} when given the known multiplier {13}. The explanation provided indicates that the multiplicative inverse can be computed using the extended Euclidean algorithm, which finds polynomials that satisfy a specific equation involving the modulus polynomial m(x). The user seeks clarity on this process, indicating a struggle to grasp the concept despite understanding the multiplication steps. The conversation highlights the complexities of polynomial arithmetic in cryptographic algorithms.
CyberStasi
Messages
4
Reaction score
0
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"
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 don't 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 don't 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 don't 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},
thus,
{57} · {13} = {57} · ({01} XOR {02} XOR {10})
= {57} XOR {ae} XOR {07}
= {fe}.
 
Last edited by a moderator:
Mathematics news on Phys.org
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?
 

Thread 'Area of Overlapping Squares'

Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?
View full post »