Esquema de assinatura

FALCON explicado matematicamente

Como uma avaliação da McGesund é assinada com FN-DSA (FALCON) — e porque é que um único caráter alterado quebra a assinatura.

Atualizado: 2026-09-07

1. Do que se trata aqui

Uma avaliação na McGesund não é um campo de texto numa base de dados em que seja preciso acreditar. Ao ser enviada, é assinada digitalmente, e qualquer visitante pode mais tarde recalcular essa assinatura no seu próprio navegador.

Para uma parte destas assinaturas utilizamos FALCON — mais precisamente FN-DSA-512 e FN-DSA-1024. Este artigo explica o que acontece matematicamente.

Uma nota prévia importante:

FALCON não é cifragem. O texto da avaliação destina-se justamente a ser lido. O FALCON não prova sigilo, mas sim origem e integridade.

2. O que é exatamente assinado

O que se assina não é o texto corrido, mas um objeto de dados compacto que fixa o texto de forma inequívoca:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<ID da empresa>",
  "c":   "<ID da avaliação>",
  "h":   "<SHA-256 do texto da avaliação>",
  "rh":  "<SHA-256 de todo o registo de submissão>",
  "rv":  1,
  "qh":  "<SHA-256 do envelope QR, apenas em avaliações por QR>",
  "iat": 1757203200
}

Esta é a nossa mensagem mm. Ela liga entre si:

  1. a que empresa pertence a avaliação (f),
  2. de que avaliação se trata (c),
  3. que texto estava por trás — sob a forma de hash (h),
  4. que registo foi submetido no seu conjunto (rh): texto, corações, estado de geolocalização e dados sobre o motivo, serializados canonicamente e reduzidos a hash, na versão de esquema rv,
  5. de que código QR provém a avaliação (qh) — numa avaliação sem QR o campo não existe,
  6. quando foi assinada (iat).

Um único caráter alterado no texto da avaliação quebra esta cadeia. É precisamente esse o objetivo — e, desde a introdução de rh, o mesmo vale para um coração deslocado a posteriori ou para um estado de geolocalização alterado.

3. O problema de base

Um leitor que chega ao perfil de uma empresa tem duas perguntas à sua frente:

  1. Esta avaliação vem realmente do sistema da McGesund?
  2. Foi alterada posteriormente?

Para isso existe um par de chaves:

  • uma chave privada — permanece no serviço de assinatura
  • uma chave pública — pode estar em poder de qualquer pessoa

Assina-se com a chave privada e verifica-se com a pública. E isso acontece no aparelho do leitor, não no nosso servidor.

4. Porquê FALCON?

Muitos dos esquemas de assinatura atuais assentam em problemas difíceis para computadores clássicos, mas que poderiam tornar-se bastante mais fáceis para computadores quânticos suficientemente grandes.

No caso de uma avaliação, isso é mais relevante do que numa mensagem efémera: uma avaliação deve continuar verificável daqui a cinco ou dez anos. Quem assina hoje, assina para todo o tempo de vida do registo.

Por isso, o FALCON assenta em criptografia de reticulados:

Constrói-se um reticulado de descrição matemática simples, no qual uma determinada tarefa de procura é extremamente difícil.

5. O que é um reticulado matemático?

Dois vetores:

v1=(2,0),v2=(1,2).v_1=(2,0), \qquad v_2=(1,2).

Todas as combinações com coeficientes inteiros

a v1+b v2,a,b∈Za\,v_1+b\,v_2, \qquad a,b\in\mathbb{Z}

formam um reticulado de pontos. Por exemplo:

2v1+3v2=(4,0)+(3,6)=(7,6).2v_1+3v_2=(4,0)+(3,6)=(7,6).
v₁ = (2,0)v₂ = (1,2)(7,6)0
Dois vetores geram um reticulado. Cada ponto é uma combinação inteira dos dois — o ponto marcado resulta de duas vezes v₁ e três vezes v₂.

O decisivo é isto:

O reticulado em si é fácil de descrever. Encontrar nele determinadas propriedades é muito difícil.

