Change foreign key constraint naming convention

You can implement a custom sql generator class derived from SqlServerMigrationSqlGenerator from System.Data.Entity.SqlServer namespace:

public class CustomSqlGenerator : SqlServerMigrationSqlGenerator
{
    protected override void Generate(AddForeignKeyOperation addForeignKeyOperation)
    {
        addForeignKeyOperation.Name = getFkName(addForeignKeyOperation.PrincipalTable,
            addForeignKeyOperation.DependentTable, addForeignKeyOperation.DependentColumns.ToArray());
        base.Generate(addForeignKeyOperation);
    }

    protected override void Generate(DropForeignKeyOperation dropForeignKeyOperation)
    {
        dropForeignKeyOperation.Name = getFkName(dropForeignKeyOperation.PrincipalTable,
            dropForeignKeyOperation.DependentTable, dropForeignKeyOperation.DependentColumns.ToArray());
        base.Generate(dropForeignKeyOperation);
    }

    private static string getFkName(string primaryKeyTable, string foreignKeyTable, params string[] foreignTableFields)
    {
        // Return any format you need
    }
}

Then you need to register your generator in DbContext using DbConfiguration:

public class CustomDbConfiguration : DbConfiguration
{
    public CustomDbConfiguration()
    {
        SetMigrationSqlGenerator(SqlProviderServices.ProviderInvariantName,
            () => new CustomSqlGenerator());
    }
}

And DbConfigurationTypeAttribute:

[DbConfigurationType(typeof(CustomDbConfiguration))]
public class YourEntities : DbContext

UPDATE: If you want to change a primary key name, you need to override following Generate methods:

protected override void Generate(CreateTableOperation createTableOperation) 
{
    createTableOperation.PrimaryKey.Name = getPkName(createTableOperation.Name);
    base.Generate(createTableOperation);
}

protected override void Generate(AddPrimaryKeyOperation addPrimaryKeyOperation)
{
    addPrimaryKeyOperation.Name = getPkName(addPrimaryKeyOperation.Table);
    base.Generate(addPrimaryKeyOperation);
}

protected override void Generate(DropPrimaryKeyOperation dropPrimaryKeyOperation)
{
    dropPrimaryKeyOperation.Name = getPkName(dropPrimaryKeyOperation.Table);
    base.Generate(dropPrimaryKeyOperation);
}