Alguma informação sobre a chave secreta do RSA, sem
fatorar o módulo N.
Dep. Eng. Produção
UFF –
Niterói / RJ
Resumo:
Para n = pq, p, q, primos distintos maiores que 3, e Ø (n) = (p – 1) (q – 1), prova-se que, se n = 1 mod 6, então Ø (n) = 0 mod 36 ou Ø (n) = 2 (n – 1) mod 36. Obtém-se, também, resultados semelhantes para n = - 1 mod 6, n = + 1 mod 4 e n = - 1 mod 4, sem fatorar n. É provada uma conjectura apresentada no Eurocrypt ’88. Mostra-se que, se t é um fator de Ø (n), e d é o expoente secreto do RSA, então d mod t é conhecido.
Conclui-se
que não se pode considerar uma publicação editada acima do equador,
necessariamente, melhor do que uma feita no Brasil, e que se pode obter Ø (n)
(para n “pequeno”) sem fatorar n.
Sejam:
p, q primos inteiros maiores que 3, q > p, n = pq, Ø (n) = (p – 1) (q – 1)
...
(Ø é a
função de Euler) [1]
Em
trabalho apresentado no Eurocrypt ’88 [2], Gorgui-Naguib e Dlay provaram
que:
(n – 1)
Ø (n) = 24 t’ , t’ є N e conjecturaram, sem provar,
que também valesse
(n – 1) Ø (n) = 48 t. (1)
A prova de (1) é trivial, como se verá a seguir.
Prova
da conjectura:
Sejam p
= 2a + 1, q = 2b + 1, p, q > 3, p,
q,
primos,
a, b, є N, b > a, n = pq. Então:
(n – 1)
= 4ab + 2 (a + b)
(2)
Ø = Ø
(n) = (p – 1) (q – 1) = 4ab
(3)
(n – 1) Ø = 8ab (2ab + a + b) (4)
Seja H
= a b (2ab + a + b) (5)
A
conjectura estará provada se H = 6t
De (5),
se a ou
b par, H é par;
(6)
se a e
b ímpares, H é par.
(7)
Assim,
se (6) e (7), H é par.
(8)
Note-se
que p = 2a + 1, p > 3, p primo, implicam ser a = 0 ou a = 2 mod 3.
Analogamente,
b = 0 ou b = 2 mod 3, considerando-se q = 2b + 1.
Voltando
a (5), se a = 0 ou b = 0 mod 3, H = 0 mod 3. (9)
Se a ¹ 0 e b ¹ 0 mod
3, então, como visto acima, a = 2 e b = 2 mod 3. De (5), H = 0 mod 3. (10)
De (9)
e (10), H = 0 mod 3. (11)
De (08)
e (11), H = 6t , cqd.
2. OBTENÇÃO DE FATORES DE Ø
O teorema permite a determinação de fatores de Ø sem fatorar n, o que é mostrado a seguir em um exemplo numérico, sem perda de generalidade.
Exemplo:
n = 701
x 1447 = 1.014.347
De (1),
1.014.346 Ø = 48t, daí,
507173
Ø = 24t. (12)
De
(12), por ser mdc (507.173,24) = 1, conclui-se que 24 divide Ø, Ø = 24 Ø’. (13)
3. CHAVE
SECRETA DO RSA, MÓDULO UM FATOR DE Ø
Considerem-se
as equações:
bd – K Ø
= 1 (14)
e
bg – 24j = 1. (15)
A
equação (14) ocorre na obtenção da chave secreta d do RSA a partir da chave
pública (n, b) ([1] página 183) e a equação (15), da aplicação do algoritmo
euclideano estendido ([1],
página 31) ao par (b, 24).
De
(15), conclui-se que:
b (g +
24h) – 24 (j + bh) = 1, para todo inteiro h. (16)
O que
leva, por resultado conhecido ([1],
página 31) e por (14) a
d = g + 24h. (17).
(Note-se
que g foi determinado em (15))
A chave
secreta d é então conhecida, módulo 24.
Mostrou-se que um fator r de Ø e a chave pública (n, b) do RSA determinam d mod r, onde d é a chave secreta. Daí a motivação da busca de fatores de Ø sem a fatoração de n, com a obtenção independente dos seguintes resultados:
A –
módulo 6
A.1. –
Se p = 6a + 1, q = 6b + 1,
n = pq
= 1 mod 6 e Ø = 36 ab.
A.2. –
Se p = 6a – 1 , q = 6b – 1,
n = 1
mod 6 e 2 (n + 1) – Ø = 36ab, ie,
Ø = 2(n
+ 1) mod 36.
Assim,
se n = 1 mod 6, pode-se ter
Ø = 0
mod 36 ou Ø = 2(n + 1) mod 36.
A.3 Se n = (6a + 1) (6b – 1),
n = - 1
mod 6
(n + 1)
/ 6 = 6ab + (b – a) (18)
Ø = 12a
(3b – 1) (19)
De
(18), determina-se se (b – a) é par ou ímpar.
De
(19),
Se (b –
a) é ímpar, Ø = 12Ø’, Ø’ ímpar, ou ...
Ø = 48 Ø’’.
De qualquer modo,
Ø = 12h.
Se (b –
a) é par, Ø = 24Ø’.
B –
módulo 4
B.1 Se
n = (4a + 1) (4b + 1) = 1 mod 4,
B.2. Se
n = (4a – 1) (4b – 1) = 1 mod 4,
2 (n + 1) = Ø + 16ab, ie,
Ø = 2 (n + 1) mod 16.
Assim,
se n = 1 mod 4,
Ø = 0 mod 16 ou
Ø = 8a (2b – 1)
Assim, se n = - 1 mod 4, Ø = 0 mod 8.
Mais informações sobre o comportamento de Ø mod q, onde q é primo ímpar maior do que 3 podem ser obtidas por um procedimento de crivo (cf crivo de Eratóstones) [3].
Assim, por exemplo, sem fatorar n = 10249 (Ø (n) = 9936), pode-se determinar que Ø = 0, 1 ou 4 mod 5 (Ø = 1 mod 5) e que Ø = 0, 1, 3 ou 4 mod 7 (Ø = 3 mod 7)
4. ALGUMAS CONSIDERAÇÕES
1. A prova (trivial) da conjectura de G-ND, pode ser vista como um contra-exemplo à tendência, que parece equivocada, dominante nos meios universitários, de avaliar publicações feitas no exterior (acima do equador) como, por definição, de nível melhor do que as feitas no Brasil. A conjectura foi feita em um congresso internacional de Criptologia, cujos anais foram publicados pela Springer-Verlag. A prova foi apresentada pela primeira vez, há mais de 10 anos, em um curso de preparação de alunos de 2 º grau, para Olimpíadas de Matemática!
Referências
1. S. C. Coutinho
Números Inteiros e Criptografia RSA
Soc. Brasileira de Matemática
Rio de Janeiro – 1997.
2.
R. N.
Gorgui-Naguib and S.S. Dlay
Properties Of The Euler Totient Function Mod 24
And Some Of Its Cryptographic Applications, in Advances in Cryptology
Eurocrypt ’88
Ed. C. G. Gunther
Springer – Berlin – 1989
3. A. Paz de Lima
Prova da Existência da Solução de Euler e Algumas Novas Propostas Para a Fatoração de Inteiros.
Simpósio Bennett-IME de Criptografia – Rio de Janeiro – 2003.