Here is a first variant of matrix keyboard. I choose 5x9 size as the smallest suitable to support full cyrillic charset and digits on separate keys (33+10).

It will use 2 shift keys: the red shift and the blue shift, which state will be indicated by the 2 LEDs of corresponding colors.