Estou desenvolvendo um aplicativo que assina e verifica assinaturas de documentos utilizando uma chave privada e publica do algoritmo ElGamal (estou utilizando o provedor criado pelo autor do livro Java Cryptography). Sendo que o par de chaves é salvo em um arquivo .txt. A minha dúvida é, mesmo estando tudo certo, ALGUMAS vezes, o java lança uma ArithmeticException com a mensagem “BigInteger not invertible”, sendo que também informa que vem de uma fonte desconhecida (unknown source). Não é sempre que ocorre este erro, por isso eu estou achando bem estranho… Bom, gostaria que me ajudassem…
Você deve estar informando valores iniciais inválidos pro provedor.
Só por curiosidade, por que usar ElGamal, que apesar de ser tão seguro quando DSA ou RSA, é mais lento e dobra o tamanho da saida criptografada?
RSA é uma escolha muito mais segura dado que o problema de fatoração inteira é muito mais conhecido e estudado que o de logaritmo discreto.
Sim, mas no projeto utilizamos um algoritmo de derivação de chaves criptográficas utilizando o sistema ElGamal…
Aqui está o printStackTrace do erro:
java.lang.ArithmeticException: BigInteger not invertible.
at java.math.MutableBigInteger.modInverse(Unknown Source)
at java.math.MutableBigInteger.mutableModInverse(Unknown Source)
at java.math.BigInteger.modInverse(Unknown Source)
at java.math.BigInteger.modPow(Unknown Source)
at ecfv.compartilhamento.elgamal.ElGamalSignature.engineSign(ElGamalSignature.java:65)
at java.security.Signature$Delegate.engineSign(Unknown Source)
at java.security.Signature.sign(Unknown Source)
at ecfv.cliente.processamento.Processamento.realizaAssinatura(Processamento.java:239)
at ecfv.cliente.Cliente.assinaOffLine(Cliente.java:520)
at ecfv.cliente.Cliente.actionPerformed(Cliente.java:577)
at javax.swing.AbstractButton.fireActionPerformed(Unknown Source)
at javax.swing.AbstractButton$ForwardActionEvents.actionPerformed(Unknown Source)
at javax.swing.DefaultButtonModel.fireActionPerformed(Unknown Source)
at javax.swing.DefaultButtonModel.setPressed(Unknown Source)
at javax.swing.AbstractButton.doClick(Unknown Source)
at javax.swing.plaf.basic.BasicMenuItemUI.doClick(Unknown Source)
at javax.swing.plaf.basic.BasicMenuItemUI$MouseInputHandler.mouseReleased(Unknown Source)
at java.awt.AWTEventMulticaster.mouseReleased(Unknown Source)
at java.awt.Component.processMouseEvent(Unknown Source)
at java.awt.Component.processEvent(Unknown Source)
at java.awt.Container.processEvent(Unknown Source)
at java.awt.Component.dispatchEventImpl(Unknown Source)
at java.awt.Container.dispatchEventImpl(Unknown Source)
at java.awt.Component.dispatchEvent(Unknown Source)
at java.awt.LightweightDispatcher.retargetMouseEvent(Unknown Source)
at java.awt.LightweightDispatcher.processMouseEvent(Unknown Source)
at java.awt.LightweightDispatcher.dispatchEvent(Unknown Source)
at java.awt.Container.dispatchEventImpl(Unknown Source)
at java.awt.Component.dispatchEvent(Unknown Source)
at java.awt.EventQueue.dispatchEvent(Unknown Source)
at java.awt.EventDispatchThread.pumpOneEventForHierarchy(Unknown Source)
at java.awt.EventDispatchThread.pumpEventsForHierarchy(Unknown Source)
at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
at java.awt.EventDispatchThread.run(Unknown Source)
E aqui a linha onde ele acusa erro:
BigInteger b = top.multiply(
k.modPow(kOne.negate(), pminusone)).mod(pminusone);
Esse erro ocorre apenas algumas poucas vezes… Poderiam me ajudar?
Bom, como você sabe como se usa o ElGamal, deve saber o suficiente de teoria dos números para descobrir porque é que o erro está sendo gerado pelas linhas “if f.isZero() throw new ArithmeticException” que constam do código da função abaixo (veja o arquivo src\java\math\MutableBigInteger.java em src.zip).
Algum dos parâmetros que você está usando pode ocasionar esse problema, mas não sei lhe dizer.
/**
* Calculate the multiplicative inverse of this mod mod, where mod is odd.
* This and mod are not changed by the calculation.
*
* This method implements an algorithm due to Richard Schroeppel, that uses
* the same intermediate representation as Montgomery Reduction
* ("Montgomery Form"). The algorithm is described in an unpublished
* manuscript entitled "Fast Modular Reciprocals."
*/
private MutableBigInteger modInverse(MutableBigInteger mod) {
MutableBigInteger p = new MutableBigInteger(mod);
MutableBigInteger f = new MutableBigInteger(this);
MutableBigInteger g = new MutableBigInteger(p);
SignedMutableBigInteger c = new SignedMutableBigInteger(1);
SignedMutableBigInteger d = new SignedMutableBigInteger();
MutableBigInteger temp = null;
SignedMutableBigInteger sTemp = null;
int k = 0;
// Right shift f k times until odd, left shift d k times
if (f.isEven()) {
int trailingZeros = f.getLowestSetBit();
f.rightShift(trailingZeros);
d.leftShift(trailingZeros);
k = trailingZeros;
}
// The Almost Inverse Algorithm
while(!f.isOne()) {
// If gcd(f, g) != 1, number is not invertible modulo mod
if (f.isZero())
throw new ArithmeticException("BigInteger not invertible.");
// If f < g exchange f, g and c, d
if (f.compare(g) < 0) {
temp = f; f = g; g = temp;
sTemp = d; d = c; c = sTemp;
}
// If f == g (mod 4)
if (((f.value[f.offset + f.intLen - 1] ^
g.value[g.offset + g.intLen - 1]) & 3) == 0) {
f.subtract(g);
c.signedSubtract(d);
} else { // If f != g (mod 4)
f.add(g);
c.signedAdd(d);
}
// Right shift f k times until odd, left shift d k times
int trailingZeros = f.getLowestSetBit();
f.rightShift(trailingZeros);
d.leftShift(trailingZeros);
k += trailingZeros;
}
while (c.sign < 0)
c.signedAdd(p);
return fixup(c, p, k);
}
Sim, o problema é que há vezes em que eu passo os mesmos parâmetros idênticos e dá certo, outras vezes, ocorre este erro… acho isto muito estranho…
Você está gerando uma chave usando números aleatórios (e é por isso que está ocorrendo esse erro de vez em quando, certo? )
Talvez sua implementação requeira testar os números para que não ocorram determinados problemas (por exemplo, o número deve ser provavelmente primo, por exemplo. Você não deve usar qualquer número aleatório).
Acho que eu resolvi o erro, o problema estava que eu implementei um algoritmo de derivação de chaves criptográficas e neste algoritmo havia uma variavel chamada k, entao pus pra essa variavel ser a mesma que o k usado no processo de assinatura… Creio que ai estivesse gerando algum conflito, nunca mais vi o erro depois de corrigido… Também reparei que os k não precisam ser iguais para que as assinaturas sejam autenticadas com as chaves derivadas… Bom, valeu por tudo.