6. O segredo são os vetores curtos

A tarefa difícil clássica é:

min⁡v∈L,  v≠0∥v∥.\min_{v\in L,\;v\neq0}\|v\|.

Este é o Shortest Vector Problem. Em duas dimensões pode resolver-se por tentativa. O FALCON trabalha em dimensão 512 ou 1024 — e aí não há hipótese.

base longaquase paralelosvetor mais curto
O mesmo reticulado, duas descrições. Os vetores cinzentos também o geram, mas são longos e quase paralelos — uma base má. O vetor curto é aquilo que é difícil de encontrar.

O FALCON não precisa, porém, do vetor mais curto em absoluto, mas de algo aparentado: encontrar um ponto do reticulado próximo de um ponto-alvo dado. Também isso é difícil sem a informação adicional certa.

ponto-alvo derivado da avaliaçãoponto próximo do reticuladomuito distante
O ponto-alvo derivado da avaliação (círculo vazado) não pertence ao reticulado. Procura-se um ponto do reticulado mesmo ao lado — o caminho a tracejado até um ponto distante também é uma solução da primeira condição, só que não é curto.

7. Polinómios em vez de números

O FALCON utiliza um reticulado NTRU e calcula com polinómios. Ou seja, em vez de números isolados, com listas de coeficientes:

f=(1,0,1,0,0,1)⟷f(x)=1+x2+x5.f=(1,0,1,0,0,1) \quad\longleftrightarrow\quad f(x)=1+x^2+x^5.

Calcula-se no anel

Rq=Zq[x]/(xn+1).R_q=\mathbb{Z}_q[x]/(x^n+1).

Isso significa:

  • Zq\mathbb{Z}_q: calcular módulo qq. Com q=7q=7, por exemplo, 10≡310\equiv3, pois 10−7=310-7=3.
  • xn=−1x^n=-1: mantém os polinómios com comprimento fixo.

Em concreto, o FALCON usa:

q=12289,n=512  ou  1024.q=12289, \qquad n=512 \;\text{ou}\; 1024.

8. O truque central

A chave privada é constituída por quatro polinómios pequenos

f,  g,  F,  Gf,\;g,\;F,\;G

com a equação NTRU

fG−gF=q.fG-gF=q.

Estes quatro formam em conjunto uma base secreta e bem comportada do reticulado — uma descrição do reticulado feita de vetores curtos.

A chave pública é, no essencial, um único polinómio:

h=gf(modq).h=\frac{g}{f}\pmod q.

De hh resulta o mesmo reticulado, mas numa base pouco manejável, feita de vetores longos:

L={(s1,s2)  :  s1+s2 h≡0(modq)}.L=\{(s_1,s_2)\;:\;s_1+s_2\,h\equiv0 \pmod q\}.

É este o núcleo inteiro do FALCON. Ambas as bases descrevem o mesmo reticulado. Só que uma serve para calcular e a outra não.

Pode imaginar-se como uma planta da cidade: público é o mapa completo. Secreto é o conhecimento dos atalhos.

9. A avaliação transforma-se num ponto

Antes de se assinar, o objeto do payload passa por uma função de hash. O FALCON usa para isso hash-to-point: da mensagem não resulta um valor numérico, mas diretamente um ponto no anel.

Além disso, o serviço de assinatura sorteia um salt aleatório rr (320 bits) e inclui-o no hash:

c=HashToPoint(r ∥ m).c=\mathrm{HashToPoint}(r \,\|\, m).

O salt não é acessório. Sem ele, a mesma avaliação daria sempre a mesma assinatura, e a partir de muitas assinaturas seria possível reconstruir a base secreta. Por isso segue também dentro da assinatura.

10. O que é uma assinatura válida

Procura-se um par

(s1,s2)(s_1,s_2)

com duas propriedades:

s1+s2 h≡c(modq)e∥(s1,s2)∥  pequena.s_1+s_2\,h\equiv c \pmod q \qquad\text{e}\qquad \|(s_1,s_2)\|\;\text{pequena}.

