Aritmética de curvas NIST em Pascal puro para assinar PDF

O HotPDF executa acordo de chaves em curva elíptica e verificação de assinaturas para PDF em Object Pascal puro, sem binding de OpenSSL e sem provedor criptográfico de plataforma no caminho. Isso cobre cinco curvas: P-256, P-384 e P-521 para as famílias de primos NIST, mais X25519 e X448 para acordo de chaves em curva de Montgomery. A razão para escrever esse código em vez de linká-lo é implantação, não pureza. Um aplicativo Delphi ou Free Pascal que distribui um executável e nenhuma DLL criptográfica não tem desvio de versão para gerenciar, nenhum provedor por plataforma a detectar e nada que mude de comportamento quando um cliente aplica patches nas bibliotecas do sistema

O custo é que agora você é dono da aritmética. Multiplicação modular de inteiros grandes é um código impiedoso: ou produz resultados idênticos byte a byte contra vetores de teste publicados ou produz lixo de aparência plausível, e a distância entre esses dois estados pode ser uma única comparação. Esta é a história dessa comparação, porque a forma do bug se generaliza para qualquer port Pascal de aritmética de campo

Por que uma biblioteca PDF precisa de aritmética de curvas?

Dois recursos puxam isso. O primeiro é a criptografia de documentos por chave pública: o handler de lista de destinatários da ISO 32000 embrulha uma chave por documento para certificados nomeados, e quando um destinatário tem uma chave EC o embrulho roda por acordo de chaves em vez de transporte de chave RSA. Sem ECDH não há como abrir tal documento. O segundo é a validação de assinaturas. Verificar uma assinatura ECDSA sobre os bytes do /ByteRange precisa de uma multiplicação de pontos na curva do signatário, e P-384 é comum em perfis de governo e de assinatura qualificada em que P-256 é considerado o piso e não o alvo. O HotPDF expõe os resultados desse trabalho por o caminho de verificação ECDSA e CMS e por o modelo de provedor de assinatura plugável

CIOS, e a única subtração no final

A multiplicação de Montgomery evita a divisão trabalhando em um domínio transformado em que a redução é um shift. A variante que o HotPDF usa é Coarsely Integrated Operand Scanning, que intercala a multiplicação e a redução limb a limb para que o intermediário nunca cresça além da largura do módulo mais um limb. O corpo do loop é direto e fácil de testar. A cauda não é: depois das passadas intercaladas o acumulador pode estar em qualquer lugar do intervalo até duas vezes o módulo, então o algoritmo termina com uma subtração condicional que remove uma cópia do primo se e somente se o acumulador for maior ou igual a ele

Comparar dois números de múltiplos limbs significa caminhar do limb mais significativo para baixo enquanto carrega um borrow. A maneira óbvia de escrever é comparar o limb do acumulador contra o limb do módulo mais o borrow que chega. Essa expressão está errada, e está errada de um jeito que a maioria das curvas esconde

// Errado: P[I] + Borrow pode dar wrap quando P[I] é $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Correto: compare sem nunca somar a um limb
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Como um wrap-around de borrow realmente se parece?

Parece uma curva que funciona em todo lugar menos em produção. Os primos de P-384 e P-521 contêm limbs que são inteiramente uns, então P[I] é igual a $FFFFFFFFFFFFFFFF. Some a isso o borrow que chega de um e um unsigned de 64 bits dá wrap para zero. A comparação então pergunta se o limb do acumulador é menor que zero, decide que não, e conclui que nenhum borrow é necessário. Um limb do resultado fica errado por um

P-256 escapa porque nenhum de seus limbs é todo de uns, então a adição nunca overflowa e a expressão com bug por acaso concorda com a correta. Esse é o pior desfecho possível para uma suíte de testes: a curva mais testada passa, as menos testadas falham intermitentemente dependendo dos valores dos operandos, e a falha aparece como um resultado de verificação "assinatura inválida" em documentos perfeitamente válidos. O HotPDF carregava um gate explícito no P-384 exatamente por essa razão, retornando um status de indisponível em vez de uma resposta errada, até a aritmética ser provada contra vetores de referência

Como o bug foi de fato localizado

