Convert the numbers from base 8 to base 10.

The first number is $645_8$.

$$645_8 = 6 \times 8^2 + 4 \times 8^1 + 5 \times 8^0$$ $$= 6 \times 64 + 4 \times 8 + 5 \times 1$$ $$= 384 + 32 + 5$$ $$= 421_{10}$$

The second number is $776_8$.

$$776_8 = 7 \times 8^2 + 7 \times 8^1 + 6 \times 8^0$$ $$= 7 \times 64 + 7 \times 8 + 6 \times 1$$ $$= 448 + 56 + 6$$ $$= 510_{10}$$

We need to calculate $645_8 - 776_8$, which is equivalent to $421_{10} - 510_{10}$.

$$421_{10} - 510_{10} = -89_{10}$$

We use successive division by 8:

$$89 \div 8 = 11 \text{ remainder } 1$$ $$11 \div 8 = 1 \text{ remainder } 3$$ $$1 \div 8 = 0 \text{ remainder } 1$$

Reading the remainders from bottom to top, $89_{10} = 131_8$.

Since the result of the subtraction in base 10 was negative, the final answer in base 8 is also negative.

$$645_8 - 776_8 = \boxed{-131_8}$$