A primeira condição, isolada, é trivial de satisfazer — basta pôr s2=0s_2=0 e s1=cs_1=c. É a segunda condição que torna a tarefa difícil.

A pequenez eˊ a assinatura.\boxed{\text{A pequenez é a assinatura.}}

11. Um pequeno exemplo integralmente calculado

Encolhemos tudo para tamanho de brinquedo: polinómios com um único coeficiente, ou seja, números vulgares, e

q=97.q=97.

A chave secreta. Dois números pequenos:

f=3,g=5.f=3, \qquad g=5.

A chave pública. Tem-se 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, pois 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. Logo:

h=g⋅f−1=5⋅65=325≡34(mod97).h=g\cdot f^{-1}=5\cdot65=325\equiv \boxed{34} \pmod{97}.

O reticulado. L={(s1,s2):s1+34 s2≡0(mod97)}L=\{(s_1,s_2): s_1+34\,s_2\equiv0 \pmod{97}\}.

A base pública resulta diretamente de hh:

(97,0)e(−34,1).(97,0) \quad\text{e}\quad (-34,1).

Ambos pertencem a LL — e ambos são longos.

A base secreta só o serviço de assinatura conhece:

(−g,f)=(−5,3)e(−G,F)=(−9,−14),(-g,f)=(-5,3) \quad\text{e}\quad (-G,F)=(-9,-14),

pois −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 e −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. O determinante é

(−5)(−14)−(3)(−9)=70+27=97=q,(-5)(-14)-(3)(-9)=70+27=97=q,

logo a equação NTRU verifica-se. Ambos os vetores são curtos.

Passo 1: Reduzir a avaliação a hash

Admitamos que o objeto do payload da avaliação dá

c=71.c=71.

Passo 2: Uma primeira solução, má

(s1,s2)=(71,0)(s_1,s_2)=(71,0)

satisfaz 71+34⋅0=71≡c71+34\cdot0=71\equiv c. Mas o comprimento é 7171 — demasiado longo.

Passo 3: Encurtar com a base secreta

O serviço de assinatura exprime o ponto-alvo na sua base curta:

(71,0)=a (−5,3)+b (−9,−14).(71,0)=a\,(-5,3)+b\,(-9,-14).

Isso conduz a a≈−10,25a\approx-10{,}25 e b≈−2,20b\approx-2{,}20. Arredondando para a=−10a=-10, b=−2b=-2, obtém-se o ponto do reticulado

−10 (−5,3)−2 (−9,−14)=(50,−30)+(18,28)=(68,−2).-10\,(-5,3)-2\,(-9,-14)=(50,-30)+(18,28)=(68,-2).

Controlo: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, portanto pertence de facto a LL. Subtraindo:

(71,0)−(68,−2)=(3,2)(71,0)-(68,-2)=\boxed{(3,2)}

Comprimento:

∥(3,2)∥=9+4=13≈3,61.\|(3,2)\|=\sqrt{9+4}=\sqrt{13}\approx3{,}61.

Esta é a assinatura.

Passo 4: O mesmo procedimento com a base pública

Quem conhece apenas h=34h=34 tem a base {(97,0),(−34,1)}\{(97,0),(-34,1)\}. O mesmo cálculo de arredondamento dá aí o ponto do reticulado (97,0)(97,0) e, com ele,

(71,0)−(97,0)=(−26,0),∥(−26,0)∥=26.(71,0)-(97,0)=(-26,0), \qquad \|(-26,0)\|=26.

Também é uma solução válida da equação — mas sete vezes mais longa. Se o limiar de aceitação for definido abaixo de 26, ela não vale nada.

Mesmo algoritmo, mesmo reticulado, mesmo ponto-alvo.Soˊ a base difere — e com ela o resultado.\boxed{ \begin{array}{c} \text{Mesmo algoritmo, mesmo reticulado, mesmo ponto-alvo.}\\ \text{Só a base difere — e com ela o resultado.} \end{array}}

É este o alçapão do FALCON numa linha.

Passo 5: O navegador verifica

O navegador recebe a avaliação, o salt e s2=2s_2=2. Recalcula o hash, obtém c=71c=71, reconstrói

