How to validate CPF with DataAnnotation on client and server?

First, create a class that will be the Custom Validation Attribute. The class code will be as follows:

/// <summary>
/// Validação customizada para CPF
/// </summary>
public class CustomValidationCPFAttribute : ValidationAttribute, IClientValidatable
{
    /// <summary>
    /// Construtor
    /// </summary>
    public CustomValidationCPFAttribute() { }

    /// <summary>
    /// Validação server
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public override bool IsValid(object value)
    {
        if (value == null || string.IsNullOrEmpty(value.ToString()))
        return true;

        bool valido = Util.ValidaCPF(value.ToString());
        return valido;
    }

    /// <summary>
    /// Validação client
    /// </summary>
    /// <param name="metadata"></param>
    /// <param name="context"></param>
    /// <returns></returns>
    public IEnumerable<ModelClientValidationRule> GetClientValidationRules(
        ModelMetadata metadata, ControllerContext context)
    {
        yield return new ModelClientValidationRule
        {
            ErrorMessage = this.FormatErrorMessage(null),
            ValidationType = "customvalidationcpf"
        };
    }
}

The Code of the Util class, which has the method that does the CPF validation is as follows:

    /// <summary>
    /// Remove caracteres não numéricos
    /// </summary>
    /// <param name="text"></param>
    /// <returns></returns>
    public static string RemoveNaoNumericos(string text)
    {
        System.Text.RegularExpressions.Regex reg = new System.Text.RegularExpressions.Regex(@"[^0-9]");
        string ret = reg.Replace(text, string.Empty);
        return ret;
    }

    /// <summary>
    /// Valida se um cpf é válido
    /// </summary>
    /// <param name="cpf"></param>
    /// <returns></returns>
    public static bool ValidaCPF(string cpf)
    {
        //Remove formatação do número, ex: "123.456.789-01" vira: "12345678901"
        cpf = Util.RemoveNaoNumericos(cpf);

        if (cpf.Length > 11)
            return false;

        while (cpf.Length != 11)
            cpf = '0' + cpf;

        bool igual = true;
        for (int i = 1; i < 11 && igual; i++)
            if (cpf[i] != cpf[0])
                igual = false;

        if (igual || cpf == "12345678909")
            return false;

        int[] numeros = new int[11];

        for (int i = 0; i < 11; i++)
            numeros[i] = int.Parse(cpf[i].ToString());

        int soma = 0;
        for (int i = 0; i < 9; i++)
            soma += (10 - i) * numeros[i];

        int resultado = soma % 11;

        if (resultado == 1 || resultado == 0)
        {
            if (numeros[9] != 0)
                return false;
        }
        else if (numeros[9] != 11 - resultado)
            return false;

        soma = 0;
        for (int i = 0; i < 10; i++)
            soma += (11 - i) * numeros[i];

        resultado = soma % 11;

        if (resultado == 1 || resultado == 0)
        {
            if (numeros[10] != 0)
                return false;
        }
        else
            if (numeros[10] != 11 - resultado)
                return false;

        return true;
    }

Add on the page or Layout that the page is using reference for the following Javascript files, which are used to use DataAnnotations:

    <script src="@Url.Content("~/Scripts/jquery-1.4.4.min.js")" type="text/javascript"></script>
    <script src="@Url.Content("~/Scripts/jquery.validate.min.js")" type="text/javascript"></script>
    <script src="@Url.Content("~/Scripts/jquery.validate.unobtrusive.min.js")" type="text/javascript"></script>
    <script src="@Url.Content("~/Scripts/jquery.unobtrusive-ajax.min.js")" type="text/javascript"></script>

Also, add the reference to the Javascript file created to make the validation on client:

In the class with the properties add the created attribute name.

public class Usuario
{
[Required(ErrorMessage="Nome requerido")]
public string Nome { get; set; }

[Required(ErrorMessage="CPF obrigatório")]
[CustomValidation.CustomValidationCPF(ErrorMessage="CPF inválido")]
public string CPF { get; set; }
}

And in the form the spaces to display the error messages:

@using (Html.BeginForm())
{
@Html.LabelFor(a => a.Nome, "Nome")
@Html.TextBoxFor(a => a.Nome)
@Html.ValidationMessageFor(a => a.Nome)
<br />

@Html.LabelFor(a => a.CPF, "CPF")
@Html.TextBoxFor(a => a.CPF)
@Html.ValidationMessageFor(a => a.CPF)
<br />

<input type="submit" value="Enviar" />
}

I make here a complement to the answer given by @ samir-braga, which will make the validation only on the server. Even if the code appears to be being validated on the client, since the error message will be displayed, this validation is done on the server.

For validation to actually occur on the client, before data is submitted to the server, a javascript implementation of the ValidaCPF method will be required in addition to including this method in $.validator and $.validator.unobtrusive, like this:

$.validator.addMethod("customvalidationcpf", function (value, element, param) {
    return validaCPF(value); //chama um método validaCPF implementado em javascript
});
$.validator.unobtrusive.adapters.addBool("customvalidationcpf");

The name customvalidationcpf must match the value of ValidationType declared in the GetClientValidationRules method.

Here is a CPF validation implementation in javascript:

function validaCPF(s) {
    var i;
    var l = '';
    for (i = 0; i < s.length; i++) if (!isNaN(s.charAt(i))) l += s.charAt(i);
    s = l;
    if (s.length != 11) return false;
    var c = s.substr(0, 9);
    var dv = s.substr(9, 2);
    var d1 = 0;
    for (i = 0; i < 9; i++) d1 += c.charAt(i) * (10 - i);
    if (d1 == 0) return false;
    d1 = 11 - (d1 % 11);
    if (d1 > 9) d1 = 0;
    if (dv.charAt(0) != d1) return false;
    d1 *= 2;
    for (i = 0; i < 9; i++) d1 += c.charAt(i) * (11 - i)
    d1 = 11 - (d1 % 11);
    if (d1 > 9) d1 = 0;
    if (dv.charAt(1) != d1) return false;
    return true;
}

[System.Web.Mvc.Remote("MetodoValidarCPF", "SeuController", ErrorMessage = "CPF inválido.")]

And then you can create a validations-only class and call this DLL in controler and it will recognize

public JsonResult ValidarCPF(string cpf = "")
{
   bool validaCPF = SIBValidacoesBLL.ValidarCPF(strCpf);
   return Json(validaCPF, JsonRequestBehavior.AllowGet);
}

If it returns true passes on validation, if it returns false it bar, you can also return a message for each validation, so if it returns true passes if it returns string presents the string, example

return Json("Se não passou na validação retorna uma mensagem customizada", JsonRequestBehavior.AllowGet);