I want to calculate a Rijndael S-box but something went wrong. How can I calculate the inverse? In the following is my approach:
given: $f(x)=x^8+x^4+x^3+x+1 \rightarrow$ binary: 100011011
0x12 = 10010
calculation:
ggT(100011011,10010):
(x^8+x^4+x^3+x+1)/(x^4+x)=x^4+x+1
-(x^8+x^5)
__________
x^5+x^4+x^3+x+1
-(x^5+x^2)
__________
x^4+x^3+x^2+x+1
-(x^4+x)
__________
x^3+x^2+1 => 1101=100011011+10010*10011
ggT(10010,1101):
(x^4+x)/(x^3+x^2+1)=x+1
-(x^4+x^3+x)
__________
x^3
-(x^3+x^2+1)
____________
x^2+1 => 101=10010+1101*11
ggT(1101,101):
(x^3+x^2+1)/(x^2+1)=x+1
-(x^3+x)
__________
x^2+x+1
-(x^2+1)
_________
x => 10=1101+101*11
ggT(101,10):
(x^2+1)/(x)=x
-(x^2)
__________
1 => 1=101+10*10
1 = 101+10*10
= (10010+1101*11)+10(1101+101*11)
= (10010+11(100011011+10010*10011))+10((100011011+10010*10011)+11(10010+1101*11)))
= (10010+11(100011011+10010*10011))+10((100011011+10010*10011)+11(10010+(100011011+10010*10011)*11)))
a = 100011011 b = 10010
= (b+11(a+10011b))+10((a+10011b)+11(b+11(a+10011b)))
= b+11a+11*10011b+10(a+10011b+11(b+11a+11*10011b))
= b+11a+11*10011b+10(a+10011b+11b+11*11a+11*11*10011b)
= b+11a+11*10011b+10a+10*10011b+10*11+10*11*11a+10*11*1110011b
= b(1+11*10011+10*10011+10*11+10*11*11*10011)
= b(110111100) -> 9 bit but i need 8 bit