s1=c−s2 h=71−68=3,s_1=c-s_2\,h=71-68=3,

e verifica o comprimento:

∥(3,2)∥=13  ≤  β⟹Assinatura vaˊlida\|(3,2)\|=\sqrt{13}\;\leq\;\beta \quad\Longrightarrow\quad \boxed{\text{Assinatura válida}}

Passo 6: Alguém altera o texto da avaliação

Se o texto for alterado a posteriori, muda o hash do conteúdo e, com ele, o ponto — digamos

c′=40.c'=40.

A assinatura antiga continua a ser (3,2)(3,2), mas

3+34⋅2=71≠40⟹Assinatura invaˊlida3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Assinatura inválida}}

Podemos apagar uma avaliação. Alterá-la sem que isso se note, não.

Nota de honestidade sobre o exemplo

Em duas dimensões, um atacante pode simplesmente experimentar soluções curtas — para c′=40c'=40, por exemplo, (6,1)(6,1). O exemplo não é seguro; mostra apenas o mecanismo. No FALCON-1024 o vetor tem 2048 coeficientes, e aí a tentativa exaustiva não leva a lado nenhum.

12. Porque é que não se arredonda simplesmente?

O método do passo 3 chama-se arredondamento de Babai. Para um exemplo didático chega — para um esquema de assinatura real, não.

A razão: as assinaturas arredondadas não se distribuem uniformemente. A sua forma depende da geometria da base secreta. A partir de um número suficiente de assinaturas, seria possível reconstruir essa geometria — e, com ela, a chave privada. Foi exatamente aí que falharam esquemas de assinatura baseados em reticulados anteriores.

Por isso, o FALCON extrai os vetores curtos de uma distribuição gaussiana discreta sobre o reticulado:

P(x)∝e−∥x−c∥2/(2σ2).P(x)\propto e^{-\|x-c\|^2/(2\sigma^2)}.

Valores próximos do ponto-alvo são mais prováveis, mas qual deles é escolhido em concreto é aleatório. O resultado é uma distribuição que nada revela sobre a base utilizada — matematicamente: não é distinguível de uma distribuição que dependa apenas do próprio reticulado.

Este amostrador é a parte mais exigente do FALCON. Corre recursivamente sobre uma estrutura em árvore e trabalha com números de vírgula flutuante — o que torna a implementação delicada e é a principal razão pela qual o FALCON é mais difícil de implementar corretamente do que o ML-DSA.

13. O que é efetivamente transmitido

A assinatura consiste em

σ=(r,  s2).\sigma=(r,\;s_2).

Apenas s2s_2 — não o par. O s1s_1 é calculado pelo próprio verificador:

s1=c−s2 h(modq).s_1=c-s_2\,h \pmod q.

Como os coeficientes de s2s_2 são pequenos e se dispersam à volta de zero, podem ser fortemente comprimidos. É essa a razão para as assinaturas notoriamente compactas do FALCON:

chave públicaassinatura
FALCON-512897 B~666 B
FALCON-10241 793 B~1 280 B

Para comparar: o ML-DSA-87 precisa de 4 627 bytes. Na McGesund, porém, nenhuma destas assinaturas está no próprio código QR — o autocolante transporta apenas o envelope Ed25519; os carimbos pós-quânticos ficam junto ao registo e são carregados no momento da verificação. Aqui, o tamanho não decide sobre a possibilidade de impressão, mas sobre armazenamento e transmissão: um carimbo FALCON tem cerca de um quarto do tamanho de um carimbo ML-DSA.

14. Porque é que o FALCON verifica depressa

A multiplicação ingénua de polinómios custa

O(n2).O(n^2).

Com a transformada rápida de Fourier, isso desce para aproximadamente

O(nlog⁡n).O(n\log n).

Com n=1024n=1024, essa é a diferença entre um milhão e cerca de dez mil operações. É por isso que a verificação no navegador de um visitante corre em milissegundos — e é por isso que o F está no nome:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. O processo em imagem

