Simple Hex Multiplication question from AES Algorithm

In summary, the conversation is about a problem with understanding the inverse function of multiplication by X in the AES crypto algorithm. The conversation also includes a discussion on how multiplication by X can be implemented at the byte level and how to find the multiplicative inverse of a non-zero binary polynomial using the extended Euclidean algorithm.
  • #1
CyberStasi
4
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
  • #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?
 

1. What is the AES Algorithm?

The AES (Advanced Encryption Standard) algorithm is a widely used symmetric-key encryption algorithm that is used to protect data by transforming it into an unreadable format. It is commonly used in various security protocols and applications, such as online banking and secure messaging.

2. How does the AES Algorithm work?

The AES algorithm works by taking a plain text message and converting it into a cipher text that can only be deciphered by someone with the correct encryption key. It uses a series of mathematical operations, such as substitution and permutation, to transform the data. The strength of the algorithm lies in its use of multiple rounds of these operations, making it difficult to crack.

3. What is "Simple Hex Multiplication" in the AES Algorithm?

"Simple Hex Multiplication" refers to a specific step in the AES algorithm where the original data is multiplied by a special matrix using hexadecimal numbers. This is done to add an extra layer of security and make it more difficult for hackers to decipher the data.

4. Why is "Simple Hex Multiplication" important in the AES Algorithm?

The "Simple Hex Multiplication" step is crucial in the AES algorithm as it helps to further obscure the original data, making it harder to decrypt. This step, along with other operations, creates a complex and secure encryption that is difficult to break without the proper key.

5. How is "Simple Hex Multiplication" different from other encryption methods?

"Simple Hex Multiplication" is unique to the AES algorithm and is not used in other encryption methods. Other encryption methods may use different mathematical operations or algorithms to transform data, but the AES algorithm specifically uses this step to enhance its security.

Back
Top