Provando o conhecimento de fatores primos pela transferência cegaVocês dois conhecem um número n, que é o produto n = pq de dois números primos p e q, e
vocês dois conhecem p e q. Uma fonte independente e confiável fornece a ambos uma
sequência de bits aleatórios 0 ou 1, a partir dos quais você é capaz de gerar quaisquer
números aleatórios necessários ao protocolo. Você poderá então convencer a gerente do seu
banco de que conhece p e q sem revelar quais são. Este método utiliza a “aritmética
modular”, na qual os múltiplos de um número n específico, chamado de módulo, são
identificados com o zero. Especificamente, a notação y mod n representa o resto da divisão
de y por n, para y e n inteiros. Com essa notação, o método funciona da seguinte maneira.
A fonte independente gera um número inteiro aleatório x e envia a você e à sua gerente o
resto r da divisão de x^2 por n (ou seja, r = x^2 mod n).
Segundo a teoria dos números, r possui exatamente quatro diferentes raízes quadradas
módulo n. Você usa o seu conhecimento de p e q para achá-las. Uma delas é x, e as
outras três são n–- x, y e n – y, para algum y. (Se você não conhecer p e q, não existe
nenhum algoritmo eficiente para encontrar essas raízes quadradas; de fato, se você
conhecer as quatro raízes quadradas poderá facilmente deduzir p e q.)
Você escolhe aleatoriamente um desses quatro números: vamos chamá-lo de z.
Você escolhe ao acaso um número inteiro k e envia à sua gerente o número inteiro s = k^2
mod n. Você determina então que a = k mod n, b = kz mod n e envia esses dois números
à sua gerente por transferência cega.
A gerente consegue ler exatamente uma dessas duas mensagens. Ela verifica que sua raiz
quadrada mod n é s (se ela ler a mensagem a) ou rs (se ela ler a mensagem b).
Esses passos são repetidos T vezes. Ao final do processo, a sua gerente ficará convencida
(com probabilidade igual a 1 – 2–T) de que você conhece a fatoração.Observe que não há comunicação de volta da gerente para você; isto é, o protocolo não é
interativo.