Não lendo o código. A sequência produtiva foi mecânica, e é reutilizável. Primeiro, elimine as constantes: cada limb de p, R e R^2 foi regenerado de forma independente e comparado limb a limb, o que descarta a fonte mais comum de bugs de curvas. Segundo, instrumente a aritmética em vez da API: um procedimento temporário de dump imprimia os valores intermediários da multiplicação de Montgomery de R^2, de x^3 e de y^2 para um ponto conhecido, para que pudessem ser conferidos contra a verdade calculada de forma independente

Essa comparação apontou direto para o culpado. A cadeia do x estava correta de ponta a ponta, enquanto y^2 diferia em exatamente um limb por exatamente um. Uma diferença de um em um único limb não é um bug de multiplicação, um bug de propagação de carry nem um bug de constante; é um bug de cadeia de borrow, e a única cadeia de borrow na rotina é a subtração condicional final. Um detalhe quase descarrilou isto: a constante de referência usada para o dump estava ela própria escrita na ordem de bytes errada na primeira tentativa, o que produziu uma incompatibilidade no valor de y e brevemente sugeriu um segundo defeito inexistente. Verifique a endianness da sua verdade de referência antes de confiar nela para acusar seu código

As armadilhas vizinhas na mesma rotina

Mais três modos de falha vivem a poucas linhas dessa comparação, e os três estiveram vivos em algum momento durante o desenvolvimento

// 1. O acumulador tem um limb acima da largura do módulo. Comparar
//    apenas os L limbs baixos perde o caso em que T é exatamente p mais
//    2^(64*L), que acontece para uma parcela relevante de entradas
//    aleatórias porque 2p excede 2^256 para P-256 e 2^384 para P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. Uma subtração genérica de múltiplos limbs tem o mesmo risco de
//    wrap: quando Y[I] é $FFFFFFFFFFFFFFFF, Y[I] + Borrow dá wrap para
//    zero e o borrow precisa sobreviver ao próximo limb em vez de ser zerado
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

A terceira não é código, é proveniência. O primo de P-521 foi inicialmente transcrito com 130 dígitos hexadecimais em vez de 131, um F a menos, e as constantes de Montgomery foram então calculadas a partir desse primo errado, então as constantes eram autocoerentes e conjuntamente erradas. Parâmetros de curva devem ser derivados, nunca digitados: calcule R como (1 shl (64 * L)) mod p a partir do primo que você está de fato usando, depois confira R * R mod p contra o valor que sua constante R^2 alega. Um par de constantes que concorda entre si não prova nada sobre nenhuma delas

Estratégia de verificação que escala além de uma curva

A técnica que tornou X25519 e X448 tratáveis foi escrever uma implementação espelho em uma linguagem com inteiros sem limites e transcrever para ela o fluxo de controle Pascal linha a linha. Quando o espelho produz a resposta certa e o Pascal não, o defeito é um deslize de transcrição e sondar o mesmo valor intermediário nas duas implementações o encontra em segundos. Os três erros clássicos de ladder da RFC 7748 foram capturados assim: um swap de tempo constante cuja segunda linha reutilizava o valor já trocado, uma inversão final que retornava z elevado a menos um em vez de multiplicá-lo em X, e uma multiplicação por constante pequena que montava produtos de meia palavra com um bitwise or e perdia o carry

Para material de teste, tome vetores como bytes em vez de como texto. Extrair uma chave privada com um padrão de texto é como uma implementação correta é acusada de um erro de um byte que vive inteiramente na etapa de extração. Corte o hex da codificação DER em offsets conhecidos e compare arrays de bytes

Com a cadeia de borrow corrigida, as cinco curvas batem com os vetores de referência publicados byte a byte, e o HotPDF não aplica mais gate a nenhuma delas. Se você está integrando assinatura baseada em certificado ou criptografia de lista de destinatários, a conclusão prática é que a escolha de curva agora é uma decisão de política e não uma questão de capacidade; os perfis e armadilhas de ordem de bytes do lado da assinatura são cobertos em o passo a passo de assinatura PAdES. Detalhes do componente e a matriz de algoritmos suportados estão na página de produto do HotPDF Delphi PDF component