Critical captures are possible against legendaries, but not always. The chance of a critical capture equals (min(255, X) P) / 6 rounded down out of 256, where X is the final capture rate calculated by the capture formula and P is a multiplier based on how many species of Pokémon you've already caught. If X P is less than six, which it might easily be when attempting to capture a legendary (if you've caught thirty species or fewer, in fact, P is 0 so critical captures are always impossible), then it is not possible for a critical capture to occur.
The calculator here will tell you if critical captures are possible with the parameters you put in.
