Segurança em formulários! JavaScript+PHP!

Olá pessoal, sempre vejo o pessoal discutindo a melhor forma de proteger um formulário, seja criando máscaras com jQuery para dados como CPF, CNPJ, etc, ou criando uma condicional para verificar se uma senha tem o número mínimo de caracteres ou se o E-mail está no formato correto. Mas se eu usar, por exemplo, o firebug eu consigo remover tudo isso e enviar os dados sem serem verificados! Então, devo fazer essas verificações tanto com JavaScript como com PHP? Qual é a melhor forma? Qual a mais eficiente?

Obrigado!