SERVIÇO DE ASSINATURA (MCGESUND)NAVEGADOR DO VISITANTEchave privada (f, g, F, G — base curta)Payload m = {Empresa, Avaliação, h, rh, iat}Salt r + HashToPoint(r ‖ m) = cAmostragem gaussiana: vetor curto (s₁, s₂)Assinatura σ = (r, s₂) + kidAvaliação + σ + chave pública hrecalcular c, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?válidainválida
Do payload até ao visto no navegador. Tudo o que está acima da linha de separação acontece uma única vez, no momento do envio; tudo o que está abaixo, de novo em cada visitante — no seu aparelho, com a chave pública.

16. Porque é que um atacante fracassa

Ele conhece hh e, com isso, todo o reticulado. Conhece também o ponto-alvo cc, assim que a avaliação é pública. O que lhe falta é a base curta.

Para falsificar uma avaliação, teria de encontrar um vetor curto para um cc escolhido por si — apenas a partir da descrição pública. É essa a tarefa que o passo 4 do exemplo ilustrou: sem os bons vetores, o mesmo cálculo desemboca numa solução demasiado longa.

Em dimensão 1024, os melhores métodos conhecidos — tanto clássicos como quânticos — estão muito longe disso.

Assinar: raˊpidoVerificar: raˊpidoFalsificar: difıˊcil\boxed{\text{Assinar: rápido}\quad \text{Verificar: rápido}\quad \text{Falsificar: difícil}}

17. O que a McGesund faz concretamente com isto

O envelope. Cada avaliação assinada leva uma assinatura Ed25519. Essa é a variante obrigatória — clássica, muito pequena, verificável nativamente em qualquer navegador.

Os carimbos pós-quânticos. Ao lado ficam uma ou duas assinaturas resistentes a computadores quânticos. Quais, depende do plano:

Planoníveis de assinatura disponíveis
BasisEd25519, FN-DSA-512
KlassikEd25519, FN-DSA-512, FN-DSA-1024
ProEd25519, FN-DSA-1024, ML-DSA-87
PremiumEd25519, FN-DSA-1024, ML-DSA-87, ambas em paralelo

A variante paralela é deliberadamente redundante. O FALCON assenta em reticulados NTRU, o ML-DSA em reticulados de módulo. Se uma das duas famílias vier a revelar-se mais fraca do que hoje se admite, a outra continua a sustentar.

A âncora temporal. A impressão digital da chave de assinatura é ancorada num bloco da Bitcoin através do OpenTimestamps. Fica assim demonstrado não só que a assinatura é autêntica, mas também que já existia num determinado momento — sem que ninguém tenha de acreditar no nosso carimbo temporal.

Tudo isto é calculado no navegador do leitor, através de um módulo WASM. Nós fornecemos os dados; a verificação corre no aparelho do visitante. Se amanhã saíssemos da rede, uma avaliação já carregada continuaria verificável.

Sobre os nomes: o FALCON está a ser normalizado atualmente como FN-DSA; o projeto está previsto como FIPS 206, mas ainda não está concluído. Por isso, no código da McGesund os níveis chamam-se FN-DSA-512 e FN-DSA-1024, mesmo que na linguagem corrente se continue a falar de FALCON.

18. A intuição mais importante

A chave pública é a descrição completa de um labirinto. Qualquer pessoa a pode consultar.

A assinatura é a prova: «Encontrei um caminho muito curto para exatamente esta avaliação.»

A chave privada é o conhecimento dos atalhos.

O leitor não precisa de conhecer os atalhos. Limita-se a medir se o caminho apresentado é de facto curto e se pertence de facto a esta avaliação. Ambas as coisas as pode fazer sem nós.

O FALCON transforma uma avaliac¸a˜o num ponto de um reticuladoe a assinatura num caminho curto ateˊ laˊ.\boxed{ \begin{array}{c} \text{O FALCON transforma uma avaliação num ponto de um reticulado}\\ \text{e a assinatura num caminho curto até lá.} \end{array}}

Quem altera o texto desloca o ponto — e o caminho antigo passa a não levar a lado nenhum.