Simple Hex Multiplication question from AES Algorithm

AI Thread 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 'Video on imaginary numbers and some queries'
Hi, I was watching the following video. I found some points confusing. Could you please help me to understand the gaps? Thanks, in advance! Question 1: Around 4:22, the video says the following. So for those mathematicians, negative numbers didn't exist. You could subtract, that is find the difference between two positive quantities, but you couldn't have a negative answer or negative coefficients. Mathematicians were so averse to negative numbers that there was no single quadratic...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Back
Top