Well the dictionary definition of society is: the aggregate of people living together in a more or less ordered community. "More or less ordered" comes from the creation and enforcement of norms. That's how I get legitimate.

I do consider punishment ethical, from a utilitarian perspective it acts as a deterrent, and preventing men from benefiting from evil acts appeals to a human sense of justice and well ordering.